Jeśli istnieją OWF, możliwe jest statystycznie wiążące zobowiązanie do bitu. [1]
Czy wiadomo, że jeśli istnieją OWF, możliwe jest doskonale wiążące zaangażowanie bitów?
Jeśli nie, to czy istnieje między nimi znana czarna skrzynka?
[1] http://en.wikipedia.org/wiki/Pseudorandom_generator_theorem i
http://en.wikipedia.org/wiki/Commitment_scheme#Bit-commitment_from_a_pseudo-random_generator
Odpowiedzi:
W niedawnej pracy z Rafael Pass wykazano, że bez tych dodatkowych założeń Barak-Ong-Vadhan, nieinteraktywne zobowiązania nie mogą opierać się na funkcjach jednokierunkowych w czarnej skrzynce. W rzeczywistości nawet przy tych dodatkowych założeniach (sformalizowanych jako pewnego rodzaju właściwość uderzenia zakładana jako dodatek do jednokierunkowej) nadal istnieje separacja czarnej skrzynki:
http://eprint.iacr.org/2012/523.pdf
(konstrukcja Baraka-Ong-Vadhana nie jest czarną skrzynką).
Aby uzyskać pozytywną odpowiedź na to pytanie, przy niektórych dodatkowych założeniach teoretycznych dotyczących złożoności, zobacz artykuł „Derandomizacja w kryptografii” autorstwa Baraka, Onga i Vadhana.