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: Research - peer-reviewArticle

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
Number of pages31
JournalJournal of Cryptology
DOIs
StatePublished - 2018

Keywords

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

Cite this

@article{2819d539805d42cb8f73c723da0a822c,
title = "Improved security proofs in lattice-based cryptography: Using the Renyi divergence rather than the statistical distance",
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.",
keywords = "Lattice-based cryptography, Renyi divergence, Security proofs, Statistical distance",
author = "Shi Bai and Tancrède Lepoint and Adeline Roux-Langlois and Amin Sakzad and Damien Stehle and Ron Steinfeld",
year = "2018",
doi = "10.1007/s00145-017-9265-9",
journal = "Journal of Cryptology",
issn = "0933-2790",
publisher = "Springer Verlag",

}

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, 2018.

Research output: Research - peer-reviewArticle

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

Y1 - 2018

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

JO - Journal of Cryptology

JF - Journal of Cryptology

SN - 0933-2790

ER -