Pytania dotyczące łatwych do obliczenia, ale trudnych do odwrócenia funkcji.
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
Czy można przekształcić CNF w inny CNF Ψ ( C ), taki jak?CC\mathcal CΨ(C)Ψ(C)\Psi(\mathcal C) Funkcja może być obliczona w czasie wielomianowym z jakiegoś tajnego parametru losowego r .ΨΨ\Psirrr ma rozwiązanie wtedy i tylko wtedy, gdy C ma rozwiązanie.Ψ(C)Ψ(C)\Psi(\mathcal C)CC\mathcal C Każde...
Funkcja jest jednokierunkowa, jeśli f można obliczyć za pomocą algorytmu wielomianowego czasu, ale dla każdego losowego algorytmu wielomianowego czasu A ,f:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f \colon \{0, 1\}^* \to \{0, 1\}^*fffAAA Pr[f(A(f(x)))=f(x)]<1/p(n)Pr[f(A(f(x)))=f(x)]<1/p(n)\Pr[f(A(f(x)))...
Nieformalnie funkcje jednokierunkowe są definiowane w odniesieniu do algorytmów PTIME. Są obliczalne w czasie wielomianowym, ale nie są odwracalne w czasie wielomianowym średniego przypadku. Istnienie takich funkcji jest ważnym otwartym problemem w informatyce teoretycznej. Interesują mnie funkcje...
Istnieje stara sztuczka polegająca na spisaniu algorytmu, który, jeśli P = NP, rozwiązuje SAT w czasie wielomianowym. Zasadniczo, wymieniono wszystkie wielomianowe wehikuły czasu i wielozadaniowość nad nimi. Czy istnieje analogiczna sztuczka dla funkcji jednokierunkowych (a nawet jednokierunkowych...
Niech będzie permutacją. Zauważ, że chociaż działa w nieskończonej domenie, jego opis może być skończony. Przez opis rozumiem program, który opisuje funkcjonalność . (Jak w złożoności Kołmogorowa.) Zobacz wyjaśnienia poniżej. π ππ:{0,1}∗→{0,1}∗π:{0,1}∗→{0,1}∗\pi \colon \{0,1\}^* \to...
Moje pytanie dotyczy równoważności bezpieczeństwa różnych kandydujących funkcji jednokierunkowych, które można zbudować w oparciu o twardość faktoringu. Zakładając problem FAKTORING: [Biorąc pod uwagę dla losowych liczb pierwszych , znajdź , ]P , Q < 2 n P QN.= PQN=PQN = PQP., Q <...
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...
W skrócie: Zakładając, że istnieją kombinacje jednokierunkowe , czy możemy zbudować taką, która nie ma zapadni? Więcej informacji: Permutacja jednokierunkowa to permutacja którą łatwo obliczyć, ale trudno ją odwrócić ( więcej informacji na temat formalnej definicji znajduje się w wiki tagu...
Powszechnie wiadomo, że istnienie funkcji jednokierunkowych jest konieczne i wystarczające dla dużej części kryptografii (podpisy cyfrowe, generatory pseudolosowe, szyfrowanie kluczem prywatnym itp.). Moje pytanie brzmi: jakie są teoretyczne konsekwencje istnienia funkcji jednokierunkowych? Na...