Welcome to the resource topic for 2020/1257
Title:
Improved Reduction Between SIS Problems over Structured Lattices
Authors: ZaHyun Koo, Yongwoo Lee, Joon-Woo Lee, Jong-Seon No, Young-Sik Kim
Abstract:Lattice-based cryptographic scheme is constructed based on hard problems on an algebraic structured lattice such as the short integer solution (SIS) problems. These problems are called ring-SIS (R-SIS) and its generalized version, module-SIS (M-SIS). Generally, it has been considered that problems defined on the module-lattice are more difficult than the problems defined on the ideal-lattice. However, Koo, No, and Kim showed that R-SIS is more difficult than M-SIS under some norm constraints of R-SIS. However, this reduction has problems that the rank of the module is limited to about half of the instances of R-SIS, and the comparison is not performed through the same modulus of R-SIS and M-SIS. In this paper, we propose that R-SIS is more difficult than M-SIS with the same modulus under some constraint of R-SIS. Also, we show that R-SIS with the modulus prime q is more difficult than M-SIS with the composite modulus c such that c is divided by q. In particular, it shows that through the reduction from M-SIS to R-SIS with the same modulus, the rank of the module is extended as much as the number of instances of R-SIS from half of the number of instances of R-SIS. Finally, this paper shows that R-SIS is more difficult than M-SIS under some constraint, which is tighter than the M-SIS in the previous work.
ePrint: https://eprint.iacr.org/2020/1257
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .