[en] Zero-Knowledge Proofs (ZKPs) are cryptographic building blocks of many privacy-preserving security protocols. An important research focus in this area is the development of post-quantum ZKPs. These are ZKPs whose security is reduced to computational hardness assumptions that are assumed to be intractable even by scalable quantum computers. In this paper, we study the post-quantum ZKPs of Jain, Krenn, Pietrzak, and Tentes (Asiacrypt 2012). These are the only ZKPs for proving arbitrary binary statements whose security reduces to the Learning Parity with Noise (LPN) problem-a very conservative post-quantum hardness assumption. We make the following contributions to further develop the potential and understanding of these ZKPs. First, we optimize the efficiency of the verifier by several orders of magnitude, making this part as computationally light as that of the prover. Second, we show that the only open source implementation of these ZKPs does not implement them correctly, allowing a malicious prover to convince the verifier of false statements. Third, we formally verify for the first time the security of these (optimized) ZKPs in EasyCrypt. Fourth, we show how these ZKPs can be used to construct the first code-based ZKP of shuffle and verifiable e-voting protocol.
Disciplines :
Computer science
Author, co-author :
HAINES, Thomas; ANU - Australian National University
MOSAHEB, Rafieh ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > APSIA
MUELLER, Johannes ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust > APSIA > Team Johannes MUELLER ; LORIA/INRIA/CNRS
REETIKA, Reetika; Indian Institute of Space Science and Technology
External co-authors :
yes
Language :
English
Title :
Zero-Knowledge Proofs from Learning Parity with Noise: Optimization, Verification, and Application
Ben Adida. Helios: Web-based Open-Audit Voting. In Paul C. van Oorschot, editor, Proceedings of the 17th USENIX Security Symposium, July 28-August 1, 2008, San Jose, CA, USA, pages 335-348. USENIX Association, 2008.
José Bacelar Almeida, Endre Bangerter, Manuel Barbosa, Stephan Krenn, Ahmad-Reza Sadeghi, and Thomas Schneider. A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols. In Dimitris Gritzalis, Bart Preneel, and Marianthi Theoharidou, editors, Computer Security-ESORICS 2010, 15th European Symposium on Research in Computer Security, Athens, Greece, September 20-22, 2010. Proceedings, volume 6345 of Lecture Notes in Computer Science, pages 151-167. Springer, 2010.
José Bacelar Almeida, Manuel Barbosa, Gilles Barthe, Benjamin Grégoire, Vincent Laporte, Jean-Christophe Léchenet, Tiago Oliveira, Hugo Pacheco, Miguel Quaresma, Peter Schwabe, Antoine Séré, and Pierre-Yves Strub. Formally verifying Kyber Episode IV: Implementation correctness. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(3):164-193, 2023.
Diego F. Aranha, Carsten Baum, Kristian Gjosteen, and Tjerand Silde. Verifiable Mix-Nets and Distributed Decryption for Voting from Lattice-Based Assumptions. In Weizhi Meng, Christian Damsgaard Jensen, Cas Cremers, and Engin Kirda, editors, Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 26-30, 2023, pages 1467-1481. ACM, 2023.
Diego F. Aranha, Carsten Baum, Kristian Gjosteen, Tjerand Silde, and Thor Tunge. Lattice-Based Proof of Shuffle and Applications to Electronic Voting. In Kenneth G. Paterson, editor, Topics in Cryptology-CT-RSA 2021-Cryptographers' Track at the RSA Conference 2021, Virtual Event, May 17-20, 2021, Proceedings, volume 12704 of Lecture Notes in Computer Science, pages 227-251. Springer, 2021.
Myrto Arapinis, Véronique Cortier, Steve Kremer, and Mark Ryan. Practical Everlasting Privacy. In David A. Basin and John C. Mitchell, editors, Principles of Security and Trust-Second International Conference, POST 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings, volume 7796 of Lecture Notes in Computer Science, pages 21-40. Springer, 2013.
Manuel Barbosa, Gilles Barthe, Christian Doczkal, Jelle Don, Serge Fehr, Benjamin Grégoire, Yu-Hsuan Huang, Andreas Hülsing, Yi Lee, and Xiaodi Wu. Fixing and Mechanizing the Security Proof of Fiat-Shamir with Aborts and Dilithium. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology-CRYPTO 2023-43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part V, volume 14085 of Lecture Notes in Computer Science, pages 358-389. Springer, 2023.
Manuel Barbosa, Gilles Barthe, Xiong Fan, Benjamin Grégoire, Shih-Han Hung, Jonathan Katz, Pierre-Yves Strub, Xiaodi Wu, and Li Zhou. Easypqc: Verifying post-quantum cryptography. In Yongdae Kim, Jong Kim, Giovanni Vigna, and Elaine Shi, editors, CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, Republic of Korea, November 15-19, 2021, pages 2564-2586. ACM, 2021.
Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, and Jean-Pierre Tillich. Revisiting algebraic attacks on minrank and on the rank decoding problem. Des. Codes Cryptogr., 91(11):3671-3707, 2023.
Gilles Barthe, Daniel Hedin, Santiago Zanella Béguelin, Benjamin Grégoire, and Sylvain Heraud. A Machine-Checked Formalization of Sigma-Protocols. In Proceedings of the 23rd IEEE Computer Security Foundations Symposium, CSF 2010, Edinburgh, United Kingdom, July 17-19, 2010, pages 246-260. IEEE Computer Society, 2010.
Emanuele Bellini, Philippe Gaborit, Alexandros Hasikos, and Víctor Mateu. Enhancing Code Based Zero-Knowledge Proofs Using Rank Metric. In Stephan Krenn, Haya Schulmann, and Serge Vaudenay, editors, Cryptology and Network Security-19th International Conference, CANS 2020, Vienna, Austria, December 14-16, 2020, Proceedings, volume 12579 of Lecture Notes in Computer Science, pages 570-592. Springer, 2020.
David Bernhard, Véronique Cortier, David Galindo, Olivier Pereira, and Bogdan Warinschi. SoK: A Comprehensive Analysis of Game-Based Ballot Privacy Definitions. In 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17-21, 2015, pages 499-516. IEEE Computer Society, 2015.
Slim Bettaieb, Löic Bidoux, Olivier Blazy, Yann Connan, and Philippe Gaborit. A gapless code-based hash proof system based on RQC and its applications. Des. Codes Cryptogr., 90(12):3011-3044, 2022.
Löic Bidoux, Philippe Gaborit, Mukul Kulkarni, and Nicolas Sendrier. Quasi-Cyclic Stern Proof of Knowledge. In IEEE International Symposium on Information Theory, ISIT 2022, Espoo, Finland, June 26-July 1, 2022, pages 1459-1464. IEEE, 2022.
Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50(4):506-519, 2003.
Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology-EUROCRYPT 2016-35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, volume 9666 of Lecture Notes in Computer Science, pages 327-357. Springer, 2016.
Xavier Boyen, Thomas Haines, and Johannes Müller. A Verifiable and Practical Lattice-Based Decryption Mix Net with External Auditing. In Liqun Chen, Ninghui Li, Kaitai Liang, and Steve A. Schneider, editors, Computer Security-ESORICS 2020-25th European Symposium on Research in Computer Security, ESORICS 2020, Guildford, UK, September 14-18, 2020, Proceedings, Part II, volume 12309 of Lecture Notes in Computer Science, pages 336-356. Springer, 2020.
Xavier Boyen, Thomas Haines, and Johannes Müller. Epoque: Practical End-to-End Verifiable Post-Quantum-Secure E-Voting. In IEEE European Symposium on Security and Privacy, EuroS&P 2021, Vienna, Austria, September 6-10, 2021, pages 272-291. IEEE, 2021.
Véronique Cortier, David Galindo, Ralf Küsters, Johannes Müller, and Tomasz Truderung. SoK: Verifiability Notions for E-Voting Protocols. In IEEE Symposium on Security and Privacy, SP 2016, San Jose, CA, USA, May 22-26, 2016, pages 779-798. IEEE Computer Society, 2016.
Núria Costa, Ramiro Martínez, and Paz Morillo. Proof of a Shuffle for Lattice-Based Cryptography. In Helger Lipmaa, Aikaterini Mitrokotsa, and Raimundas Matulevicius, editors, Secure IT Systems-22nd Nordic Conference, NordSec 2017, Tartu, Estonia, November 8-10, 2017, Proceedings, volume 10674 of Lecture Notes in Computer Science, pages 280-296. Springer, 2017.
Núria Costa, Ramiro Martínez, and Paz Morillo. Lattice-Based Proof of a Shuffle. In Andrea Bracciali, Jeremy Clark, Federico Pintore, Peter B. Ronne, and Massimiliano Sala, editors, Financial Cryptography and Data Security-FC 2019 International Workshops, VOTING and WTSC, St. Kitts, St. Kitts and Nevis, February 18-22, 2019, Revised Selected Papers, volume 11599 of Lecture Notes in Computer Science, pages 330-346. Springer, 2019.
Ivan Damgard, Oded Goldreich, Tatsuaki Okamoto, and Avi Wigderson. Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs. In Don Coppersmith, editor, Advances in Cryptology-CRYPTO '95, 15th Annual International Cryptology Conference, Santa Barbara, California, USA, August 27-31, 1995, Proceedings, volume 963 of Lecture Notes in Computer Science, pages 325-338. Springer, 1995.
Rafäel del Pino, Vadim Lyubashevsky, Gregory Neven, and Gregor Seiler. Practical Quantum-Safe Voting from Lattices. In Bhavani Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30-November 03, 2017, pages 1565-1581. ACM, 2017.
Xuan-Thanh Do, Dang Truong Mac, and Quoc-Huy Vu. zk-SNARKs from Codes with Rank Metrics. In Elizabeth A. Quaglia, editor, Cryptography and Coding-19th IMA International Conference, IMACC 2023, London, UK, December 12-14, 2023, Proceedings, volume 14421 of Lecture Notes in Computer Science, pages 99-119. Springer, 2023.
Denis Firsov and Dominique Unruh. Zero-Knowledge in EasyCrypt. In 36th IEEE Computer Security Foundations Symposium, CSF 2023, Dubrovnik, Croatia, July 10-14, 2023, pages 1-16. IEEE, 2023.
Kristian Gjosteen, Thomas Haines, Johannes Müller, Peter B. Ronne, and Tjerand Silde. Verifiable Decryption in the Head. In Khoa Nguyen, Guomin Yang, Fuchun Guo, and Willy Susilo, editors, Information Security and Privacy-27th Australasian Conference, ACISP 2022, Wollongong, NSW, Australia, November 28-30, 2022, Proceedings, volume 13494 of Lecture Notes in Computer Science, pages 355-374. Springer, 2022.
Shay Gueron, Edoardo Persichetti, and Paolo Santini. Designing a Practical Code-Based Signature Scheme from Zero-Knowledge Proofs with Trusted Setup. Cryptogr., 6(1):5, 2022.
Thomas Haines, Rajeev Goré, and Mukesh Tiwari. Machine-checking Multi-Round Proofs of Shuffle: Terelius-Wikstrom and Bayer-Groth. In Joseph A. Calandrino and Carmela Troncoso, editors, 32nd USENIX Security Symposium, USENIX Security 2023, Anaheim, CA, USA, August 9-11, 2023, pages 6471-6488. USENIX Association, 2023.
Thomas Haines and Johannes Müller. SoK: Techniques for Verifiable Mix Nets. In 33rd IEEE Computer Security Foundations Symposium, CSF 2020, Boston, MA, USA, June 22-26, 2020, pages 49-64. IEEE, 2020.
Thomas Haines and Johannes Müller. A Novel Proof of Shuffle: Exponentially Secure Cut-and-Choose. In Joonsang Baek and Sushmita Ruj, editors, Information Security and Privacy-26th Australasian Conference, ACISP 2021, Virtual Event, December 1-3, 2021, Proceedings, volume 13083 of Lecture Notes in Computer Science, pages 293-308. Springer, 2021.
Javier Herranz, Ramiro Martínez, and Manuel Sánchez. Shorter Lattice-Based Zero-Knowledge Proofs for the Correctness of a Shuffle. In Matthew Bernhard, Andrea Bracciali, Lewis Gudgeon, Thomas Haines, Ariah Klages-Mundt, Shin'ichiro Matsuo, Daniel Perez, Massimiliano Sala, and Sam Werner, editors, Financial Cryptography and Data Security. FC 2021 International Workshops-CoDecFin, DeFi, VOTING, and WTSC, Virtual Event, March 5, 2021, Revised Selected Papers, volume 12676 of Lecture Notes in Computer Science, pages 315-329. Springer, 2021.
Patrick Hough, Caroline Sandsbraten, and Tjerand Silde. Concrete NTRU Security and Advances in Practical Lattice-Based Electronic Voting. IACR Cryptol. ePrint Arch., page 933, 2023.
Rong Hu, Kirill Morozov, and Tsuyoshi Takagi. Proof of plaintext knowledge for code-based public-key encryption revisited. In Kefei Chen, Qi Xie, Weidong Qiu, Ninghui Li, and Wen-Guey Tzeng, editors, 8th ACM Symposium on Information, Computer and Communications Security, ASIA CCS '13, Hangzhou, China-May 08-10, 2013, pages 535-540. ACM, 2013.
Andreas Hülsing, Matthias Meijers, and Pierre-Yves Strub. Formal Verification of Saber's Public-Key Encryption Scheme in EasyCrypt. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology-CRYPTO 2022-42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part I, volume 13507 of Lecture Notes in Computer Science, pages 622-653. Springer, 2022.
Abhishek Jain, Stephan Krenn, Krzysztof Pietrzak, and Aris Tentes. Commitments and Efficient Zero-Knowledge Proofs from Learning Parity with Noise. In Xiaoyun Wang and Kazue Sako, editors, Advances in Cryptology-ASIACRYPT 2012-18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Proceedings, volume 7658 of Lecture Notes in Computer Science, pages 663-680. Springer, 2012.
Carlos Aguilar Melchor, Nicolas Gama, James Howe, Andreas Hülsing, David Joseph, and Dongze Yue. The Return of the SDitH. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology-EUROCRYPT 2023-42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V, volume 14008 of Lecture Notes in Computer Science, pages 564-596. Springer, 2023.
David Mestel, Johannes Müller, and Pascal Reisert. How efficient are replay attacks against vote privacy A formal quantitative analysis. J. Comput. Secur., 31(5):421-467, 2023.
Miguel Angel Prada-Delgado, Iluminada Baturone, Gero Dittmann, Jens Jelitto, and Andreas Kind. PUF-derived IoT identities in a zeroknowledge protocol for blockchain. Internet Things, 9:100057, 2020.
Kazue Sako and Joe Kilian. Receipt-Free Mix-Type Voting Scheme-A Practical Solution to the Implementation of a Voting Booth. In Louis C. Guillou and Jean-Jacques Quisquater, editors, Advances in Cryptology-EUROCRYPT '95, International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May 21-25, 1995, Proceeding, volume 921 of Lecture Notes in Computer Science, pages 393-403. Springer, 1995.
Claus-Peter Schnorr. Efficient identification and signatures for smart cards. In Gilles Brassard, editor, Advances in Cryptology-CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, pages 239-252. Springer, 1989.
Tjerand Silde. Short Paper: Verifiable Decryption for BGV. In Shin'ichiro Matsuo, Lewis Gudgeon, Ariah Klages-Mundt, Daniel Perez Hernandez, Sam Werner, Thomas Haines, Aleksander Essex, Andrea Bracciali, and Massimiliano Sala, editors, Financial Cryptography and Data Security. FC 2022 International Workshops-CoDecFin, DeFi, Voting, WTSC, Grenada, May 6, 2022, Revised Selected Papers, volume 13412 of Lecture Notes in Computer Science, pages 381-390. Springer, 2022.
Jacques Stern. A New Identification Scheme Based on Syndrome Decoding. In Douglas R. Stinson, editor, Advances in Cryptology-CRYPTO '93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings, volume 773 of Lecture Notes in Computer Science, pages 13-21. Springer, 1993.
