{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:41:59Z","timestamp":1767930119128,"version":"3.49.0"},"reference-count":38,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T00:00:00Z","timestamp":1751846400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,12,1]]},"abstract":"<jats:p>Wave is a code-based digital signature scheme. Its hardness relies on the unforgeability of the signature and the indistinguishability of its public key, a parity check matrix of a ternary (U, U+V)-code. The best known attacks involve solving the Decoding Problem using the Information Set Decoding algorithm (ISD) to defeat these two problems. Our main contribution is the description of a quantum smoothed Wagner\u2019s algorithm within the ISD framework, which improves the forgery attack on Wave in the quantum setting. We also recap the best known key and forgery attacks against Wave in both classical and quantum settings. For each one, we express their time complexity as function of Wave parameters and deduce its claimed security.<\/jats:p>","DOI":"10.62056\/ae89ksuc2","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:39:47Z","timestamp":1767915587000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Quantum security analysis of Wave"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-4639-7660","authenticated-orcid":false,"given":"Johanna","family":"Loyer","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02kvxyf05","id-type":"ROR","asserted-by":"publisher"}],"name":"Inria Saclay","place":["France"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"ref1:NISTPQC-ADD-R1:Wave23","volume-title":"Wave","author":"Gustavo Banegas","year":"2023"},{"key":"ref2:AC:DebSenTil19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-030-34578-5_2","article-title":"Wave: A New Family of Trapdoor One-Way Preimage Sampleable\n  Functions Based on Codes","volume":"11921","author":"Thomas Debris-Alazard","year":"2019"},{"key":"ref3:STOC:GenPeiVai08","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1145\/1374376.1374407","article-title":"Trapdoors for hard lattices and new cryptographic\n  constructions","author":"Craig Gentry","year":"2008"},{"key":"ref4:NISTPQC:FALCON22","volume-title":"FALCON","author":"Thomas Prest","year":"2022"},{"key":"ref5:EPRINT:BDNS21","volume-title":"Wavelet: Code-based postquantum signatures with fast\n  verification on microcontrollers","author":"Gustavo Banegas","year":"2021"},{"key":"ref6:DBLP:journals\/tit\/BerlekampMT78","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","article-title":"On the inherent intractability of certain coding problems\n  (Corresp.)","volume":"24","author":"Elwyn R. Berlekamp","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref7:DBLP:journals\/tit\/Prange62","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1109\/TIT.1962.1057777","article-title":"The use of information sets in decoding cyclic codes","volume":"8","author":"Eugene Prange","year":"1962","journal-title":"IRE Trans. Inf. Theory"},{"key":"ref8:DBLP:conf\/coding\/Stern88","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/BFB0019850","article-title":"A method for finding codewords of small weight","volume":"388","author":"Jacques Stern","year":"1988"},{"key":"ref9:dumer86","first-page":"157","article-title":"On syndrome decoding of linear codes","volume":"2","author":"II Dumer","year":"1986"},{"key":"ref10:AC:FinSen09","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-642-10366-7_6","article-title":"Security Bounds for the Design of Code-Based Cryptosystems","volume":"5912","author":"Matthieu Finiasz","year":"2009"},{"key":"ref11:PQCRYPTO:Bernstein10","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-642-12929-2_6","article-title":"Grover vs. McEliece","author":"Daniel J. Bernstein","year":"2010"},{"key":"ref12:C:BerLanPet11","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1007\/978-3-642-22792-9_42","article-title":"Smaller Decoding Exponents: Ball-Collision Decoding","volume":"6841","author":"Daniel J. Bernstein","year":"2011"},{"key":"ref13:AC:MayMeuTho11","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-25385-0_6","article-title":"Decoding Random Linear Codes in\n  $\\tilde{\\mathcal{O}}(2^{0.054n})$","volume":"7073","author":"Alexander May","year":"2011"},{"key":"ref14:EC:BJMM12","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/978-3-642-29011-4_31","article-title":"Decoding Random Binary Linear Codes in $2^{n\/20}$: How 1 +\n  1 = 0 Improves Information Set Decoding","volume":"7237","author":"Anja Becker","year":"2012"},{"key":"ref15:EC:MayOze15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-662-46800-5_9","article-title":"On Computing Nearest Neighbors with Applications to Decoding\n  of Binary Linear Codes","volume":"9056","author":"Alexander May","year":"2015"},{"key":"ref16:PQCRYPTO:BotMay18","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-319-79063-3_2","article-title":"Decoding Linear Codes with High Error Rate and Its Impact\n  for LPN Security","author":"Leif Both","year":"2018"},{"key":"ref17:PQCRYPTO:KacTil17","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-319-59879-6_5","article-title":"Quantum Information Set Decoding Algorithms","author":"Ghazal Kachigar","year":"2017"},{"key":"ref18:PQCRYPTO:Kirshanova18","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/978-3-319-79063-3_24","article-title":"Improved Quantum Information Set Decoding","author":"Elena Kirshanova","year":"2018"},{"key":"ref19:AC:CDMT22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-031-22972-5_17","article-title":"Statistical Decoding 2.0: Reducing Decoding to LPN","volume":"13794","author":"Kevin Carrier","year":"2022"},{"key":"ref20:McEliece78","first-page":"114","volume-title":"A public-key cryptosystem based on algebraic coding theory","author":"Robert J. McEliece","year":"1978"},{"key":"ref21:FOCS:Alekhnovich03","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1109\/SFCS.2003.1238204","article-title":"More on Average Case vs Approximation Complexity","author":"Michael Alekhnovich","year":"2003"},{"key":"ref22:NISTPQC-R1:BIKE17","volume-title":"BIKE","author":"Nicolas Aragon","year":"2017"},{"key":"ref23:NISTPQC-R4:HQC22","volume-title":"HQC","author":"Carlos Aguilar-Melchor","year":"2022"},{"key":"ref24:SAC:BCDL19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/978-3-030-38471-5_18","article-title":"Ternary Syndrome Decoding with Large Weight","volume":"11959","author":"R\u00e9mi Bricout","year":"2019"},{"key":"ref25:PQCRYPTO:ChaDebEti21","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-030-81293-5_3","article-title":"Classical and Quantum Algorithms for Generic Syndrome\n  Decoding Problems and Applications to the Lee Metric","author":"Andr\u00e9 Chailloux","year":"2021"},{"key":"ref26:PKC:KarLef22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/978-3-030-97121-2_4","article-title":"Time-Memory Tradeoffs for Large-Weight Syndrome Decoding in\n  Ternary Codes","volume":"13177","author":"Pierre Karpman","year":"2022"},{"key":"ref27:PQCRYPTO:Sendrier23","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-031-40003-2_4","article-title":"Wave Parameter Selection","author":"Nicolas Sendrier","year":"2023"},{"key":"ref28:PQCRYPTO:Sendrier11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-642-25405-5_4","article-title":"Decoding One Out of Many","author":"Nicolas Sendrier","year":"2011"},{"key":"ref29:C:Wagner02","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-45708-9_19","article-title":"A Generalized Birthday Problem","volume":"2442","author":"David Wagner","year":"2002"},{"key":"ref30:DBLP:conf\/tqc\/Kuperberg13","series-title":"LIPIcs","doi-asserted-by":"publisher","first-page":"20","DOI":"10.4230\/LIPICS.TQC.2013.20","article-title":"Another Subexponential-time Quantum Algorithm for the\n  Dihedral Hidden Subgroup Problem","volume":"22","author":"Greg Kuperberg","year":"2013"},{"key":"ref31:STOC:Grover96","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1145\/237814.237866","article-title":"A Fast Quantum Mechanical Algorithm for Database Search","author":"Lov K. Grover","year":"1996"},{"key":"ref32:BHMT02","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1090\/conm\/305\/05215","volume-title":"Quantum amplitude amplification and estimation","author":"Gilles Brassard","year":"2002","journal-title":"Quantum Computation and Information","ISSN":"https:\/\/id.crossref.org\/issn\/0271-4132","issn-type":"electronic"},{"key":"ref33:DBLP:journals\/tit\/JohanssonJ02a","doi-asserted-by":"publisher","first-page":"2669","DOI":"10.1109\/TIT.2002.802608","article-title":"On the complexity of some cryptographic problems based on\n  the general decoding problem","volume":"48","author":"Thomas Johansson","year":"2002","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref34:IMA:AlJabri01","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45325-3_1","article-title":"A Statistical Decoding Algorithm for General Linear Block\n  Codes","volume":"2260","author":"A. Kh. Al Jabri","year":"2001"},{"key":"ref35:SAC:Schrottenloher21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-030-99277-4_15","article-title":"Improved Quantum Algorithms for the k-XOR Problem","volume":"13203","author":"Andr\u00e9 Schrottenloher","year":"2022"},{"key":"ref36:SODA:MinSin09","first-page":"586","article-title":"The extended k-tree algorithm","author":"Lorenz Minder","year":"2009"},{"key":"ref37:AC:BBSS20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/978-3-030-64834-3_22","article-title":"Improved Classical and Quantum Algorithms for Subset-Sum","volume":"12492","author":"Xavier Bonnetain","year":"2020"},{"key":"ref38:NIST","volume-title":"PQC Standardization Process: Announcing Four Candidates to\n  be Standardized, Plus Fourth Round Candidates","author":"NIST","year":"2022"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:41:30Z","timestamp":1767915690000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/4\/5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":38,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2026,1,8]]}},"URL":"https:\/\/doi.org\/10.62056\/ae89ksuc2","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-07-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-3-67"}}