A BRICS Mini-Course
May 1 and 2, 1997
ETH Zurich, Switzerland
In this series of 3 lectures I will give an overview of the recent progress in information-theoretic (i.t.) security in cryptography which has lead to systems and protocols that offer provable security without computational assumptions and can be argued to be practical or at least close to practical. These recent results has come in two different flavors: pessimistic results showing that certain types of protocols or reults are impossible or that the price in terms of secret key is very high, and constructive results for various scenarios (e.g. quantum cryptography, noisy channel scenarios, very large public randomizers, etc.) showing that i.t. security is possible under sometimes surprisingly mild assumptions.
The lectures will guide through various topics, often presenting basic ideas without giving detailed proofs. The noisy channel scenario discussed in the second lecture is demonstrated in an interactive WWW demo at http://www.inf.ethz.ch/department/TI/um/keydemo/.
Ueli Maurer is one of the finest representatives of the line of research that has been establishing new results in provable security in recent years. In particular, he has been one of the key researchers in the development of privacy amplification, the main tool in unconditionally secure key distribution protocols.
The first lecture gives an overview of various aspects of unconditional or information-theoretic security in cryptography, including secrecy, authentication, secret sharing and secure multi-party computation. The basic concepts of information theory are briefly reviewed, but a deep background in information theory is not required for following most of the lectures. Shannon's and Simmons' pessimistic results on perfect secrecy and authenticity, respectively, are reviewed, and some i.t. secure authentication schemes are discussed.
Shannon proved that perfect secrecy (e.g. the one-time pad) requires a secret key of the same length as the plaintext. Several ways of ``cheating around'' Shannon's theorem are discussed in this and the subsequent lectures. One such scenario that will perhaps be addressed in this first lecture is the so-called strongly randomized whose security is based on the sole assumption that an opponent's memory capacity is somewhat smaller that the size of a large random bit string that is either broadcast (for instance by one of the parties or by a satellite) or otherwise available (as the signal from a deep-space radio source). The last part is joint work with Christian Cachin.
This lecture focuses on secret-key agreement, a fundamental problem in cryptography. Two parties Alice and Bob are connected by an insecure but authenticated communication channel and wish to generate a mutual secret key. This is the classical problem solved in the computational model by public-key cryptography. We consider scenarios in which Alice and Bob share no secret key initially but nevertheless can generate, by public discussion, a secret key about which a computationally unbounded eavesdropper Eve overhearing the entire communication between Alice and Bob obtains no information. We mention Wyner's wire-tap channel as an early example and quantum cryptography as a more prominent such scenario, but concentrate on the noisy channel scenario: Alice, Bob, and Eve receive the bits broadcast by a satellite over three independent noisy channels, where Eve's channel can be (by orders of magnitude) less noisy than Alice's and Bob's channels. We present several existence and impossibility results (obtained jointly with Stefan Wolf) for more general scenarios and discuss a very recent result showing that such secret key agreement can be possible even when the public channel is NOT authenticated.
This lecture gives a general treatment of privacy amplification by public discussion, a concept introduced in 1985 by Bennett, Brassard and Robert for a special scenario. Privacy amplification is a fundamental final step in information-theoretically secure key agreement protocols. It allows two parties Alice and Bob to distill a secret key from a common random variable about which an eavesdropper Eve has partial information. Alice and Bob generally know nothing about Eve's information except that it satisfies a certain constraint, for instance a lower bound on the Renyi entropy. The concept of ``spoiling knowledge'' is introduced as a technique for proving better and sometimes optimal lower bounds on Eve's information about the secret key.
The lecture is based on joint work with Bennett, Brassard, and Crépeau. We also discuss recent results obtained jointly with Stefan Wolf showing that privacy amplification is possible even when the public discussion channel is not authenticated and hence completely insecure.
The course will be accessible to anyone in theoretic computer science, in particular a strong background in cryptography is not necessary.