Knowledge k-M-ISIS broken

Propose Edit

Updated:

Albrecht, Cini, Lai, Malavolta, and Thyagarajan [1] provide a knowledge variant of \(k\)-M-ISIS. They utilise this assumption to build a succinct non-interactive argument of knowledge (SNARK). Wee and Wu invalidated this assumption (at least morally) in [2].

Definition

The knowledge \(k\)-M-ISIS assumption captures the intuition that if the images are restricted to scalar multiples of \(\vec{t}\), then the only way to produce preimages of them, is via a linear combination of the given preimages with small coefficients.

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

Adopt the notation from \(k\)-M-ISIS. Let \(\alpha^{*} \geq 1\). Let \(\mathcal{T}\) contain elements \(\vec{t} \in \mathcal{R}_q^n\) s.t. \(\abs{\text{span}(\vec{t})} / \abs{\mathcal{R}_q^n} = \negl{\lambda}\). If a ppt adversary \(\adv\) outputs \((c, \vec{u}_c)\) satisfying the following condition

\[\mat{A} \cdot \vec{u}_c = c \cdot \vec{t} \bmod q \land 0 < \norm{\vec{u}_c} \leq \beta^{*},\]

then there exists a ppt extractor \(\mathcal{E}_{\adv}\) that – with access to the adversary’s randomness – outputs short \(\set{c_g}\) s.t.

\[c = \sum_{g \in \mathcal{G}} c_g \cdot g(\vec{v}) \bmod q \land \norm{(c_g)_{g \in \mathcal{G}}} \leq \alpha^*.\]

In other words, the assumption states that no adversary \(\adv\) can compute \((c, \vec{u}_c)\) where \(c\) is not just a short linear combination of the given hints.

Hardness

The assumption is invalidated – at least “morally” – in [2]. Roughly speaking, the attack uses that the preimages of \(g(\vec{v}) \cdot \vec{t}\) span a short basis of the submodule spanned by \(\vec{t}\): essentially an Ajtai-style trapdoor. Then, sampling an arbitrary, not-necessarily short, preimage of some \(c \cdot \vec{t}\), Babai rounding can be applied to obtain a short preimage of some other, random \(\bar{c} \cdot \vec{t}\).

An implementation of the attack in SageMath is available here.

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

  • Succinct non-interactive argument of knowledge (SNARK) [1]
  • \(k\)-M-ISIS yields the underlying assumption of Knowledge \(k\)-M-ISIS.

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
  • [2]Hoeteck Wee and David J. Wu. 2023. Lattice-Based Functional Commitments: Fast Verification and Cryptanalysis. In Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part V (Lecture Notes in Computer Science), 2023. Springer, 201–235. Retrieved from https://ia.cr/2024/028