Common Notation

LWE with Error-Leakage implied

Propose Edit

Updated:

The LWE with Error-Leakage or Error-Leakage LWE (elLWE) assumption was introduced by Döttling, Kolonelos, Lai, Lin, Malavolta, and Rahimi in 2023 [1]. It enables some partial leakage of the error vector in LWE in a pre-defined form. They utilise this assumption to construct Laconic Encryption and Registration-Based Encryption schemes.

Definition

elLWE\(_{\mathcal{R},n,m,k,q,\chi,\bar{\chi},\mathcal{L}}\)

Let \(\mathcal{L}\) be an efficiently decidable set and \(\adv = (\adv_0, \adv_1)\) be a two-stage adversary. Given a uniformly chosen matrix \(\mat{A} \in \mathcal{R}_q^{n \times m}\), the adversary \(\adv_0\) outputs a matrix \(\mat{Z} \in \mathcal{L}\). For \(\vec{s} \sample \mathcal{R}_q^n\), \(\vec{e} \sample \chi^m\), \(\bar{\vec{e}} \sample \bar{\chi}^k\), \(\vec{x} \sample \mathcal{R}_q^m\), the adversary \(\adv_1\) is asked to distinguish the following distribution

\[(\mat{A}, \vec{y}^T = \vec{s}^T \cdot \mat{A} + \vec{e}^T, \vec{l}^T = \vec{e}^T \cdot \mat{Z} + \bar{\vec{e}}^T) \text{ from } (\mat{A}, \vec{x}^T, \vec{l}^T).\]

Variants

Noisy Error-Leakage LWE

Noisy Error-Leakage LWE is a special case of elLWE, where \(\mat{Z} = \mat{I}_m\).

The specialisation was introduced by Yin, Zhang, Dong, Wojtczak, and Lim in 2026 [2]. They describe the assumption as a special case of Leaky LWE, which is itself a generalisation of elLWE and Hint-LWE with tighter reductions.

Hardness

LWE with Error-Leakage is at least as hard as LWE for discrete Gaussian error distributions and small losses in parameter choices according to Theorem 3 in [1]. A much looser reduction can be obtained via statistical noise flooding [3].

Constructions built from elLWE

  • Bi-deniable Public-Key Encryption [3]
  • Laconic and Registration-Based Encryption [1]
  • Updatable Public-Key Encryption [4]
  • Proxy Re-Encryption [2]
  • Leaky LWE generalises elLWE and provides a tighter reduction from LWE.
  • Hint MLWE also supports error-leakage in LWE instances.

References

  • [1]Nico Döttling, Dimitris Kolonelos, Russell W. F. Lai, Chuanwei Lin, Giulio Malavolta, and Ahmadreza Rahimi. 2023. Efficient Laconic Cryptography from Learning with Errors. In Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part III (Lecture Notes in Computer Science), 2023. Springer, 417–446. Retrieved from https://ia.cr/2023/404
  • [2]Haotian Yin, Jie Zhang, Yuji Dong, Dominik Wojtczak, and Eng Gee Lim. 2026. Single-Hop HRA-Secure Owner-Encrypted Lattice-Based Proxy Re-Encryption without Statistical Noise Flooding. Retrieved from https://ia.cr/2026/1113
  • [3]Adam O’Neill, Chris Peikert, and Brent Waters. 2011. Bi-Deniable Public-Key Encryption. In Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings (Lecture Notes in Computer Science), 2011. Springer, 525–542. Retrieved from https://ia.cr/2011/352
  • [4]Calvin Abou Haidar, Alain Passelègue, and Damien Stehlé. 2023. Efficient Updatable Public-Key Encryption from Lattices. In ASIACRYPT (5) (Lecture Notes in Computer Science), 2023. Springer, 342–373. Retrieved from https://ia.cr/2023/1400