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 journalArticleResearchpeer-review

    47 Citations (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)610-640
    Number of pages31
    JournalJournal of Cryptology
    Volume31
    Issue number2
    DOIs
    Publication statusPublished - Apr 2018

    Keywords

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

    Cite this