Given a Gaussian matrix \(\textbf{X} \) , a Gaussian Leftover Hash Lemma (LHL) states that \(\textbf{X} \cdot \textbf{v} \) for a Gaussian \(\textbf{v} \) is an essentially independent Gaussian sample. It has seen numerous applications in cryptography for hiding sensitive distributions of \(\textbf{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: \(\left\| \textbf{v} \right\| /\left\| \textbf{X} \right\| \) . To this end, we also prove when \(\textbf{X} \) is surjective (assuming the Generalised Riemann Hypothesis) and give bounds on the smoothing parameter of the kernel of \(\textbf{X} \) . We also establish when the resulting distribution is independent of the geometry of \(\textbf{X} \) and establish the hardness of the \(k\) -SIS and \(k\) -LWE problems over modules ( \(k\text {-}\textsf{M}\text {-}\textsf{SIS}/k\text {-}\textsf{M}\text {-}\textsf{LWE} \) ) based on the hardness of SIS and LWE over modules ( \(\textsf{M}\text {-}\textsf{SIS}/\textsf{M}\text {-}\textsf{LWE} \) ) respectively, which was assumed without proof in prior works.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

摘要

Given a Gaussian matrix \(\textbf{X} \) , a Gaussian Leftover Hash Lemma (LHL) states that \(\textbf{X} \cdot \textbf{v} \) for a Gaussian \(\textbf{v} \) is an essentially independent Gaussian sample. It has seen numerous applications in cryptography for hiding sensitive distributions of \(\textbf{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: \(\left\| \textbf{v} \right\| /\left\| \textbf{X} \right\| \) . To this end, we also prove when \(\textbf{X} \) is surjective (assuming the Generalised Riemann Hypothesis) and give bounds on the smoothing parameter of the kernel of \(\textbf{X} \) . We also establish when the resulting distribution is independent of the geometry of \(\textbf{X} \) and establish the hardness of the \(k\) -SIS and \(k\) -LWE problems over modules ( \(k\text {-}\textsf{M}\text {-}\textsf{SIS}/k\text {-}\textsf{M}\text {-}\textsf{LWE} \) ) based on the hardness of SIS and LWE over modules ( \(\textsf{M}\text {-}\textsf{SIS}/\textsf{M}\text {-}\textsf{LWE} \) ) respectively, which was assumed without proof in prior works.