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

16

Funkcja jest jednokierunkowa, jeśli można obliczyć za pomocą algorytmu wielomianowego czasu, ale dla każdego losowego algorytmu wielomianowego czasu , $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 , przy założeniu, że jest wybrany równomiernie z $p(n)$ $n$ $x$ . Prawdopodobieństwo jest przejmowane wyboru i przypadkowości . $\{ 0, 1 \}^n$ $x$ $A$

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

cc.complexity-theory cr.crypto-security one-way-function

— Tarek Radwan
źródło

1

Poprawiłem formuły do formularza LaTeX, ale wydaje się, że w MathJax występuje usterka, ponieważ poprawnie wyświetla podgląd równań, ale pokazuje błąd `Niewłaściwie \ '. Myślę, że zostanie to wkrótce poprawione ...

— MS Dousti,

1

Dla mnie wygląda to bardziej na błąd w SE. Z jakiegoś powodu wydaje się, że nie rozpoznaje podwójnego \ jako sekwencji ucieczki, która powinna wypisywać pojedynczy \, który następnie byłby przetwarzany przez MathJax.

— Jukka Suomela,

2

Na stanowisku jest to

, ale wymaga jednego dodatkowego wspornika zamykającego „)”.

P r [f (A (f (x), 1^{n}) = x] < 1 / p (n)

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

— Oleksandr Bondarenko

2

@Sadeq i Jukka: Może to być związane z ostatnio naprawionym błędem w SE: meta.math.stackexchange.com/questions/1115/…

— Tsuyoshi Ito

@Tsuyoshi: Dziękujemy za pouczający komentarz!

— MS Dousti,

23

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.

— mikero
źródło

11

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 jest -Complete ale „nie powinno” jest izomorficzny SAT. $f$ $f(SAT)$ $NP$

— Joshua Grochow
źródło

8

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 .

— sharptooth
źródło

Tak, funkcje skrótu są szeroko stosowane w tablicach skrótów.

— Gamlor

2

twoja odpowiedź jest nieprawidłowa. Do wykrywania duplikatów wymagana jest odporność na zderzenia, co nie jest tym samym, co bycie jednokierunkowym. Zobacz definicję w pierwotnym pytaniu, aby uzyskać dokładną definicję jednokierunkową. Czasami ludzie luźno używają wyrażenia „skrót jednokierunkowy” jako synonim kryptograficznej funkcji skrótu, ale jest to bardzo mylące, ponieważ w wielu aplikacjach ważna jest nie właściwość „jednokierunkowa”, ale raczej odporność na kolizje ( jak w przypadku wykrywania duplikatów) lub zachowanie jak losowa wyrocznia (jak w haszowaniu).

— DW

6

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.

— Dana Moshkovitz
źródło

4

Czy możesz podać mi dokładną definicję „twardości kryptograficznej”?

— Tarek Radwan,

1

Standardowe wyniki twardości zakładają, że P nie jest równe NP; w takim przypadku problem zajmuje czas super-wielomianowy. Wyniki „twardości kryptograficznej” zakładają coś silniejszego: istnieją funkcje jednokierunkowe. To założenie implikuje (i jest silniejsze niż) średnią twardość niektórych problemów.

— Dana Moshkovitz

5

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

— Mohammad Al-Turkistany
źródło