{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T01:07:09Z","timestamp":1759799229337,"version":"build-2065373602"},"reference-count":23,"publisher":"International Association for Cryptologic Research","issue":"3","license":[{"start":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T00:00:00Z","timestamp":1751932800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Forschung, Technologie und Raumfahrt","doi-asserted-by":"publisher","award":["16KIS1837"],"award-info":[{"award-number":["16KIS1837"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Forschung, Technologie und Raumfahrt","doi-asserted-by":"publisher","award":["16KISR010K"],"award-info":[{"award-number":["16KISR010K"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,9,2]]},"abstract":"<jats:p>Code-based cryptography, originally proposed nearly 50 years ago, has been highly successful in the NIST standardization process for post-quantum key encapsulation mechanisms.  With HQC and BIKE, two of the considered candidates are based on the hardness of quasi-cyclic codes. One important attack first presented by Guo et al. at ASIACRYPT 2016 that targets moderately dense codes is the distance spectrum recovery attack. The attack makes use of the correlation between the error patterns causing a decryption failure and the sparse private key. However, for random keys, decoding failures are highly unlikely and the attack thus only succeeds with negligible probability. Another line of cryptanalysis on quasi-cyclic code-based cryptosystems has focused on weak keys with higher DFR, which invalidate the provable security guarantees. However, so far the distance spectrum of such weak keys have never been analyzed, leaving a gap in the cryptanalysis research of modern code-based cryptosystems. In this work, we show that Type I weak keys feature a new distance spectrum not analyzed before that cannot be attacked with known key recovery techniques proposed by  Guo et al. Instead, we introduce a new key recovery algorithm that, considering the reaction attacker setting, exceeds the state-of-the-art recovery methods by exploiting the distance spectrum of the new weak keys with high probability. When considering a natural side-channel occurring in real-world implementations of the decoding phase, our attack can be enhanced even further. <\/jats:p>","DOI":"10.62056\/a0qj5wol7","type":"journal-article","created":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T18:49:52Z","timestamp":1759776592000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Weak Key Recovery for QC-MDPC Codes like BIKE"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-2334-1265","authenticated-orcid":false,"given":"Tim","family":"Gellersen","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00t3r8h32","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Luebeck","place":["Ratzeburger Allee 160, L\u00fcbeck, Schleswig-Holstein, 23562, Germany"],"department":["Institute for IT Security"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0061-0415","authenticated-orcid":false,"given":"Till","family":"Eifert","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00t3r8h32","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Luebeck","place":["Ratzeburger Allee 160, L\u00fcbeck, Schleswig-Holstein, 23562, Germany"],"department":["Institute for IT Security"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4177-8081","authenticated-orcid":false,"given":"Sebastian","family":"Berndt","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/032xqbj11","id-type":"ROR","asserted-by":"publisher"}],"name":"Technische Hochschule L\u00fcbeck","place":["M\u00f6nkhofer Weg 239, L\u00fcbeck, Schleswig-Holstein, 23562, Germany"],"department":["Fachbereich Elektrotechnik und Informatik"]},{"id":[{"id":"https:\/\/ror.org\/00t3r8h32","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Luebeck","place":["Ratzeburger Allee 160, L\u00fcbeck, Schleswig-Holstein, 23562, Germany"],"department":["Institute for IT Security"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1116-6973","authenticated-orcid":false,"given":"Thomas","family":"Eisenbarth","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00t3r8h32","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Luebeck","place":["Ratzeburger Allee 160, L\u00fcbeck, Schleswig-Holstein, 23562, Germany"],"department":["Institute for IT Security"]}]}],"member":"48349","published-online":{"date-parts":[[2025,10,6]]},"reference":[{"key":"ref1:McEliece78","first-page":"114","volume-title":"A public-key cryptosystem based on algebraic coding theory","author":"Robert J. McEliece","year":"1978"},{"key":"ref2:AC:GuoJohSta16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/978-3-662-53887-6_29","article-title":"A Key Recovery Attack on MDPC with CCA Security Using\n  Decoding Errors","volume":"10031","author":"Qian Guo","year":"2016"},{"key":"ref3:sendrier:hal-01095935","article-title":"QC-MDPC-McEliece: A public-key code-based encryption scheme\n  based on quasi-cyclic moderate density parity check codes","author":"Nicolas Sendrier","year":"2014"},{"key":"ref4:DBLP:journals\/tecs\/MaurichOG15","doi-asserted-by":"publisher","DOI":"10.1145\/2700102","article-title":"Implementing QC-MDPC McEliece Encryption","volume":"14","author":"Ingo von Maurich","year":"2015","journal-title":"ACM Trans. Embed. Comput. Syst."},{"key":"ref5:DBLP:journals\/icl\/MoufekGG17","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1109\/LCOMM.2016.2640271","article-title":"A New Variant of the McEliece Cryptosystem Based on QC-LDPC\n  and QC-MDPC Codes","volume":"21","author":"Hamza Moufek","year":"2017","journal-title":"IEEE Communications Letters"},{"key":"ref6:DBLP:journals\/telsys\/LiuTWZM22","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s11235-022-00881-7","article-title":"An improved McEliece cryptosystem based on QC-MDPC code\n  with compact key size","volume":"80","author":"Jie Liu","year":"2022","journal-title":"Telecommun. Syst."},{"key":"ref7:PQCRYPTO:ELPS18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-319-79063-3_3","article-title":"QC-MDPC: A Timing Attack and a CCA2 KEM","author":"Edward Eaton","year":"2018"},{"key":"ref8:DBLP:journals\/tit\/GuoJW19","doi-asserted-by":"publisher","first-page":"1845","DOI":"10.1109\/TIT.2018.2877458","article-title":"A Key Recovery Reaction Attack on QC-MDPC","volume":"65","author":"Qian Guo","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref9:druguekos19a","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-030-54074-6_4","article-title":"On Constant-Time QC-MDPC Decoders with Negligible Failure\n  Rate","volume":"12087","author":"Nir Drucker","year":"2020"},{"key":"ref10:C:WanWanWan23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/978-3-031-38548-3_3","article-title":"Exploring Decryption Failures of BIKE: New Class of Weak\n  Keys and Key Recovery Attacks","volume":"14083","author":"Tianrui Wang","year":"2023"},{"key":"ref11:TCHES:NilJohWag18","doi-asserted-by":"publisher","first-page":"238","DOI":"10.13154\/tches.v2019.i1.238-258","article-title":"Error Amplification in Code-based Cryptography","volume":"2019","author":"Alexander Nilsson","year":"2018","journal-title":"IACR TCHES","ISSN":"https:\/\/id.crossref.org\/issn\/2569-2925","issn-type":"electronic"},{"key":"ref12:EPRINT:Vasseur21","volume-title":"QC-MDPC codes DFR and the IND-CCA security of\n  BIKE","author":"Valentin Vasseur","year":"2021"},{"key":"ref13:NISTPQC-R4:BIKE22","volume-title":"BIKE","author":"Nicolas Aragon","year":"2022"},{"key":"ref14:dgkp20","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1080\/23799927.2021.1930176","article-title":"On the applicability of the Fujisaki-Okamoto transformation\n  to the BIKE KEM","volume":"6","author":"Nir Drucker","year":"2021","journal-title":"Int. J. Comput. Math. Comput. Syst. Theory"},{"key":"ref15:druguekos19b","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-030-44223-1_3","article-title":"QC-MDPC Decoders with Several Shades of Gray","volume":"12100","author":"Nir Drucker","year":"2020"},{"key":"ref16:Reaction_Attacks","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-540-47942-0_2","article-title":"Reaction Attacks against several Public-Key Cryptosystems","volume":"1726","author":"Chris Hall","year":"1999"},{"key":"ref17: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":"ref18:EC:EssMayZwe22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/978-3-031-07082-2_16","article-title":"McEliece Needs a Break - Solving McEliece-1284 and\n  Quasi-Cyclic-2918 with Modern ISD","volume":"13277","author":"Andre Esser","year":"2022"},{"key":"ref19: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":"ref20:Drucker21-binding","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-030-78086-9_21","article-title":"Binding BIKE Errors to a Key Pair","volume":"12716","author":"Nir Drucker","year":"2021"},{"key":"ref21:DBLP:journals\/corr\/abs-2404-19756","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2404.19756","article-title":"KAN: Kolmogorov-Arnold Networks","volume":"abs\/2404.19756","author":"Ziming Liu","year":"2024","journal-title":"CoRR"},{"key":"ref22:EPRINT:Sendrier21","volume-title":"Secure Sampling of Constant-Weight Words \u2013 Application to\n  BIKE","author":"Nicolas Sendrier","year":"2021"},{"key":"ref23:PQM4","volume-title":"PQM4: Post-quantum crypto library for the ARM\n  Cortex-M4","author":"Matthias J. Kannwischer"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T20:23:36Z","timestamp":1759782216000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/3\/37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,6]]},"references-count":23,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2025,10,6]]}},"URL":"https:\/\/doi.org\/10.62056\/a0qj5wol7","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,6]]},"assertion":[{"value":"2025-07-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-3-84"}}