On the Leftover Hash Lemma over Cyclotomic Rings

252

2026-03-24

Niko Kindsvogel

14:45

The Leftover Hash Lemma (LHL) is a fundamental result in cryptography that provides conditions under which a random variable with sufficient entropy can be transformed into an output that is statistically close to uniform. In lattice-based cryptography, the LHL plays a central role in security proofs. While the classical lemma is formulated over vector spaces or the integers, modern cryptographic constructions frequently operate in more structured algebraic settings such as cyclotomic integer rings. Extending the LHL to these rings introduces additional challenges, since quotient rings of cyclotomic integers modulo an integer modulus are generally not fields and contain non-invertible elements. This thesis studies the LHL in the setting of cyclotomic integer rings from an algebraic perspective. After reviewing the necessary background from algebraic number theory, probability, and universal hashing, we present the ring-based formulation of the LHL and focus on the proof technique based on counting ideals generated by differences of random ring elements. Within this framework, we describe both the standard and the leakage-resilient variants of the lemma and present several concrete corollaries. A central aspect of the counting-ideals approach is the probability distribution of ideals generated by random differences of ring elements. Motivated by an open question posed in recent work on LHLs over cyclotomic rings, we investigate this problem in more detail. To gain intuition, small quotient rings are studied computationally. The resulting observations are interpreted in regards of the algebraic structure of the quotient rings and the asymptotic behavior relevant for cryptographic parameter regimes. In particular, the experiments reveal that, in these small settings, the gap between the previously analyzed inclusion probabilities and the actual probabilities of generating a given ideal is dominated by the contribution of the zero idea.