\(\ell\)-succinct SIS

Propose Edit

Updated:

\(\ell\)-succinct SIS was introduced in 2024 by Wee [1] dual to \(\ell\)-succinct LWE. It can be seen as a slightly less-structured version of BASIS\(_{\text{struct}}\). Both assumptions follow a similar idea and therefore, provide similar capabilities for constructions, which are currently limited to succinct functional commitments [2].

Definition

\(\ell\)-succinct SIS\(_{n,m,q,\beta,\sigma}\)

Let matrix \(\mat{A} \in \ZZ_q^{n \times m}\) and \(\mat{W} \in \ZZ_q^{\ell n \times m}\) be chosen uniformly at random. Let \(\mat{B} := \begin{bmatrix} \mat{I}_\ell \otimes \mat{A} &\mat{W} \end{bmatrix}\) and a short trapdoor \(\mat{T} \gets \mat{B}_\sigma^{-1}(\mat{I}_\ell \otimes \mat{G}_n)\). Given matrices \(\mat{B}\) and \(\mat{T}\), an adversary is asked to find a short non-zero vector \(\vec{s} \in \ZZ^{m}\) s.t.

\[\mat{A} \cdot \vec{s} = \vec{0} \bmod q \land 0 < \norm{\vec{s}} \leq \beta.\]

Intuitively, the assumption states that it is hard to solve SIS w.r.t. matrix \(\mat{A}\), given a trapdoor for the related matrix \(\mat{B}\). Naively, one could state that \(\ell\)-succinct SIS is BASIS\(_{\text{struct}}\) where the matrices \(\mat{W}\) and \(\mat{G}_n\) switched their positions.

Hardness

Wee proved that \(\ell\)-succinct SIS is at least as hard as BASIS\(_{\text{struct}}\) for the same choice of \(\ell\) in Lemma 2 of [1].

Furthermore, \(\ell\)-succinct LWE trivially implies \(\ell\)-succinct SIS [1]. As \(\ell\)-succinct LWE was shown to be at least as hard as Evasive LWE according to Lemma 3 in [1], this might suggest that a similar reduction from Evasive SIS to \(\ell\)-succinct SIS exists.

Constructions built from \(\ell\)-succinct SIS

  • Succinct functional commitments [2]

References

  • [1]Hoeteck Wee. 2024. Circuit ABE with poly(depth,\(λ\))-Sized Ciphertexts and Keys from Lattices. In Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part III (Lecture Notes in Computer Science), 2024. Springer, 178–209. Retrieved from https://ia.cr/2024/1416
  • [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