Common Notation

Learning with Short and Sparse Errors (LWSSE)

Propose Edit

Updated:

The Learning with Short and Sparse Errors (LWSSE) problem was introdcued by Ghosal, Jain, Luo, Sahai, and Vafa in 2025 [1]. It provides a slightly unusual definition of LWE, where the secret is of dimension \(m-n\) and the error term is sampled sparsely from a discrete Gaussian distribution, i.e. the error term is zero for several coordinates.

Definition

LWSSE\(_{n,m,q,\eta,\gamma}\)

Let \(q\) be prime and \(y \in (0,1)\). Define the distribution \(\mathcal{E}_{n,m,\eta,\gamma}\) as a distribution over \(\ZZ\) which samples \(0\) with probability \(1-(m-n)^{-\gamma}\) or a random element from \(D_{\ZZ,\eta}\) with probability \((m-n)^{-\gamma}\). Sample \(\mat{A} \sample \ZZ_q^{m \times (m-n)}\), \(\vec{s} \sample \ZZ_q^{m-n}\), \(\vec{e} \sample \mathcal{S}_{n,m,\eta,\gamma}^m\), and \(\vec{b} \sample \ZZ_q^m\). An adverary is asked to distinguish between the distribution

\[(\mat{A}, \mat{A} \vec{s} + \vec{e}) \text{ and } (\mat{A}, \vec{b}).\]

Hardness

There are no known reductions to LWSSE. Rather the authors [1] provide upper bounds on the hardness of LWSSE by reducing it to \(\beta\)-CVP (Lemma 5.20), LPN (Lemma 5.15), and LWE (Lemma 5.10). Otherwise, Ghosal et al. [1] present some cryptanalysis of LWSSE in Section 7 of their paper and show the equivalence of LWSSE to ISSIS in Lemma 5.5.

Constructions built from LWSSE

  • Public-Key Encryption [1]

References

  • [1]Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai, and Neekon Vafa. 2025. Post-quantum PKE from Unstructured Noisy Linear Algebraic Assumptions: Beyond LWE and Alekhnovich’s LPN. In Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings, Part II (Lecture Notes in Computer Science), 2025. Springer, 64–93. Retrieved from https://ia.cr/2025/844