International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Fully Homomorphic NIZK and NIWI Proofs

Authors:
Prabhanjan Ananth
Apoorvaa Deshpande
Yael Tauman Kalai
Anna Lysyanskaya
Download:
DOI: 10.1007/978-3-030-36033-7_14
Search ePrint
Search Google
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 C∗(w(1),…,w(k))=D(C1(w(1)),…,Ck(w(k))) and D(b1,…,bk)=b. 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.
BibTeX
@article{tcc-2019-30000,
  title={Fully Homomorphic NIZK and NIWI Proofs},
  booktitle={Theory of Cryptography},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11892},
  pages={356-385},
  doi={10.1007/978-3-030-36033-7_14},
  author={Prabhanjan Ananth and Apoorvaa Deshpande and Yael Tauman Kalai and Anna Lysyanskaya},
  year=2019
}