Cryptology ePrint Archive: Report 2019/732

Fully Homomorphic NIZK and NIWI Proofs

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

Abstract: 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.

Category / Keywords: foundations / Non-interactive zero-knowledge (NIZK), Non-interactive witness-indistinguishability (NIWI), Homomorphism

Date: received 19 Jun 2019

Contact author: prabhanjan va at gmail com,acdeshpa@cs brown edu,yaelism@gmail com,anna@cs brown edu

Available format(s): PDF | BibTeX Citation

Version: 20190620:115259 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]