Welcome to the resource topic for 2025/1852
Title:
A Gaussian Leftover Hash Lemma for Modules over Number Fields
Authors: Martin R. Albrecht, Joël Felderhoff, Russell W. F. Lai, Oleksandra Lapiha, Ivy K. Y. Woo
Abstract:Leftover Hash Lemma (LHL) states that (\mathbf{X} \cdot \mathbf{v}) for a Gaussian (\mathbf{v}) is an essentially independent Gaussian sample. It has seen numerous applications in cryptography for hiding sensitive distributions of (\mathbf{v}). We generalise the Gaussian LHL initially stated over (\mathbb{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: (\lVert\mathbf{v}\rVert/\lVert\mathbf{X}\rVert). To this end, we also prove when (\mathbf{X}) is surjective (assuming the Generalised Riemann Hypothesis) and give bounds on the smoothing parameter of the kernel of (\mathbf{X}). We also establish when the resulting distribution is independent of the geometry of (\mathbf{X}) and establish the hardness of the (k)-SIS and (k)-LWE problems over modules ((k)-MSIS/(k)-MLWE) based on the hardness of SIS and LWE over modules (MSIS/MLWE) respectively, which was assumed without proof in prior works.
ePrint: https://eprint.iacr.org/2025/1852
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .