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

We present barriers to provable security of two fundamental (and well-studied) cryptographic primitives

perfect non-interactive zero knowledge (NIZK)

, and

non-malleable commitments

:

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 (and thus also perfect) NIZK for

${\cal NP}$

based on any “standard” intractability assumptions.

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 assumption based on 1) the

security threshold

, 2) the number of

communication rounds

in the security game, 3) the

computational complexity

of the game challenger, 4) the

communication complexity

of the challenger, and 5) the

computational complexity of the security reduction

.