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 proceedingConference PaperResearchpeer-review

    44 Citations (Scopus)

    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 languageEnglish
    Title of host publicationAdvances in Cryptology - ASIACRYPT 2015
    Subtitle of host publication21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings Part I
    EditorsTetsu Iwata, Jung Hee Cheon
    Place of PublicationHeidelberg [Germany]
    PublisherSpringer
    Pages3-24
    Number of pages22
    ISBN (Electronic)9783662487976
    ISBN (Print)9783662487969
    Publication statusPublished - 2015
    EventInternational 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

    ConferenceInternational Conference on the Theory and Application of Cryptology and Information Security 2015
    Abbreviated titleASIACRYPT 2015
    Country/TerritoryNew Zealand
    CityAuckland
    Period1/01/15 → …
    Internet address

    Cite this