Paper 2019/732

Fully Homomorphic NIZK and NIWI Proofs

Prabhanjan Ananth, Apoorvaa Deshpande, Yael Tauman Kalai, and Anna Lysyanskaya


In this work, 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) \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 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 $\Pi$ 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 'unlinkability': the resulting proof $\Pi$ 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.

Available format(s)
Publication info
Preprint. MINOR revision.
Non-interactive zero-knowledge (NIZK)Homomorphism
Contact author(s)
prabhanjan va @ gmail com
acdeshpa @ cs brown edu
yaelism @ gmail com
anna @ cs brown edu
2019-06-20: received
Short URL
Creative Commons Attribution


      author = {Prabhanjan Ananth and Apoorvaa Deshpande and Yael Tauman Kalai and Anna Lysyanskaya},
      title = {Fully Homomorphic NIZK and NIWI Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2019/732},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.