Paper 2024/1041
Embedding Integer Lattices as Ideals into Polynomial Rings
Abstract
Many latticebased crypstosystems employ ideal lattices for high efficiency. However, the additional algebraic structure of ideal lattices usually makes us worry about the security, and it is widely believed that the algebraic structure will help us solve the hard problems in ideal lattices more efficiently. In this paper, we study the additional algebraic structure of ideal lattices further and find that a given ideal lattice in a polynomial ring can be embedded as an ideal into infinitely many different polynomial rings by the coefficient embedding. We design an algorithm to verify whether a given fullrank lattice in $\mathbb{Z}^n$ is an ideal lattice and output all the polynomial rings that the given lattice can be embedded into as an ideal with bit operations $\mathcal{O}(n^3(\log n + B)^2(\log n)^2)$, where $n$ is the dimension of the lattice and $B$ is the upper bound of the bit length of the entries of the input lattice basis. We would like to point out that Ding and Lindner proposed an algorithm for identifying ideal lattices and outputting a single polynomial ring of which the input lattice can be regarded as an ideal with bit operations $\mathcal{O}(n^5B^2)$ in 2007. However, we find a flaw in Ding and Lindner's algorithm, and it causes some ideal lattices can't be identified by their algorithm.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Published elsewhere. The International Symposium on Symbolic and Algebraic Computation (ISSAC) 2024
 Keywords
 Ideal latticeCoefficient embeddingComplexity
 Contact author(s)

chengyihang15 @ mails ucas ac cn
fengyansong @ amss ac cn
panyanbin @ amss ac cn  History
 20240702: last of 3 revisions
 20240627: received
 See all versions
 Short URL
 https://ia.cr/2024/1041
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/1041, author = {Yihang Cheng and Yansong Feng and Yanbin Pan}, title = {Embedding Integer Lattices as Ideals into Polynomial Rings}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1041}, year = {2024}, url = {https://eprint.iacr.org/2024/1041} }