{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:15:17Z","timestamp":1778040917655,"version":"3.51.4"},"reference-count":54,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T00:00:00Z","timestamp":1769472000000},"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":[[2026,4,23]]},"abstract":"<jats:p>Quantum security most commonly encompasses only offline passive quantum attacks, where a quantum computer is used by an adversary to solve some computationally hard problem, e.g. factoring or discrete logarithm.     However, we are witnessing major efforts for the development and deployment of quantum communication networks, and in this environment, cryptographic protocols may also be implemented in quantum devices.     In this new setting, a wider range of online active attacks may become possible, for example against targets that may, either deliberately or inadvertently, run a cryptographic scheme in superposition.     In this work, we demonstrate that authentication protocols whose security is based on the difficulty of learning linear functions subject to errors may be vulnerable to attacks where adversaries can make queries in superposition \u2014 that is, under the so-called \u201cQ2\u201d adversarial model.     We do so by describing superposition attacks against a family of symmetric-key authentication protocols based on the LPN problem, a post-quantum cryptography assumption. Our attacks against the HB+ and HB# protocols, both of which have classical proofs of security against active attacks, are based on the Bernstein-Vazirani algorithm, and can efficiently recover the secret key.     Despite being conceptually simple, we suggest that our attack techniques might be extended and adapted to also allow for superposition attacks against some modern lattice-based identification and post-quantum signature schemes.<\/jats:p>","DOI":"10.62056\/abhey7n4e","type":"journal-article","created":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T18:09:08Z","timestamp":1777918148000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Superposition Attacks Against LPN-Based Authentication Protocols"],"prefix":"10.62056","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5761-8694","authenticated-orcid":false,"given":"Carlos","family":"Cid","sequence":"first","affiliation":[{"name":"Okinawa Institute of Science and Technology Graduate University","place":["Japan"]},{"name":"Simula UiB","place":["Norway"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2023-2768","authenticated-orcid":false,"given":"David","family":"Elkouss","sequence":"additional","affiliation":[{"name":"Okinawa Institute of Science and Technology Graduate University","place":["Japan"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6904-6152","authenticated-orcid":false,"given":"Manuel","family":"Goul\u00e3o","sequence":"additional","affiliation":[{"name":"INESC-ID, Instituto Superior T\u00e9cnico, Universidade de Lisboa","place":["Portugal"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"key":"ref1:shor-algorithm","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1109\/SFCS.1994.365700","article-title":"Algorithms for quantum computation: discrete logarithms and\n  factoring","author":"P.W. Shor","year":"1994"},{"key":"ref2:NIST:PQC","volume-title":"Post-Quantum Cryptography Standardization webpage","author":"National\u00a0Institute\u00a0of\u00a0Standards\u00a0and\u00a0Technology\u00a0(NIST)"},{"key":"ref3:DCC:BS15","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s10623-015-0157-4","article-title":"Quantum cryptography beyond quantum key distribution","volume":"78","author":"Anne Broadbent","year":"2016","journal-title":"Designs, Codes and Cryptography","ISSN":"https:\/\/id.crossref.org\/issn\/1573-7586","issn-type":"electronic"},{"key":"ref4:NC10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667","volume-title":"Quantum Computation and Quantum Information","author":"Michael A. Nielsen","year":"2010"},{"key":"ref5:CRYPTO:BFKL93","isbn-type":"print","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/3-540-48329-2_24","article-title":"Cryptographic Primitives Based on Hard Learning Problems","author":"Avrim Blum","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540483298"},{"key":"ref6:LPN-survey","isbn-type":"print","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-642-27660-6_9","article-title":"Cryptography from Learning Parity with Noise","author":"Krzysztof Pietrzak","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642276606"},{"key":"ref7:JACM:BKW03","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","article-title":"Noise-tolerant learning, the parity problem, and the\n  statistical query model","volume":"50","author":"Avrim Blum","year":"2003","journal-title":"Journal of the ACM"},{"key":"ref8:SCN:LF06","isbn-type":"print","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/11832072_24","article-title":"An Improved LPN Algorithm","author":"\u00c9ric Levieil","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540380818"},{"key":"ref9:INDO:FMI06","isbn-type":"print","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/11941378_5","article-title":"An Algorithm for Solving the LPN Problem and Its\n  Application to Security Evaluation of the HB Protocols for RFID\n  Authentication","author":"Marc P. C. Fossorier","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540497691"},{"key":"ref10:ASIACR:GJL14","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-662-45611-8_1","article-title":"Solving LPN Using Covering Codes","author":"Qian Guo","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/9783662456118"},{"key":"ref11:CRYPTO:EKM17","isbn-type":"print","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/978-3-319-63715-0_17","article-title":"LPN Decoded","author":"Andre Esser","year":"2017","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319637150"},{"key":"ref12:PQCrypto:KT17","isbn-type":"print","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","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319598796"},{"key":"ref13:ChaillouxT24","series-title":"LIPIcs","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2024.6","article-title":"The Quantum Decoding Problem","volume":"310","author":"Andr\u00e9 Chailloux","year":"2024"},{"key":"ref14:schmidhuber2024","doi-asserted-by":"publisher","first-page":"21077","DOI":"10.1103\/PhysRevX.15.021077","article-title":"Quartic Quantum Speedups for Planted Inference","volume":"15","author":"Alexander Schmidhuber","year":"2025","journal-title":"Phys. Rev. X"},{"key":"ref15:FOCS:A03","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":"ref16:FSE:HKL12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/978-3-642-34047-5_20","article-title":"Lapin: An Efficient Authentication Protocol Based on\n  Ring-LPN","author":"Stefan Heyse","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642340475"},{"key":"ref17:hb","isbn-type":"print","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-45682-1_4","article-title":"Secure Human Identification Protocols","author":"Nicholas J. Hopper","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540456827"},{"key":"ref18:hb-plus","isbn-type":"print","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/11535218_18","article-title":"Authenticating Pervasive Devices with Human Protocols","author":"Ari Juels","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540318705"},{"key":"ref19:hb-plus-attack","doi-asserted-by":"publisher","first-page":"1169","DOI":"10.1049\/el:20052622","article-title":"An Active Attack Against HB+ - A Provably Secure\n  Lightweight Authentication Protocol","volume":"41","author":"Henri Gilbert","year":"2005","journal-title":"IEE Electronics Letters"},{"key":"ref20:JC:KSS10","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00145-010-9061-2","article-title":"Parallel and Concurrent Security of the HB and\n  HB+ Protocols","volume":"23","author":"Jonathan Katz","year":"2010","journal-title":"Journal of Cryptology"},{"key":"ref21:hb-sharp","isbn-type":"print","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-540-78967-3_21","article-title":"HB#: Increasing the Security and Efficiency of HB+","author":"Henri Gilbert","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540789673"},{"key":"ref22:AC:OOV08","isbn-type":"print","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-89255-7_8","article-title":"On the Security of HB# against a Man-in-the-Middle\n  Attack","author":"Khaled Ouafi","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540892557"},{"key":"ref23:CC:BTV16","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s12095-015-0149-2","article-title":"On solving LPN using BKW and variants","volume":"8","author":"Sonia Bogos","year":"2016","journal-title":"Cryptography and Communications","ISSN":"https:\/\/id.crossref.org\/issn\/1936-2455","issn-type":"electronic"},{"key":"ref24:SecPerU:BCD06","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1109\/SECPERU.2006.10","article-title":"HB\\({}^{\\mbox{++}}\\): a Lightweight Authentication Protocol\n  Secure against Some Attacks","author":"Julien Bringer","year":"2006"},{"key":"ref25:CN:MP07","doi-asserted-by":"publisher","first-page":"2262","DOI":"10.1016\/J.COMNET.2007.01.011","article-title":"HB-MP: A further step in the HB-family of lightweight\n  authentication protocols","volume":"51","author":"Jorge Munilla","year":"2007","journal-title":"Comput. Networks"},{"key":"ref26:hb-star","first-page":"23","article-title":"Securing HB+ against GRS man-in-the-middle attack","author":"Dang Nguyen Duc","year":"2007"},{"key":"ref27:FC:GRS08","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-540-85230-8_12","article-title":"Good Variants of HB\\({}^{\\mbox{+}}\\) Are Hard to Find","volume":"5143","author":"Henri Gilbert","year":"2008"},{"key":"ref28:ITIT:BC08","doi-asserted-by":"publisher","first-page":"4339","DOI":"10.1109\/TIT.2008.928290","article-title":"Trusted-HB: A Low-Cost Version of HB+ Secure Against\n  Man-in-the-Middle Attacks","volume":"54","author":"Julien Bringer","year":"2008","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref29:untrusted-hb","volume-title":"Un-Trusted-HB: Security Vulnerabilities of\n  Trusted-HB","author":"Dmitry Frumkin","year":"2009"},{"key":"ref30:SIT:KM10","doi-asserted-by":"publisher","first-page":"2682","DOI":"10.1109\/ISIT.2010.5513654","article-title":"Quantum distinguisher between the 3-round Feistel cipher\n  and the random permutation","author":"Hidenori Kuwakado","year":"2010"},{"key":"ref31:SIT:KM12","first-page":"312","article-title":"Security on the quantum-type Even-Mansour cipher","author":"Hidenori Kuwakado","year":"2012"},{"key":"ref32:FOCS:S94","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1109\/SFCS.1994.365701","article-title":"On the power of quantum computation","author":"D.R. Simon","year":"1994"},{"key":"ref33:ITS:DFNS14","isbn-type":"print","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-319-04268-8_9","article-title":"Superposition Attacks on Cryptographic Protocols","author":"Ivan Damg\u00e5rd","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319042688"},{"key":"ref34:EC:BZ13","isbn-type":"print","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1007\/978-3-642-38348-9_35","article-title":"Quantum-Secure Message Authentication Codes","author":"Dan Boneh","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642383489"},{"key":"ref35:FOCS:Z12","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1109\/FOCS.2012.37","article-title":"How to Construct Quantum Random Functions","author":"Mark Zhandry","year":"2012"},{"key":"ref36:TOSC:KLLN16","doi-asserted-by":"publisher","first-page":"71","DOI":"10.13154\/tosc.v2016.i1.71-94","article-title":"Quantum Differential and Linear Cryptanalysis","volume":"2016","author":"Marc Kaplan","year":"2016","journal-title":"IACR Transactions on Symmetric Cryptology"},{"key":"ref37:C:BZ13","isbn-type":"print","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-642-40084-1_21","article-title":"Secure Signatures and Chosen Ciphertext Security in a\n  Quantum Computing World","author":"Dan Boneh","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642400841"},{"key":"ref38:C:GHS16","isbn-type":"print","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/978-3-662-53015-3_3","article-title":"Semantic Security and Indistinguishability in the Quantum\n  World","author":"Tommaso Gagliardoni","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9783662530153"},{"key":"ref39:JCSS:GM84","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","article-title":"Probabilistic encryption","volume":"28","author":"Shafi Goldwasser","year":"1984","journal-title":"Journal of Computer and System Sciences","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"electronic"},{"key":"ref40:ITS:ABF+:16","isbn-type":"print","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-319-49175-2_3","article-title":"Computational Security of Quantum Encryption","author":"Gorjan Alagic","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319491752"},{"key":"ref41:bv","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","article-title":"Quantum Complexity Theory","volume":"26","author":"Ethan Bernstein","year":"1997","journal-title":"SIAM Journal on Computing"},{"key":"ref42:DCC:XY19","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1007\/s10623-018-0510-5","article-title":"Using Bernstein-Vazirani algorithm to attack block\n  ciphers","volume":"87","author":"Huiqin Xie","year":"2019","journal-title":"Designs, Codes and Cryptography","ISSN":"https:\/\/id.crossref.org\/issn\/1573-7586","issn-type":"electronic"},{"key":"ref43:QIPj:XY20","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/s11128-020-02741-2","article-title":"A quantum related-key attack based on the\n  Bernstein-Vazirani algorithm","volume":"19","author":"Huiqin Xie","year":"2020","journal-title":"Quantum Information Processing","ISSN":"https:\/\/id.crossref.org\/issn\/1573-1332","issn-type":"electronic"},{"key":"ref44:QIPj:ZY21","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/s11128-021-03256-0","article-title":"Quantum key-recovery attack on Feistel constructions:\n  Bernstein\u2013Vazirani meet Grover algorithm","volume":"20","author":"Bao-Min Zhou","year":"2021","journal-title":"Quantum Information Processing","ISSN":"https:\/\/id.crossref.org\/issn\/1573-1332","issn-type":"electronic"},{"key":"ref45:AC:BLNS21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/978-3-030-92062-3_15","article-title":"Quantum Linearization Attacks","author":"Xavier Bonnetain","year":"2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030920623"},{"key":"ref46:PRA:GKZ19","doi-asserted-by":"publisher","first-page":"32314","DOI":"10.1103\/PhysRevA.99.032314","article-title":"Learning-with-errors problem is easy with quantum\n  samples","volume":"99","author":"Alex B. Grilo","year":"2019","journal-title":"Phys. Rev. A"},{"key":"ref47:PRA:CSS15","doi-asserted-by":"publisher","first-page":"12327","DOI":"10.1103\/PhysRevA.92.012327","article-title":"Quantum learning robust against noise","volume":"92","author":"Andrew W. Cross","year":"2015","journal-title":"Phys. Rev. A"},{"key":"ref48:reaction-attack","isbn-type":"print","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-540-47942-0_2","article-title":"Reaction Attacks against Several Public-Key\n  Cryptosystems","author":"Chris Hall","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540479420"},{"key":"ref49:pompili2021realization","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1126\/science.abg1919","article-title":"Realization of a multinode quantum network of remote\n  solid-state qubits","volume":"372","author":"Matteo Pompili","year":"2021","journal-title":"Science"},{"key":"ref50:preskill2018quantum","doi-asserted-by":"publisher","first-page":"79","DOI":"10.22331\/q-2018-08-06-79","article-title":"Quantum computing in the NISQ era and beyond","volume":"2","author":"John Preskill","year":"2018","journal-title":"Quantum"},{"key":"ref51:damgaard2007secure","isbn-type":"print","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/978-3-540-74143-5_19","article-title":"Secure Identification and QKD in the\n  Bounded-Quantum-Storage Model","author":"Ivan B. Damg\u00e5rd","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540741435"},{"key":"ref52:schaffner2010simple","doi-asserted-by":"publisher","first-page":"32308","DOI":"10.1103\/PhysRevA.82.032308","article-title":"Simple protocols for oblivious transfer and secure\n  identification in the noisy-quantum-storage model","volume":"82","author":"Christian Schaffner","year":"2010","journal-title":"Phys. Rev. A"},{"key":"ref53:hlp-joc-2017","doi-asserted-by":"publisher","first-page":"1238","DOI":"10.1007\/s00145-016-9247-3","article-title":"Efficient Authentication from Hard Learning Problems","volume":"30","author":"Eike Kiltz","year":"2017","journal-title":"Journal of Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/1432-1378","issn-type":"electronic"},{"key":"ref54:CRYPTO:BCG21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-030-84259-8_17","article-title":"Low-Complexity Weak Pseudorandom Functions in AC0[MOD2]","author":"Elette Boyle","year":"2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030842598"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:02:46Z","timestamp":1778040166000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/3\/1\/17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":54,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,5,4]]}},"URL":"https:\/\/doi.org\/10.62056\/abhey7n4e","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,4]]},"assertion":[{"value":"2026-01-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc3-1-39"}}