05264060

a

05264060 Bernstein, Daniel J. Proving tight security for Rabin-Williams signatures. Smart, Nigel (ed.), Advances in cryptology -- EUROCRYPT 2008. 27th annual international conference on the theory and applications of cryptographic techniques, Istanbul, Turkey, April 13--17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78966-6/pbk). Lecture Notes in Computer Science 4965, 70-87 (2008). 2008 Berlin: Springer EN

doi:10.1007/978-3-540-78967-3_5

Summary: 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.