Twin k-M-ISIS

Propose Edit

Updated:

Balbás, Catalano, Fiore, and Lai [1] introduced a twin-version of the \(k\)-M-ISIS assumption in 2023 to build chainable functional commitments for unbounded depth circuits from it.

Definition

Please find a definition of \(k\)-M-admissible in the \(k\)-M-ISIS article.

Twin \(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} = \begin{bmatrix} 1 &0 &\dots &0 \end{bmatrix}^t \in \mathcal{R}_q^n\). Let \(\mathcal{G}_{\mat{A}}, \mathcal{G}_{\mat{B}} \subset \mathcal{R}(\mathbf{X})\) be a set of \(w\)-variate Laurent monomial. Let \((\mathcal{G}_{\mat{A}} \cup \mathcal{G}_{\mat{B}})\) be \(k\)-M-admissible. Let \(\mat{A} \sample \mathcal{R}_q^{n \times m}, \mat{B} \sample \mathcal{R}_q^{n \times m}, \vec{v} \sample (\mathcal{R}_q^\times)^w\). Compute for all \(g_{\mat{A}} \in \mathcal{G}_{\mat{A}}\) a short vector \(\vec{z}_{g_{\mat{A}}} \sample \mat{A}_s^{-1}\left(g_{\mat{A}}(\vec{v}) \cdot \vec{u}\right)\) with \(\norm{\vec{z}_{g_{\mat{A}}}} \leq \beta\). Compute for all \(g_{\mat{B}} \in \mathcal{G}_{\mat{B}}\) a short vector \(\vec{z}_{g_{\mat{B}}} \sample \mat{B}_s^{-1}\left( g_{\mat{B}}(\vec{v}) \cdot \vec{u} \right)\) with \(\norm{\vec{z}_{g_{\mat{A}}}} \leq \beta\). Given \(\mat{A}, \mat{B}, \vec{v}, \vec{u}, \set{ \vec{z}_{g_{\mat{A}}} : {g_{\mat{A}} \in \mathcal{G}_{\mat{A}}} }\), and \(\set{ \vec{z}_{g_{\mat{B}}} : {g_{\mat{B}} \in \mathcal{G}_{\mat{B}}} }\), an adversary is asked to find \(\left(\vec{z}_{\mat{A}}, \vec{z}_{\mat{B}}\right)\) such that the following holds

\[\mat{A} \cdot \vec{z}_{\mat{A}} + \mat{B} \cdot \vec{z}_{\mat{B}} = \vec{0} \mod q \land 0 < \norm{\begin{bmatrix} \vec{z}_{\mat{A}} &\vec{z}_{\mat{B}} \end{bmatrix}} \leq \beta^{*}.\]

When \(n = 1\), we denote the problem by Twin \(k\)-R-ISIS. This definition is a specific version of Twin \(k\)-M-ISIS, as we specify the ring \(\mathcal{R}\) and \(\vec{u}^t = \begin{bmatrix} 1 &0 &\dots &0 \end{bmatrix}\). The original definition can be found in [1].

Hardness

Twin \(k\)-M-ISIS is at least as hard as solving \(2k\)-M-ISIS problem according to Theorem A.7 in [2]. This reduction is based on a re-randomization technique utilising a NTRU trapdoor.

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

  • Chainable functional commitments [1]
  • \(k\)-M-ISIS is the corresponding single version of Twin \(k\)-M-ISIS.

References

  • [1]David Balbás, Dario Catalano, Dario Fiore, and Russell W. F. Lai. 2023. Chainable Functional Commitments for Unbounded-Depth Circuits. In Theory of Cryptography - 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 - December 2, 2023, Proceedings, Part III (Lecture Notes in Computer Science), 2023. Springer, 363–393. Retrieved from https://ia.cr/2022/1365
  • [2]Martin R. Albrecht, Giacomo Fenzi, Oleksandra Lapiha, and Ngoc Khanh Nguyen. 2024. SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions. In Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part VI (Lecture Notes in Computer Science), 2024. Springer, 90–119. Retrieved from https://ia.cr/2023/1469