10
$\begingroup$

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

|cite|improve this question
$\endgroup$
6
$\begingroup$

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

|cite|improve this answer
$\endgroup$
3
$\begingroup$

For a positive answer to this question, under some additional complexity-theoretic assumptions, see the paper "Derandomization in Cryptography" by Barak, Ong, and Vadhan.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy