Common Notation

Oracle MLWE

Propose Edit

Updated:

Oracle MLWE was introduced by Liu, Sotiraki, Tromer, and Wang in 2025 [1]. The assumption is inspired by the static Diffie-Hellman with oracle problem [2]. It adds a masked hint and the output of a random oracle to the challenge samples, where the input to the random oracle depends on the previously mentioned mask.

Definition

Oracle MLWE\(_{n,N,q,\mathcal{D},\chi_\sigma,p,w_1,w_2,w_\adv}\)

Let \(\mathcal{R} = \ZZ[X]/(X^N + 1)\) be a power-of-two cyclotomic ring and \(H: \mathcal{R}_p \rightarrow \mathcal{K}\) be a random oracle. Let \(\mathcal{D}\) and \(\chi_\sigma\) denote distributions over \(\mathcal{R}_q\). Sample \(\mat{A}_1\sample \mathcal{R}_q^{w_1 \times n}\), \(\mat{A}_2\sample \mathcal{R}_q^{w_2 \times n}\), \(\mat{A}_\adv\gets \adv(\mat{A}_1, \mat{A}_2) \in \mathcal{R}_q^{w_\adv \times n}\), \(\vec{s} \sample \mathcal{D}^n\), \(\vec{e}_1 \sample \chi_\sigma^{\omega_1}\), \(\vec{e}_2 \sample \chi_\sigma^{\omega_2}\), \(\vec{e}_\adv \sample \chi_\sigma^{\omega_\adv}\), \(\vec{r}_2 \sample \mathcal{R}_q^{w_2}\), \(\vec{u}_2 \sample \mathcal{R}_q^{w_2}\), and \(\vec{u}_\adv \sample \mathcal{R}_q^{w_\adv}\). An adversary \(\adv\) is asked to distinguish between the distribution

\[\begin{align*} &\left(\mat{A}_2, {\color{blue}\mat{A}_2\vec{s} + \vec{e}_2 + \vec{u}_2}, (H(\floor{p \cdot \vec{u}_{2,i} / q}))_{i \in [w_2]}\right) \\ &(\mat{A}_1, \mat{A}_1\vec{s} + \vec{e}_1) \\ &\left(\mat{A}_\adv, \mat{A}_\adv\vec{s} + \vec{e}_\adv + \vec{u}_\adv, (H(\floor{p \cdot \vec{u}_{\adv,i} / q}))_{i \in [w_\adv]}\right) \end{align*}\]

and the distribution

\[\begin{align*} &\left(\mat{A}_2, {\color{blue}\vec{r}_2}, (H(\floor{p \cdot \vec{u}_{2,i} / q}))_{i \in [w_2]}\right) \\ &(\mat{A}_1, \mat{A}_1\vec{s} + \vec{e}_1) \\ &\left(\mat{A}_\adv, \mat{A}_\adv\vec{s} + \vec{e}_\adv + \vec{u}_\adv, (H(\floor{p \cdot \vec{u}_{\adv,i} / q}))_{i \in [w_\adv]}\right) \end{align*}.\]

Hardness

In Section 7 of [1], the authors provide two parameter regimes in which Oracle MLWE is broken. Their Lemma 7.2 states that Oracle MLWE\(_{n,N,q,\mathcal{D},\chi,p}\) is at least as hard as (entropic) Module-LWE\(_{n,N,q,\mathcal{D},\chi_\sigma}\) if \(\chi_\sigma\) is a Gaussian distribution with \(1/\sigma^N = \negl{\lambda}\) and \(p=q\). Then, they define sets of parameters used in their constructions, which are not covered by the reduction. This set of parameters was broken by Wang, Esgin, Steinfeld, Saarinen, and Yiu in [3] via an attack that they call neighborhood search attack. They propose new sets of parameters, which omit this attack.

Constructions built from Oracle MLWE

  • Multi-Message Multi-Recipient Public-Key Encryption [1]

References

  • [1]Zeyu Liu, Katerina Sotiraki, Eran Tromer, and Yunhao Wang. 2025. Lattice-Based Multi-message Multi-recipient KEM/PKE with Malicious Security. In Advances in Cryptology - ASIACRYPT 2025 - 31st International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, VIC, Australia, December 8-12, 2025, Proceedings, Part III (Lecture Notes in Computer Science), 2025. Springer, 428–460. Retrieved from https://ia.cr/2025/1655
  • [2]Daniel R. L. Brown and Robert P. Gallant. 2004. The Static Diffie-Hellman Problem. IACR Cryptol. ePrint Arch. 2004, (2004), 306. Retrieved from http://ia.cr/2004/306
  • [3]Hongxiao Wang, Muhammed F. Esgin, Ron Steinfeld, Markku-Juhani O. Saarinen, and Siu-Ming Yiu. 2026. A Practical Neighborhood Search Attack on Oracle MLWE. IACR Commun. Cryptol. 3, 1 (2026), 14. Retrieved from https://ia.cr/2026/177