Constructive Cryptography

Ueli Maurer is Professor of Computer Science at ETH Zurich and member of the advisory board of the CAS Research Focus „Physics and Security". | Modularization is a key principle in any constructive discipline. One wants to obtain complex constructions as the composition of simpler, modular construction steps, where each step constructs an object satisfying a certain specification from other objects satisfying certain (weaker) specifications. This principle can be captured abstractly by an algebraic specification theory in which the objects of interest are specifications (for example, in a concrete instantiation, specifications of probabilistic discrete systems). The set of specifications form an algebra equipped with a lattice structure. Many relevant concepts like constructions, relaxations, projections, etc., are specification homomorphisms. Goals of such an abstract approach are simplicity (or even minimality), maximal generality and reusability, and the definition of a set of rewriting rules allowing to derive new facts from given facts. One of the goals of such a theory is the suitability for formal proofs. Constructive cryptography is an instantiation of such a specification theory in which cryptographic methods can be understood (and defined) as construction step. For example, a secure encryption scheme constructs a secure channel from an authenticated channel and a shared secret key. The design of cryptographic protocols corresponds to the composition of such construction steps, where for example the shared secret key needed in the above construction can itself be constructed, e.g. by a key agreement protocol. The security proof for the protocol is then simply a consequence of the security proofs of the individual steps. In his talk Ueli Maurer gives a self-contained introduction to constructive cryptography suitable for a non specialist audience, presents many recent new developments, and shows how the theory applies to other areas.