Paper 2025/1080

Leftover Hash Lemma(s) Over Cyclotomic Rings

Katharina Boudgoust, CNRS, Univ Montpellier, LIRMM, France
Oleksandra Lapiha, Royal Holloway, University of London, UK
Abstract

In this work, we propose a novel systematic approach for obtaining leftover hash lemmas (LHLs) over cyclotomic rings. Such LHLs build a fundamental tool in lattice-based cryptography, both in theoretical reductions as well as in the design of cryptographic primitives. The scattered set of prior works makes it difficult to navigate the landscape and requires a substantial effort to understand the mathematical constraints under which the LHL holds over cyclotomic rings. This is especially painful if one’s given setting does not fit exactly into prior studies. We argue that all prior approaches boil down to two different proof strategies, resulting in two main theorems. From there on, we are able to recover all previous flavours of seemingly independent LHLs as corollaries. Moreover, we showcase the power of our interpretation by providing new statements, covering mathematical settings not considered before. Our work further proves LHLs in the presence of leakage for both approaches and provides novel bounds for wide families of leakage functions.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Lattice-Based CryptographyLeftover Hash LemmaCyclotomic RingsLeakage
Contact author(s)
katharina boudgoust @ lirmm fr
sasha lapiha 2021 @ live rhul ac uk
History
2025-06-10: approved
2025-06-09: received
See all versions
Short URL
https://ia.cr/2025/1080
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2025/1080,
      author = {Katharina Boudgoust and Oleksandra Lapiha},
      title = {Leftover Hash Lemma(s) Over Cyclotomic Rings},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1080},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1080}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.