Abstract
The approaching threat of quantum computing to conventional cryptography underscores the urgent need to reassess information security and develop practical quantum-safe primitives. In this paper, we present concrete implementations of Zero-Knowledge Arguments (ZKAs), analogous to but distinct from traditional Σ-protocols. Our implementation, termed the Cryptographic Primitive Argument (CPA), can be realized securely using any post-quantum Key Exchange Mechanism (KEM) and Digital Signature (DS) scheme. We describe two variants: one with dynamic public key encapsulation (CPA-DE) and another that is non-interactive (CPA-NI). We further detail efficient, NIST-standard-compliant CPAs instantiated with ML-KEM and ML-DSA, and provide a comparison with a post-quantum Σ-protocol. The lightweight and modular nature of our CPAs makes them suitable for a wide range of applications, including quantum-secure authentication, blockchain systems, and digital currencies.
References
Carlos Aguilar Melchor, Nicolas Aragon, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Edoardo Persichetti, and Gilles Zémor. Hamming Quasi-Cyclic (HQC), November 2017. Submission to the NIST post quantum standardization process. 2017.
Gorjan Alagic, Quynh Dang, Dustin Moody, Angela Robinson, Hamilton Silberg, and Daniel Smith-Tone. Module-lattice-based key-encapsulation mechanism standard, 2024-08-13 04:08:00 2024.
S. Almuhammadi and C. Neuman. Security and privacy using one-round zero-knowledge proofs. In Seventh IEEE International Conference on E-Commerce Technology (CEC’05), pages 435–438, 2005.
Jean-Philippe Aumasson, Daniel J. Bernstein, Ward Beullens, Christoph Dobraunig, Maria Eichlseder, Scott Fluhrer, Stefan-Lukas Gazdag, Andreas Hülsing, Panos Kampanakis, Stefan Kölbl, Tanja Lange, Martin M. Lauridsen, Florian Mendel, Ruben Niederhagen, Christian Rechberger, Joost Rijneveld, Peter Schwabe, and Bas Westerbaan. SPHINCS+. Tech. rep. available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions, 2020. National Institute of Standards and Technology.
Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Stehlé Damien. CRYSTALS-KYBER. Technical report available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions, 2020. National Institute of Standards and Technology.
Elaine Barker, Don Johnson, and Miles Smid. Recommendation for pair-wise key establishment using discrete logarithm cryptography (revised), 2007-03-14 2007.
Claudia Bartoli and Ignacio Cascudo. On sigma-protocols and (packed) black-box secret sharing schemes. In Qiang Tang and Vanessa Teague, editors, Public-Key Cryptography – PKC 2024, pages 426–457, Cham, 2024. Springer Nature Switzerland.
Andrea Basso, Giulio Codogni, Deirdre Connolly, Luca de Feo, Tako Bories Fouotsa, Guido Maria Lido, Travis Morrison, Lorenz Panny, Sikhar Patranabis, and Benjamin Wesolowski. Supersingular curves you can trust. EUROCRYPT 2023, LNCS 14005:405–437, 2023.
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, 2018.
Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, and David Levit. Scalable and transparent proofs over all large fields, via elliptic curves (ecfft part ii). Cryptology ePrint Archive, Paper 2022/1542, 2022.
E. Berlekamp, R. McEliece, and H. van Tilborg. On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information Theory, 24(3):384–386, 1978.
Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, page 326–349, New York, NY, USA, 2012. Association for Computing Machinery.
Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, page 103–112, New York, NY, USA, 1988. Association for Computing Machinery.
Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical hardness of learning with errors. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, page 575–584, New York, NY, USA, 2013. Association for Computing Machinery.
Stanislav Bulygin, Albrecht Petzoldt, and Johannes Buchmann. Towards provable security of the unbalanced oil and vinegar signature scheme under direct attacks. In Guang Gong and Kishan Chand Gupta, editors, Progress in Cryptology - INDOCRYPT 2010, pages 17–32, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
Wouter Castryck and Thomas Decru. An efficient key recovery attack on sidh (preliminary version). Cryptology ePrint Archive, Paper 2022/975, 2022.
Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, and Greg Zaverucha. Post-quantum zero-knowledge and signatures from symmetric-key primitives. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS ’17, page 1825–1842, New York, NY, USA, 2017. Association for Computing Machinery.
Craig Costello, Patrick Longa, and Michael Naehrig. Efficient algorithms for supersingular isogeny diffie-hellman. Cryptology ePrint Archive, Paper 2016/413, 2016.
Thinh Dang, Jacob Lichtinger, Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, Ray Perlner, and Angela Robinson. Module-lattice-based digital signature standard, 2024-08-13 04:08:00 2024.
W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976.
Jintai Ding, Joshua Deaton, Kurt Schmidt, Vishakha, and Zheng Zhang. Cryptanalysis of the lifted unbalanced oil vinegar signature scheme. In Annual International Cryptology Conference, pages 279–298. Springer, 2020.
Jintai Ding and Bo-Yin Yang. Multivariate Public Key Cryptography, pages 193–241. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.
Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. Security of the Fiat-Shamir transformation in the quantum random-oracle model. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, pages 356–383, Cham, 2019. Springer International Publishing.
Jens Ernstberger, Stefanos Chaliasos, Liyi Zhou, Philipp Jovanovic, and Arthur Gervais. Do you need a zero knowledge proof? Cryptology ePrint Archive, Paper 2024/050, 2024.
Luca De Feo, David Jao, and Jérôme Plût. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Cryptology ePrint Archive, Paper 2011/506, 2011.
Luca De Feo, David Jao, and Jérôme Plût. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Journal of Mathematical Cryptology, 8(3):209–247, 2014.
S Goldwasser, S Micali, and C Rackoff. The knowledge complexity of interactive proof-systems. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC ’85, page 291–304, New York, NY, USA, 1985. Association for Computing Machinery.
Randy Kuang. Optimized HPPK cryptography for post-quantum security. Cryptology ePrint Archive, Paper 2025/1467, 2025.
V Lyubashevsky, L Ducas, E Kiltz, T Lepoint, P Schwabe, G Seiler, D Stehlé, and S Bai. CRYSTALS-DILITHIUM. Technical report available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions, 2020. National Institute of Standards and Technology.
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, pages 1–23, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
R. J. McEliece. A Public-Key Cryptosystem Based On Algebraic Coding Theory. Deep Space Network Progress Report, 44:114–116, January 1978.
NIST. Status report on the 3rd round of the NIST pqc cryptography standardization process. https://csrc.nist.gov/publications/detail/nistir/8413/final, July 2022.
Shien Jin Ong and Salil P. Vadhan. Zero knowledge and soundness are symmetric. In Advances in Cryptology - EUROCRYPT 2007, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20–24, 2007, Proceedings, volume 4515 of Springer, Lecture Notes in Computer Science, pages 187–209, 2007.
T Prest, P-A Fouque, J Hoffstein, P Kirchner, V. Lyubashevsky, T Pornin, T Ricosset, G Seiler, W Whyte, and Z Zhang. FALCON. Tech. rep. available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions, 2020. National Institute of Standards and Technology.
Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978.
Damien Robert. Breaking sidh in polynomial time. Cryptology ePrint Archive, Paper 2022/1038, 2022.
Claus-Peter Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4:161–174, 1991.
P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994.
Chengdong Tao, Adama Diene, Shaohua Tang, and Jintai Ding. Simple matrix scheme for encryption. In Philippe Gaborit, editor, Post-Quantum Cryptography, pages 231–242, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
Jiaming Wen, Houzhen Wang, and Huanguo Zhang. Post-quantum Sigma Protocols and Signatures from Low-Rank Matrix Completions, pages 186–206. Springer, Nature. 10 2023.
Lizhen Zhang, Shang Gao, and Bin Xiao. Lattice-based σ-protocols for polynomial relations with standard soundness. Cryptology ePrint Archive, Paper 2025/313, 2025.
Lu Zhou, Abebe Diro, Akanksha Saini, Shahriar Kaisar, and Pham Cong Hiep. Leveraging zero knowledge proofs for blockchain-based identity sharing: A survey of advancements, challenges and opportunities. Journal of Information Security and Applications, 80:103678, 2024.