Common Notation

Yet-Another LWE implied

Propose Edit

Updated:

Yet-Another LWE was introduced by Passelègue and Stehlé in 2024 [1]. The assumption is a natural combination of Known-Norm LWE and Reused-A LWE.

Definition

Yet-Another LWE\(_{n,m,q,\sigma_1,\sigma_2,\chi}\)

Let \(\chi\) denote a distribution over \(\ZZ^n\). Sample \(\mat{A} \sample \ZZ_q^{m \times n}\), \(\vec{s} \sample \chi^n\), \(\vec{e}_1 \sample D_{\ZZ^m, \sigma_1}\), \(\vec{e}_2 \sample D_{\ZZ^m, \sigma_2}\), \(\vec{u} \sample \ZZ_q^m\), and \(\vec{h} \sample D_{\ZZ^m, \sqrt{\sigma_1^2 + \sigma_2^2}}\). An adversary is asked to distinguish between the distribution

\[(\mat{A}, \mat{A}\vec{s} + \vec{e}_1, \mat{A}\vec{s} + \vec{e}_2, \norm{\vec{s}}) \text{ and } \left( \mat{A}, \vec{u}, \vec{u} + \vec{h}, \norm{\vec{s}} \right).\]

Variants

(Yet-Another)2 LWE\(_{n,m,q,\sigma,w,B,\chi}\)

Let \(\chi\) denote a distribution over \(\ZZ^n\) and \(\Phi\) denote the distribution \(\sum_{i=1}^w \mathcal{U}([-B,\dots,B])\). Sample \(\mat{A} \sample \ZZ_q^{m \times n}\), \(\vec{s} \sample \chi^n\), \(\vec{e}_1 \sample D_{\ZZ^m, \sigma}\), \(\vec{e}_2 \sample \Phi_{w,B}\), \(\vec{u} \sample \ZZ_q^m\), and \(\vec{h} \sample D_{\ZZ^m, \sigma} + \Phi_{w,B}\). An adversary is asked to distinguish between the distribution

\[(\mat{A}, \mat{A}\vec{s} + \vec{e}_1, \mat{A}\vec{s} + \vec{e}_2, \norm{\vec{s}}) \text{ and } \left( \mat{A}, \vec{u}, \vec{u} + \vec{h}, \norm{\vec{s}} \right).\]

(Yet-Another)2 LWE [2] changes the error distribution of the second LWE sample to \(\Phi = \sum_{i=1}^w \mathcal{U}([-B,\dots,B])\). Smart and Walter argue that the attack on Reused-A LWE for both error vectors chosen from a small uniform distribution [3] fails, state that the distribution of \(\Phi\) approaches the discrete Gaussian for growing \(w\), and conjecture the hardness of their assumption.

Hardness

Lemma 2.6 of [1] states that Yet-Another LWE is at least as hard as small-secret LWE if \(\chi = D_{\ZZ^n, \sigma_s}\), \(\sigma_s \leq \poly{\lambda}\) and \((1/\sigma_s^2 + 1/(\sigma_i - \sigma_s)^2)^{-1/2} > \eta_\epsilon(\ZZ^m)\) for \(i \in \set{1,2}\) and negligible \(\epsilon\).

Constructions built from Yet-Another LWE

  • Threshold Fully Homomorphic Encryption [1]

References

  • [1]Alain Passelègue and Damien Stehlé. 2024. Low Communication Threshold Fully Homomorphic Encryption. In Advances in Cryptology - ASIACRYPT 2024 - 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9-13, 2024, Proceedings, Part I (Lecture Notes in Computer Science), 2024. Springer, 297–329. Retrieved from https://ia.cr/2024/1984
  • [2]Nigel P. Smart and Michael Walter. 2025. Error-Simulatable Sanitization for TFHE and Applications. IACR Commun. Cryptol. 2, 3 (2025), 1. Retrieved from https://ia.cr/2025/275
  • [3]Daniele Micciancio and Adam Suhl. 2024. Simulation-Secure Threshold PKE from LWE with Polynomial Modulus. IACR Commun. Cryptol. 1, 4 (2024), 2. Retrieved from https://ia.cr/2023/1728