Title: Fully Homomorphic NIZK and NIWI Proofs Authors: Prabhanjan Ananth; Apoorvaa Deshpande; Yael Kalai; Anna Lysyanskaya Key words: NIZK, NIWI, Homomorphism, Definitions Abstract: In this work, we define and realize {\em 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 \emph{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 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 \textit{unlinkability}: the resulting proof \Pi is indistinguishable from a fresh proof of the same statement. Our first result, under the Decisional Linear Assumption (DLIN) is an FH-NIZK proof system for L in the common reference 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.