Czy „Funkcje jednokierunkowe” mają jakieś aplikacje poza kryptografią?

Funkcja jest jednokierunkowa, jeśli f można obliczyć za pomocą algorytmu wielomianowego czasu, ale dla każdego losowego algorytmu wielomianowego czasu A ,$f \colon \{0, 1\}^* \to \{0, 1\}^*$$f$$A$

$\Pr[f(A(f(x))) = f(x)] < 1/p(n)$

dla każdego wielomianu i wystarczająco dużego n , przy założeniu, że x jest wybrany równomiernie z { 0 , 1 $p(n)$$n$$x$ . Prawdopodobieństwo jest przejmowane wyboru X i przypadkowości A .$\{ 0, 1 \}^n$$x$$A$

Więc ... czy „Funkcje jednokierunkowe” mają jakieś aplikacje poza kryptografią? Jeśli tak, jakie one są?

Funkcje jednokierunkowe mają zasadnicze znaczenie w wynikach naturalnych dowodów Razborova-Rudicha. Nie rozważałbym dolnych granic obwodu jako części „kryptografii”, więc może to pasuje do twoich kryteriów.

Funkcje jednokierunkowe pojawiły się również w niektórych dyskusjach wokół hipotezy izomorfizmu Bermana-Hartmanisa . Joseph i Young przypuszczali, że jeśli istniałyby funkcje jednokierunkowe, wówczas hipoteza izomorfizmu zawodzi (w jedną stronę przeciw deterministycznym przeciwnikom, nie probabilistycznym, ale miejmy nadzieję, że jest to wystarczająco bliskie dla celów tego pytania). John Rogers dał relatywizowany świat, w którym zawiodła hipoteza Josepha-Younga (to znaczy tam, gdzie istnieją funkcje jednokierunkowe, ale hipoteza izomorfizmu obowiązuje). Ale o ile wiem, hipoteza JY jest nadal jednym z głównych dowodów technicznych, które prowadzą ludzi do myślenia, że ​​hipoteza izomorfizmu jest fałszywa (jeśli tak uważają).

Istota idei Joseph i Young, że jeżeli jest funkcja jednokierunkowa, to F ( S A , T ) jest N P -Complete ale „nie powinno” jest izomorficzny SAT.$f$$f(SAT)$$NP$

Tak, tabela skrótów lub mapa skrótów wymagają funkcji jednokierunkowej. Również wykrywanie duplikatów (patrz to i to ) można wykonać bardzo skutecznie za pomocą funkcji jednokierunkowych. Oba przypadki wymagają „dobrych” (przy małych szansach na kolizję) jednokierunkowych funkcji, podczas gdy siła kryptograficzna zwykle nie jest wymagana .

Istnieje wiele wyników „twardości kryptograficznej” (tylko Google to wyrażenie) w przypadku problemów z nauką. Są to wyniki twardości przy założeniu, że istnieją funkcje jednokierunkowe.

Funkcje jednokierunkowe mają zastosowanie w złożoności Kołmogorowa:

Twierdzenie o symetrii informacji stwierdza, że ​​informacje zawarte w ciągu znaków $x$ o sznurku $y$jest symetryczny do logarytmicznego błędu addytywnego. Podobnie, domniemana symetria informacji wielomianowej ograniczona czasowo stwierdza, że

$K^q(x, y) = K^q(x) + K^q(y|x) + O(\log n)$ dla dowolnego wielomianu $q$

Jeśli istnieją funkcje jednokierunkowe, wówczas symetria domniemania związanego z czasem wielomianowym jest fałszywa.

L. Longpre i S. Mocas. Symetria informacji i funkcje jednokierunkowe. Information processing Letters, 46 (2): 95 {100, 1993

L. Longpre i O. Watanabe. O symetrii informacji i wielomianowej odwracalności czasu. Information and Computation, 121 (1): 14 {22, 1995