CWI Cryptology Group

Abstract: Randomness extractors are functions whose output is guaranteed to be uniformly distributed, given some assumption on the distribution of the input. The first instance of a randomness extraction problem comes from von-Neumann who gave an elegant solution to the following problem: How can a biased coin with unknown bias be used to generate ‘fair’ coin tosses? In this case the input distribution consists of independent identically distributed bits. Since then many families of more complex input distributions have been studied. Also, the concept of randomness extraction has proven to be useful for various applications. The talk will give some background on extractors and review applications and techniques used in recent constructions of extractors.

Abstract: Motivated by the classical problem of privacy amplification, Dodis and Wichs (STOC '09) introduced the notion of a non-malleable extractor, significantly strengthening the notion of a strong extractor. A non-malleable extractor is a function nmExt that takes two inputs: a weak source W and a uniform (independent) seed S, and outputs a string nmExt(W,S) that is nearly uniform given the seed S *as well* as the value nmExt(W,S') for any seed S' \neq S that may be determined as an arbitrary function of S. In this work we present the first unconditional construction of a non-malleable extractor with short seeds. By instantiating the framework of Dodis and Wichs with our non-malleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate 1/2 + delta with asymptotically optimal entropy loss and poly-logarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs whose entropy loss is not asymptotically optimal, and the protocol of Dodis, Li, Wooley and Zuckerman whose communication complexity is linear and relies on a number-theoretic assumption. Joint work with Ran Raz and Gil Segev.

Abstract: TBA

Abstract: Randomness extraction is a fundamental task in cryptography, where it is intimately connected with the problem of privacy amplification. In this talk we will survey the specific challenges posed by this task in the setting where an adversary may hold *quantum* information about the source and give an overview over the known results in the area. In the last part, we touch on recent joint work with Fehr and Gelles. We demonstrate that quantum mechanics allows to expand some initial randomness in a secure way even if the used devices are manufactured by the adversary.