Identifying Ideal Lattices

Jintai Ding University of Cincinnati, Department of Mathematical Sciences, PO Box 210025, Cincinnati, OH 45221-0025, USA Richard Lindner Technische Universit┬Ęat Darmstadt, Department of Computer Science Hochschulstra├če 10, 64289 Darmstadt, Germany

TBD mathscidoc:2207.43102

IACR Cryptol. ePrint Arch., 2007.8
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 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.
No keywords uploaded!
[ Download ] [ 2022-07-21 14:21:47 uploaded by dingjt ] [ 324 downloads ] [ 0 comments ]
  title={Identifying Ideal Lattices},
  author={Jintai Ding, and Richard Lindner},
  booktitle={IACR Cryptol. ePrint Arch.},
Jintai Ding, and Richard Lindner. Identifying Ideal Lattices. 2007. In IACR Cryptol. ePrint Arch..
Please log in for comment!
Contact us: | Copyright Reserved