Pytania otagowane jako one-way-function

Pytania dotyczące łatwych do obliczenia, ale trudnych do odwrócenia funkcji.

5
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:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f \colon \{0, 1\}^* \to \{0, 1\}^*fffAAA Pr[f(A(f(x)))=f(x)]&lt;1/p(n)Pr[f(A(f(x)))=f(x)]&lt;1/p(n)\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
Funkcja, która ma być jednokierunkowa, jeśli istnieją funkcje jednokierunkowe?
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 funkcji zapadni)? Czy możemy zapisać funkcję, która, jeśli istnieją funkcje jednokierunkowe, jest koniecznie …
1
Funkcje jednokierunkowe w odniesieniu do różnych granic zasobów
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 jednokierunkowe (niekoniecznie dla aplikacji kryptograficznych) zdefiniowane w odniesieniu do różnych granic zasobów. Takimi …
2
Funkcje jednokierunkowe a doskonale wiążące zobowiązania
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
1
Zredukowanie podstawowych produktów faktoringowych do faktoringowych liczb całkowitych (w przeciętnym przypadku)
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 &lt; 2 n P QN.= PQN=PQN = PQP., Q &lt; 2nP,Q&lt;2nP, Q < 2^nP.PPQQQ funkcja nie może …
1
Skończona jednokierunkowa permutacja z nieskończoną domeną
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 \{0,1\}^*ππ\piππ\pi Na przykład funkcja NOT jest jedną z takich permutacji: funkcja NOT (x) Niech y …
2
Konsekwencje OWF dla złożoności
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 przykład sugerują to OWFN P ≠ PN.P.≠P.\mathsf{NP}\ne\mathsf{P}, B P P = PbP.P.=P.\mathsf{BPP}=\mathsf{P}, i C Z K = …
2
Permutacje w jedną stronę bez klapy
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 jednokierunkowego ). Zazwyczaj rozważamy rodziny permutacji jednokierunkowej, , gdzie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.