You are looking at a specific version 20201014:180003 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Lattice-based cryptographyring-short integer solution (R-SIS) problemshort integer solution (SIS) problem
Contact author(s)
bravokoo @ ccl snu ac kr,jsno @ snu ac kr,iamyskim @ chosun ac kr
History
2021-02-24: revised
2020-10-14: received
See all versions
Short URL
https://ia.cr/2020/1257
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.