Abstract: In a two-party RSA signature scheme, a client and server, each holding a share of an RSA decryption exponent d, collaborate to compute an RSA signature under the corresponding public key N,e known to both. This primitive is of growing interest in the domain of server-aided password-based security, where the client's share of d is based on its password. To minimize cost, designers are looking at very simple, practical protocols based on the early ideas of Boyd, but their security is unclear. We analyze a class of these protocols. We suggest two notions of security for two-party signature schemes and provide proofs of security for the schemes in our class based on assumptions about RSA and the hash function underlying the scheme.
Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).