Density of Ideal Lattices

2009/01/01 by Johannes Buchmann, Buchmann, Johannes A., Richard Lindner +1 · 2 citations
Computer Science · Engineering · #Coding theory and cryptography #Cryptography and Data Security #Post-quantum cryptography #graph theory and CDMA systems #ideal lattices #provable security

paper · doi:10.4230/dagsemproc.09221.2

openalex publication_date 2009/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The security of many emphefficient cryptographic constructions, e.g.~collision-resistant hash functions, digital signatures, and identification schemes, has been proven assuming the hardness of emphworst-case computational problems in ideal lattices. These lattices correspond to ideals in the ring of integers of some fixed number field K. In this paper we show that the density of n-dimensional ideal lattices with determinant le b among all lattices under the same bound is in O(b^1-n). So for lattices of dimension > 1 with bounded determinant, the subclass of ideal lattices is always vanishingly small.

Cited by

• Natural Density Distribution of Hermite Normal Forms of Integer Matrices
• Counting ideals in polynomial rings

Related

• Embedding Integer Lattices as Ideals into Polynomial Rings
• B(H) lattices, density and arithmetic mean ideals
• On the ideal shortest vector problem over random rational primes
• Mean Value for Random Ideal Lattices
• Dense generic well-rounded lattices