Paper 2020/588

Reduction from Module-SIS to Ring-SIS Under Norm Constraint of Ring-SIS

ZaHyun Koo, Jong-Seon No, and Young-Sik Kim


Lattice-based cryptographic scheme is constructed based on hard problems on a lattice such as the short integer solution (SIS) problem and the learning with error (LWE). However, the cryptographic scheme based on SIS or LWE is inefficient since the size of the key is too large. Thus, most cryptographic schemes use the variants of LWE and SIS with ring and module structures. Albrecht and Deo showed that there is a reduction from module-LWE (M-LWE) to ring-LWE (R-LWE) in the polynomial ring (Asiacrypt 2017) by handling the error rate and modulus. However, unlike the LWE problem, the SIS problem does not have an error rate, but there is the upper bound $\beta$ on the norm of the solution of the SIS problem. In this paper, we propose the two novel reductions related to module-SIS (M-SIS) and ring-SIS (R-SIS) on a polynomial ring. We propose (i) the reduction from R-SIS$_{q^{k},m^{k},\beta^{k}}$ to R-SIS$_{q,m,\beta}$ and (ii) the reduction from M-SIS to R-SIS under norm constraint of R-SIS. Combining these two results implies that R-SIS for a specified modulus and number samples is more difficult than M-SIS under norm constraints of R-SIS, which provides the range of possible module ranks for M-SIS.

Available format(s)
Publication info
Preprint. MINOR revision.
Lattice-based cryptographylearning with error (LWE)ring-short integer solution (R-SIS) problemshort integer solution (SIS) problem
Contact author(s)
bravokoo @ ccl snu ac kr
2020-05-22: received
Short URL
Creative Commons Attribution


      author = {ZaHyun Koo and Jong-Seon No and Young-Sik Kim},
      title = {Reduction from Module-SIS to Ring-SIS Under Norm Constraint of Ring-SIS},
      howpublished = {Cryptology ePrint Archive, Paper 2020/588},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.