Common Notation

\(t\)-M-ISIS implied

Propose Edit

Updated:

\(t\)-Module-ISIS was introduced in 2024 by Fouque, Gajland, de Groote, Janneck, and Kiltz [1]. It yields a natural extension of Inhomogeneous SIS, which provides multiple target vectors and the adversary can choose which one it provides a preimage of. The authors utilise the specialised NTRU-based ring-version of this \(t\)-Module-ISIS to reduce to the Falcon signature scheme.

Definition

\(t\)-M-ISIS\(_{n,m,q,\beta,\mathcal{R}}\)

Let matrix \(\mat{A} \in \mathcal{R}_q^{n \times m}\) and a set of \(t\) target vectors \(\mathcal{T} \subsetneq \mathcal{R}_q^n\) be chosen uniformly at random with \(\abs{\mathcal{T}} = t\). Given \(\mat{A}\) and \(\mathcal{T}\), an adversary is asked to find a short vector \(\vec{s} \in \mathcal{R}^m\) satisfying

\[\mat{A} \cdot \vec{s} \in \mathcal{T} \bmod q \land \norm{\vec{s}} \leq \beta.\]

Fouque et al. [1] originally introduce a NTRU-based ring version of \(t\)-M-ISIS, i.e. \(n=1\), which they denote as \(t\)-R-ISIS.

The multi-target approach roughly outlines the intuition that \(t\)-M-ISIS can be at least \(t\)-times easier ISIS. Alongside a preimage oracle, this intuition has also been captured in One-More-ISIS, which trivially implies \(t\)-M-ISIS.

Variants

\(t\)-M-SPISIS\(_{n,m,q,\beta,\sigma,\mathcal{R}}\)

Let matrix \(\mat{A} \in \mathcal{R}_q^{n \times m}\) and a set of \(t\) target vectors \(\mathcal{T} \subsetneq \mathcal{R}_q^n\) be chosen uniformly at random with \(\abs{\mathcal{T}} = t\) and \(\vec{s}_i \sample D_{\Lambda_q^{\vec{t}_i}(\mat{A}), \sigma}\) for all \(\vec{t}_i \in \mathcal{T}\). Given \(\mat{A}\), \(\mathcal{T}\), and \(\set{\vec{s}_i}_i\), an adversary is asked to find a short vector \(\vec{s} \in \mathcal{R}^m\) satisfying

\[\mat{A} \cdot \vec{s} \in \mathcal{T} \bmod q \land \vec{s} \notin \set{\vec{s}_i}_i \land \norm{\vec{s}} \leq \beta.\]

This variant appeals to the second-preimage resistance property of the SIS hash function with multiple potential target vectors, given a single preimage for each of them. It’s reduction from SIS is essentially identical to the one presented below for \(t\)-M-ISIS, simplifying the proof that the SIS solution is non-zero through the condition \(\vec{s} \notin \set{\vec{s}_i}_i\).

Fouque et al. [1] originally introduce a NTRU-based ring version of \(t\)-M-SPISIS, i.e. \(n=1\), which they denote as \(t\)-R-SPISIS.

Hardness

M-SIS\(_{n,m,q,2\beta,\mathcal{R}}\) can be reduced to \(t\)-M-ISIS\(_{n,m,q,\beta,\mathcal{R}}\) by sampling \(t\) discrete Gaussian vectors \(\vec{s}_i \sample D_{\mathcal{R}^m, s}\). Then, the target vectors \(\vec{t}_i = \mat{A} \cdot \vec{s}_i \in \mathcal{T}\) are distributed statistcally close to uniform over \(\mathcal{R}_q^n\) and the reduction algorithm can recover a M-SIS solution from any \(t\)-M-ISIS solution \(\vec{s}\) for target vector \(j\) by outputting \(\vec{s} - \vec{s}_j\).

We refer to the original paper [1] regarding statements about the hardness of \(t\)-R-ISIS based on NTRU.

Constructions built from \(t\)-M-ISIS

  • Signature (specifically Falcon) [1]

References

  • [1]Pierre-Alain Fouque, Phillip Gajland, Hubert de Groote, Jonas Janneck, and Eike Kiltz. 2026. A Closer Look at Falcon. In Advances in Cryptology - EUROCRYPT 2026 - 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10-14, 2026, Proceedings, Part IV (Lecture Notes in Computer Science), 2026. Springer, 3–31. Retrieved from https://ia.cr/2024/1769