Key Escrow Papers

Two papers about finding better compromises on the subject of key escrow. We suggest and investigate the possibility of having time delays or a computational work factor in key recovery. The first paper, Verifiable partial key escrow, explores the partial key escrow method while the second, Encapsulated key escrow, introduces a new paradigm based on the notion of time capsules.

Verifiable partial key escrow

Authors: M. Bellare and S. Goldwasser

Abstract: One of the main objections to existing proposals for key escrow is that the individual's privacy relies on too high a level of trust in the law enforcement agencies. In particular, even if the government is trustworthy today, it may be replaced by an un-trustworthy government tomorrow which could immediately and suddenly recover the secret keys of all users.

``Partial key escrow'' was suggested to address this concern, in the context of DES keys. Only some part of a user key is escrowed, so that the authority must make a computational effort to find the rest. We extend this idea and provide schemes to perform partial key escrow in a verifiable manner in a public-key encryption setting.

We uncover some subtle issues which must be addressed for any partial key escrow scheme to be secure, the most important of which is the danger of early recovery. We show that other proposals for verifiable partial key escrow suffer from the early recovery problem, and thus do not in fact offer an advantage over standard key-escrow schemes. Our verifiable partial key escrow scheme for the Diffie-Hellman cryptosystem does not suffer from early recovery.

Political debate will not make the user versus law-enforcement conflict on privacy vanish. Today we are seeing corporations, pushed by their business needs, ready to accept some form of key escrow. The realistic and urgent question is to find the form which guarantees the most privacy. Our schemes are candidates.

Ref: Extended abstract in Proc. 4th ACM Conference on Computer and Communications Security, April 1997. Earlier version was Technical Report CS95-447, Department of Computer Science and Engineering, UCSD, October 1995. Full paper available below.

Full paper: Available as compressed postscript or postscript. ( Help if this doesn't work).

Encapsulated key escrow

Authors: M. Bellare and S. Goldwasser

Abstract: The main objection to current key-escrow proposals is that they assume complete faith in the authority and its trustees. If the authority does not follow the rules, or is replaced by an un-trustworthy authority tomorrow, it can immediately recover the secret keys of all users, and embark on massive wiretapping.

We introduce a new approach to key escrow called encapsulated key escrow (EKE). With this approach it is computationally possible for an authority to wiretap individual users, but computationally prohibitive for the authority to launch large scale wiretapping. This is achieved by imposing a time delay between obtaining the escrowed information of a user and actually recovering the secret key. Furthermore, the recoverability is verifiable at escrow time. The approach is applicable both for session keys and for public key cryptography.

EKE is a simple general paradigm, applicable across cryptosystems and key distribution protocols, regardless of their type. It solves in one stroke the problem of imposing time delays in key escrow. In particular it yields the first time delayed key escrow system for RSA, and more efficient solutions for Diffie-Hellman than achievable by the previous approach to time delays, namely partial key escrow (PKE).

The idea behind EKE is a new cryptographic tool called a verifiable cryptographic time capsule (VCTC). This has broader applications to ``sending information into the future.''

Ref: Early version was MIT Laboratory for Computer Science Technical Report 688, April 1996. Full paper of most recent version available below.

Full paper: Available as compressed postscript or postscript. ( Help if this doesn't work).

Related work and links