Verifiable partial key escrow
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. ∗Department of Computer Science & Engineering, Mail Code 0114, University of California at San Diego, 9500 Gilman Drive, La Jolla, California 92093, USA. E-mail: mihir@cs.ucsd.edu. † MIT Laboratory of Computer Science, 545 Technology Square, Cambridge, MA 02139, USA. E-mail: shafi@theory.lcs.mit.edu.