Paper 2023/1412 Original: eprint.iacr.org/2023/1412 ↗

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

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.