Split SIS implied

Propose Edit

Updated:

Split-SIS was first introduced in 2015 by Nguyen, Zhang, and Zhang [1] to build more efficient group signatures in terms of public-key and signature sizes.

Definition

Split-SIS\(_{n,m,q,\beta,N}\)

Let matrices \(\mat{A}_0 \in \ZZ_q^{n \times m}\) and \(\mat{A}_1 \in \ZZ_q^{n \times m}\) be chosen uniformly at random. An adversary is asked to output a tuple \((\vec{s} = (\vec{s}_0, \vec{s}_1), h) \in \ZZ^{2m} \times [N]\) satisfying

\[\mat{A}_0 \vec{s}_0 + h \mat{A}_1 \vec{s}_1 = \vec{0} \land (\vec{s}_0 \neq \vec{0} \lor h\vec{s}_1 \neq \vec{0}) \land \norm{\vec{s}} \leq \beta \land h \in [N].\]

Compared to SIS, Split-SIS allows the adversary to scale parts of the challenge matrix by a scalar \(h \in [N]\).

Variants

Extended Split-SIS\(_{n,m,q,\beta,N}\)

Let matrices \(\mat{A}_0, \mat{A}_1, \mat{A}_2 \in \ZZ_q^{n \times m}\) be chosen uniformly at random. An adversary is asked to find a vector \(\vec{s} = (\vec{s}_0, \dots, \vec{s}_N) \in \ZZ^{(N+1)m}\) satisfying

\[\mat{A}_0 \vec{s}_0 + \sum_{j \in [N]} \left(\mat{A}_1 + j\mat{A}_2\right) \vec{s}_j = \vec{0} \land j\vec{s}_j\neq \vec{0} \bmod q \land 0 < \vec{s} \leq \beta.\]

Extended Split-SIS is utilised in [2] and [3]. It fixes the scalars to \(j\), which denotes the index / position of the vector in the solution vector \(\vec{s}\).

According to Theorem 1 in [2], the problem is at least as hard as SIS\(_{n,3m,q,N\beta}\) if \(q \geq \beta \omega(\sqrt{n \log n}) > (N^2 + N)/2\).

Hardness

According to Theorem 1 in [1], Split-SIS\(_{n,m,q,\beta,N}\) is at least as hard as SIS\(_{n,2m,q,\beta}\) if \(q \geq \beta \cdot \omega(\sqrt{n \log n}) > N\). Roughly outlined, the reduction algorithm guesses \(h\) and scales the first part of the challenge matrix corresponding to \(\mat{A}_0\) in advance. If \(h\) was picked correctly, the Split-SIS solution should also be a SIS solution.

Any reductions in this section should be reflected as an edge in the graph.

Constructions built from Split-SIS

References

  • [1]Phong Q. Nguyen, Jiang Zhang, and Zhenfeng Zhang. 2015. Simpler Efficient Group Signatures from Lattices. In Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 - April 1, 2015, Proceedings (Lecture Notes in Computer Science), 2015. Springer, 401–426. Retrieved from https://ia.cr/2015/020
  • [2]Gao Wen, Hu Yupu, Wang Baocang, and Xie Jia. 2016. Improved lattice-based ring signature schemes from basis delegation. The Journal of China Universities of Posts and Telecommunications 23, 3 (2016), 11–28. https://doi.org/10.1016/S1005-8885(16)60027-4
  • [3]Wen Gao, Yupu Hu, Baocang Wang, Jiangshan Chen, and Xin Wang. 2019. Efficient Ring Signature Scheme Without Random Oracle from Lattices*. Chinese Journal of Electronics 28, 2 (2019), 266–272. https://doi.org/10.1049/cje.2018.12.005