Abstracts of the Keynotes and Tutorials

KEYNOTE: List error-correction: New constructions and algorithms

Speaker: Venkatesan Guruswami

Affiliation: University of Washington

Abstract:
The construction of error-correcting codes that achieve the best possible trade-off between information rate and the amount of errors that can be corrected has been a long sought-after goal. In this talk, I will survey some of our work on list decoding, culminating in the construction of codes with the optimal rate for any desired error-correction radius. I will describe these codes (called folded Reed-Solomon codes), and give a peek into the algebraic ideas underlying their error-correction. The new algorithms correct a factor of two more errors compared to the conventional algorithms currently used in every CD player and desktop PC, as well as many other applications that impact our daily lives.

Further, the newly discovered codes admit a "soft" decoding algorithm that can utilize channel reliability estimates on codeword symbols in a powerful way. This is an attractive feature in practice, and also very useful in concatenation schemes. Exploiting this, we construct binary codes with the currently best known trade-off between list decoding radius and information rate.

KEYNOTE: Beyond the 80 bit barrier

Speaker: Nigel Smart

Affiliation: University of Bristol

Abstract:
With the advent of AES nearly eight years ago, and the factoring of a "special" 1024 bit number in 2007, the world is now seriously adopting elliptic curve cryptography. This talk will present a number of practical issues associated with turning some mathematics into a real world implementation. In addition I will survey a number of systems currently in use which use elliptic curves.

TUTORIAL: Algebraic Function Fields and Applications in Coding Theory

Speaker: Alp Bassa

Affiliation: EPF Lausanne

Abstract:
In this tutorial we will give an introduction to the theory of functions fields in one variable and try to exhibit some of its applications in coding theory and cryptography. We will start by introducing the basic concepts. Since it is a fundamental result on which the rest of the theory heavily depends, the theorem of Riemann-Roch will be treated in detail. Furthermore we will describe the correspondence between curves and function fields in one variable and, in fact, will use both languages interchangably. We will also explore the exciting analogy with number fields.

Next we will consider applications to coding theory. Around 1980, Goppa introduced a construction of error-correcting codes using curves over finite fields, which resulted in a renewed interest in these curves and their rational points. We will try to explain this beautiful application of algebraic geometry in coding theory.

Motivated by applications in coding theory and cryptography, but also for its own intrinsic interest, we will continue with the study of rational points on curves over finite fields. Although the Riemann Hypothesis for the classical Riemann zeta function is still an open question, its analogue in the case of function fields has already been proved by Hasse (for elliptic curves, in 1933) and by Weil (for curves of any genus, in the 1940's). It is directly related with the number of rational points on these curves. Hence we will study the Riemann Hypothesis for curves over finite fields and some of its consequence.

TUTORIAL: Public key encryption from a mathematical perspective

Speaker: Dennis Hofheinz

Affiliation: CWI Amsterdam

Abstract:
We introduce the concept of encryption schemes from a mathematical perspective. In the process, we take care to hint at common pitfalls in the design and analysis of encryption schemes.

After an informal motivation of public key cryptography, we will start by discussing the public key cryptosystem Polly Cracker. This scheme, introduced by Fellows and Koblitz as an alternative to the established RSA- and Diffie-Hellman-based encryption schemes, has several interesting properties. First, it is conceptually amazingly simple. Second, it uses multivariate polynomials instead of finite fields or rings, so attacks on other cryptosystems are unlikely to apply to Polly Cracker. Third, computing the secret key of Polly Cracker is NP-hard in general, something which currently cannot be proven about RSA- or Diffie-Hellman-based schemes. However, we will present a number of easy concrete attacks on Polly Cracker. This will not only exemplify several typical shortcomings of informal security analyses of encryption schemes. It will also motivate the need for a formal definition of security.

We will proceed to give formal security definitions for encryption schemes, and will show how to achieve them. In particular, we will use security reductions, as introduced by Goldwasser and Micali in a ground-breaking work from 1982. In a security reduction, the formal security of the investigated system is reduced to a computational assumption (like, e.g., the hardness of factoring large numbers). Security reductions are a powerful technical tool, as they enable modularity: e.g., encryption schemes can be designed and analyzed with abstract building blocks, such as an abstract trapdoor one-way permutation. Once this is done, it is possible to focus on finding instantiations of these building blocks. There is no need to design a whole system from scratch. We will exemplify this approach with several constructions. In particular, as time permits, we will discuss a generic system due to Goldwasser and Micali, Rabin's variant of the RSA encryption system, the ElGamal encryption scheme, and an encryption scheme due to Cramer and Shoup.

This tutorial assumes only basic knowledge about algebra and group theory. Previous knowledge about cryptography is helpful but not necessary.

TUTORIAL: Quantum Information Theory & Crypto:

Speaker: Serge Fehr

Affiliation: CWI Amsterdam

Abstract:
The goal of cryptography is to provide tools for securing private information and preventing critical operations from adversarialy provoked malfunction. These are very crucial objectives in today's society where information plays a fundamental role. However, most of today's cryptography relies on unproven complexity assumptions (like the hardness of factoring large numbers) in combination with the assumption that an attacker has not overwhelming computing power. This approach leads to very practical schemes but obviously has its dangers. Not only might the underlying complexity assumption be broken from one day to another (e.g. by an efficient factoring algorithm being discovered), but also with the increasing advances in computer technology it is not unlikely that cryptosystems that are secure today can be broken in 10, 20 or 30 years, and thus that information that is used today in a "secure" way may be compromised in the not too distant future. Furthermore, a quantum computer would make most of the commonly used cryptographic schemes insecure. This clearly poses a serious threat to long-term highly-sensitive data.

There are a few approaches in order to (try to) circumvent the need for relying on unproven complexity assumptions and in order to achieve "everlasting" security. One of the most promising ones is quantum cryptography. Quantum cryptography investigates the (im)possibilities in using quantum-mechanical principles for cryptographic purposes to achieve provable security. A main tool is Heisenberg's Uncertainty Principle, which essentially states that no information can be learned about a quantum state (for instance the polarization of a single photon) without disturbing it. This was for instance used by Bennett and Brassard in 1984 to show that two mutually-trusted entities (which don't share any secret information to start with) can agree on a secret key solely by public communication, i.e., such that a potential attacker who evesdrops the full communication (and which may have infinite computing power) does not learn any information on the agreed-upon secret key. This is well-known to be (provably) impossible without using quantum effects and without any additional assumption.

Other cryptographic tasks, like secure identification, can also be achieved by quantum cryptographic means, without assuming a limit on the attacker's computation power, but instead by assuming a limit on his quantum memory. Thus, in order to break the cryptographic scheme, the attacker does not need to solve some believed-to-be-hard computational problem, but has to store a large quantum state during the execution of the scheme. This still avoids having to rely security on unproven complexity assumptions, and it allows for schemes with everlasting security: even if the attacker should be able to store a sufficiently large quantum state sometime in the future, this will be too late to break the scheme "in retrospect" as the crucial (quantum) information is already lost during the execution. Furthermore, assuming that a potential attacker has limited quantum storage capacity is a very realistic assumption since storing quantum states is an extremely difficult task: storing even a few qubits (i.e. elementary quantum states) for a small fraction of a second requires enormous machinery.

In this tutorial, I give a suitable introduction to quantum mechanics and to quantum information theory, and I discuss some recent quantum-information-theoretic results and how they can be used to analyze the above and other quantum-cryptographic schemes. Some keywords are: quantum teleportation, uncertainty relation, quantum privacy amplification, quantum de Finetti theorem, quantum key-distribution, bit commitment, oblivious transfer and secure identification.

No prior knowledge on quantum theory is needed for this tutorial, only some elementary linear algebra.

TUTORIAL: Combinatorics in Cryptology -- Secret Sharing Schemes and Private Information Retrieval

Speaker: Enav Weinreb

Affiliation: CWI Amsterdam

Abstract:
The implementation of many cryptographic primitives relies on combinatorial tools. In this tutorial we will concentrate on secret sharing schemes and private information retrieval protocols, focusing on the combinatorial ideas that are used for proving lower and upper bounds on the efficiency of the construction of these primitives.

Our first focus is secret sharing schemes (Shamir 79, Blakley 79). A secret sharing scheme enables a dealer to share a secret among a set of parties, such that only some predefined authorized subsets will be able to reconstruct the secret from their shares. Such schemes allow the distribution of sensitive data in environments where not all participants are fully trusted. The family of predefined authorized subsets is called the access structure of the secret sharing scheme. The efficiency of a secret sharing scheme is the overall size of the shares given to the parties. Originally motivated by the problem of secure information storage, secret-sharing schemes have found numerous other applications in cryptography and distributed computing.

Most of the known secret sharing schemes are linear. Interestingly, the power of linear secret sharing schemes is captured by a computational model called monotone span programs. In this tutorial, we will concentrate on methods for proving lower bounds on the efficiency of linear secret sharing scheme for certain access structures. Towards this goal, we will discuss an interesting relation between linear secret sharing and the task of covering 0/1 matrices by a set of monochromatic rectangles. This will allow us to prove super-polynomial lower bounds on the share size of linear secret sharing scheme for some specific access structures. To complete the picture, we will survey the known techniques to obtain upper bounds on the share size of secret sharing schemes for various families of access structures.

Our second focus is private information retrieval (PIR; Chor Goldreich Kushilevitz Sudan 95) protocols, which allow to query a remote database while hiding the identity of the items being retrieved even from the server holding the database. This can be helpful, e.g., for retrieving sensitive medical data or for getting information related to stock exchange. The trivial solution is to send the whole database for every query, but we are interested in more communication efficient protocols. If information theoretical secrecy of the item being retrieved is required, then the trivial solution is optimal. However, this can be overcome by replicating the database into several copies, each held by a different server, and then send a different query to each database. To achieve computational secrecy, highly efficient protocols exist that avoid the need for replication. In this tutorial we will focus on information theoretical PIR protocol, and present the best known protocol by Yekhanin, together with the beautiful combinatorial and linear algebraic ideas behind it.