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

Language | English |
---|---|

Pages | 610-640 |

Number of pages | 31 |

Journal | Journal of Cryptology |

Volume | 31 |

Issue number | 2 |

DOIs | |

State | Published - Apr 2018 |

### Keywords

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

### Cite this

*Journal of Cryptology*,

*31*(2), 610-640. DOI: 10.1007/s00145-017-9265-9

}

*Journal of Cryptology*, vol. 31, no. 2, pp. 610-640. DOI: 10.1007/s00145-017-9265-9

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

Research output: Contribution to journal › Article › Research › peer-review

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 -