Paper 2008/168

Possibility and impossibility results for selective decommitments

Dennis Hofheinz

Abstract

The *selective decommitment problem* can be described as follows: assume an adversary receives a number of commitments and then may request openings of, say, half of them. Do the unopened commitments remain secure? Although this question arose more than twenty years ago, no satisfactory answer could be presented so far. We answer the question in several ways: - 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.

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.