Common Notation

Inhomogeneous Short and Sparse Integer Solution (ISSIS)

Propose Edit

Updated:

The ISSIS assumption was introdcued by Ghosal, Jain, Luo, Sahai, and Vafa in 2025 under the name Inhomogeneous Short and Sparse Decision assumption [1]. The problem is a sparse variant of ISIS where the solution vector \(\vec{s}\) does not only have to be short but it has to have low Hamming-weight.

Definition

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

Let \(q\) be prime and \(\gamma \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^{n \times m}\) and \(\vec{r} \sample \mathcal{E}_{n,m,\eta,\gamma}^m\). Given \(\mat{A}\) and \(\vec{t} = \mat{A} \vec{r}\), an adversary is asked to find a short, low Hamming-weight vector \(\vec{s} \in \ZZ^m\) s.t.

\[\mat{A} \vec{s} = \vec{t} \land \norm{\vec{s}}_\infty \leq \beta \land \operatorname{hw}(\vec{s}) \leq 2m(m-n)^{-\gamma}.\]

Note that the authors also define a decisional variant of ISSIS, where \(\mat{A} \vec{s}\) should be distinguished from a uniform distribution over \(\ZZ_q^m\). They prove that the decisional version is equivalent to the search version in Theorem 5.4.

Hardness

In Section 5.2 of [1], the authors show that ISSIS is equivalent to the Learning with Short and Sparse Errors problem.

Constructions built from ISSIS

  • Public-Key Encryption in combination with LW2E [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