Non-malleable Extractors and Application to Privacy Amplification

Speaker: Divesh Aggarwal

  Part I - 14:30 - 16:00, 5th January, 2018
  Part II - 9:30 - 11:00, 6th January, 2018

In this talk, I will focus on the problem of privacy amplification, where Alice and Bob share an n-bit secret X, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, it is desirable to construct an authenticated key agreement protocol in which Alice and Bob use X to agree on a nearly uniform key R (of length close to k), by communicating over a public channel controlled by an active adversary Eve.

I will show how to design a communication efficient two-round (challenge-response) protocol extracting nearly k random bits. This construction will be achieved by studying and constructing what has now become one of the most important primitives in the broad area of pseudorandomness -- ``non-malleable'' seeded randomness extractors. In a non-malleable seeded randomness extractor, if an attacker sees a random seed S and comes up with an arbitrarily related seed S', then there is limited or no dependence between nmExt(X, S) and nmExt(X,S'). The talk will be based on the following papers:
1. Y. Dodis and D. Wichs. Non-Malleable Extractors and Symmetric Key Cryptography from Weak Secrets. STOC 2009.
2. X. Li. Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification. FOCS 2012.
3. D. Aggarwal, K. Hosseini, and S. Lovett. Affine-malleable extractors, spectrum doubling, and application to privacy amplification. ISIT 2016.

Speaker Bio
Divesh Aggarwal has received Ph.D. degree in Computer Science from ETH Zurich in 2012. From 2012 to 2016, he spent two years each as a postdoctoral researcher at New York University and at EPFL. Since 2016, he is an Assistant Professor in the Department of Computer Science, and a Principal Investigator in the Centre for Quantum Technologies at the National University of Singapore. His research interests include lattices, pseudorandomness, cryptography, coding theory, algorithms, and computational complexity.