Fully Homomorphic NIZK and NIWI Proofs

Apoorvaa Deshpande


In this work, we define and construct fully homomorphic non-interactive zero knowledge (FH-NIZK) and non-interactive witness-indistinguishable (FH-NIWI) proof systems. Specifically, given non-interactive zero-knowledge (NIZK) or witness-indistinguishable (NIWI) proofs for different statements, we give a framework to homomorphically evaluate on them to compute proofs for new arbitrarily inferred statements. The security guarantee along with soundness and ZK or WI (respectively) is that of unlinkability; an inferred proof should be indistinguishable from a fresh proof for a combined statement.

Our first result, under the Decision Linear Assumption (DLIN), is a fully homomorphic NIZK proof system in the common random string model. Our more surprising second result (under a new decisional assumption on groups with bilinear maps) is a fully homomorphic NIWI proof system that requires no setup. [Joint work with Prabhanjan Ananth, Yael Kalai and Anna Lysyanskaya]


Apoorvaa Deshpande is a PhD student at Brown University, advised my Prof. Anna Lysyanskaya. Her research has been around zero-knowledge proofs and its applications.

Time and Place

Tuesday, August 13, 4:15pm
Gates 463A