Unprovable security of perfect NIZK and non-interactive non-malleable commitments. (English) Zbl 1315.94099
Sahai, Amit (ed.), Theory of cryptography. 10th theory of cryptography conference, TCC 2013, Tokyo, Japan, March 3–6, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-36593-5/pbk). Lecture Notes in Computer Science 7785, 334-354 (2013).
Summary: We present barriers to provable security of two fundamental (and well-studied) cryptographic primitives perfect non-interactive zero knowledge (NIZK), and non-malleable commitments:
\(\bullet\) 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 \({\mathcal NP}\) based on any “standard” intractability assumptions.
\(\bullet\) 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.
For the entire collection see [Zbl 1258.94005].
\(\bullet\) 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 \({\mathcal NP}\) based on any “standard” intractability assumptions.
\(\bullet\) 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.
For the entire collection see [Zbl 1258.94005].
MSC:
| 94A60 | Cryptography |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
