Randomness Extraction and its Applications in Cryptography

Xin Li, University of Washington
Host: Vladimir Braverman

Modern cryptography has become a huge success and has enabled many important applications such as public-key encryption systems, zero-knowledge proofs and secure multi-party computation protocols. However, the security of these applications relies crucially on the assumption that we have access to truly uniform random bits. On the other hand, in reality high quality random sources may be hard to obtain, and natural random sources tend to be biased in unknown ways. The situation is made even worse by possible side channel attacks, which may leak information to an adversary and thus compromise even initially uniform secret keys. Therefore, fundamental questions are whether we can use imperfect randomness in cryptographic applications without jeopardizing their security, and whether we can protect against information leakage in secret keys. These topics have been the focus of intensive recent research.

In this talk I will describe a general and powerful tool to deal with imperfect randomness and information leakage, called “randomness extractors”. A randomness extractor is an algorithm that transforms an imperfect random source into nearly uniform random bits. I will discuss different kinds of randomness extractors and their applications in cryptography. I will then describe my new approaches in constructing these objects, which have led to significant progress and almost optimal solutions to two long standing open problems: privacy amplification with an active adversary [Maurer-Wolf’ 1997] and explicit extractors for independent weak random sources [Chor-Goldreich’ 1985]. Interestingly, my techniques also established new connections between randomness extractors and other seemingly unrelated problems such as leader election in distributed computing.

Speaker Biography

Xin Li is a postdoctoral researcher in Computer Science and Engineering at the University of Washington. He received his B.S. and M.S. in computer science from Tsinghua University, China and his Ph.D. in computer science from the University of Texas at Austin, where he was advised by David Zuckerman. His current work focuses on randomness extractors and their applications in leakage-resilient cryptography and information-theoretic security. His general research interests include pseudorandomness, cryptography, complexity theory and fault-tolerant distributed computing. He is the recipient of a Simons postdoctoral fellowship.