{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T18:38:46Z","timestamp":1784831926284,"version":"3.55.0"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031577215","type":"print"},{"value":"9783031577222","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-57722-2_8","type":"book-chapter","created":{"date-parts":[[2024,4,14]],"date-time":"2024-04-14T00:56:16Z","timestamp":1713056176000},"page":"243-274","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Zero Knowledge Protocols and\u00a0Signatures from\u00a0the\u00a0Restricted Syndrome Decoding Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8754-5526","authenticated-orcid":false,"given":"Marco","family":"Baldi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5928-359X","authenticated-orcid":false,"given":"Sebastian","family":"Bitzer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessio","family":"Pavoni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0631-3668","authenticated-orcid":false,"given":"Paolo","family":"Santini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5174-1947","authenticated-orcid":false,"given":"Antonia","family":"Wachter-Zeh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9186-2885","authenticated-orcid":false,"given":"Violetta","family":"Weger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,4,14]]},"reference":[{"key":"8_CR1","unstructured":"Aaraj, N., et al.: PERK: PERmuted Kernels. Submission to the NIST Post-Quantum Standardization project (2023)"},{"key":"8_CR2","unstructured":"Adj, G., et al.: MiRitH: MinRank in-the-Head. Submission to the NIST Post-Quantum Standardization project (2023)"},{"key":"8_CR3","unstructured":"Aguilar\u00a0Melchor, C., et al.: SDitH: Syndrome Decoding in-the-Head. Submission to the NIST Post-Quantum Standardization project (2023)"},{"key":"8_CR4","unstructured":"Aragon, N., et al.: RYDE: Rank Decoding in-the-Head. Submission to the NIST Post-Quantum Standardization project (2023)"},{"key":"8_CR5","unstructured":"Aragon, N., et al.: MIRA: MinRank in-the-Head. Submission to the NIST Post-Quantum Standardization project (2023)"},{"key":"8_CR6","unstructured":"Baldi, M., et al.: LESS: Linear Equivalence Signature Scheme. Submission to the NIST Post-Quantum Standardization project (2023)"},{"key":"8_CR7","unstructured":"Baldi, M., et al.: CROSS: codes and restricted objects signature scheme. Submission to the NIST Post-Quantum Standardization project (2023)"},{"key":"8_CR8","unstructured":"Baldi, M., et al.: A new path to code-based signatures via identification schemes with restricted errors. arXiv preprint arXiv:2008.06403 (2020)"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Baldi, M., Bitzer, S., Pavoni, A., Santini, P., Wachter-Zeh, A., Weger, V.: Zero knowledge protocols and signatures from the restricted syndrome decoding problem. Cryptology ePrint Archive (2023)","DOI":"10.1007\/978-3-031-57722-2_8"},{"key":"8_CR10","unstructured":"Banegas, G., et al.: WAVE. Submission to the NIST Post-Quantum Standardization project (2023)"},{"issue":"3","key":"8_CR11","first-page":"23","volume":"30","author":"S Barg","year":"1994","unstructured":"Barg, S.: Some new NP-complete coding problems. Problemy Peredachi Informatsii 30(3), 23\u201328 (1994)","journal-title":"Problemy Peredachi Informatsii"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-20465-4_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"A Becker","year":"2011","unstructured":"Becker, A., Coron, J.-S., Joux, A.: Improved generic algorithms for hard knapsacks. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 364\u2013385. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20465-4_21"},{"issue":"3","key":"8_CR13","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"E Berlekamp","year":"1978","unstructured":"Berlekamp, E., McEliece, R., Van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384\u2013386 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-030-45727-3_7","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10\u201314, 2020, Proceedings, Part III","author":"W Beullens","year":"2020","unstructured":"Beullens, W.: Sigma protocols for MQ, PKP and SIS, and fishy signature schemes. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology \u2013 EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10\u201314, 2020, Proceedings, Part III, pp. 183\u2013211. Springer International Publishing, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45727-3_7"},{"key":"8_CR15","unstructured":"Bidoux, L., Gaborit, P.: Shorter signatures from proofs of knowledge for the SD, MQ, PKP and RSD Problems. arXiv preprint arXiv:2204.02915 (2022)"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-031-22972-5_17","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2022: 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5\u20139, 2022, Proceedings, Part IV","author":"K Carrier","year":"2022","unstructured":"Carrier, K., Debris-Alazard, T., Meyer-Hilfiger, C., Tillich, J.-P.: Statistical decoding 2.0: reducing decoding to\u00a0LPN. In: Agrawal, S., Lin, D. (eds.) Advances in Cryptology \u2013 ASIACRYPT 2022: 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5\u20139, 2022, Proceedings, Part IV, pp. 477\u2013507. Springer Nature Switzerland, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-22972-5_17"},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-642-19574-7_12","volume-title":"Selected Areas in Cryptography","author":"P-L Cayrel","year":"2011","unstructured":"Cayrel, P.-L., V\u00e9ron, P., El Yousfi Alaoui, S.M.: A zero-knowledge identification scheme based on the q-ary syndrome decoding problem. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) Selected Areas in Cryptography, pp. 171\u2013186. Springer Berlin Heidelberg, Berlin, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19574-7_12"},{"key":"8_CR18","volume-title":"On the (in) security of optimized stern-like signature schemes","author":"A Chailloux","year":"2023","unstructured":"Chailloux, A., Etinski, S.: On the (in) security of optimized stern-like signature schemes. Designs, Codes and Cryptography (2023)"},{"key":"8_CR19","unstructured":"Cho, J., No, J.S., Lee, Y., Kim, Y.S., Koo, Z.: Enhanced pqsigRM. Submission to the NIST Post-Quantum Standardization project (2023)"},{"key":"8_CR20","unstructured":"Chou, T., et al.: MEDS: Matrix equivalence digital signature. Submission to the NIST Post-Quantum Standardization project (2023)"},{"key":"8_CR21","unstructured":"Debris-Alazard, T., Sendrier, N., Tillich, J.P.: Wave: A new code-based signature scheme. In: Asiacrypt 2019 (2019)"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Debris-Alazard, T., Tillich, J.P.: Statistical decoding. In: 2017 IEEE International Symposium on Information Theory (ISIT), pp. 1798\u20131802. IEEE (2017)","DOI":"10.1109\/ISIT.2017.8006839"},{"issue":"1","key":"8_CR23","first-page":"24","volume":"25","author":"II Dumer","year":"1989","unstructured":"Dumer, I.I.: Two decoding algorithms for linear codes. Problemy Peredachi Informatsii 25(1), 24\u201332 (1989)","journal-title":"Problemy Peredachi Informatsii"},{"key":"8_CR24","first-page":"1","volume-title":"Shared permutation for syndrome decoding: New zero-knowledge protocol and code-based signature","author":"T Feneuil","year":"2022","unstructured":"Feneuil, T., Joux, A., Rivain, M.: Shared permutation for syndrome decoding: New zero-knowledge protocol and code-based signature, pp. 1\u201346. Designs, Codes and Cryptography pp (2022)"},{"key":"8_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 86","author":"A Fiat","year":"1987","unstructured":"Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186\u2013194. Springer, Heidelberg (1987). https:\/\/doi.org\/10.1007\/3-540-47721-7_12"},{"issue":"1","key":"8_CR26","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3390\/cryptography6010005","volume":"6","author":"S Gueron","year":"2022","unstructured":"Gueron, S., Persichetti, E., Santini, P.: Designing a practical code-based signature scheme from zero-knowledge proofs with trusted setup. Cryptography 6(1), 5 (2022)","journal-title":"Cryptography"},{"key":"8_CR27","first-page":"708","volume":"2016","author":"A H\u00fclsing","year":"2016","unstructured":"H\u00fclsing, A., Rijneveld, J., Samardjiska, S., Schwabe, P.: From 5-pass MQ-based identification to MQ-based signatures. IACR Cryptol. ePrint Arch. 2016, 708 (2016)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Proceedings of the Thirty-ninth Annual ACM Symposium on Theory Of Computing, pp. 21\u201330 (2007)","DOI":"10.1145\/1250790.1250794"},{"key":"8_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45325-3_1","volume-title":"Cryptography and Coding","author":"AA Jabri","year":"2001","unstructured":"Jabri, A.A.: A statistical decoding algorithm for general linear block codes. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, pp. 1\u20138. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45325-3_1"},{"key":"8_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-65411-5_1","volume-title":"Cryptology and Network Security","author":"D Kales","year":"2020","unstructured":"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 2020. LNCS, vol. 12579, pp. 3\u201322. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-65411-5_1"},{"key":"8_CR31","doi-asserted-by":"crossref","unstructured":"Ritterhoff, S., et al.: FuLeeca: A Lee-based Signature Scheme. Submission to the NIST Post-Quantum Standardization project (2023)","DOI":"10.1007\/978-3-031-46495-9_4"},{"key":"8_CR32","unstructured":"Santini, P., Baldi, M., Chiaraluce, F.: Computational hardness of the permuted kernel and subcode equivalence problems. Cryptology ePrint Archive (2022)"},{"key":"8_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/0-387-34805-0_54","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 89 Proceedings","author":"A Shamir","year":"1990","unstructured":"Shamir, A.: An efficient identification scheme based on permuted kernels (extended abstract). In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 606\u2013609. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34805-0_54"},{"issue":"2","key":"8_CR34","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1109\/TIT.1964.1053661","volume":"10","author":"R Singleton","year":"1964","unstructured":"Singleton, R.: Maximum distance $$q$$-nary codes. IEEE Trans. Inf. Theory 10(2), 116\u2013118 (1964)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"8_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/BFb0019850","volume-title":"Coding Theory and Applications","author":"J Stern","year":"1989","unstructured":"Stern, J.: A method for finding codewords of small weight. In: Cohen, G., Wolfmann, J. (eds.) Coding Theory 1988. LNCS, vol. 388, pp. 106\u2013113. Springer, Heidelberg (1989). https:\/\/doi.org\/10.1007\/BFb0019850"},{"key":"8_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-48329-2_2","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 93","author":"J Stern","year":"1994","unstructured":"Stern, J.: A new identification scheme based on syndrome decoding. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 13\u201321. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-48329-2_2"},{"key":"8_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/3-540-48658-5_18","volume-title":"Advances in Cryptology \u2014 CRYPTO \u201994","author":"J Stern","year":"1994","unstructured":"Stern, J.: Designing identification schemes with keys of short size. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 164\u2013173. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-48658-5_18"},{"key":"8_CR38","unstructured":"Weger, V., Khathuria, K., Horlemann, A.L., Battaglioni, M., Santini, P., Persichetti, E.: On the hardness of the Lee syndrome decoding problem. In: Advances in Mathematics of Communications (2022)"}],"updated-by":[{"DOI":"10.1007\/978-3-031-57722-2_15","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T00:00:00Z","timestamp":1716422400000}}],"container-title":["Lecture Notes in Computer Science","Public-Key Cryptography \u2013 PKC 2024"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-57722-2_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T14:03:32Z","timestamp":1716386612000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-57722-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031577215","9783031577222"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-57722-2_8","relation":{"correction":[{"id-type":"doi","id":"10.1007\/978-3-031-57722-2_15","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"14 April 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"23 May 2024","order":2,"name":"change_date","label":"Change Date","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"A correction has been published.","order":4,"name":"change_details","label":"Change Details","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"PKC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"IACR International Conference on Public-Key Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sydney, NSW","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Australia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 April 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 April 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pkc2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}