Asymmetric SIS implied

Propose Edit

Updated:

Asymmetric SIS was introduced in 2020 by Zhang, Yu, Fan, Zhang, and Yang [1] to provide an optimised Fiat-Shamir with Abort signature by purposefully allowing for some asymmetry in the norm of the SIS solution.

Definition

Asymmetric SIS\(_{n,m_0,m_1,q,\beta_0,\beta_1}\)

Let matrix \(\mat{A} \in \ZZ_q^{n \times m}\) be chosen uniformly at random. Given \(\mat{A}\), an adversary is asked to find a short non-zero vector \(\vec{s} := \begin{bmatrix} \vec{s}_0^T &\vec{s}_1^T \end{bmatrix}^T \in \ZZ^{m_0} \times \ZZ^{m_1}\) satisfying

\[\mat{A} \cdot \vec{s} = \vec{0} \bmod q \land \norm{\vec{s}_0} \leq \beta_0 \land \norm{\vec{s}_1} \leq \beta_0.\]

Asymmetric SIS splits the SIS solution vector \(\mathsf{s}\) into two parts with different norm bounds. In [1] and [2], they define an inhomogeneous version and module- / ring-versions of this assumption corresponding to ISIS, Ring-SIS, and Module-SIS. Further, they provide an asymmetric version of SelfTargetMSIS.

Hardness

Asymmetric SIS\(_{n,m_0,m_1,q,\beta_0,\beta_1}^\infty\) is at least as hard as SIS\(_{n,m_0+m_1,q,\max(\beta_0,\beta_1)}^{\infty}\) and at most as hard as SIS\(_{n,m_0+m_1,q,\min(\beta_0,\beta_1)}^\infty\) [1], where \(\infty\) denotes that these problems use the infinity norm. For the Euclidean norm, the reduction same reduction to Asymmetric SIS applies for \(\beta = \sqrt{\beta_0^2 + \beta_1^2}\). The authors of [1] describe further cryptanalytic approaches against Asymmetric SIS in Section 5.

Constructions built from Asymmetric SIS

  • Asymmetric LWE is the LWE version of Asymmetric SIS.
  • Split SIS splits the SIS solution in a similar way with the additional opportunity to linearly scale one part of the solution.

References

  • [1]Jiang Zhang, Yu Yu, Shuqin Fan, Zhenfeng Zhang, and Kang Yang. 2020. Tweaking the Asymmetry of Asymmetric-Key Cryptography on Lattices: KEMs and Signatures of Smaller Sizes. In Public-Key Cryptography - PKC 2020 - 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, May 4-7, 2020, Proceedings, Part II (Lecture Notes in Computer Science), 2020. Springer, 37–65. Retrieved from https://ia.cr/2019/510
  • [2]Renjie Jin, Shuoqu Jian, and Longjiang Qu. 2026. Optimized G+G Signature. In Public-Key Cryptography - PKC 2026 - 29th IACR International Conference on Practice and Theory of Public-Key Cryptography, West Palm Beach, FL, USA, May 25-28, 2026, Proceedings, Part I (Lecture Notes in Computer Science), 2026. Springer, 364–392. Retrieved from https://ia.cr/2026/943