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


2 Answers 2


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:


(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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.