Density of Ideal Lattices - Preliminary Draft -
Johannes A Buchmann, Richard Lindner · 2009
The security of many ecient cryptographic constructions, e.g. collision-resistant hash functions, digital signatures, and identica- tion schemes, has been proven assuming the hardness of worst-case com- putational problems in ideal lattices. These lattices correspond to ideals in the ring Z( ), where is some xed algebraic integer. In this paper we show that the density of n-dimensional ideal lattices with determinant b among all lattices under the same bound is in O(b 1n ). So for lattices of dimension > 1 with bounded determinant,