Argumenty za istnieniem funkcji jednokierunkowych

25

Czytałem w kilku artykułach, że powszechnie uważa się istnienie funkcji jednokierunkowych . Czy ktoś może wyjaśnić, dlaczego tak jest? Jakie mamy argumenty za poparciem istnienia funkcji jednokierunkowych?

Anonimowy
źródło
1
Uważam za nieco mylące, że wiele artykułów stwierdza, że ​​istnienie funkcji jednokierunkowych jest powszechnie uważane, ponieważ jak dotąd nie mamy silnego argumentu na ich istnienie. Pisanie „istnienie funkcji jednokierunkowych jest powszechnie akceptowane przez ekspertów jako prawdopodobne założenie, które jest zgodne z naszym doświadczeniem w praktyce i obecnym stanem wiedzy” jest bardziej odpowiednie i sprawiedliwe.

Odpowiedzi:

22

Oto argument, że funkcje jednokierunkowe powinny być trudne do odwrócenia. Załóżmy, że istnieje trudna do rozwiązania klasa problemów 3-SAT z posadzonymi rozwiązaniami. Rozważ następującą mapę:

(x,r)s

gdzie oznacza dowolny ciąg bitów, r jest ciągiem bitów (można z nich korzystać do materiału siewnego generator liczb losowych, lub można poprosić o tak wielu przypadkowych kawałków, jak trzeba) i s jest k -sat problemem konieczności X jak posadzone rozwiązanie, w którym generator liczb losowych określa dokładnie, jaki problem k- SAT wybierzesz. Aby odwrócić tę funkcję jednokierunkową, musisz rozwiązać problem k- SAT za pomocą posadzonego rozwiązania.xrskxkk

Argument ten pokazuje, że odwrócenie funkcji jednokierunkowej jest tak trudne, jak rozwiązywanie problemów SAT za pomocą posadzonych rozwiązań. A ponieważ k- SAT jest problemem NP-zupełnym, jeśli możesz dowiedzieć się, jak konstruować twarde instancje z posadzonymi rozwiązaniami dla dowolnego problemu NP, możesz sadzić rozwiązania we wzorach k -SAT.kkk

Nie zostało udowodnione, że można znaleźć klasę problemów z NP-zupełnymi rozwiązaniami, które są tak samo trudne jak arbitralne problemy z NP-zupełnymi (a nawet jeśli jest to prawdą, będzie to niezwykle trudne do udowodnienia) , ale ludzie zdecydowanie wiedzą, jak sadzić rozwiązania problemów SAT w sposób, którego nikt obecnie nie umie rozwiązać.k

DODANO: Teraz zdaję sobie sprawę, że połączenie to zostało już podane (bardziej szczegółowo) w Abadi, Allender, Broder, Feigenbaum i Hemachandra ; zwracają uwagę, że funkcje jednokierunkowe mogą dawać rozwiązane trudne przypadki SAT i odwrotnie.

Mówiąc w bardziej nieformalnym języku, brak jednokierunkowych funkcji pokazuje, że naprawdę trudne zagadki nie mogą istnieć. Jeśli istnieje rodzaj łamigłówki, w którym ktoś może wymyślić zarówno układankę, jak i jej rozwiązanie algorytmicznie, istnieje również algorytm wielomianowy do znalezienia rozwiązania układanki. Wydaje mi się to bardzo sprzeczne z intuicją. Oczywiście może istnieć wielomianowa luka; może się zdarzyć, że jeśli stworzenie układanki wykona kroków, to rozwiązanie może zająć O ( n 3 ) kroków. Jednak moja intuicja mówi, że powinna istnieć luka wielobiegunowa. nO(n3)

Peter Shor
źródło
1
Czy to nie jest ostatecznie ten sam argument, co argument Sadeqa, w tym sensie, że oba polegają na pewnych problemach, których nikt obecnie nie umie rozwiązać pomimo dużego wysiłku?
Tsuyoshi Ito,
2
@Sadeq: możesz podać algorytmowi zasadniczo wszystkie losowe bity potrzebne do tego argumentu; tak naprawdę nie potrzebujesz PRG, a na pewno nie kryptograficznie silnego.
Peter Shor,
6
@Tsuyoshi: Myślę, że generowanie trudnych przypadków problemów NP z posadzonymi rozwiązaniami jest nieco bardziej ogólne niż faktoring lub dyskretny log; z jednej strony nie wiadomo, że jest w BQP.
Peter Shor,
3
@Tsuyoshi: Chciałbym zobaczyć inne podejście; niestety nie mam. Ale to oznacza, że ​​naprawdę trudne łamigłówki nie mogą istnieć; jeśli istnieje rodzaj układanki, w którym ktoś może wymyślić układankę i jej rozwiązanie algorytmicznie, istnieje również algorytm wielomianowy do rozwiązania układanki. Wydaje mi się to bardzo sprzeczne z intuicją.
Peter Shor,
4
@Tsuyoshi: Myślę, że Peter ma na myśli to, że nie ma tylko dwóch lub trzech kandydatów na OWF; kandydaci są niezwykle bogaci i prawie trywialni do wymyślenia. Na przykład, jeśli spojrzysz na prace związane z konkursem SHA-3 NIST, wydaje się, że „łatwe” jest zbudowanie OWF, a ludzie są głównie zainteresowani projektowaniem superszybkich OWF, które nadal spełniają bardzo rygorystyczne pojęcie bezpieczeństwa.
Timothy Chow,
13

Dam krótką odpowiedź: istnienie pozornie trudnych problemów, takich jak FACTORING lub DISCRETE LOG, sprawiło, że teoretycy wierzą, że OWF istnieje. W szczególności przez dziesięciolecia (od lat 70.) próbowali znaleźć wydajne algorytmy (probabilistyczny czas wielomianowy) dla takich problemów, ale żadna próba się nie powiodła. To rozumowanie jest bardzo podobne do tego, dlaczego większość badaczy uważa, że ​​P ≠ NP.

MS Dousti
źródło
W tym przekonaniu nie podoba mi się to, że oba problemy są w BQP, więc jeśli rzeczywiście są one jednokierunkowe, a komputery kwantowe okażą się praktyczne, to należy zmienić definicję funkcji jednokierunkowej (aby oprzeć się kwantowym poli przeciwnicy czasowi zamiast po prostu losowo. Czy znasz w tym sensie kandydatów na silne funkcje jednokierunkowe? Czy są kandydaci na takie silne funkcje jednokierunkowe, które w swoim twierdzeniu przyjmują Razborova-Rudicha?
Diego de Estrada,
1
Odpowiedź na moje pierwsze pytanie: dx.doi.org/10.1016/j.tcs.2007.03.013
Diego de Estrada
3
DTIME(exp(n1/4))
10
Musi istnieć lepszy argument za tym, dlaczego istnieją funkcje jednokierunkowe, niż że znamy wiele funkcji, których jeszcze nie wiemy jak odwrócić. Zobaczę, czy mogę coś wymyślić.
Peter Shor,
1
DTIME(exp(n1/4))
-5

Argument Sasho opiera się na odwiecznym problemie P = NP, dla którego obecnie nie ma konsensusu.

r1,r2,r3,,rns1,s2,s3,,sn

f(ri,si)=risi=ci

f1(ri,si)

Możemy naśladować wynik Shannona dla funkcji jednokierunkowych.

f:Z/nZ×Z/nZZ/nZf:Z/nZZ/nZ×Z/nZ

Problem polega na tym, że nie wiemy, czy istnieją naprawdę losowe liczby, ponieważ pytanie to odpowiada komentarzowi Einsteina na temat „Bóg nie gra w kości”.

Jednak do wszystkich celów generator liczb losowych oparty na fizycznym procesie jest uważany przez ekspertów za wystarczająco losowy.

(ci,ri)

f(ri,sk)f(rj,sk)skf(ri,si)=f(rj,sj)

mathersjj1
źródło
5
Wynik Shannona dotyczy bezpieczeństwa teoretycznego (gdzie przeciwnik ma nieograniczoną moc obliczeniową). Nie o to pyta pytanie. Pytanie dotyczy funkcji jednokierunkowych z zabezpieczeniami obliczeniowymi (gdzie przeciwnik ogranicza się do obliczeń w czasie wielomianowym). W związku z tym argumenty w stylu Shannona nie mówią nic o tym, czy istnieją bezpieczne obliczeniowo jednokierunkowe funkcje.
DW
Przeczytaj definicję funkcji jednokierunkowej .
Kaveh
Ker-I Ko definiuje funkcję jednokierunkową w odniesieniu do problemu P = NP i wielomianowego izomorfizmu. Mówiąc dokładniej, jeśli istnieją funkcje jednokierunkowe, wówczas hipoteza Cooka o kompletności NP, tj. Izomorfizmie między zbiorami NP-kompletnymi, nie ma zastosowania. Z punktu widzenia entropii informacji chodzi o poznanie rzeczy, aby pokazać, że klasa izomorfizmów matematycznie definiowalnych funkcji jest bezpieczna (nieodwracalna) tylko wtedy, gdy można zdefiniować zestaw losowy. Nie jestem pewien wkładu Shannona w trudność i użycia wyrażenia „matematycznie bezpieczny”.
mathersjj1
2
cstheory nie jest forum dyskusyjnym ani osobistym blogiem, jest to strona z pytaniami i odpowiedziami. Twój post nie jest odpowiedzią na pytanie dotyczące funkcji jednokierunkowych (zgodnie z definicją w linku). Sprawdź przewodnik i centrum pomocy, aby uzyskać wyjaśnienie zakresu cstheory.
Kaveh
-6

Czy byłoby to tak proste, jak sugerowanie na przykład funkcji Sinus?

Ponieważ dla danego wejścia i wyjścia sygnał wejściowy można zwiększyć lub zmniejszyć o 360 stopni (lub 2 pi, jeśli jesteś w radianach), to wiele do jednego, więc nigdy nie możesz być pewien, który sygnał miałeś?

Powiedz mi jednak, czy źle zrozumiałem pytanie.

Aaron Robson
źródło
4
Sprawdź definicję .
Kaveh
3
Mieszasz dwie koncepcje: funkcje jednokierunkowe i funkcje nieodwracalne. Chociaż funkcja Sinus jest nieodwracalna, nie jest to jeden sposób. W szczególności, zawsze można wymyślić w preimage (aby cokolwiek precyzja chcesz), nawet jeśli nie jest preimage.
MS Dousti,
Rozumiem, dziękuję za wyjaśnienie tego rozróżnienia.
Aaron Robson,