Cryptology ePrint Archive: Report 2020/1257

Improved Reduction Between SIS Problems over Structured Lattices

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

Abstract: 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 (R-SIS), ring-LWE (R-LWE), module-SIS (M-SIS), and module-LWE (M-LWE). Generally, it has been considered that problems defined on the module-lattice are more difficult than the problems defined on the ideal-lattices. 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-SIS$_{q^{k},m^{k},\beta'}$ to R-SIS$_{q,m,\beta}$ 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-SIS$_{q^{k},m,\beta'}$ to R-SIS$_{q^{k},m^{k},\beta^{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-SIS$_{q^{k},m,\beta'}$ to R-SIS$_{q^{k},m,\beta}$ with $k \ge 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-SIS$_{q,m,\beta}$ is more difficult than M-SIS$_{C,m,\beta'}$, where $C$ is a multiple of $q^{k}$ for some $k \ge 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.

Category / Keywords: foundations / Lattice-based cryptography, module-short integer solution (M-SIS) problem, ring-short integer solution (R-SIS) problem, short integer solution (SIS) problem

Date: received 10 Oct 2020

Contact author: bravokoo at ccl snu ac kr,jsno@snu ac kr,iamyskim@chosun ac kr

Available format(s): PDF | BibTeX Citation

Version: 20201014:180003 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]