Common Notation

Reused-A LWE implied

Propose Edit

Updated:

Reused-\(\mat{A}\) LWE was introduced by Micciancio and Suhl in 2024 [1]. This LWE-based assumption essentially provides two LWE samples for the same matrix \(\mat{A}\), i.e. a Reused-A LWE sample is defined by \((\mat{A}, \mat{A} \vec{s} + \vec{e}_1, \mat{A} \vec{s} + \vec{e}_2)\).

Definition

Reused-\(\mat{A}\) LWE\(_{n,m,q,\sigma_1,\sigma_2}\)

Let \(\chi\) be a distribution over \(\ZZ\). Sample \(\mat{A} \sample \ZZ_q^{m \times n}\), \(\vec{s} \sample \ZZ_q^n\), \(\vec{e}_1 \sample \mathcal{N}_{\sigma_1}^m\), \(\vec{e}_2 \sample \mathcal{N}_{\sigma_2}^m\), \(\vec{b}' \sample \ZZ_q^m\), and \(\vec{c} \sample \mathcal{N}_\sqrt{\sigma_1^2 + \sigma_2^2}^m\). An adversary is asked to distinguish between the distribution

\[(\mat{A}, \mat{A} \cdot \vec{s} + \vec{e}_1, \mat{A} \cdot \vec{s} + \vec{e}_2) \text{ and } \left( \mat{A}, \vec{b}', \vec{b}' + \vec{c} \right).\]

Note that the definition given in [1] uses a continuous Gaussian error term. Considering Reused-A LWE a special case of Hint-LWE, there are (hard) variants using a discrete Gaussian error term.

Hardness

Lemma 8 of [1] states that Reused-A LWE is at least as hard as LWE with Gaussian noise of width \(1/\sqrt{\sigma_1^2 + \sigma_2^2}\). However, they also state that their result is not new and that more general version (adjacent to Hint-LWE) prove the same result for more general versions (with discrete Gaussian error).

Further, they provide a conrete attack for Reused-A LWE where the error is chosen uniformly random in a small interval centered around zero.

Constructions built from Reused-\(\mat{A}\) 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