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 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)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 (Ci,bi)L along with their proofs Πi, for i{1,,k}, and given any circuit D:{0,1}k{0,1}, one can efficiently compute a proof Π for (C,b)L, where and . The key security property is 'unlinkability': the resulting 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Non-interactive zero-knowledge (NIZK)Homomorphism
Contact author(s)
prabhanjan va @ gmail com
acdeshpa @ cs brown edu
yaelism @ gmail com
anna @ cs brown edu
History
2019-06-20: received
Short URL
https://ia.cr/2019/732
License
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2019/732}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.