Abstract. The deployment of a public-key infrastructure (PKI) has recently started. Another recent concern in business and on the national level is the issue of escrowed encryption, key recovery, and emergency access to information (e.g., in the medical record area). Independent development of a PKI and an escrowed PKI (whenever required or desired) will pose a lot of constraints, duplication efforts and increased costs of the deployment. It will introduce inter-operability issues which will be hard to overcome. Thus, what we advocate here is a joint design of an escrowed PKI and a regular PKI.

In this work we develop an approach to such an integrated design. We give the first auto-recoverable systems based on RSA (or factoring), whereas the original auto-recoverable auto-certifiable schemes were based on Discrete Logarithm based keys. The security proof of our system assumes only that RSA is hard, while the original schemes required new specific discrete log based assumptions. We also put forth the notion of generic auto-recoverable systems where one can start with an unescrowed user key and then by simply doing re-registration , change the key into an escrowed one. In contrast, in the original systems the user keys were tightly connected with the escrow authorities' key. Besides this novel (re)-registration procedure there are no changes or differences for users between a PKI and a generic auto-recoverable PKI.