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.
Category / Keywords: public-key cryptography / Rényi Divergence, Security Proofs, Lattice-Based Cryptography, Gaussian Sampling Date: received 29 May 2017 Contact author: thomas prest at ens fr Available format(s): PDF | BibTeX Citation Version: 20170530:001139 (All versions of this report) Short URL: ia.cr/2017/480 Discussion forum: Show discussion | Start new discussion