Improved Security Proofs in Lattice-Based Cryptography: Using the Rényi Divergence Rather than the Statistical Distance

The Rényi divergence is a measure of closeness of two probability distributions. We show that it can often be used as an alternative to the statistical distance in security proofs for lattice-based cryptography. Using the Rényi divergence is particularly suited for security proofs of primitives in w...

Full description

Saved in:
Bibliographic Details
Published in:Journal of cryptology 2018-04, Vol.31 (2), p.610-640
Main Authors: Bai, Shi, Lepoint, Tancrède, Roux-Langlois, Adeline, Sakzad, Amin, Stehlé, Damien, Steinfeld, Ron
Format: Article
Language:English
Subjects:
Coding and Information Theory
Combinatorics
Communications Engineering
Computational Mathematics and Numerical Analysis
Computer Science
Cryptography
Cryptography and Security
Divergence
Encryption
Forging
Networks
Probability Theory and Stochastic Processes
Security
Statistical analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Rényi divergence is a measure of closeness of two probability distributions. We show that it can often be used as an alternative to the statistical distance in security proofs for lattice-based cryptography. Using the Rényi divergence is particularly suited for security proofs of primitives in which the attacker is required to solve a search problem (e.g., forging a signature). We show that it may also be used in the case of distinguishing problems (e.g., semantic security of encryption schemes), when they enjoy a public sampleability property. The techniques lead to security proofs for schemes with smaller parameters, and sometimes to simpler security proofs than the existing ones.
ISSN:0933-2790
1432-1378
DOI:10.1007/s00145-017-9265-9