Funkcje jednokierunkowe a doskonale wiążące zobowiązania

10

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

Mohammad Al-Turkistany
źródło

Odpowiedzi:

6

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

Mohammad
źródło
3

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.

użytkownik686
źródło