Paper 2019/732
Fully Homomorphic NIZK and NIWI Proofs
Prabhanjan Ananth, Apoorvaa Deshpande, Yael Tauman Kalai, and Anna Lysyanskaya
Abstract
In this work, we define and construct fully homomorphic noninteractive zero knowledge (FHNIZK) and noninteractive witnessindistinguishable (FHNIWI) 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 noninteractive 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 FHNIZK 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 FHNIWI proof system that requires no setup.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Noninteractive zeroknowledge (NIZK)Homomorphism
 Contact author(s)

prabhanjan va @ gmail com
acdeshpa @ cs brown edu
yaelism @ gmail com
anna @ cs brown edu  History
 20190620: received
 Short URL
 https://ia.cr/2019/732
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/732, 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{https://eprint.iacr.org/2019/732}}, url = {https://eprint.iacr.org/2019/732} }