Algebraic isomorphic spaces of ideal lattices, reduction of Ring-SIS problem, and new reduction of Ring-LWE problem

Zhuang Shan; Leyou Zhang; Qing Wu; Qiqi Lai

Paper 2023/1412

Algebraic isomorphic spaces of ideal lattices, reduction of Ring-SIS problem, and new reduction of Ring-LWE problem

Zhuang Shan

, School of Mathematics and Statistics, Xidian University, Xi’an 710126, China

Leyou Zhang, School of Mathematics and Statistics, Xidian University, Xi’an 710126, China

Qing Wu, School of Automation, Xi’an University of Posts and Telecommunications, Xi’an 710121, China

Qiqi Lai, School of Computer Science, Shaanxi Normal University, Xi’an, China

Abstract

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 problem shortest trapdoor in ideal lattices Ring-LWE problem knapsack problem SIVP.
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},
      url = {https://eprint.iacr.org/2023/1412}
}