A Gaussian Leftover Hash Lemma for Modules over Number Fields

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.