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).\]

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].

Constructions built from elLWE

  • Laconic and Registration-Based Encryption [1]
  • 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