{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:15:19Z","timestamp":1778040919335,"version":"3.51.4"},"reference-count":20,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T00:00:00Z","timestamp":1769904000000},"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,11]]},"abstract":"<jats:p>The Oracle Module Learning with Errors (Oracle MLWE) assumption, recently introduced by Liu et al. (Asiacrypt 2025), strengthens standard (Module) LWE by allowing masked linear leakages of the secret under an adversarially-chosen challenge matrix. This feature is used for the construction of new efficient primitives such as Oracle MLWE-based multi-message multi-recipient KEM\/PKE (mmKEM\/mmPKE) without requiring public-key well-formedness proofs. In this work, we present a practical cryptanalytic attack on Oracle MLWE, which we call a neighborhood search attack. Our attack exploits adversarially-chosen matrices (or maliciously generated public keys), together with the small ring dimension and small-norm secrets required for correctness, showing that rounding errors can be recovered via a bounded search, leading to recovery of the underlying MLWE secret. To demonstrate the effectiveness of our attack, we apply it against the Oracle MLWE-based mmKEM of Liu et al. (Asiacrypt 2025), proving that its recommended parameter sets do not achieve the claimed security level. We further implement the attack in SageMath and report concrete timings, showing that an adversary controlling a moderate number of recipients can recover other recipients' encapsulated keys within a few seconds on a standard PC under the proposed parameters, which were claimed to achieve a 128-bit security level.<\/jats:p>","DOI":"10.62056\/ab0l5w4e-","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":["A Practical Neighborhood Search Attack on Oracle MLWE"],"prefix":"10.62056","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-2983-7239","authenticated-orcid":false,"given":"Hongxiao","family":"Wang","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02zhqgq86","id-type":"ROR","asserted-by":"publisher"}],"name":"The University of Hong Kong","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1650-3748","authenticated-orcid":false,"given":"Muhammed","family":"Esgin","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02bfwt286","id-type":"ROR","asserted-by":"publisher"}],"name":"Monash University","place":["Australia"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1745-4183","authenticated-orcid":false,"given":"Ron","family":"Steinfeld","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02bfwt286","id-type":"ROR","asserted-by":"publisher"}],"name":"Monash University","place":["Australia"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2555-235X","authenticated-orcid":false,"given":"Markku-Juhani","family":"Saarinen","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/033003e23","id-type":"ROR","asserted-by":"publisher"}],"name":"Tampere University","place":["Finland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3975-8500","authenticated-orcid":false,"given":"Siu-Ming","family":"Yiu","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02zhqgq86","id-type":"ROR","asserted-by":"publisher"}],"name":"The University of Hong Kong","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"key":"ref1:agrawal2022practical","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/3548606.3560650","article-title":"Practical, round-optimal lattice-based blind signatures","author":"Shweta Agrawal","year":"2022"},{"key":"ref2:wee2023succinct","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-031-30620-4_13","article-title":"Succinct vector, polynomial, and functional commitments from\n  lattices","author":"Hoeteck Wee","year":"2023"},{"key":"ref3:kim2023toward","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/978-3-031-38554-4_18","article-title":"Toward practical lattice-based proof of knowledge from\n  hint-MLWE","author":"Duhyeong Kim","year":"2023"},{"key":"ref4:dottling2023efficient","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/978-3-031-30620-4_14","article-title":"Efficient laconic cryptography from learning with errors","author":"Nico D\u00f6ttling","year":"2023"},{"key":"ref5:espitau2024flood","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/978-3-031-68394-7_14","article-title":"Flood and submerse: Distributed key generation and robust\n  threshold signature from lattices","author":"Thomas Espitau","year":"2024"},{"key":"ref6:esgin2024leopard","article-title":"LeOPaRd: Towards practical post-quantum oblivious PRFs via\n  interactive lattice problems","author":"Muhammed F Esgin","year":"2024","journal-title":"Cryptology ePrint Archive"},{"key":"ref7:lai2025leaky","doi-asserted-by":"publisher","first-page":"1","DOI":"10.62056\/ah89ksuc2","article-title":"Leaky LWE: learning with errors with semi-adaptive\n  secret-and error-leakage","author":"Russell Lai","year":"2025","journal-title":"IACR Communications in Cryptology"},{"key":"ref8:boudgoust2025hardness","article-title":"Hardness of M-LWE with General Distributions and\n  Applications to Leaky Variants","author":"Katharina Boudgoust","year":"2026"},{"key":"ref9:mmCipher","article-title":"mmCipher: Batching Post-Quantum Public Key Encryption Made\n  Bandwidth-Optimal","author":"Hongxiao Wang","year":"2026"},{"key":"ref10:liu2025lattice","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/978-981-95-5099-9_14","article-title":"Lattice-Based Multi-message Multi-recipient KEM\/PKE with\n  Malicious Security","author":"Zeyu Liu","year":"2025"},{"key":"ref11:alperin2012circular","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-30057-8_20","article-title":"Circular and KDM security for identity-based encryption","author":"Jacob Alperin-Sheriff","year":"2012"},{"key":"ref12:agrawal2016fully","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-662-53015-3_12","article-title":"Fully secure functional encryption for inner products, from\n  standard assumptions","author":"Shweta Agrawal","year":"2016"},{"key":"ref13:abou2023efficient","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/978-981-99-8733-7_11","article-title":"Efficient updatable public-key encryption from lattices","author":"Calvin Abou Haidar","year":"2023"},{"key":"ref14:wang2024ring","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-031-57722-2_9","article-title":"Ring\/Module Learning with Errors Under Linear\n  Leakage\u2013Hardness and Applications","author":"Zhedong Wang","year":"2024"},{"key":"ref15:pinto2014multi","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/2590296.2590329","article-title":"Multi-recipient encryption, revisited","author":"Alexandre Pinto","year":"2014"},{"key":"ref16:kurosawa2002multi","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/3-540-45664-3_4","article-title":"Multi-recipient Public-Key Encryption with Shortened\n  Ciphertext","author":"Kaoru Kurosawa","year":"2002"},{"key":"ref17:bellare2003multi","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-36288-6_7","article-title":"Multi-recipient encryption schemes: Security notions and\n  randomness re-use","author":"Mihir Bellare","year":"2003"},{"key":"ref18:bellare2007multirecipient","doi-asserted-by":"publisher","first-page":"3927","DOI":"10.1109\/TIT.2007.907471","article-title":"Multirecipient encryption schemes: How to save on bandwidth\n  and computation without sacrificing security","volume":"53","author":"Mihir Bellare","year":"2007","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref19:katsumata2020scalable","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-030-64837-4_10","article-title":"Scalable ciphertext compression techniques for post-quantum\n  KEMs and their applications","author":"Shuichi Katsumata","year":"2020"},{"key":"ref20:alwen2023post","doi-asserted-by":"publisher","first-page":"1108","DOI":"10.1145\/3576915.3623185","article-title":"Post-quantum multi-recipient public key encryption","author":"Jo\u00ebl Alwen","year":"2023"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:02:25Z","timestamp":1778040145000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/3\/1\/14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":20,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,5,4]]}},"URL":"https:\/\/doi.org\/10.62056\/ab0l5w4e-","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-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc3-1-29"}}