- If simulation-based security is desired (i.e., if we demand that the adversary's output can be simulated by a machine that does not see the unopened commitments), then security is *not achievable* for non-interactive or perfectly binding commitment schemes via black-box reductions to standard cryptographic assumptions. *However,* we show how to achieve security in this sense with interaction and a non-black-box reduction to one-way permutations.
- If only indistinguishability of the unopened commitments from random commitments is desired, then security is *not achievable* for (interactive or non-interactive) perfectly binding commitment schemes, via black-box reductions to standard cryptographic assumptions. *However,* any statistically hiding scheme *does* achieve security in this sense.
Our results give an almost complete picture when and how security under selective openings can be achieved. Applications of our results include:
- Essentially, an encryption scheme *must* be non-committing in order to achieve provable security against an adaptive adversary.
- When implemented with our commitment scheme, the interactive proof for graph 3-coloring due to Goldreich et al. becomes black-box zero-knowledge under parallel composition.
On the technical side, we develop a technique to show very general impossibility results for black-box proofs.
Category / Keywords: cryptography, commitments, zero-knowledge, black-box separations Date: received 14 Apr 2008, last revised 11 Jun 2008 Contact author: Dennis Hofheinz at cwi nl Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: [29.4.2008:] Added a commitment scheme which achieves simulation-based security using non-blackbox techniques. Fixed some typos. [30.4.2008:] Fixed more typos. [7.5.2008:] Minor changes. [15.5.2008:] Correction: the first impossibility result does not generalize to noninteractive commitment schemes. Added: an interactive (but constant-round) commitment scheme which achieves simulatability using a blackbox reduction. [16.5.2008:] Minor changes. [16.06.2008:] Corrections in proof of Theorem 4.2. Improved presentation. [17.06.2008:] Minor changes. Removed RSCom. Version: 20080611:141840 (All versions of this report) Discussion forum: Show discussion | Start new discussion