Efficient String-Commitment from Weak Bit-Commitment

We study security amplification for commitment schemes and improve the efficiency of black-box security amplification in the computational setting, where the security holds against PPT active adversaries. We show that

ω

(log

s

) black-box calls to a weak bit-commitment scheme with constant security is sufficient to construct a commitment scheme with standard negligible security, where

s

denotes the security parameter and

ω

(log

s

) denotes any super-logarithmic function of

s

. Furthermore, the resulting scheme is a string commitment scheme that can commit to

O

(log

s

)-bit strings. This improves on previous work of Damgård et al. [DKS99] and Halevi and Rabin [HR08], whose transformations require

ω

(log

2

s

) black-box calls to commit a single bit.

As a byproduct of our analysis, we also improve the efficiency of security amplification for message authentication codes, digital signatures, and pseudorandom functions studied in [DIJK09]. This is from an improvement of the “Chernoff-type Theorems” of dynamic weakly-verifiable puzzles of [DIJK09].