Basis-Augmented SIS (BASIS)

Propose Edit

Updated:

\(\newcommand{\rand}{\text{rand}}\newcommand{\struct}{\text{struct}}\newcommand{\power}{\text{power}}\) The Basis-Augmented SIS (BASIS) problem was introduced in 2023 by Wee and Wu [1]. They consider several instantiations of their proposed framework and utilise it to construct vector commitments, functional commitments, aggregatable commitments, and combinations thereof.

Definition

BASIS\(_{n, q, \beta, m, n', m', \ell, s, \mathsf{Samp}}\)

Let \(\mathsf{Samp}\) be an efficient sampling algorithm that takes a matrix \(\mat{A} \in \ZZ_q^{n \times m}\) as input and outputs a matrix \(\mat{B} \in \ZZ_q^{n' \times m'}\) with auxiliary information \(\text{aux}\). Choose a matrix \(\mat{A} \in \ZZ_q^{n \times m}\) uniform at random and run \((\mat{B}, \text{aux}) \gets \mathsf{Samp}(\mat{A})\). Compute a trapdoor \(\mat{T} \sample \mat{B}^{-1}(\mat{G}_{n'})\) for the matrix \(\mat{B}\). Given \(\mat{A}, \mat{B}, \mat{T},\) and \(\text{aux}\), the adversary is asked to find a vector \(\vec{z} \in \ZZ^m\) s.t.

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

Intuitively, the BASIS assumption states that it is hard to solve SIS for \(\mat{A}\), given a trapdoor for a matrix \(\mat{B}\) related to \(\mat{A}\). The trapdoor allows the adversary to sample preimages of \(\mat{B}\) and thus, it is easy to break the assumption if \(\mat{B}\) contains too much information about \(\mat{A}\), e.g. when \(\mat{B} = \mat{A}\) according to Section 3 of [2].

Variants

There are three concrete instantiations of the sampling algorithm \(\mathsf{Samp}\).

BASIS\(_\text{rand}\) standard

The sampling algorithm \(\mathsf{Samp}(\mat{A})\) samples \(i^{*} \sample [\ell], \mat{A}_i \sample \ZZ_q^{(n+1) \times m}\) for all \(i \neq i^{*}, \vec{a} \sample \ZZ_q^m\), sets \(\mat{A}_{i^{*}}^T = \begin{bmatrix} \vec{a} & \mat{A}^T \end{bmatrix}\), and outputs

\[\mat{B} = \left[ \begin{array}{ccc|c} \mat{A}_1 & & &-\mat{G}_{n+1} \\ &\ddots & &\vdots \\ & &\mat{A}_\ell&-\mat{G}_{n+1} \end{array} \right] \text{ and } \text{aux} = i^*.\]

This instantiation was proposed by Wee and Wu [1]. They proved BASIS\(_\rand\) to be as hard as SIS in Lemmas 3.5 to 3.7 of [1]. We briefly elaborate on this equivalence.

\[\mat{B} \cdot \begin{bmatrix} \vec{z}_1 \\ \vdots \\ \vec{z}_\ell \\ \vec{z}_{\mat{G}} \end{bmatrix} = \vec{0} \Leftrightarrow \mat{A}_i \cdot \vec{z}_i = \mat{G}_{n+1} \cdot \vec{z}_{\mat{G}} \text{ for all } i \in [\ell]\]

We can sample \(\vec{z}_{i^{*}} \in \ZZ^m\) s.t. \(\mat{A}_{i^{*}} \cdot \vec{z}_{i^{*}}\) is close to uniform. Then, use the gadget structure of \(\mat{G}_{n+1}\) to find a short \(\vec{z}_{\mat{G}}\) so that \(\mat{A}_{i^{*}} \cdot \vec{z}_{i^{*}} = \mat{G}_{n+1} \cdot \vec{z}_{\mat{G}}\). All other matrices \(\mat{A}_i\) with \(i \neq i^{*}\) are chosen with a trapdoor. Using these trapdoors, we can find short \(\vec{z}_i\) s.t. \(\mat{A}_i \cdot \vec{z}_i = \mat{G}_{n+1} \cdot \vec{z}_{\mat{G}}\) holds for all \(i \neq i^{*}\).

In Section 7.2 of [3], a reduction from a modified ring-version of BASIS\(_\rand\) to Twin k-M-ISIS is sketched. Nevertheless, a formal connection to standard assumptions like R-SIS or M-SIS is missing.

BASIS\(_{\text{struct}}\)

The sampling algorithm \(\mathsf{Samp}(\mat{A})\) samples \(\mat{W}_i \sample \ZZ_q^{n \times n}\) for all \(i \in [\ell]\) and outputs

\[\mat{B} = \left[ \begin{array}{ccc|c} \mat{W}_1 \mat{A} & & &-\mat{G}_{n} \\ &\ddots & &\vdots \\ & &\mat{W}_\ell\mat{A} &-\mat{G}_{n} \end{array} \right] \text{ and } \text{aux} = (\mat{W}_1, \dots, \mat{W}_\ell).\]

This instantiation was also introduced by Wee and Wu [1]. They compare this instance to k-M-ISIS by comparing the approach of publishing a full trapdoor for BASIS\(_\text{struct}\) with the approach of publishing short preimages. The authors provide a reduction from k-M-ISIS to BASIS\(_\struct\) in Section 6 of [1]. The BASIS\(_\text{struct}\) instance solved in the reduction is of size \(\ell < m/k\) for a k-M-ISIS challenge.

Wee and Wu utilise the hardness assumption of this problem for another application, namely a succinct vector commitment scheme that is secure if BASIS\(_\struct\) is hard to solve according to Corollary 4.8 in [1].

BASIS\(_{\text{power}}\)

The sampling algorithm \(\mathsf{Samp}(\mat{A})\) samples a vector \(\vec{a} \sample \ZZ_q^m\) and an invertible matrix \(\mat{W} \sample \ZZ_q^{(n+1) \times (n+1)}\). Set \(\mat{A^{*}}^T = \begin{bmatrix} \vec{a} & \mat{A}^T \end{bmatrix}\) and output

\[\mat{B} = \left[ \begin{array}{ccc|c} \mat{W}^0 \mat{A^*} & & &-\mat{G}_{n} \\ &\ddots & &\vdots \\ & &\mat{W}^{\ell -1}\mat{A^*} &-\mat{G}_{n} \end{array} \right] \text{ and } \text{aux} = \mat{W}.\]

As BASIS\(_\power\) is more structured than BASIS\(_\struct\), we might expect hardness results to translate to BASIS\(_\struct\). It turns out the additional structure allows to prove a small regime of parameters as hard as M-SIS.

This instantiation was first proposed by Fenzi et al. [2]. The authors utilise the BASIS\(_\text{power}\) assumption to prove the binding property of a commitment scheme.

The ring version of BASIS\(_\text{power}\), called Power Ring-BASIS (PRISIS), was also introduced in [2]. The authors show that PRISIS is at least as hard as M-SIS for \(\ell = 2\) in Lemma 3.6 of [2].

Hardness

For the general BASIS assumption, there are no known hardness results as its hardness depends crucially on the choice of the sampling algorithm \(\mathsf{Samp}\). However, there are several (partial) reductions for the variants described above. Please find the reductions in the corresponding sections.

Constructions built from BASIS

  • Vector commitment [1]
  • Succinct functional commitment [1]
  • Polynomial commitment [1]
  • Aggregatable functional commitment [1]
  • k-M-ISIS is related to BASIS\(_\struct\) and was utilised for build similar construction.
  • \(h\)-BASIS is a multi-instance of BASIS.
  • \(\ell\)-Succinct SIS was inspired by BASIS\(_\struct\). It can be seen as a slightly less-structured version of BASIS\(_\struct\).

References

  • [1]Hoeteck Wee and David J. Wu. 2023. Succinct Vector, Polynomial, and Functional Commitments from Lattices. In Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part III (Lecture Notes in Computer Science), 2023. Springer, 385–416. Retrieved from https://ia.cr/2022/1515
  • [2]Giacomo Fenzi, Hossein Moghaddas, and Ngoc Khanh Nguyen. 2024. Lattice-Based Polynomial Commitments: Towards Asymptotic and Concrete Efficiency. J. Cryptol. 37, 3 (2024), 31. Retrieved from https://ia.cr/2023/846
  • [3]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