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.
|Title of host publication||Advances in cryptology - eurocrypt 2008 : 27th annual international conference on the Theory and applications of cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008 : proceedings|
|Place of Publication||Berlin|
|Publication status||Published - 2008|
|Name||Lecture Notes in Computer Science|