Topics in Contemporary Cryptography

Professor Ronald Cramer (BRICS - Dept. of Computer Science, Aarhus University, Denmark) will teach a postgraduate course entitled Topics in Contemporary Cryptography. This course is supported by the Spanish Ministerio de Educación, Cultura y Deporte and is is a part of the Seminar on Mathematics Applied to Cryptography.

Timetable

The course will be held from 7 to 16 January 2003. There will be eight sessions:

7, 8, 9 January 2003 and 13, 14, 15, 16 January 2003, from 3 pm to 6 pm with 1/2 hour coffee break.
10 January 2003, from 11 am to 1.30 pm.
On thursday 9 January 2003, after the course, there will be a special session, in which the participants may present their current research in five minutes talks.

Location

Hall 005 in building C3 in the Campus Nord of the Universitat Politècnica de Catalunya in Barcelona.

List of key-words

Public-key crypto-systems, security against adaptive chosen cipher-text attack, Cramer-Shoup scheme, universal hash proof systems, information theoretically secure multi-party computations, verifiable secret sharing, linear secret sharing, black-box secret sharing over Abelian groups.

Abstract

This graduate-level course consists of two parts:

I. Securing Crypto-Systems against Active Attacks

The goal in this series of lectures is to review the theory of public-key crypto-systems and their security, and to discuss recent results on practical public-key crypto-systems that enjoy the highest level of security for such systems.

We will start by reviewing the existing theory. This includes semantic security, security against adaptive chosen cipher-text attack, and an overview of theoretical constructions of encryption schemes, based on trapdoor one-way functions and non-interactive zero-knowledge.

We then discuss in detail a new paradigm (Cramer/Shoup, 2001/2002) for the construction of practical public-key crypto-systems that are secure against adaptive chosen cipher-text attack. This is the highest level of security for such scheme. The Cramer-Shoup scheme (1998), which, up to know, was the only practical public-key crypto-system proven secure against adaptive chosen cipher-text attack under a ``reasonable'' intractability assumption, namely the Decisional Diffie/Hellman assumption, is an instance of the new paradigm, as we will also show in the lectures.

II. The Algebra of Secure Multi-Party Computations

Secure multi-party computation (MPC) can be defined as the problem of n players computing an agreed function of their inputs in a secure way, where security means guaranteeing the correctness of the output as well as the privacy of the players' inputs, even when some players cheat. Motivating examples for MPC include electronic voting, distributed signatures and decryption, and so forth.

We will discuss the following topics.

Shamir's classical secret sharing scheme.
Sudan's error correction algorithm based on Bezout's Theorem.
Optimal black-box secret sharing over arbitrary Abelian groups. A secret sharing scheme that always blindly works, over any group! This is based on a weak form of interpolation over conveniently chosen low degree algebraic number fields. (Cramer/Fehr).
Verifiable Secret Sharing (VSS). This extends the ideas behind Shamir's scheme so as to tolerate arbitrarily malicious parties.
The classical (1988) theoretical results of Ben-Or, Goldwasser Wigderson and Chaum, Crépeau, Damgaard which show that even if < n / 3 players are corrupted by an active adversary, any function can be securely computed. No intractability assumptions are needed.
Constructing MPC protocols from linear secret sharing schemes (Cramer/Damgaard/Maurer).

Back to MAK's main page

Last Update: December 18, 2002