Common Notation

Known-Norm LWE implied

Propose Edit

Updated:

Known-Norm LWE was introduced by Micciancio and Suhl in 2024 [1]. It describes LWE with leakage of \(\norm{\vec{s}}^2 + \norm{\vec{e}}^2\).

Definition

Known-Norm LWE\(_{n,m,q,\chi}\)

Let \(\chi\) be a distribution over \(\ZZ\). Sample \(\mat{A} \sample \ZZ_q^{m \times n}\), \(\vec{s} \sample \chi^n\), and \(\vec{e} \sample \chi^m\). An adversary is asked to distinguish between the distribution

\[(\mat{A}, \mat{A} \cdot \vec{s} + \vec{e}, \norm{\vec{s}}^2 + \norm{\vec{e}}^2) \text{ and } \left( \mat{A}, \mathcal{U}(\ZZ_q^m), \norm{\vec{s}}^2 + \norm{\vec{e}}^2 \right).\]

Variants

Known-Covariance RLWE\(_{\mathcal{R},m,q,\chi}\)

Let \(\mathcal{R}_q = \ZZ[X]/(X^n + 1)\) be a power-of-two cyclotomic ring. Let \(\chi\) be a distribution over \(\mathcal{R}\). Sample \(\vec{a} \sample \mathcal{R}_q^m\), \(s \sample \chi\), and \(\vec{e} \sample \chi^m\). An adversary is asked to distinguish between the distribution

\[(\vec{a}, \vec{a} \cdot \vec{s} + \vec{e}, s\bar{s} + \sum_{i=1}^m e_i \bar{e}_i) \text{ and } \left( \vec{a}, \mathcal{U}(\mathcal{R}_q^m), s\bar{s} + \sum_{i=1}^m e_i \bar{e}_i \right).\]

Known-Covariance RLWE [1] is a natural generalisation of Known-Norm LWE to rings.

Hardness

Lemma 9 of [1] states that Known-Norm LWE is as hard as small-secret LWE up to a polynomial factor in the advantage. This proof does not directly carry over to the ring setting. However, a general result by Boudgoust, Jeudy, Tairi, and Wen [2] can be applied to account for the leakage of Known-Covariance RLWE. They summarise the explicit application to Known-Covariance RLWE in Appendix A of their paper.

Constructions built from Known-Norm LWE

  • Public-Key Encryption [1]
  • Threshold Public-Key Encryption [1]

References

  • [1]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
  • [2]Katharina Boudgoust, Corentin Jeudy, Erkan Tairi, and Weiqiang Wen. 2026. Hardness of M-LWE with General Distributions and Applications to Leaky Variants. In PKC (1) (Lecture Notes in Computer Science), 2026. Springer, 3–37. Retrieved from https://ia.cr/2025/1472