qLWE implied

Propose Edit

Updated:

qLWE was introduced by Hoffmann, Méaux, Rossi, and Standaert in 2025 [1] as a multi-LWE instance with potentially different error distributions. So far, this assumption is only utilised as an intermediate step to give a partial reduction from LWE to LWE with Output Dependencies.

Definition

qLWE\(_{n,m,q}\)

Let \(\vec{s} \in (\ZZ_q^n)^*\) be a fixed secret vector and let \(\chi_0,\dots,\chi_{q-1}\) be distributions over \(\ZZ_q\). Sample \(\mat{A} \sample \ZZ_q^{mq \times n}\) and \(\vec{e} \sample \left(\chi_0 \times \dots\times \chi_{q-1}\right)^m \in \ZZ_q^{mq}\). An adversary is asked to distinguish between the distribution

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

Hardness

Theorem 2 of [1] states that qLWE is at least as hard as LWE for \(q \in \poly{n}\) and several conditions on the error distributions. The core idea is that qLWE is at least as hard as the LWE instance with the weakest error distribution by carefully adding error-terms to the samples.

Constructions built from qLWE

As qLWE is a multi-LWE instance, i.e. this list could theoretically contain all of the constructions built from LWE. However, there were no constructions built from qLWE explicitly yet.

References

  • [1]Clément Hoffmann, Pierrick Méaux, Mélissa Rossi, and François-Xavier Standaert. 2026. Learning with Errors with Output Dependencies: LWE, LWR, and Physical Learning Problems Under the Same Umbrella. In Post-Quantum Cryptography - 17th International Workshop, PQCrypto 2026, Saint-Malo, France, April 14-16, 2026, Proceedings, Part I (Lecture Notes in Computer Science), 2026. Springer, 287–318. Retrieved from https://ia.cr/2025/2225