Improved security proofs in lattice-based cryptography: Using the Renyi divergence rather than the statistical distance

Shi Bai, Tancrède Lepoint, Adeline Roux-Langlois, Amin Sakzad, Damien Stehle, Ron Steinfeld

Research output: Contribution to journalArticle

Abstract

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.

LanguageEnglish
Pages610-640
Number of pages31
JournalJournal of Cryptology
Volume31
Issue number2
DOIs
StatePublished - Apr 2018

Keywords

  • Lattice-based cryptography
  • Renyi divergence
  • Security proofs
  • Statistical distance

Cite this

Bai, Shi ; Lepoint, Tancrède ; Roux-Langlois, Adeline ; Sakzad, Amin ; Stehle, Damien ; Steinfeld, Ron. / Improved security proofs in lattice-based cryptography : Using the Renyi divergence rather than the statistical distance. In: Journal of Cryptology. 2018 ; Vol. 31, No. 2. pp. 610-640
@article{2819d539805d42cb8f73c723da0a822c,
title = "Improved security proofs in lattice-based cryptography: Using the Renyi divergence rather than the statistical distance",
abstract = "The R{\'e}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{\'e}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.",
keywords = "Lattice-based cryptography, Renyi divergence, Security proofs, Statistical distance",
author = "Shi Bai and Tancr{\`e}de Lepoint and Adeline Roux-Langlois and Amin Sakzad and Damien Stehle and Ron Steinfeld",
year = "2018",
month = "4",
doi = "10.1007/s00145-017-9265-9",
language = "English",
volume = "31",
pages = "610--640",
journal = "Journal of Cryptology",
issn = "0933-2790",
publisher = "Springer-Verlag London Ltd.",
number = "2",

}

Improved security proofs in lattice-based cryptography : Using the Renyi divergence rather than the statistical distance. / Bai, Shi; Lepoint, Tancrède; Roux-Langlois, Adeline; Sakzad, Amin; Stehle, Damien; Steinfeld, Ron.

In: Journal of Cryptology, Vol. 31, No. 2, 04.2018, p. 610-640.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Improved security proofs in lattice-based cryptography

T2 - Journal of Cryptology

AU - Bai,Shi

AU - Lepoint,Tancrède

AU - Roux-Langlois,Adeline

AU - Sakzad,Amin

AU - Stehle,Damien

AU - Steinfeld,Ron

PY - 2018/4

Y1 - 2018/4

N2 - 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.

AB - 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.

KW - Lattice-based cryptography

KW - Renyi divergence

KW - Security proofs

KW - Statistical distance

UR - http://www.scopus.com/inward/record.url?scp=85028567499&partnerID=8YFLogxK

U2 - 10.1007/s00145-017-9265-9

DO - 10.1007/s00145-017-9265-9

M3 - Article

VL - 31

SP - 610

EP - 640

JO - Journal of Cryptology

JF - Journal of Cryptology

SN - 0933-2790

IS - 2

ER -