{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T23:31:36Z","timestamp":1768519896532,"version":"3.49.0"},"reference-count":42,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T00:00:00Z","timestamp":1643241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1906360"],"award-info":[{"award-number":["1906360"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>This paper defines a new practical construction for a code-based signature scheme. We introduce a new protocol that is designed to follow the recent paradigm known as \u201cSigma protocol with helper\u201d, and prove that the protocol\u2019s security reduces directly to the Syndrome Decoding Problem. The protocol is then converted to a full-fledged signature scheme via a sequence of generic steps that include: removing the role of the helper; incorporating a variety of protocol optimizations (using e.g., Merkle trees); applying the Fiat\u2013Shamir transformation. The resulting signature scheme is EUF-CMA secure in the QROM, with the following advantages: (a) Security relies on only minimal assumptions and is backed by a long-studied NP-complete problem; (b) the trusted setup structure allows for obtaining an arbitrarily small soundness error. This minimizes the required number of repetitions, thus alleviating a major bottleneck associated with Fiat\u2013Shamir schemes. We outline an initial performance estimation to confirm that our scheme is competitive with respect to existing solutions of similar type.<\/jats:p>","DOI":"10.3390\/cryptography6010005","type":"journal-article","created":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T21:59:55Z","timestamp":1643320795000},"page":"5","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["Designing a Practical Code-Based Signature Scheme from Zero-Knowledge Proofs with Trusted Setup"],"prefix":"10.3390","volume":"6","author":[{"given":"Shay","family":"Gueron","sequence":"first","affiliation":[{"name":"Amazon Web Services Inc., Seattle, WA 98101, USA"},{"name":"Department of Mathematics, University of Haifa, Haifa 3498838, Israel"}]},{"given":"Edoardo","family":"Persichetti","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Florida Atlantic University, Boca Raton, FL 33431, USA"}]},{"given":"Paolo","family":"Santini","sequence":"additional","affiliation":[{"name":"Department of Engineering, Marche Polytechnic University, 60121 Ancona, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1137\/S0097539795293172","article-title":"Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer","volume":"26","author":"Shor","year":"1997","journal-title":"SIAM J. Comput."},{"key":"ref_2","first-page":"114","article-title":"A Public-Key Cryptosystem Based On Algebraic Coding Theory","volume":"44","author":"McEliece","year":"1978","journal-title":"Deep Space Netw. Prog. Rep."},{"key":"ref_3","unstructured":"Albrecht, M.R., Bernstein, D.J., Chou, T., Cid, C., Gilcher, J., Lange, T., Maram, V., von Maurich, I., Misoczki, R., and Niederhagen, R. (2021). Classic McEliece: Conservative Code-Based Cryptography. NIST Post-Quantum Standardization, 3rd Round, Available online: https:\/\/www.hyperelliptic.org\/tanja\/vortraege\/mceliece-round-3.pdf."},{"key":"ref_4","unstructured":"(2021, December 09). 2017. NIST Call for Standardization, Available online: https:\/\/csrc.nist.gov\/Projects\/Post-Quantum-Cryptography."},{"key":"ref_5","unstructured":"Melchor, C.A., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Bos, J., Deneuville, J.C., Arnaud Dion, I.S., Gaborit, P., and Lacan, J. (2021). HQC: Hamming Quasi-Cyclic. NIST Post-Quantum Standardization, 3rd Round, Available online: https:\/\/pqc-hqc.org\/doc\/hqc-specification_2021-06-06.pdf."},{"key":"ref_6","unstructured":"Aragon, N., Barreto, P.S.L.M., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.C., Gaborit, P., Gueron, S., G\u00fcneysu, T., and Melchor, C.A. (2021). BIKE: Bit Flipping Key Encapsulation. NIST Post-Quantum Standardization, 3rd Round, Available online: https:\/\/bikesuite.org\/files\/v4.2\/BIKE_Spec.2021.07.26.1.pdf."},{"key":"ref_7","unstructured":"(2021, December 09). 2021. NIST Status Update, Available online: https:\/\/csrc.nist.gov\/Presentations\/2021\/status-update-on-the-3rd-round."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Stinson, D.R. (1994). A new identification scheme based on syndrome decoding. Advances in Cryptology\u2014CRYPTO\u2019 93, Springer.","DOI":"10.1007\/3-540-48329-2"},{"key":"ref_9","unstructured":"Fiat, A., and Shamir, A. (1986). How to prove yourself: Practical solutions to identification and signature problems. CRYPTO, Springer."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s002000050053","article-title":"Improved identification schemes based on error-correcting codes","volume":"8","year":"1997","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Gaborit, P., and Girault, M. (2007, January 24\u201329). Lightweight code-based identification and signature. Proceedings of the 2007 IEEE International Symposium on Information Theory, Nice, France.","DOI":"10.1109\/ISIT.2007.4557225"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Cayrel, P.L., V\u00e9ron, P., and El Yousfi Alaoui, S.M. (2011). A zero-knowledge identification scheme based on the q-ary syndrome decoding problem. Selected Areas in Cryptography, Springer.","DOI":"10.1007\/978-3-642-19574-7_12"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/3-540-45682-1_10","article-title":"How to Achieve a McEliece-Based Digital Signature Scheme","volume":"2248","author":"Courtois","year":"2001","journal-title":"Lect. Notes Comput. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Debris-Alazard, T., Sendrier, N., and Tillich, J.P. (2019). Wave: A new family of trapdoor one-way preimage sampleable functions based on codes. ASIACRYPT, Springer.","DOI":"10.1007\/978-3-030-34578-5_2"},{"key":"ref_15","unstructured":"Nitaj, A., and Youssef, A. (2020). LESS is More: Code-Based Signatures Without Syndromes. AFRICACRYPT, Springer."},{"key":"ref_16","first-page":"23","article-title":"LESS-FM: Fine-tuning Signatures from a Code-based Cryptographic Group Action","volume":"2021","author":"Barenghi","year":"2021","journal-title":"PQCrypto"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Beullens, W. (2020, January 21\u201323). Not Enough LESS: An Improved Algorithm for Solving Code Equivalence Problems over Fq. Proceedings of the International Conference on Selected Areas in Cryptography, Halifax, NS, Canada.","DOI":"10.1007\/978-3-030-81652-0_15"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Gaborit, P., Ruatta, O., Schrek, J., and Z\u00e9mor, G. (2014). RankSign: An efficient signature algorithm based on the rank metric. International Workshop on Post-Quantum Cryptography, Springer.","DOI":"10.1007\/978-3-319-11659-4_6"},{"key":"ref_19","unstructured":"Ishai, Y., and Rijmen, V. (2019). Durandal: A Rank Metric Based Signature Scheme. Advances in Cryptology\u2013EUROCRYPT 2019, Springer International Publishing."},{"key":"ref_20","unstructured":"Baldi, M., Battaglioni, M., Chiaraluce, F., Horlemann-Trautmann, A.L., Persichetti, E., Santini, P., and Weger, V. (2020). A new path to code-based signatures via identification schemes with restricted errors. arXiv."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Debris-Alazard, T., and Tillich, J.P. (2018, January 2\u20136). Two attacks on rank metric code-based schemes: RankSign and an IBE scheme. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, Australia.","DOI":"10.1007\/978-3-030-03326-2_3"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Bardet, M., and Briaud, P. (2021). An algebraic approach to the Rank Support Learning problem. arXiv.","DOI":"10.1007\/978-3-030-81293-5_23"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Katz, J., Kolesnikov, V., and Wang, X. (2018, January 15\u201319). Improved non-interactive zero knowledge with applications to post-quantum signatures. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, ON, Canada.","DOI":"10.1145\/3243734.3243805"},{"key":"ref_24","first-page":"183","article-title":"Sigma Protocols for MQ, PKP and SIS, and Fishy Signature Schemes","volume":"12107","author":"Beullens","year":"2020","journal-title":"Eurocrypt"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","article-title":"On the inherent intractability of certain coding problems (Corresp.)","volume":"24","author":"Berlekamp","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_26","first-page":"23","article-title":"Some new NP-complete coding problems","volume":"30","author":"Barg","year":"1994","journal-title":"Probl. Peredachi Informatsii"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Beullens, W. (2020, January 10\u201314). Sigma protocols for MQ, PKP and SIS, and fishy signature schemes. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia.","DOI":"10.1007\/978-3-030-45727-3_7"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Abdalla, M., An, J.H., Bellare, M., and Namprempre, C. (2002). From identification to signatures via the Fiat-Shamir transform: Minimizing assumptions for security and forward-security. EUROCRYPT, Springer.","DOI":"10.1007\/3-540-46035-7_28"},{"key":"ref_29","unstructured":"Kiltz, E., Lyubashevsky, V., and Schaffner, C. (May, January 29). A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Don, J., Fehr, S., Majenz, C., and Schaffner, C. (2019). Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model. CRYPTO, Springer.","DOI":"10.1007\/978-3-030-26951-7_13"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Liu, Q., and Zhandry, M. (2019). Revisiting Post-quantum Fiat-Shamir. Advances in Cryptology-CRYPTO 2019, Springer.","DOI":"10.1007\/978-3-030-26951-7_12"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Unruh, D. (2016, January 8\u201312). Computationally binding quantum commitments. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria.","DOI":"10.1007\/978-3-662-49896-5_18"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Fehr, S. (2018, January 11\u201314). Classical proofs for the quantum collapsing property of classical hash functions. Proceedings of the Theory of Cryptography Conference, Panaji, India.","DOI":"10.1007\/978-3-030-03810-6_12"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Beullens, W., Katsumata, S., and Pintore, F. (2020, January 7\u201311). Calamari and Falafl: Logarithmic (linkable) ring signatures from isogenies and lattices. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Daejeon-gu, Korea.","DOI":"10.1007\/978-3-030-64834-3_16"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1109\/TIT.1962.1057777","article-title":"The use of information sets in decoding cyclic codes","volume":"8","author":"Prange","year":"1962","journal-title":"IRE Trans. Inf. Theory"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Peters, C. (2010). Information-set decoding for linear codes over Fq. International Workshop on Post-Quantum Cryptography, Springer.","DOI":"10.1007\/978-3-642-12929-2_7"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Bellini, E., Caullery, F., Gaborit, P., Manzano, M., and Mateu, V. (2019, January 7\u201312). Improved Veron Identification and Signature Schemes in the Rank Metric. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849585"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V. (2009). Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures. ASIACRYPT, Springer.","DOI":"10.1007\/978-3-642-10366-7_35"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Bardet, M., Briaud, P., Bros, M., Gaborit, P., Neiger, V., Ruatta, O., and Tillich, J.P. (2020, January 10\u201314). An algebraic attack on rank metric code-based cryptosystems. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia.","DOI":"10.1007\/978-3-030-45727-3_3"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Bardet, M., Bros, M., Cabarcas, D., Gaborit, P., Perlner, R., Smith-Tone, D., Tillich, J.P., and Verbel, J. (2020, January 7\u201311). Improvements of Algebraic Attacks for solving the Rank Decoding and MinRank problems. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Daejeon-gu, Korea.","DOI":"10.1007\/978-3-030-64837-4_17"},{"key":"ref_41","unstructured":"Feneuil, T., Joux, A., and Rivain, M. (2021, December 09). Shared Permutation for Syndrome Decoding: New Zero-Knowledge Protocol and Code-Based Signature. Cryptology ePrint Archive: Report 2021\/1576. Available online: https:\/\/eprint.iacr.org\/2021\/1576."},{"key":"ref_42","unstructured":"Gueron, S., Persichetti, E., and Santini, P. (2021, December 09). Designing a Practical Code-Based Signature Scheme from Zero-Knowledge Proofs with Trusted Setup. Cryptology ePrint Archive: Report 2021\/1020. Available online: https:\/\/eprint.iacr.org\/2021\/1020."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/6\/1\/5\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:09:03Z","timestamp":1760134143000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/6\/1\/5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,27]]},"references-count":42,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,3]]}},"alternative-id":["cryptography6010005"],"URL":"https:\/\/doi.org\/10.3390\/cryptography6010005","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,27]]}}}