Course Contents
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/.
- Lecture I: Information-theoretic security: an overview
- 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.
- Lecture II: Secret-key agreement by public discussion
- 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.
- Lecture III: Privacy amplification
- 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.
![[BRICS symbol]](http://www.brics.dk/GIF/BRICS/msymbol8mm.GIF)
BRICS WWW home page