Binding Cryptography.
A fraud-detectible alternative to key-escrow proposals

(c) 1996 Eric Verheul, Bert-Jaap Koops, Henk van Tilborg
The text of this page may only be redistributed in its entirety and with inclusion of the copyright notice.
Please credit if quoting.

We introduce binding cryptography, a new proposal for establishing an information security infrastructure that does not hamper law-enforcement. We present an alternative that can give law-enforcement agencies access to session keys, without users having to deposit private keys. Unilateral fraud in this scheme is easily detectible. We outline the proposal below, and announce two articles which will describe the proposal in more detail and which will provide the legal and the technical context.

Eric Verheul, e-mail Eric.Verheul@pobox.com
Bert-Jaap Koops, e-mail E.J.Koops@kub.nl
Henk van Tilborg, e-mail henkvt@win.tue.nl

Binding Cryptography
a fraud-detectible alternative to key-escrow proposals

1. Introduction

Information security, and so cryptography, is essential in today's information society. A robust (information) security infrastructure must be set up, including a Key Management Infrastructure. However, the unconditional use of encryption by criminals poses a threat to law enforcement, a problem that is hard to solve. Consequently, governments have two tasks. The first is stimulating the establishment of a security structure that protects their citizens, but which does not aid criminals. The second task is coping with the use of encryption by criminals outside of this framework. We think that encryption outside of the framework (e.g., PGP) should not be outlawed - but it need not be mainstream either. It is crucial that any such established security structure is widely accepted and trusted, as this will lower the demand for encryption outside of this framework, and so will make the second goal easier to achieve (or, at least, not more difficult). The establishment of such a widely accepted and trusted security structure is now the challenge that (US) IT businesses face if they want to participate in the recent CLIPPER IV initiative.

2. Binding cryptography

In a series of two articles, we address the establishment of an information security infrastructure. Several proposals have been made by governments and others to establish such an infrastructure, but a satisfactory overall solution remains yet to be found. In the non-technical article [VKT], we review several technical proposals and a few government initiatives, focusing on key-escrow proposals. We present a series of criteria that acceptable solutions should meet, and note that all proposals so far fail to meet many of these criteria. We argued that the establishment of a worldwide security infrastructure can not be achieved without strong cooperation of governments. In fact, governments themselves should take up the challenge of establishing a security infrastructure, based on public-key encryption, which does not hamper law enforcement. We offer a new solution to achieve this: "binding data", which also improves upon current proposals. It has the advantage that it helps the establishment of a strong security infrastructure which discourages abuse for criminal or subversive purposes by making unilateral abuse easily detectible. It allows a straightforward monitoring of compliance with law-enforcement regulations, without users having to deposit ("escrow") keys beforehand. Thus, an information security infrastructure can be established, which does not worsen the crypto problem for law enforcement.

Metaphorically speaking, our solution consists of equipping public-key encryption systems used for confidentiality with a (car) governor (a speed-limiting device). The specifications of this governor are rather general, and so many systems can probably be equipped with them. It is inspired by the proposal of Bellare and Rivest [BR], in which users' encrypted messages consist of three components:

  1. the (actual) message encrypted with any symmetric system, using a random session key;
  2. the session key encrypted with the public key(s) of the addressee(s);
  3. the session key encrypted with the public key of a Trusted Retrieval Party (TRP).

In effect, the TRP is treated as a virtual addressee, although the message is not sent to it. When a law-enforcement agency is conducting a lawful intercept and strikes upon an enciphered message, they take the third information component to the TRP. If shown an appropriate warrant, the TRP decrypts the information component and hands over the session key, so that the law-enforcement agency has access to the message. Observe that users are not obliged to escrow their (master) keys, they only give access to the (temporary) session keys used in the communication. The concept of "virtual escrow" has been the base of several escrow products (AT&T; Crypto, RSA Secure, TIS Commercial Key Escrow).

The main drawback of this concept is that it offers no possibility, at least for others than the TRP, to check whether the third component actually contains the (right) session key; moreover, the TRP will only discover fraud after a lawful wiretap. This renders the solution almost entirely unenforceable.

Therefore, we propose a binding alternative, which adds a fourth component to the encrypted message: 4. binding data.

The idea is that any third party, e.g., a network or service provider, who has access to components 2, 3 and 4 (but not to any additional secret information) can:
a. check whether the session keys in components 2 and 3 coincide;
b. not determine any information on the actual session key.

In this way, fraud is easily detectible: a sender that attempts to virtually address a session key to the TRP (component 3) that is different from the real one he uses on the message (or just non-sense) will be discovered by anyone checking the binding data. If such checking happens regularly, fraud can be properly discouraged and punished. The binding concept supports the virtual addressing of session keys to several TRPs (or none for that matter), for instance, one to a TRP in the country of the sender and one in the country of the addressee. The solution therefore offers the same advantage for worldwide usability as the Royal Holloway [Holl]concept. We also remark that the concept supports the use of controllable key splitting in the sense of Micali [Mica] as well: a sender can split the session key and virtually address all the shares separately to the addressee and various TRPs using the binding concept. Moreover, the number of shares and the TRPs can - in principle - be chosen freely by each user. Finally we remark that the time-boundedness conditon (the enforceability of the timelimits of a warrant) can be fulfilled by additionally demanding that encrypted information (or all components) be timestamped and signed by the sender; a condition that can be publicly verified by any third party (e.g., monitor) as well.

A PKI that incorporates binding data hence has the following four players:

In [VKT], we explain how we envision the framework in which the binding concept could present a security tool in the information society. We think the concept is flexible enough (e.g., in the choice of TRPs) to be incorporated into almost any national crypto policy, on both the domestic and foreign use of cryptography.

In a mathematical paper [VT], Verheul and Van Tilborg propose a technical construction for binding data for an important public-key encryption system: ElGamal. This construction is compatible with Desmedt's [DESM] traceable variant of ElGamal. The construction is based on the techniques used in zero knowledge proofs. We expect that these constructions can be improved and that various other public-key encryption systems can be equipped with binding data. We present this as a challenge to the cryptographic research community.

Here is an outline of the mathematical construction of binding ElGamal.

3. References

[BR]
M. Bellare, R.L. Rivest, Translucent Cryptography. An Alternative to Key Escrow, and its Implementation via Fractional Oblivious Transfer
[Desm]
Y. Desmedt, "Securing Traceability of Ciphertexts - Towards a Secure Key Escrow System", Advances in Cryptology - EUROCRYPT'95 Proceedings, Springer-Verlag, 1995, pp.147-157.
[Holl]
N. Jefferies, C. Mitchell, M. Walker, A Proposed Architecture for Trusted Third Party Services, Royal Holloway, University of London. In: Cryptography: Policy and Algorithms - Proceedings: International Conference, Brisbane, Australia, July 1995. Springer-Verlag LNCS 1029, 1996, pp.98-104.
[Mica]
S. Micali, "Fair Public-key Cryptosystems'", Advances in Cryptology - CRYPTO '92 Proceedings, Springer-Verlag, 1993, pp. 113-138.
[VKT]
E. Verheul, B.J. Koops, H.C.A. van Tilborg, "Binding Cryptography. A fraud-detectible alternative to key-escrow solutions", Computer Law and Security Report, January-February 1997, pp. 3-14.
[VT]
E. Verheul, H.C.A. van Tilborg, "Binding ElGamal. A fraud-detectible alternative to key-escrow solutions", will be presented at Eurocrypt 97. A summary is available online.

Send comments and questions on this scheme to Eric Verheul or Bert-Jaap Koops.
This page was last updated by Bert-Jaap Koops on 15 April 1997
Homepage