k-M-ISIS

Propose Edit

Updated:

Based on the obersation that \(k\)-SIS is trivially insecure for \(k \geq m\), Albrecht, Cini, Lai, Malavolta, and Thyagarajan [1] introduce \(k\)-M-ISIS to overcome these restrictions. They specialise the assumption to rings, i.e. \(k\)-R-ISIS, and utilise it to build a vector commitment.

To elaborate on the restriction of \(k\)-SIS, let \(k \geq m\). Intuitively, the set of hints \(\set{\vec{z}_i}_{i \in [k]}\) forms a short basis trapdoor for \(\mat{A}\) if the \(\vec{z}_i\) are linearly independent. Formally, if the hints are \(\mathbb{Q}\)-linearly independent, the \(\mathbb{Q}\text{-}\text{span}\set{\vec{z}_i}_{i \in [k]}\) spans \(\ZZ^m\), i.e. there are no valid solutions. Hence, they introduce a problem called \(k\)-M-ISIS overcoming these restrictions by imposing an algebraic structure on the images, which is independent of the challenge matrix \(\mat{A}\). This algebraic structure is provided by a Laurent monomial \(g \in \mathcal{R}(\mathbf{X})\), i.e. \(g(\mathbf{X}) = \mathbf{X}^{\vec{e}} := \prod_{i \in [w]} X_i^{e_i}\) for some exponent vector \(\vec{e}^t = \begin{bmatrix} e_1 &\dots &e_w \end{bmatrix} \in \ZZ^w\). To rule out trivial wins, they introduce the notion of \(k\)-M-Admissiblility.

Definition

As there are some choices for which \(k\)-M-ISIS is trivially insecure, we need to define \(k\)-M-Admissible [1] to define admitted instances before we can define \(k\)-M-ISIS.

\(k\)-M-Admissible

Let \(\mathcal{G} \subset \mathcal{R}(\mathbf{X})\) be a set of Laurent monomials with \(k := \abs{\mathcal{G}}\). Let \(g^{*} \in \mathcal{R}(\mathbf{X})\) be a target Laurent monomial. We call a family \(\mathcal{G}\) \(k\)-M-ISIS-admissible if

  1. all \(g \in \mathcal{G}\) have constant degree,
  2. all \(g \in \mathcal{G}\) are distinct, i.e. \(\mathcal{G}\) is not a multiset, and
  3. \(0 \notin \mathcal{G}\).

We call a family \((\mathcal{G}, g^{*})\) \(k\)-M-ISIS-admissible if \(\mathcal{G}\) is \(k\)-M-ISIS-admissible, \(g^{*}\) has constant degree, and \(g^{*} \notin G\).

To explain the conditions:

  • Condition 1 ensures that no monomials are chosen that depend on the ring \(\mathcal{R}\).
  • Condition 2 rules out that trivial linear combinations of known preimages produce a preimage for the target.
  • Condition 3 disallows trivially producing multiple preimages of the same image.

Based on the definition of \(k\)-M-admissibility, we can provide the \(k\)-M-ISIS problem. Let \(\mathcal{R}_q^\times\) contain all invertible elements in \(\mathcal{R}_q\) for this purpose. Furthermore, \(\mat{A}_s^{-1}(\vec{x})\) defines sampling a preimage from \(D_{\Lambda_q^{\vec{x}}(\mat{A}), s}\) for some vector \(\vec{x} \in \mathcal{R}_q^{n}\).

\(k\)-M-ISIS\(_{n,q,\beta,\beta^{*},m,N,w,s}\)

Let \(q \in \ZZ\) be a prime and \(\mathcal{R} = \ZZ[X] / (X^N + 1)\). Let \(\vec{u}^t = \begin{bmatrix} 1 &0 &\dots &0 \end{bmatrix} \in \mathcal{R}_q^n\). Let \(\mathcal{G} \subset \mathcal{R}(\mathbf{X})\) be a set of \(w\)-variate Laurent monomials. Let \(g^{*} \in \mathcal{R}(\mathbf{X})\) be a target Laurent monomial. Let \((\mathcal{G}, g^{*})\) be \(k\)-M-admissible. Let \(\mat{A} \leftarrow \mathcal{R}_q^{n \times m}, \vec{v} \leftarrow (\mathcal{R}_q^\times)^w\). Compute for all \(g \in \mathcal{G}\) a short vector \(\vec{z}_g \leftarrow \mat{A}_s^{-1}\left( g(\vec{v}) \cdot \vec{u} \right)\) with \(\norm{\vec{z}_g} \leq \beta\). Given \(\mat{A}, \vec{v}, \vec{u}\), and \(\set{\vec{z}_g : g \in \mathcal{G} }\), an adversary is asked to find \(\left(s^{*}, \vec{z}_{g^{*}}\right)\) such that the following holds

\[\mat{A} \cdot \vec{z}_{g^{*}} = s^{*} \cdot g^{*}(\vec{v}) \cdot \vec{u} \bmod q \land 0 < \norm{s^{*}} \leq \beta^{*} \land \norm{\vec{z}_{g^{*}}} \leq \beta^{*} \land (g^{*}, \vec{z}_{g^{*}}) \neq (0, \vec{0}).\]

When \(n=1\), i.e. when \(\mat{A}\) is just a vector, we denote the problem by \(k\)-R-ISIS. Furthermore, in \(k\)-M-ISIS, we provide a specific version of \(k\)-M-ISIS by choosing a specific ring \(\mathcal{R}\) and \(\vec{u}^t = \begin{bmatrix}1 &0 &\dots &0\end{bmatrix}\). The original definition can be found in [1].

Hardness

The analysis of \(k\)-M-ISIS in [1] yields the following results.

  • \(k\)-R-ISIS with \(g^{*} = 1\) is as hard as R-SIS when \(k < m\) or when the system generated by \(\mathcal{G}\) is efficiently invertible according to Lemmas 3 and 4 of [1].
  • \(k\)-M-ISIS is at least as hard as \(k\)-R-ISIS and \(k\)-M-ISIS is a true generalization of \(k\)-R-ISIS according to Theorems 1 and 2 of [1].
  • \((\mathcal{G}, g^{*})\) is as hard as \((\mathcal{G}, 0)\) for any \(\mathcal{G}\), i.e. the non-homogeneous variant is no easier than the homogeneous one according to Lemma 6 of [1].
  • Scaling \((\mathcal{G}, g^{*})\) multiplicatively by any Laurent monomial does not change the hardness, e.g. we may choose to normalise instances to \(g^{*} = 1\) according to Lemma 7 [1].

As these reductions are not interesting for applications, the authors explore attacks utilizing a direct SIS attack on \(\mat{A}\), finding short \(\ZZ\)-linear combinations of \(\vec{z}_i\), and finding \(\mathbb{Q}\)-linear of \(\vec{z}_i\) that produce short images in Section 4.1 of [1].

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

  • Vector commitment [1]

Further Reading Suggestions

References

  • [1]Martin R. Albrecht, Valerio Cini, Russell W. F. Lai, Giulio Malavolta, and Sri Aravinda Krishnan Thyagarajan. 2022. Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable - (Extended Abstract). In Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part II (Lecture Notes in Computer Science), 2022. Springer, 102–132. Retrieved from https://ia.cr/2022/941