2021/12/25 by Zhiyong Zheng, Zheng, Zhiyong, Fengxia Liu +5
Computer Science · Engineering · #Advanced Algebra and Logic #Coding theory and cryptography #FOS: Computer and information sciences #H.4 #Information Theory (cs.IT) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2112.13185
openalex publication_date 2021/12/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Cyclic lattices and ideal lattices were introduced by Micciancio in \citeD2, Lyubashevsky and Micciancio in \citeL1 respectively, which play an efficient role in Ajtai's construction of a collision resistant Hash function (see \citeM1 and \citeM2) and in Gentry's construction of fully homomorphic encryption (see \citeG). Let R=Z[x]/⟨ ϕ(x)⟩ be a quotient ring of the integer coefficients polynomials ring, Lyubashevsky and Micciancio regarded an ideal lattice as the correspondence of an ideal of R, but they neither explain how to extend this definition to whole Euclidean space ℝn, nor exhibit the relationship of cyclic lattices and ideal lattices. In this paper, we regard the cyclic lattices and ideal lattices as the correspondences of finitely generated R-modules, so that we may show that ideal lattices are actually a special subclass of cyclic lattices, namely, cyclic integer lattices. In fact, there is a one to one correspondence between cyclic lattices in ℝn and finitely generated R-modules (see Theorem \refth4 below). On the other hand, since R is a Noether ring, each ideal of R is a finitely generated R-module, so it is natural and reasonable to regard ideal lattices as a special subclass of cyclic lattices (see corollary \refco3.4 below). It is worth noting that we use more general rotation matrix here, so our definition and results on cyclic lattices and ideal lattices are more general forms. As application, we provide cyclic lattice with an explicit and countable upper bound for the smoothing parameter (see Theorem \refth5 below). It is an open problem that is the shortest vector problem on cyclic lattice NP-hard? (see \citeD2). Our results may be viewed as a substantial progress in this direction.