Skip to main navigation Skip to search Skip to main content

Optimal security proofs for Full Domain Hash, revisited

  • Saqib A. Kakvi*
  • , Eike Kiltz
  • *Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

    53 Citations (Scopus)

    Abstract

    RSA Full Domain Hash (RSA-FDH) is a digital signature scheme, secure again chosen message attacks in the random oracle model. The best known security reduction from the RSA assumption is nontight, i.e., it loses a factor of q s , where q s is the number of signature queries made by the adversary. It was furthermore proved by Coron (EUROCRYPT 2002) that a security loss of q s is optimal and cannot possibly be improved. In this work we uncover a subtle flaw in Coron's impossibility result. Concretely, we show that it only holds if the underlying trapdoor permutation is certified. Since it is well known that the RSA trapdoor permutation is (for all practical parameters) not certified, this renders Coron's impossibility result moot for RSA-FDH. Motivated by this, we revisit the question whether there is a tight security proof for RSA-FDH. Concretely, we give a new tight security reduction from a stronger assumption, the Phi-Hiding assumption introduced by Cachin et al (EUROCRYPT 1999). This justifies the choice of smaller parameters in RSA-FDH, as it is commonly used in practice. All of our results (positive and negative) extend to the probabilistic signature scheme PSS.

    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Pages537-553
    Number of pages17
    Volume7237 LNCS
    DOIs
    Publication statusPublished - 2012
    Event31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2012 - Cambridge, United Kingdom
    Duration: 15 Apr 2012 → 19 Apr 2012

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume7237 LNCS
    ISSN (Print)03029743
    ISSN (Electronic)16113349

    Conference

    Conference31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2012
    Country/TerritoryUnited Kingdom
    CityCambridge
    Period15/04/12 → 19/04/12

    Fingerprint

    Dive into the research topics of 'Optimal security proofs for Full Domain Hash, revisited'. Together they form a unique fingerprint.

    Cite this