A Practical Neighborhood Search Attack on Oracle MLWE
IACR Communications in Cryptology · 04.05.2026 · 3 (1)
DOI: 10.62056/ab0l5w4e- ↗Kurz gefasst
Fachartikel in der Zeitschrift IACR Communications in Cryptology, online erschienen am 04.05.2026. Verfasst von Hongxiao Wang und 4 weiteren Autor:innen. Die Arbeit nennt 20 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Wang, H., Esgin, M., Steinfeld, R., Saarinen, M., & Yiu, S. (2026). A Practical Neighborhood Search Attack on Oracle MLWE. IACR Communications in Cryptology, 3(1). https://doi.org/10.62056/ab0l5w4e-
Vancouver
Wang H, Esgin M, Steinfeld R, Saarinen M, Yiu S. A Practical Neighborhood Search Attack on Oracle MLWE. IACR Communications in Cryptology. 2026;3(1). doi:10.62056/ab0l5w4e-
BibTeX
@article{Wang2026,
author = {Wang, Hongxiao and Esgin, Muhammed and Steinfeld, Ron and Saarinen, Markku-Juhani and Yiu, Siu-Ming},
title = {A Practical Neighborhood Search Attack on Oracle MLWE},
journal = {IACR Communications in Cryptology},
year = {2026},
volume = {3},
number = {1},
doi = {10.62056/ab0l5w4e-}
}
EUVIMED