Unconditional Characterizations of Non-Interactive Zero-Knowledge

Non-interactive zero-knowledge (NIZK) proofs have been investigated in two models: the Public Parameter
model and the Secret Parameter model.  In the former, a public string is ``ideally'' chosen according to some efficiently samplable distribution and made available to both the Prover and Verifier.  In the latter, the parties instead obtain correlated (possibly different) private strings.

To add further choice, the definition of zero-knowledge in these settings can either be non-adaptive or adaptive.
 
In this paper, we obtain several unconditional characterizations of computational, statistical and perfect NIZK for all combinations of these settings.  Specifically, we show:

In the secret parameter model, \nizk$=\,$\niszk$=\,$\nipzk$=\,$\am.

In the public parameter model,

• for the non-adaptive definition, \niszk $\subseteq$ \am $\cap$ \coam,
• for the adaptive one, it also holds that \niszk $\subset$ \bpp/1,
• for computational NIZK for ``hard'' languages, one-way functions are both necessary and sufficient.
  

From our last result, we arrive at the following unconditional characterization of computational NIZK in the public parameter model (which complements well-known results for interactive zero-knowledge):

• Either NIZK proofs exist only for ``easy'' languages (i.e., languages that are not hard-on-average), or theyexist for all of \am (i.e., all languages which admit non-interactive proofs).
  

[PDF]