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

作者：Pass Rafael^*

来源：Computational Complexity, 2016, 25(3): 607-666.

DOI：10.1007/s00037-016-0122-2

• Cryptography
• Black-box separations
• Non-malleable commitments
• Non-interactive zero-knowledge

We present barriers to provable security of two important cryptographic primitives, perfect non-interactive zero knowledge (NIZK) and non-interactive non-alleable 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 NIZK for 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.
As an independent contribution, we suggest a taxonomy of game-based intractability assumptions.

• 出版日期2016-9