Aristeidis Tentes

On the (In)Security of RSA signatures

Yevgeniy Dodis, Iftach Haitner and Aristeidis Tentes

RSA signature is one of the most commonly used "hash-then-sign"
signature scheme, whose security, however, has only been proven in the
Random Oracle Model. This paper studies the problem of instantiating
Random Oracle in the RSA signature with a concrete Hash Function Family.
Our main result is a black box separation between the security RSA
signature (using any concrete, efficient Hash Function Family) and
almost any natural assumption about the RSA modulus n. This includes the
standard RSA assumption and, more generally, any assumption  which can
be expressed using only multiplication and inverse operations in Z_n^*.
Our separation rules out an important class of reductions, namely those
which do not use the representation of group elements (which includes
most standard reductions from RSA to other primitives, including RSA
signatures in the Random Oracle Model).

To complement our negative result, for any fixed t, we construct a Hash
Function Family of size poly(t, log n), which makes RSA signatures
provably secure (under the RSA assumption in the standard model) against
t-chosen message attack.