{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T09:44:56Z","timestamp":1766223896714,"version":"3.48.0"},"reference-count":18,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Bidoux and Gaborit introduced a new general technique to improve zero-knowledge (\n                    <jats:monospace>ZK<\/jats:monospace>\n                    ) proof-of-knowledge (\n                    <jats:monospace>PoK<\/jats:monospace>\n                    ) schemes for a large set of well-known post-quantum hard computational problems such as the syndrome decoding, the permuted kernel, the rank syndrome decoding, and the multivariate quadratic (\n                    <jats:monospace>MQ<\/jats:monospace>\n                    ) problems. In particular, the authors\u2019 idea in the study of Bidoux and Gaborit was to use the structure of these problems in the multi-instance setting to minimize the communication complexity of the resulting\n                    <jats:monospace>ZK<\/jats:monospace>\n                    <jats:monospace>PoK<\/jats:monospace>\n                    schemes. The security of the new schemes is then related to new hard problems. In this article, we focus on the new multivariate-based\n                    <jats:monospace>ZK<\/jats:monospace>\n                    <jats:monospace>PoK<\/jats:monospace>\n                    and the corresponding new underlying problem: the so-called\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2024-0046_eq_001.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:msub>\n                            <m:mrow>\n                              <m:mi mathvariant=\"monospace\">DiffMQ<\/m:mi>\n                            <\/m:mrow>\n                            <m:mrow>\n                              <m:mi mathvariant=\"normal\">H<\/m:mi>\n                            <\/m:mrow>\n                          <\/m:msub>\n                        <\/m:math>\n                        <jats:tex-math>{{\\mathtt{DiffMQ}}}_{{\\rm{H}}}<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . We present a new efficient probabilistic algorithm for solving the\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2024-0046_eq_003.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:msub>\n                            <m:mrow>\n                              <m:mi mathvariant=\"monospace\">DiffMQ<\/m:mi>\n                            <\/m:mrow>\n                            <m:mrow>\n                              <m:mi mathvariant=\"normal\">H<\/m:mi>\n                            <\/m:mrow>\n                          <\/m:msub>\n                        <\/m:math>\n                        <jats:tex-math>{{\\mathtt{DiffMQ}}}_{{\\rm{H}}}<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    which is polynomial-time if\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2024-0046_eq_004.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:mi>m<\/m:mi>\n                          <m:mo>\u2212<\/m:mo>\n                          <m:mi>n<\/m:mi>\n                          <m:mo>\u2208<\/m:mo>\n                          <m:mi>O<\/m:mi>\n                          <m:mrow>\n                            <m:mo>(<\/m:mo>\n                            <m:mrow>\n                              <m:mn>1<\/m:mn>\n                            <\/m:mrow>\n                            <m:mo>)<\/m:mo>\n                          <\/m:mrow>\n                        <\/m:math>\n                        <jats:tex-math>m-n\\in O\\left(1)<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . We also present experimental results showing that the algorithm is efficient in practice.\n                  <\/jats:p>","DOI":"10.1515\/jmc-2024-0046","type":"journal-article","created":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T06:00:46Z","timestamp":1744696846000},"source":"Crossref","is-referenced-by-count":0,"title":["Security analysis of ZKPoK based on MQ problem in the multi-instance setting"],"prefix":"10.1515","volume":"19","author":[{"given":"Delaram","family":"Kahrobaei","sequence":"first","affiliation":[{"name":"Departments of Computer Science and Mathematics, Queens College, City University of New York , New York , United States of America"},{"name":"Initiative for the Theoretical Sciences, Graduate Center, City University of New York , New York , United States of America"},{"name":"Department of Computer Science and Engineering, Tandon School of Engineering, New York University , New York , United States of America"}]},{"given":"Ludovic","family":"Perret","sequence":"additional","affiliation":[{"name":"Sorbonne University, CNRS, LIP6 , PolSys , Paris , France"},{"name":"Laboratoire de Recherche de l\u2019EPITA , 94270 Le Kremlin-Bic\u00eatres , France"}]},{"given":"Martina","family":"Vigorito","sequence":"additional","affiliation":[{"name":"Departments of Mathematics, University of Salerno , Salerno , Italy"}]}],"member":"374","published-online":{"date-parts":[[2025,4,15]]},"reference":[{"key":"2025122009205606559_j_jmc-2024-0046_ref_001","doi-asserted-by":"crossref","unstructured":"Bernstein D, Lange T. Post-quantum cryptography. Nature. 2017;549:188\u201394.","DOI":"10.1038\/nature23461"},{"key":"2025122009205606559_j_jmc-2024-0046_ref_002","doi-asserted-by":"crossref","unstructured":"Bidoux L, Gaborit P. Compact post-quantum signatures from proofs of knowledge leveraging structure for the sfPKP, sfSD and sfRSD problems. In: Hajji SE, Mesnager S, Souidi EM, editors. Codes, Cryptology and Information Security - 4th International Conference, C2SI 2023, Rabat, Morocco, May 29\u201331, 2023, Proceedings. vol. 13874 of Lecture Notes in Computer Science. Springer; 2023. p. 10\u201342. 10.1007\/978-3-031-33017-9_2.","DOI":"10.1007\/978-3-031-33017-9_2"},{"key":"2025122009205606559_j_jmc-2024-0046_ref_003","unstructured":"Bidoux L, Gaborit P. Shorter signatures from proofs of knowledge for the SD, MQ, PKP and RSD problems. In: arXiv Preprint; 2022. Initial version, April 2022, Creative Commons Attribution 4.0 International. https:\/\/arxiv.org\/abs\/2204.02915."},{"key":"2025122009205606559_j_jmc-2024-0046_ref_004","unstructured":"Bellini E, Makarim RH, Sanna C, Verbel J. An estimator for the hardness of the MQ problem. IACR; 2022. Cryptology ePrint Archive, Paper 2022\/708. https:\/\/eprint.iacr.org\/2022\/708."},{"key":"2025122009205606559_j_jmc-2024-0046_ref_005","doi-asserted-by":"crossref","unstructured":"Bettale L, Kahrobaei D, Perret L, Verbel JA. Biscuit: new MPCitH signature scheme from structured multivariate polynomials. In: P\u00f6pper C, Batina L, editors. Applied Cryptography and Network Security \u2013 22nd International Conference, ACNS 2024, Abu Dhabi, United Arab Emirates, March 5\u20138, 2024, Proceedings, Part I. vol. 14583 of Lecture Notes in Computer Science. Springer; 2024. p. 457\u201386. 10.1007\/978-3-031-54770-6_18.","DOI":"10.1007\/978-3-031-54770-6_18"},{"key":"2025122009205606559_j_jmc-2024-0046_ref_006","unstructured":"Casanova A, Faug\u00e8re J, Macario-Rat G, Patarin J, Perret L, Ryckeghem J. GeMSS: AGreat Multivariate Signature Scheme;. NIST round 3 post-quantum submission. Gaithersburg, Maryland, United States: National Institute of Standards and Technology (NIST)."},{"key":"2025122009205606559_j_jmc-2024-0046_ref_007","doi-asserted-by":"crossref","unstructured":"Kipnis A, Patarin J, Goubin L. Unbalanced oil and vinegar signature schemes. In: Stern J, editor. Advances in Cryptology - EUROCRYPT \u201999, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2\u20136, 1999, Proceedings. vol. 1592 of Lecture Notes in Computer Science. Springer; 1999. p. 206\u201322. 10.1007\/3-540-48910-X_15.","DOI":"10.1007\/3-540-48910-X_15"},{"key":"2025122009205606559_j_jmc-2024-0046_ref_008","doi-asserted-by":"crossref","unstructured":"Beullens W. MAYO: Practical post-quantum signatures from oil-and-vinegar maps. In: Aitawy R, H\u00fclsing A, editors. Selected Areas in Cryptography - 28th International Conference, SAC 2021, Virtual Event, September 29\u2013October 1, 2021, Revised Selected Papers. vol. 13203 of Lecture Notes in Computer Science. Springer; 2021. p. 355\u201376. 10.1007\/978-3-030-99277-4_17.","DOI":"10.1007\/978-3-030-99277-4_17"},{"key":"2025122009205606559_j_jmc-2024-0046_ref_009","doi-asserted-by":"crossref","unstructured":"Cayrel PL, V\u00e9ron P, Alaoui SMEY. A zero-knowledge identification scheme based on the q-ary syndrome decoding problem. In: Biryukov A, Gong G, Stinson DR, editors. Selected Areas in Cryptography. vol. 6544 of Lecture Notes in Computer Science. Springer; 2010. p. 171\u201386. https:\/\/hal-univ-tln.archives-ouvertes.fr\/hal-00674249\/document.","DOI":"10.1007\/978-3-642-19574-7_12"},{"key":"2025122009205606559_j_jmc-2024-0046_ref_010","doi-asserted-by":"crossref","unstructured":"Stern J. A new paradigm for public key identification. IEEE Trans Inform Theory. 1996;42(6):1757\u201368. https:\/\/www.di.ens.fr\/users\/stern\/data\/St55b.pdf.","DOI":"10.1109\/18.556672"},{"key":"2025122009205606559_j_jmc-2024-0046_ref_011","doi-asserted-by":"crossref","unstructured":"Sakumoto K, Shirai T, Hiwatari H. Public-key identification schemes based on multivariate quadratic polynomials. In: Rogaway P, editor. Advances in Cryptology - CRYPTO 2011. vol. 6841 of Lecture Notes in Computer Science. Springer; 2011. p. 706\u201323. https:\/\/www.iacr.org\/archive\/crypto2011\/68410703\/68410703.pdf.","DOI":"10.1007\/978-3-642-22792-9_40"},{"key":"2025122009205606559_j_jmc-2024-0046_ref_012","unstructured":"Wang W. Shorter Signatures from MQ; 2022. https:\/\/eprint.iacr.org\/2022\/344. Cryptology ePrint Archive, Paper 2022\/344."},{"key":"2025122009205606559_j_jmc-2024-0046_ref_013","unstructured":"Beullens W. Sigma Protocols for MQ, PKP and SIS, and Fishy Signature Schemes; 2019. Cryptology ePrint Archive, Paper 2019\/490. https:\/\/eprint.iacr.org\/2019\/490."},{"key":"2025122009205606559_j_jmc-2024-0046_ref_014","doi-asserted-by":"crossref","unstructured":"Fiat A, Shamir A. How to prove yourself: Practical solutions to identification and signature problems. In: Oswald E, Fischlin M, editors., Advances in Cryptology - EUROCRYPT 2015. Lecture Notes in Computer Science(), vol. 9057. Berlin, Heidelberg: Springer; 2015. https:\/\/doi.org\/10.1007\/978-3-662-46803-6_25","DOI":"10.1007\/978-3-662-46803-6_25"},{"key":"2025122009205606559_j_jmc-2024-0046_ref_015","doi-asserted-by":"crossref","unstructured":"Unruh D. Non-interactive zero-knowledge proofs in the quantum random oracle model. In: Theory of Cryptography, 12th Theory of Cryptography Conference (TCC 2015). Springer; 2015. p. 755\u201384.","DOI":"10.1007\/978-3-662-46803-6_25"},{"key":"2025122009205606559_j_jmc-2024-0046_ref_016","doi-asserted-by":"crossref","unstructured":"Yesina M, Shahov BS. Analysis and research of digital signature algorithm Picnic. Radiotekhnika. 2020;4(203):19\u201324. https:\/\/doi.org\/10.30837\/rt.2020.4.203.02.","DOI":"10.30837\/rt.2020.4.203.02"},{"key":"2025122009205606559_j_jmc-2024-0046_ref_017","unstructured":"Bettale L, Faug\u00e8re J, Perret L. Security analysis of multivariate polynomials for hashing. In: Yung M, Liu P, Lin D, editors. Information Security and Cryptology, 4th International Conference, Inscrypt 2008, Beijing, China, December 14\u201317, 2008, Revised Selected Papers. vol. 5487 of Lecture Notes in Computer Science. Springer; 2008. p. 115\u201324. 10.1007\/978-3-642-01440-6_11."},{"key":"2025122009205606559_j_jmc-2024-0046_ref_018","unstructured":"Ding J, Yang B. Multivariate polynomials for hashing. In: Pei D, Yung M, Lin D, Wu C, editors. Information Security and Cryptology, Third SKLOIS Conference, Inscrypt 2007, Xining, China, August 31\u2013September 5, 2007, Revised Selected Papers. vol. 4990 of Lecture Notes in Computer Science. Springer; 2007. p. 358\u201371. 10.1007\/978-3-540-79499-8_28."}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2024-0046\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2024-0046\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T09:40:19Z","timestamp":1766223619000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2024-0046\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,1]]},"references-count":18,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,4,14]]},"published-print":{"date-parts":[[2025,4,14]]}},"alternative-id":["10.1515\/jmc-2024-0046"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2024-0046","relation":{},"ISSN":["1862-2984"],"issn-type":[{"type":"electronic","value":"1862-2984"}],"subject":[],"published":{"date-parts":[[2025,1,1]]},"article-number":"20240046"}}