Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
If OWFs exist, then statistically binding bit commitment is possible.[1]
Is it known that if OWFs exist then perfectly binding bit commitment is possible?
If no, is there a known black-box separation between them?
[1] http://en.wikipedia.org/wiki/Pseudorandom_generator_theorem and
http://en.wikipedia.org/wiki/Commitment_scheme#Bit-commitment_from_a_pseudo-random_generator
In a recent work with Rafael Pass, it is shown that without those extra complexity assumptions of Barak-Ong-Vadhan, noninteractive commitments can not be based on one-way functions in a black-box way. In fact even with these extra assumptions (when formalized as some kind of hitting property assumed in addition to one-way-ness) still a black-box separation holds:
http://eprint.iacr.org/2012/523.pdf
(the construction of Barak-Ong-Vadhan is non-black-box).
For a positive answer to this question, under some additional complexity-theoretic assumptions, see the paper "Derandomization in Cryptography" by Barak, Ong, and Vadhan.
