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

Shi Bai; Adeline Langlois; Tancrede Lepoint; Damien Stehle; Ron Steinfeld

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

Shi Bai, Adeline Langlois, Tancrede Lepoint, Damien Stehle, Ron Steinfeld

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

Abstract

The Renyi 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´enyi 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.

Original language	English
Title of host publication	Advances in Cryptology - ASIACRYPT 2015
Subtitle of host publication	21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings Part I
Editors	Tetsu Iwata, Jung Hee Cheon
Place of Publication	Heidelberg [Germany]
Publisher	Springer
Pages	3-24
Number of pages	22
ISBN (Electronic)	9783662487976
ISBN (Print)	9783662487969
Publication status	Published - 2015
Event	International Conference on the Theory and Application of Cryptology and Information Security 2015 - University of Auckland, Auckland, New Zealand Duration: 1 Jan 2015 → … Conference number: 21st https://www.math.auckland.ac.nz/~sgal018/AC2015/index.html

Conference

Conference	International Conference on the Theory and Application of Cryptology and Information Security 2015
Abbreviated title	ASIACRYPT 2015
Country/Territory	New Zealand
City	Auckland
Period	1/01/15 → …
Internet address	https://www.math.auckland.ac.nz/~sgal018/AC2015/index.html

Cite this

Bai, S., Langlois, A., Lepoint, T., Stehle, D., & Steinfeld, R. (2015). Improved security proofs in lattice-based cryptography: Using the Renyi divergence rather than the statistical distance. In T. Iwata, & J. H. Cheon (Eds.), Advances in Cryptology - ASIACRYPT 2015: 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings Part I (pp. 3-24). Springer.

Bai, Shi ; Langlois, Adeline ; Lepoint, Tancrede et al. / Improved security proofs in lattice-based cryptography : Using the Renyi divergence rather than the statistical distance. Advances in Cryptology - ASIACRYPT 2015: 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings Part I. editor / Tetsu Iwata ; Jung Hee Cheon. Heidelberg [Germany] : Springer, 2015. pp. 3-24

@inproceedings{826de793286b4364a77c73bbcb30f34c,

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

abstract = "The Renyi 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´enyi 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.",

author = "Shi Bai and Adeline Langlois and Tancrede Lepoint and Damien Stehle and Ron Steinfeld",

year = "2015",

language = "English",

isbn = "9783662487969",

pages = "3--24",

editor = "Tetsu Iwata and Cheon, \{Jung Hee\}",

booktitle = "Advances in Cryptology - ASIACRYPT 2015",

publisher = "Springer",

address = "Switzerland",

note = "International Conference on the Theory and Application of Cryptology and Information Security 2015, ASIACRYPT 2015 ; Conference date: 01-01-2015",

url = "https://www.math.auckland.ac.nz/\textasciitilde{}sgal018/AC2015/index.html",

}

Bai, S, Langlois, A, Lepoint, T, Stehle, D & Steinfeld, R 2015, Improved security proofs in lattice-based cryptography: Using the Renyi divergence rather than the statistical distance. in T Iwata & JH Cheon (eds), Advances in Cryptology - ASIACRYPT 2015: 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings Part I. Springer, Heidelberg [Germany], pp. 3-24, International Conference on the Theory and Application of Cryptology and Information Security 2015, Auckland, New Zealand, 1/01/15.

Improved security proofs in lattice-based cryptography: Using the Renyi divergence rather than the statistical distance. / Bai, Shi; Langlois, Adeline; Lepoint, Tancrede et al.
Advances in Cryptology - ASIACRYPT 2015: 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings Part I. ed. / Tetsu Iwata; Jung Hee Cheon. Heidelberg [Germany]: Springer, 2015. p. 3-24.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Improved security proofs in lattice-based cryptography

T2 - International Conference on the Theory and Application of Cryptology and Information Security 2015

AU - Bai, Shi

AU - Langlois, Adeline

AU - Lepoint, Tancrede

AU - Stehle, Damien

AU - Steinfeld, Ron

N1 - Conference code: 21st

PY - 2015

Y1 - 2015

N2 - The Renyi 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´enyi 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 Renyi 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´enyi 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.

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

M3 - Conference Paper

SN - 9783662487969

SP - 3

EP - 24

BT - Advances in Cryptology - ASIACRYPT 2015

A2 - Iwata, Tetsu

A2 - Cheon, Jung Hee

PB - Springer

CY - Heidelberg [Germany]

Y2 - 1 January 2015

ER -

Bai S, Langlois A, Lepoint T, Stehle D, Steinfeld R. Improved security proofs in lattice-based cryptography: Using the Renyi divergence rather than the statistical distance. In Iwata T, Cheon JH, editors, Advances in Cryptology - ASIACRYPT 2015: 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings Part I. Heidelberg [Germany]: Springer. 2015. p. 3-24

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

Abstract

Conference

Other files and links