(Nearly) Round-Optimal Black-Box Constructions of Commitments Secure against Selective Opening Attacks

Selective opening attacks against commitment schemes occur when the commitment scheme is repeated in parallel (or concurrently) and an adversary can choose depending on the commit-phase transcript to see the values and openings to some subset of the committed bits. Commitments are secure under such attacks if one can prove that the remaining, unopened commitments stay secret.

We prove the following black-box constructions and black-box lower bounds for commitments secure against selective opening attacks:

1

For parallel composition, 4 (resp. 5) rounds are necessary and sufficient to build computationally (resp. statistically) binding and computationally hiding commitments. Also, there are no perfectly binding commitments.

2

For parallel composition,

O

(1)-round statistically-hiding commitments are equivalent to

O

(1)-round statistically-binding commitments.

3

For concurrent composition,

ω

(log

n

) rounds are sufficient to build statistically binding commitments and are necessary even to build computationally binding and computationally hiding commitments, up to loglog

n

factors.

Our lower bounds improve upon the parameters obtained by the impossibility results of Bellare et al. (EUROCRYPT ’09), and are proved in a fundamentally different way, by observing that essentially all known impossibility results for black-box zero-knowledge can also be applied to the case of commitments secure against selective opening attacks.