Paper 2017/480

Sharper Bounds in Lattice-Based Cryptography using the Rényi Divergence

Thomas Prest

Abstract

The Rényi divergence is a measure of divergence between distributions. It has recently found several applications in lattice-based cryptography. The contribution of this paper is twofold. First, we give theoretic results which renders it more efficient and easier to use. This is done by providing two lemmas, which give tight bounds in very common situations { for distributions that are tailcut or have a bounded relative error. We then connect the Rényi divergence to the max-log distance. This allows the Rényi divergence to indirectly benefit from all the advantages of a distance. Second, we apply our new results to five practical usecases. It allows us to claim 256 bits of security for a floating-point precision of 53 bits, in cases that until now either required more than 150 bits of precision or were limited to 100 bits of security: rejection sampling, trapdoor sampling (61 bits in this case) and a new sampler by Micciancio and Walter. We also propose a new and compact approach for table-based sampling, and squeeze the standard deviation of trapdoor samplers by a factor that provides a gain of 30 bits of security in practice.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2017
Keywords
Rényi DivergenceSecurity ProofsLattice-Based CryptographyGaussian Sampling
Contact author(s)
thomas prest @ ens fr
History
2017-09-07: revised
2017-05-30: received
See all versions
Short URL
https://ia.cr/2017/480
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/480,
      author = {Thomas Prest},
      title = {Sharper Bounds in Lattice-Based Cryptography using the Rényi Divergence},
      howpublished = {Cryptology ePrint Archive, Paper 2017/480},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/480}},
      url = {https://eprint.iacr.org/2017/480}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.