Paper 2023/1412
Algebraic isomorphic spaces of ideal lattices, reduction of Ring-SIS problem, and new reduction of Ring-LWE problem
, School of Mathematics and Statistics, Xidian University, Xi’an 710126, ChinaAbstract
This paper mainly studies an open problem in modern cryptography, namely the Ring-SIS reduction problem. In order to prove the hardness of the Ring-SIS problem, this paper introduces the concepts of the one-dimensional SIS problem, the Ring-SIS$|_{x=0}$ problem, and the variant knapsack problem. The equivalence relations between the three are first established, on which the connection between the Ring-SIS$|_{x=0}$ problem and the Ring-SIS problem is built. This proves that the hardness of the Ring-SIS problem is no less than that of the variant knapsack problem and no more than that of the SIS problem. Additionally, we reduce the Ring-LWE problem to the Ring-SIS problem, which guarantees the security of encryption schemes based on Ring-LWE to a certain degree. Lastly, this article proves that the difficulty of the Ring-SIS problem and the Ring-LWE problem is moderate with respect to the spatial dimension or polynomial degree.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Ring-SIS problemshortest trapdoor in ideal latticesRing-LWE problemknapsack problemSIVP.
- Contact author(s)
-
arcsec30 @ 163 com
lyzhang @ mail xidian edu cn - History
- 2024-03-20: last of 2 revisions
- 2023-09-19: received
- See all versions
- Short URL
- https://ia.cr/2023/1412
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1412,
author = {Zhuang Shan and Leyou Zhang and Qing Wu and Qiqi Lai},
title = {Algebraic isomorphic spaces of ideal lattices, reduction of Ring-SIS problem, and new reduction of Ring-LWE problem},
howpublished = {Cryptology ePrint Archive, Paper 2023/1412},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1412}},
url = {https://eprint.iacr.org/2023/1412}
}
