SPEAKER: Aristeidis Tentes TITLE: On the (In)Security of RSA signatures AUTHORS: Yevgeniy Dodis, Iftach Haitner and Aristeidis Tentes ABSTRACT: 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. LINKS: