Unprovable Security of Perfect NIZK and Non-interactive Non-malleable Commitments

We present barriers to provable security of two important cryptographic primitives, perfect non-interactive zero knowledge (NIZK) and non-interactive non-alleable commitments:

1. ○
   Black-box reductions cannot be used to demonstrate adaptive soundness (i.e., that soundness holds even if the statement to be proven is chosen as a function of the common reference string) of any statistical NIZK for NP based on any “standard” intractability assumptions.
    
2. ○
   Black-box reductions cannot be used to demonstrate non-malleability of non-interactive, or even 2-message, commitment schemes based on any “standard” intractability assumptions.
    

We emphasize that the above separations apply even if the construction of the considered primitives makes a non-black-box use of the underlying assumption.

As an independent contribution, we suggest a taxonomy of game-based intractability assumptions.