A Gaussian Leftover Hash Lemma for Modules over Number Fields

Martin R. Albrecht; Joël Felderhoff; Russell W. F. Lai; Oleksandra Lapiha; Ivy K. Y. Woo

doi:10.1007/978-3-032-25327-9_5

A Gaussian Leftover Hash Lemma for Modules over Number Fields

Martin R. Albrecht
, Joël Felderhoff
, Russell W. F. Lai
, Oleksandra Lapiha
, Ivy K. Y. Woo

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

Abstract

Given a Gaussian matrix X, a Gaussian Leftover Hash Lemma (LHL) states that X·v for a Gaussian v is an essentially independent Gaussian sample. It has seen numerous applications in cryptography for hiding sensitive distributions of v. We generalise the Gaussian LHL initially stated over Z by Agrawal, Gentry, Halevi, and Sahai (2013) to modules over number fields. Our results have a sub-linear dependency on the degree of the number field and require only polynomial norm growth: v/X. To this end, we also prove when X is surjective (assuming the Generalised Riemann Hypothesis) and give bounds on the smoothing parameter of the kernel of X. We also establish when the resulting distribution is independent of the geometry of X and establish the hardness of the k-SIS and k-LWE problems over modules (k-M-SIS/k-M-LWE) based on the hardness of SIS and LWE over modules (M-SIS/M-LWE) respectively, which was assumed without proof in prior works.

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2026 : 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings, Part IV
Editors	Joan Daemen, Emmanuel Thomé
Publisher	Springer
Pages	124-153
Number of pages	30
Volume	4
ISBN (Electronic)	978-3-032-25327-9
ISBN (Print)	978-3-032-25326-2
DOIs	https://doi.org/10.1007/978-3-032-25327-9_5
Publication status	Published - 2026
MoE publication type	A4 Conference publication
Event	Annual International Conference on the Theory and Applications of Cryptographic Techniques - Rome, Italy Duration: 10 May 2026 → 14 May 2026 Conference number: 45

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	16544
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Annual International Conference on the Theory and Applications of Cryptographic Techniques
Abbreviated title	EUROCRYPT
Country/Territory	Italy
City	Rome
Period	10/05/2026 → 14/05/2026

Funding

Martin Albrecht’s and Joël Felderhoff’s work is supported by UKRI grant EP/Y02432X/1. Russell W. F. Lai and Ivy K. Y. Woo are supported by the Research Council of Finland projects No. 358951 and 358950 respectively. Oleksandra Lapiha was supported by the EPSRC and the UK Government as part of the Centre for Doctoral Training in Cyber Security for the Everyday at Royal Holloway, University of London (EP/S021817/1).

Access to Document

10.1007/978-3-032-25327-9_5

https://eprint.iacr.org/2025/1852Licence: CC BY

Cite this

Albrecht, M. R., Felderhoff, J., Lai, R. W. F., Lapiha, O., & Woo, I. K. Y. (2026). A Gaussian Leftover Hash Lemma for Modules over Number Fields. In J. Daemen, & E. Thomé (Eds.), Advances in Cryptology – EUROCRYPT 2026 : 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings, Part IV (Vol. 4, pp. 124-153). (Lecture Notes in Computer Science ; Vol. 16544). Springer. https://doi.org/10.1007/978-3-032-25327-9_5

Albrecht, Martin R. ; Felderhoff, Joël ; Lai, Russell W. F. et al. / A Gaussian Leftover Hash Lemma for Modules over Number Fields. Advances in Cryptology – EUROCRYPT 2026 : 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings, Part IV. editor / Joan Daemen ; Emmanuel Thomé. Vol. 4 Springer, 2026. pp. 124-153 (Lecture Notes in Computer Science ).

@inproceedings{398b1ba870c34948aa28856b2498b069,

title = "A Gaussian Leftover Hash Lemma for Modules over Number Fields",

abstract = "Given a Gaussian matrix X, a Gaussian Leftover Hash Lemma (LHL) states that X·v for a Gaussian v is an essentially independent Gaussian sample. It has seen numerous applications in cryptography for hiding sensitive distributions of v. We generalise the Gaussian LHL initially stated over Z by Agrawal, Gentry, Halevi, and Sahai (2013) to modules over number fields. Our results have a sub-linear dependency on the degree of the number field and require only polynomial norm growth: v/X. To this end, we also prove when X is surjective (assuming the Generalised Riemann Hypothesis) and give bounds on the smoothing parameter of the kernel of X. We also establish when the resulting distribution is independent of the geometry of X and establish the hardness of the k-SIS and k-LWE problems over modules (k-M-SIS/k-M-LWE) based on the hardness of SIS and LWE over modules (M-SIS/M-LWE) respectively, which was assumed without proof in prior works.",

author = "Albrecht, \{Martin R.\} and Jo{\"e}l Felderhoff and Lai, \{Russell W. F.\} and Oleksandra Lapiha and Woo, \{Ivy K. Y.\}",

year = "2026",

doi = "10.1007/978-3-032-25327-9\_5",

language = "English",

isbn = "978-3-032-25326-2",

volume = "4",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "124--153",

editor = "Joan Daemen and Emmanuel Thom{\'e}",

booktitle = "Advances in Cryptology – EUROCRYPT 2026 : 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings, Part IV",

address = "Germany",

note = "Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT ; Conference date: 10-05-2026 Through 14-05-2026",

}

Albrecht, MR, Felderhoff, J, Lai, RWF, Lapiha, O & Woo, IKY 2026, A Gaussian Leftover Hash Lemma for Modules over Number Fields. in J Daemen & E Thomé (eds), Advances in Cryptology – EUROCRYPT 2026 : 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings, Part IV. vol. 4, Lecture Notes in Computer Science , vol. 16544, Springer, pp. 124-153, Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, 10/05/2026. https://doi.org/10.1007/978-3-032-25327-9_5

A Gaussian Leftover Hash Lemma for Modules over Number Fields. / Albrecht, Martin R.; Felderhoff, Joël; Lai, Russell W. F. et al.
Advances in Cryptology – EUROCRYPT 2026 : 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings, Part IV. ed. / Joan Daemen; Emmanuel Thomé. Vol. 4 Springer, 2026. p. 124-153 (Lecture Notes in Computer Science ; Vol. 16544).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - A Gaussian Leftover Hash Lemma for Modules over Number Fields

AU - Albrecht, Martin R.

AU - Felderhoff, Joël

AU - Lai, Russell W. F.

AU - Lapiha, Oleksandra

AU - Woo, Ivy K. Y.

N1 - Conference code: 45

PY - 2026

Y1 - 2026

N2 - Given a Gaussian matrix X, a Gaussian Leftover Hash Lemma (LHL) states that X·v for a Gaussian v is an essentially independent Gaussian sample. It has seen numerous applications in cryptography for hiding sensitive distributions of v. We generalise the Gaussian LHL initially stated over Z by Agrawal, Gentry, Halevi, and Sahai (2013) to modules over number fields. Our results have a sub-linear dependency on the degree of the number field and require only polynomial norm growth: v/X. To this end, we also prove when X is surjective (assuming the Generalised Riemann Hypothesis) and give bounds on the smoothing parameter of the kernel of X. We also establish when the resulting distribution is independent of the geometry of X and establish the hardness of the k-SIS and k-LWE problems over modules (k-M-SIS/k-M-LWE) based on the hardness of SIS and LWE over modules (M-SIS/M-LWE) respectively, which was assumed without proof in prior works.

AB - Given a Gaussian matrix X, a Gaussian Leftover Hash Lemma (LHL) states that X·v for a Gaussian v is an essentially independent Gaussian sample. It has seen numerous applications in cryptography for hiding sensitive distributions of v. We generalise the Gaussian LHL initially stated over Z by Agrawal, Gentry, Halevi, and Sahai (2013) to modules over number fields. Our results have a sub-linear dependency on the degree of the number field and require only polynomial norm growth: v/X. To this end, we also prove when X is surjective (assuming the Generalised Riemann Hypothesis) and give bounds on the smoothing parameter of the kernel of X. We also establish when the resulting distribution is independent of the geometry of X and establish the hardness of the k-SIS and k-LWE problems over modules (k-M-SIS/k-M-LWE) based on the hardness of SIS and LWE over modules (M-SIS/M-LWE) respectively, which was assumed without proof in prior works.

UR - https://www.scopus.com/pages/publications/105040206784

U2 - 10.1007/978-3-032-25327-9_5

DO - 10.1007/978-3-032-25327-9_5

M3 - Conference article in proceedings

SN - 978-3-032-25326-2

VL - 4

T3 - Lecture Notes in Computer Science

SP - 124

EP - 153

BT - Advances in Cryptology – EUROCRYPT 2026 : 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings, Part IV

A2 - Daemen, Joan

A2 - Thomé, Emmanuel

PB - Springer

T2 - Annual International Conference on the Theory and Applications of Cryptographic Techniques

Y2 - 10 May 2026 through 14 May 2026

ER -

Albrecht MR, Felderhoff J, Lai RWF, Lapiha O, Woo IKY. A Gaussian Leftover Hash Lemma for Modules over Number Fields. In Daemen J, Thomé E, editors, Advances in Cryptology – EUROCRYPT 2026 : 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings, Part IV. Vol. 4. Springer. 2026. p. 124-153. (Lecture Notes in Computer Science ). doi: 10.1007/978-3-032-25327-9_5

A Gaussian Leftover Hash Lemma for Modules over Number Fields

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

-: Lattice-based crypto/Lai

Brzuska ICT: Limits of Lattice-based Cryptography: A New Era of Hinted and Structured Assumptions

Cite this

A Gaussian Leftover Hash Lemma for Modules over Number Fields

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Projects

-: Lattice-based crypto/Lai

Brzuska ICT: Limits of Lattice-based Cryptography: A New Era of Hinted and Structured Assumptions

Cite this