Paper 2007/322

Identifying Ideal Lattices

Jintai Ding and Richard Lindner

Abstract

Micciancio defined a generalization of cyclic lattices, called ideal lattices. These lattices can be used in cryptosystems to decrease the number of parameters necessary to describe a lattice by a square root, making them more efficient. He proves that the computational intractability of classic lattice problems for these lattices gives rise to provably secure one-way and collision-resistant hash functions. This provable security relies on the assumption that reducing bases of ideal lattices is similar to reducing bases of random lattices. We give an indication that lattice problems in ideal lattices do not represent the general case by providing a distinguisher, which decides in time $O(n^4)$ whether a given basis of rank $n$ spans an ideal lattice or not. Using this algorithm we perform a statistical analysis for several dimensions and show that randomly generated lattices are practically never ideal.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
decision problemslatticescomplexityNTRU
Contact author(s)
rlindner @ cdc informatik tu-darmstadt de
History
2007-08-16: received
Short URL
https://ia.cr/2007/322
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/322,
      author = {Jintai Ding and Richard Lindner},
      title = {Identifying Ideal Lattices},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/322},
      year = {2007},
      url = {https://eprint.iacr.org/2007/322}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.