Abstract
We define and construct fully homomorphic non-interactive zero knowledge (FH-NIZK) and non-interactive witness-indistinguishable (FH-NIWI) proof systems.
We focus on the NP complete language L, where, for a boolean circuit C and a bit b, the pair (C,b) is in L if there exists an input w such that C(w)=b. For this language, we call a non-interactive proof system fully homomorphic if, given k instances (C_i,b_i) in L along with their proofs, and given any k-input boolean circuit D, one can efficiently compute a combined proof for (C',b) in L, where C' is defined to be the circuit obtained by applying D on the output of C_1,...,C_k and D(b_1,..., b_k) = b. The key security property is unlinkability: the resulting combined proof is indistinguishable from a fresh proof of the same statement.
Our first result, under the Decision Linear Assumption (DLIN), is an FH-NIZK proof system for L in the common random string model. Our more surprising second result (under a new decisional assumption on groups with bilinear maps) is an FH-NIWI proof system that requires no setup.
Joint work with Apoorvaa Deshpande (Brown), Yael Tauman Kalai (MSR and MIT) and Anna Lysyanskaya (Brown).