Fall 2019

On Two-Message Statistically Private Arguments

Tuesday, September 24th, 2019 4:00 pm4:30 pm

Add to Calendar


Dakshita Khurana (Microsoft Research)

Dwork and Naor (FOCS'00) first introduced and constructed two message witness indistinguishable proofs (ZAPs) for NP based on trapdoor permutations. Since then, ZAPs have also been obtained based on the decisional linear assumption on bilinear maps, and indistinguishability obfuscation, and have proven extremely useful in the design of several cryptographic primitives.

In this talk, we will describe the first constructions of two message witness indistinguishable (WI) arguments for NP with statistical privacy, assuming quasi-polynomial hardness of standard cryptographic assumptions. We will also describe how to obtain somewhat stronger privacy guarantees than witness indistinguishability, and how to achieve public verification.

This talk is based on joint works with Saikrishna Badrinarayanan, Rex Fernando, Aayush Jain, Yael Kalai and Amit Sahai.