Proving tight security for Rabin-Williams signatures

D.J. Bernstein

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    41 Citations (Scopus)


    This paper proves "tight security in the random-oracle model relative to factorization" for the lowest-cost signature systems available today: every hash-generic signature-forging attack can be converted, with negligible loss of efficiency and effectiveness, into an algorithm to factor the public key. The most surprising system is the "fixed unstructured B = 0 Rabin-Williams" system, which has a tight security proof despite hashing unrandomized messages.
    Original languageEnglish
    Title of host publicationAdvances in cryptology - eurocrypt 2008 : 27th annual international conference on the Theory and applications of cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008 : proceedings
    EditorsN. Smart
    Place of PublicationBerlin
    ISBN (Print)978-3-540-78966-6
    Publication statusPublished - 2008

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    Dive into the research topics of 'Proving tight security for Rabin-Williams signatures'. Together they form a unique fingerprint.

    Cite this