From: "Bert-Jaap Koops" <E.J.Koops@kub.nl>
Date: Wed, 9 Oct 1996 06:01:38 -0700 (PDT)
To: cypherpunks@toad.com
Subject: Binding cryptography - a fraud-detectible alternative to key-esc
Message-ID: <736E4C76D98@frw3.kub.nl>
MIME-Version: 1.0
Content-Type: text/plain


In this message, 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.

The text is also available at
http://cwis.kub.nl/~frw/people/koops/binding.htm.

9 October 1996
Eric Verheul, everheul@ngi.nl
Bert-Jaap Koops, koops@kub.nl
Henk van Tilborg, henkvt@win.tue.nl

-------------------------------------------

(c) 1996 Eric Verheul, Bert-Jaap Koops, Henk van Tilborg
This message may only be redistributed in its entirety and with
inclusion of the copyright notice. Credit if quoting.

_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 nonsense)
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: 
- Users, i.e., governments, businesses, and citizens, 
- TTPs offering trusted services (e.g., time-stamping and certification of
public keys), 
- TRPs aiding law-enforcement agencies with decrypting legally intercepted messages, 
- Monitors, monitoring communications encrypted via the PKI on compliance with 
binding regulations. For instance, these could be network operators or (Internet) service
providers.

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.

An outline of the mathematical construction of binding ElGamal can be
found at http://cwis.kub.nl/~frw/people/koops/bindtech.htm.


_3. References_

[BR]	
M. Bellare, R.L. Rivest, "Translucent Cryptography. An Alternative to
Key Escrow, and its Implementation via Fractional Oblivious Transfer",
see http://theory.lcs.mit.edu/~rivest

[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,
see http://platon.cs.rhbnc.ac.uk

[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, to appear. [*]

[VT]
E. Verheul, H.C.A. van Tilborg, "Binding ElGamal. A fraud-detectible
alternative to key-escrow solutions", will be submitted to
Eurocrypt97.

[*] For the Computer Law and Security Report, send subscription
enquiries, orders and payments to:

Pam Purvey
The Oxford Fulfilment Centre
PO Box 800, Kidlington
Oxford 0X5 1DX  UK
Tel: +44 1865 843373
Fax: +44 1865 843940

For the United States:
Elsevier Advanced Technology
Fulfilment (enquiries)
660 White Plains Road, Tarrytown
New York, NY 10591-5153
USA 
Tel: 914 333 2458

---------------------------------------------------------------------
Bert-Jaap Koops                         tel     +31 13 466 8101
Center for Law, Administration and      facs    +31 13 466 8149
Informatization, Tilburg University     e-mail  E.J.Koops@kub.nl
                  --------------------------------------------------
Postbus 90153    |  This world's just mad enough to have been made  |
5000 LE Tilburg  |    by the Being his beings into being prayed.    |
The Netherlands  |                (Howard Nemerov)                  |
---------------------------------------------------------------------
         http://cwis.kub.nl/~frw/people/koops/bertjaap.htm
---------------------------------------------------------------------