nach oben

Designs, Codes and Cryptography

Erschienen in:

18.10.2022

Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature

verfasst von: Thibauld Feneuil, Antoine Joux, Matthieu Rivain

Erschienen in: Designs, Codes and Cryptography | Ausgabe 2/2023

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The threat of a coming quantum computer motivates the research for new zero-knowledge proof techniques for (or based on) post-quantum cryptographic problems. One of the few directions is code-based cryptography for which the strongest problem is the syndrome decoding (SD) of random linear codes. This problem is known to be NP-hard and the cryptanalysis state of affairs has been stable for many years. A zero-knowledge protocol for this problem was pioneered by Stern in 1993. As a simple public-coin three-round protocol, it can be converted to a post-quantum signature scheme through the famous Fiat-Shamir transform. The main drawback of this protocol is its high soundness error of 2/3, meaning that it should be repeated \(\approx 1.7 \lambda \) times to reach a \(\lambda \)-bit security. In this paper, we improve this three-decade-old state of affairs by introducing a new zero-knowledge proof for the syndrome decoding problem on random linear codes. Our protocol achieves a soundness error of 1/n for an arbitrary n in complexity \(\mathcal {O}(n)\). Our construction requires the verifier to trust some of the variables sent by the prover which can be ensured through a cut-and-choose approach. We provide an optimized version of our zero-knowledge protocol which achieves arbitrary soundness through parallel repetitions and merged cut-and-choose phase. While turning this protocol into a signature scheme, we achieve a signature size of 17 KB for a 128-bit security. This represents a significant improvement over previous constructions based on the syndrome decoding problem for random linear codes.

Vorheriger Artikel Generalized semifield spreads

Nächster Artikel The irreducible vectors of a lattice:

Nur mit Berechtigung zugänglich

We might for instance use a computationally hiding hash-based commitment scheme defined as \({\text {Com}}: (x,\rho ) \mapsto {\text {Hash}}(x \parallel \rho )\) for a long-enough random nonce \(\rho \).

Abdalla M., An J.H., Bellare M., Namprempre C.: From identification to signatures via the Fiat-Shamir transform: minimizing assumptions for security and forward-security. In: Knudsen L.R. (ed.) Advances in Cryptology—EUROCRYPT 2002. Lecture Notes in Computer Science, vol. 2332, pp. 418–433. Springer, Amsterdam (2002). https://doi.org/10.1007/3-540-46035-7_28.

Aguilar C., Gaborit P., Schrek J.: A new zero-knowledge code based identification scheme with reduced communication. In: 2011 IEEE Information Theory Workshop, pp. 648–652 (2011). https://doi.org/10.1109/ITW.2011.6089577.

Alaoui S.M.E.Y., Cayrel P., Bansarkhani R.E., Hoffmann G.: Code-based identification and signature schemes in software. In: Cuzzocrea A., Kittl C., Simos D.E., Weippl E.R., Xu L. (eds.) Security Engineering and Intelligence Informatics—CD-ARES 2013 Workshops: MoCrySEn and SeCIHD, Regensburg, Germany, September 2–6, 2013. Proceedings. Lecture Notes in Computer Science, vol. 8128, pp. 122–136. Springer, Berlin (2013).

Albrecht M.R., Rechberger C., Schneider T., Tiessen T., Zohner M.: Ciphers for MPC and FHE. In: Oswald E., Fischlin M. (eds.) Advances in Cryptology—EUROCRYPT 2015, Part I. Lecture Notes in Computer Science, vol. 9056, pp. 430–454. Springer, Sofia (2015). https://doi.org/10.1007/978-3-662-46800-5_17.

Aragon N., Blazy O., Gaborit P., Hauteville A., Zémor G.: Durandal: a rank metric based signature scheme. In: Ishai Y., Rijmen V. (eds.) Advances in Cryptology—EUROCRYPT 2019, Part III. Lecture Notes in Computer Science, vol. 11478, pp. 728–758. Springer, Darmstadt (2019). https://doi.org/10.1007/978-3-030-17659-4_25.

Baldi M., Barenghi A., Chiaraluce F., Pelosi G., Santini P.: A finite regime analysis of information set decoding algorithms. Algorithms 12(10), 209 (2019).MathSciNetCrossRefMATH

Barenghi A., Biasse J.-F., Persichetti E., Santini P.: LESS-FM: Fine-tuning signatures from the code equivalence problem. In: Cheon J.H., Tillich J.P. (eds.) Post-Quantum Cryptography—12th International Workshop, PQCrypto 2021, pp. 23–43. Springer (2021). https://doi.org/10.1007/978-3-030-81293-5_2.

Baum C., de Saint Guilhem C., Kales D., Orsini E., Scholl P., Zaverucha G.: Banquet: short and fast signatures from AES. In: Garay J. (ed.) PKC 2021: 24th International Conference on Theory and Practice of Public Key Cryptography, Part I. Lecture Notes in Computer Science, vol. 12710, pp. 266–297. Springer, Virtual Event (2021). https://doi.org/10.1007/978-3-030-75245-3_11.

Becker A., Joux A., May A., Meurer A.: Decoding random binary linear codes in \(2^{n/20}\): How 1 + 1 = 0 improves information set decoding. In: Pointcheval D., Johansson T. (eds.) Advances in Cryptology—EUROCRYPT 2012. Lecture Notes in Computer Science, vol. 7237, pp. 520–536. Springer, Cambridge (2012). https://doi.org/10.1007/978-3-642-29011-4_31.

10.

Bernstein D.J., Hülsing A., Kölbl S., Niederhagen R., Rijneveld J., Schwabe P.: The SPHINCS\(^+\) signature framework. In: Cavallaro L., Kinder J., Wang X., Katz J. (eds.) ACM CCS 2019: 26th Conference on Computer and Communications Security, pp. 2129–2146. ACM Press, London (2019). https://doi.org/10.1145/3319535.3363229.

11.

Beullens W.: Sigma protocols for MQ, PKP and SIS, and Fishy signature schemes. In: Canteaut A., Ishai Y. (eds.) Advances in Cryptology—EUROCRYPT 2020, Part III. Lecture Notes in Computer Science, vol. 12107, pp. 183–211. Springer, Zagreb (2020). https://doi.org/10.1007/978-3-030-45727-3_7.

12.

Biasse J.-F., Micheli G., Persichetti E., Santini P.: LESS is more: code-based signatures without syndromes. In: Nitaj A., Youssef A.M. (eds.) AFRICACRYPT 20: 12th International Conference on Cryptology in Africa. Lecture Notes in Computer Science, vol. 12174, pp. 45–65. Springer, Cairo (2020). https://doi.org/10.1007/978-3-030-51938-4_3.

13.

Chailloux A.: On the (In)security of optimized Stern-like signature schemes. In: WCC 2022: The Twelfth International Workshop on Coding and Cryptography. https://www.wcc2022.uni-rostock.de/storages/uni-rostock/Tagungen/WCC2022/Papers/WCC_2022_paper_54.pdf.

14.

Chase M., Derler D., Goldfeder S., Katz J., Kolesnikov V., Orlandi C., Ramacher S., Rechberger C., Slamanig D., Wang X., Zaverucha G.: The picnic signature scheme—design document. Version 2.2—14 April 2020. https://raw.githubusercontent.com/microsoft/Picnic/master/spec/design-v2.2.pdf.

15.

de Saint Guilhem C., De Meyer L., Orsini E., Smart N.P.: BBQ: using AES in picnic signatures. In: Paterson K.G., Stebila D. (eds.) SAC 2019: 26th Annual International Workshop on Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 11959, pp. 669–692. Springer, Waterloo (2019). https://doi.org/10.1007/978-3-030-38471-5_27.

16.

Debris-Alazard T., Sendrier N., Tillich J.-P.: Wave: a new family of trapdoor one-way preimage sampleable functions based on codes. In: Galbraith, S.D., Moriai, S. (eds.) Advances in Cryptology—ASIACRYPT 2019, Part I. Lecture Notes in Computer Science, vol. 11921, pp. 21–51. Springer, Kobe (2019). https://doi.org/10.1007/978-3-030-34578-5_2.

17.

Feneuil T., Joux A., Rivain M.: Syndrome decoding in the head: shorter signatures from zero-knowledge proofs. Cryptology ePrint Archive, Report 2022/188 (2022). https://eprint.iacr.org/2022/188.

18.

Fiat A., Shamir A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko A.M. (ed.) Advances in Cryptology—CRYPTO’86. Lecture Notes in Computer Science, vol. 263, pp. 186–194. Springer, Santa Barbara (1987). https://doi.org/10.1007/3-540-47721-7_12.

19.

Gaborit P., Girault M.: Lightweight code-based identification and signature. In: IEEE International Symposium on Information Theory, ISIT 2007, Nice, France, June 24–29, 2007, pp. 191–195. IEEE (2007).

20.

Gueron S., Persichetti E., Santini P.: Designing a practical code-based signature scheme from zero-knowledge proofs with trusted setup. Cryptography (2022). https://doi.org/10.3390/cryptography6010005.CrossRef

21.

Ishai Y., Kushilevitz E., Ostrovsky R., Sahai A.: Zero-knowledge from secure multiparty computation. In: Johnson D.S., Feige U. (eds.) 39th Annual ACM Symposium on Theory of Computing, pp. 21–30. ACM Press, San Diego (2007). https://doi.org/10.1145/1250790.1250794.

22.

Kales D., Zaverucha G.: An attack on some signature schemes constructed from five-pass identification schemes. In: Krenn S., Shulman H., Vaudenay S. (eds.) CANS 20: 19th International Conference on Cryptology and Network Security. Lecture Notes in Computer Science, vol. 12579, pp. 3–22. Springer, Vienna. (2020). https://doi.org/10.1007/978-3-030-65411-5_1.

23.

Kales D., Zaverucha G.: Improving the performance of the Picnic signature scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst. 4, 154–188 (2020).CrossRef

24.

Katz J., Kolesnikov V., Wang X.: Improved non-interactive zero knowledge with applications to post-quantum signatures. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) ACM CCS 2018: 25th Conference on Computer and Communications Security, pp. 525–537. ACM Press, Toronto (2018). https://doi.org/10.1145/3243734.3243805.

25.

Lyubashevsky V.: Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Matsui M. (ed.) Advances in Cryptology—ASIACRYPT 2009. Lecture Notes in Computer Science, vol. 5912, pp. 598–616. Springer, Tokyo (2009). https://doi.org/10.1007/978-3-642-10366-7_35.

26.

May A., Meurer A., Thomae E.: Decoding random linear codes in \(\tilde{\cal{O}}(2^{0.054n})\). In: Lee D.H., Wang X. (eds.) Advances in Cryptology – ASIACRYPT 2011. Lecture Notes in Computer Science, vol. 7073, pp. 107–124. Springer, Seoul (2011). https://doi.org/10.1007/978-3-642-25385-0_6.

27.

Pointcheval D., Stern J.: Security arguments for digital signatures and blind signatures. J. Cryptol. 13(3), 361–396 (2000). https://doi.org/10.1007/s001450010003.CrossRefMATH

28.

Schnorr C.-P.: Efficient identification and signatures for smart cards. In: Brassard G. (ed.) Advances in Cryptology—CRYPTO’89. Lecture Notes in Computer Science, vol. 435, pp. 239–252. Springer, Santa Barbara (1990). https://doi.org/10.1007/0-387-34805-0_22.

29.

Shor P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE Computer Society Press, Santa Fe, NM, USA (1994). https://doi.org/10.1109/SFCS.1994.365700.

30.

Stern J.: A new identification scheme based on syndrome decoding. In: Stinson, D.R. (ed.) Advances in Cryptology—CRYPTO’93. Lecture Notes in Computer Science, vol. 773, pp. 13–21. Springer, Santa Barbara, CA, USA (1994). https://doi.org/10.1007/3-540-48329-2_2.

31.

Torres R.C., Sendrier N.: Analysis of information set decoding for a sub-linear error weight. In: Takagi T. (ed.) Post-Quantum Cryptography—7th International Workshop, PQCrypto 2016, pp. 144–161. Springer, Fukuoka (2016). https://doi.org/10.1007/978-3-319-29360-8_10.

32.

Véron P.: Improved identification schemes based on error-correcting codes. Appl. Algebra Eng. Commun. Comput. 8(1), 57–69 (1996).MathSciNetCrossRefMATH

Titel: Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature
verfasst von: Thibauld Feneuil
Antoine Joux
Matthieu Rivain
Publikationsdatum: 18.10.2022
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 2/2023
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-022-01116-1

Springer Professional

Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 2/2023

Self-orthogonal codes over a non-unital ring and combinatorial matrices

-linear codes: rank and kernel

Several classes of bent functions over finite fields

Improved generalized block inserting construction of constant dimension codes

Constructions of new matroids and designs over

Code-based signatures from new proofs of knowledge for the syndrome decoding problem

Premium Partner