Paper 2023/479

Spherical Gaussian Leftover Hash Lemma via the Rényi Divergence

Hiroki Okada, KDDI Research (Japan)
Kazuhide Fukushima, KDDI Research (Japan)
Shinsaku Kiyomoto, KDDI Research (Japan)
Tsuyoshi Takagi, The University of Tokyo
Abstract

Agrawal et al. (Asiacrypt 2013) proved the discrete Gaussian leftover hash lemma, which states that the linear transformation of the discrete spherical Gaussian is statistically close to the discrete ellipsoid Gaussian. Showing that it is statistically close to the discrete spherical Gaussian, which we call the discrete spherical Gaussian leftover hash lemma (SGLHL), is an open problem posed by Agrawal et al. In this paper, we solve the problem in a weak sense: we show that the distribution of the linear transformation of the discrete spherical Gaussian and the discrete spherical Gaussian are close with respect to the Rényi divergence (RD), which we call the weak SGLHL (wSGLHL). As an application of wSGLHL, we construct a sharper self-reduction of the learning with errors problem (LWE) problem. Applebaum et al. (CRYPTO 2009) showed that linear sums of LWE samples are statistically close to (plain) LWE samples with some unknown error parameter. In contrast, we show that linear sums of LWE samples and (plain) LWE samples with a known error parameter are close with respect to RD. As another application, we weaken the independence heuristic required for the fully homomorphic encryption scheme TFHE.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. ACNS 2023
Keywords
LatticeLWEDiscrete GaussianLeftover hash lemma
Contact author(s)
ir-okada @ kddi com
History
2023-04-05: approved
2023-04-03: received
See all versions
Short URL
https://ia.cr/2023/479
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/479,
      author = {Hiroki Okada and Kazuhide Fukushima and Shinsaku Kiyomoto and Tsuyoshi Takagi},
      title = {Spherical Gaussian Leftover Hash Lemma via the Rényi Divergence},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/479},
      year = {2023},
      url = {https://eprint.iacr.org/2023/479}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.