Computer Science Talk

Friday, June 28, 2019 - 1:00pm to 2:00pm


7501 Gates Hillman Centers


DAKSHITA KHURANA, Postdoctoral Researcher, Microsoft Research New England

Weak Zero-Knowledge Beyond the Black-Box Bar

The round complexity of zero-knowledge protocols is a long-standing open problem, yet to be settled under standard assumptions. So far, the question has appeared equally challenging for relaxations such as weak zero-knowledge and witness hiding. Protocols satisfying these relaxed notions under standard assumptions have at least four messages, just like full-fledged zero knowledge. The difficulty in improving round complexity stems from a fundamental barrier: none of these notions can be achieved in less than four messages via reductions (or simulators) that treat the verifier as a black box. We introduce a new non-black-box technique and use it to obtain the first protocols that cross this barrier under standard assumptions.

In this talk, I will give an overview of this new non-black-box simulation technique. Then, I will describe how it gives us the first constructions of weak zero-knowledge and witness hiding proof systems requiring only a single message each from the verifier and the prover.

Dakshita Khurana is currently a Postdoctoral Researcher at Microsoft Research New England working in Cryptography and related topics in Privacy, Security and Theoretical Computer Science. She will join University of Illinois at Urbana-Champaign as Assistant Professor of Computer Science starting Fall 2019. She obtained a PhD from UCLA, under Prof. Amit Sahai and Prof. Rafail Ostrovsky and received the 2017-18 Dissertation Year Fellowship and other Research Awards.  Dakshita interned with Yael Tauman Kalai at Microsoft Research New England, and Vipul Goyal at Microsoft Research India.

Faculty Host: Vipul Goyal

For More Information, Contact: