Improved Reduction Between SIS Problems over Structured Lattices
Lattice-based cryptographic scheme is constructed based on hard problems on a structured lattice such as the short integer solution (SIS) problem and the learning with error (LWE), called ring-SIS (RSIS), ring-LWE (R-LWE), module-SIS (M-SIS), and module-LWE (MLWE). Generally, it has been considered that problems defined on the module-lattice are more difficult than the problems defined on the ideallattices. However, Albrecht and Deo showed that there is a reduction from M-LWE to R-LWE in the polynomial ring by handling the error rate and modulus. Also, Koo, No, and Kim showed that there is a reduction from M-SISqk,mk,β′ to R-SISq,m,β under some norm constraint of R-SIS, where k > 1. In this paper, we propose the improved reductions related to M-SIS and R-SIS compared to the previous work. To show the improved reduction, we propose the three novel reductions related to M-SIS to R-SIS on the polynomial ring. First, we propose the reduction from R-SISqk,m,β′ to R-SISqk,mk,βk . Combining one of the previous works, we obtain the reduction between R-SIS problems with distinct parameters preserving the number of samples of R-SIS. Second, we propose the improved reduction from M-SISqk,m,β′ to R-SISqk,m,β with k ≥ 1 under some norm constraint of R-SIS. Comparing to the previous work, the upper bound of the norm of the solution of M-SIS is decreased. Finally, we propose a reduction between M-SIS with different moduli. Combining these three results implies that R-SISq,m,β is more difficult than MSISC,m,β′ , where C is a multiple of q k for some k ≥ 1 under some norm constraint of R-SIS, which provides a double extension of the possible range of module ranks for M-SIS compared to the previous work.