A method is provided for an
escrow cryptosystem that is essentially overhead-free, does not require a cryptographic tamper-proof hardware implementation (i.e., can be done in
software), is publicly verifiable, and cannot be used subliminally to enable a shadow public key
system. The keys generated are based on composite numbers (like RSA keys). A shadow public key
system is an unescrowed public key
system that is publicly displayed in a covert fashion. The keys generated by the method are auto-recoverable and auto-certifiable (abbrev. ARC). The ARC
Cryptosystem is based on a
key generation mechanism that outputs a public / private key pair, and a
certificate of proof that the key is recoverable by the
escrow authorities. Each generated public / private key pair can be verified efficiently to be escrowed properly by anyone. The
verification procedure does not use the private key. Hence, the general public has an efficient way of making sure that any given individual's private key is escrowed properly, and the trusted authorities will be able to access the private key if needed. Since the
verification can be performed by anyone, there is no need for a special trusted entity, known in the art as a "
trusted third party". Furthermore, the system is designed so that its internals can be made publicly scrutinizable (e.g., it can be distributed in
source code form). This differs from many schemes which require that the escrowing device be tamper-proof hardware. The system is efficient and can be implemented as a "drop-in" replacement to an RSA or Rabin
cryptosystem. The system is applicable for law-
enforcement, file systems, e-mail systems, certified e-mail systems, and any
scenario in which
public key cryptography can be employed and where private keys or information encrypted under public keys need to be recoverable. Another aspect of the system is the possibility to organize it in a hierarchical
tree structure, where each element in the tree is an
escrow authority (or authorities) capable to recover keys and / or information encrypted under these keys within the subtree rooted at the authority (or authorities) and only within this subtree.