Title: Fully Homomorphic NIZK and NIWI Proofs
Authors: Prabhanjan Ananth; Apoorvaa Deshpande; Yael Kalai; Anna Lysyanskaya
Key words: NIZK, NIWI, Homomorphism, Definitions
Abstract:
In this work, we define and realize {\em 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)\in L if there exists an input w such that C(w)=b. For
this language, we call a non-interactive proof system \emph{fully homomorphic}
if, given instances (C_i,b_i)\in L along with their proofs \Pi_i, for i \in
\{1,\ldots,k\}, and given any circuit D:\{0,1\}^k \rightarrow \{0,1\}, one can
efficiently compute a proof for (C,b)\in L, where
C(w^{(1)},\ldots,w^{(k)})=D(C_1(w^{(1)}),\ldots,C_k(w^{(k)})) and
D(b_1,\ldots,b_k)=b. The key security property is \textit{unlinkability}: the
resulting proof \Pi is indistinguishable from a fresh proof of the same
statement.
Our first result, under the Decisional Linear Assumption (DLIN) is an FH-NIZK
proof system for L in the common reference 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.