Proactive Two-Party Signatures for User Authentication

We study proactive two-party signature schemes in the context of user authentication. A proactive two-party signature scheme (P2SS) allows two parties—the client and the server—jointly to produce signatures and periodically to refresh their sharing of the secret key. The signature generation remains secure as long as both parties are not compromised between successive refreshes. We construct the first such proactive scheme based on the discrete log assumption by efficiently transforming Schnorr’s popular signature scheme into a P2SS. We also extend our technique to the signature scheme of Guillou and Quisquater (GQ), providing two practical and efficient P2SSs that can be proven secure in the random oracle model under standard discrete log or RSA assumptions. We demonstrate the usefulness of P2SSs (as well as our specific constructions) with a new user authentication mechanism for the Self-certifying File System (SFS) [28]. Based on a new P2SS we call 2Schnorr, the new SFS authentication mechanism lets users register the same public key in many different administrative realms, yet still recover easily if their passwords are compromised. Moreover, an audit trail kept by a secure authentication server tells users exactly what file servers an attacker may have accessed—including even accounts the user may have forgotten about.