Cryptographic Constructions of Randomness Resources

Status

This project started in the Spring of 2012 and is now closed.

Researchers

Description

Randomness Resources. Randomness is at the heart of cryptography, it is the core ingredient for achieving cryptographic security. Randomness is needed for the generation of secret keys in symmetric cryptography (for encryption and authentication), for the generation of public-key parameters, as random parameters in protocols (such as nonces or challenges in a zero-knowledge protocol), to randomize encryption (since, for example, a deterministic public-key cryptosystem cannot be secure), to play a game like poker over the Internet, etc. There are several different types of randomness, which can be classified according to the number of parties involved, which of these parties could potentially be dishonest, whether or not secrecy is required, etc. Randomness primitives can be viewed as resources, where a resource corresponds to a system with an interface to every party in consideration (e.g. Alice, Bob, and Eve in a typical communication setting) and with a specified behavior.

Constructive Cryptography. Resources are generally not given as a system in the physical world, but they must be constructed by cryptographic means. For example, a key agreement protocol (e.g. the Diffie-Hellman protocol) can be seen as constructing a secret key from authenticated communication.
Constructive cryptography, introduced in [M11] (see also [MR11]), is a new approach to cryptography in which cryptographic schemes and protocols are seen as constructions of resources. The definition of the term construction depends on the setting, i.e., on who can potentially be dishonest and whether the security should be information-theoretic (i.e., against computationally unbounded cheaters) or computational (i.e., only against computationally bounded cheaters).

Project Goals and Achievements. The goal of this project is to understand the general problem of constructing various types of randomness resources from weaker resources, to devise protocols for such constructions (and prove their security), and to prove impossibility results. Generally speaking, we want to understand the partial order relation on the space of resources defined by cryptographic constructibility.

Publications

G. Demay, P. Gaži, U. Maurer, and B. Tackmann
Query-Complexity Amplification for Random Oracles
International Conference on Information Theoretic Security, 2015
[PDF]

G. Demay, P. Gaži, U. Maurer, and B. Tackmann
Optimality of Non-Adaptive Strategies: The Case of Parallel Games
IEEE International Symposium on Information Theory, 2014
[PDF]

G. Demay and U. Maurer
Unfair Coin Tossing
IEEE International Symposium on Information Theory, 2013
[PDF]

G.Demay, P. Gazi, M. Hirt, and U. Maurer
Resource-Restricted Indierentiability
Advances in Cryptology (EUROCRYPT), 2013
[PDF]

G. Demay and U. Maurer
Common randomness amplification: A constructive view
IEEE Information Theory Workshop (ITW), 2012
[PDF]