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 każda jest permutacją jednokierunkową, działającą na skończonej domenie . Klapa jednokierunkowy permutacji jest zdefiniowany jak powyżej, z tym, że istnieje szereg klapa i poli-czas inwersji algorytm , tak, że dla wszystkich , i$\pi$$\pi = \{\pi_n\}_{n \in \mathbb{N}}$$\pi_n$$D_n$$\{t_n\}_{n \in \mathbb{N}}$$I$$n$$|t_n| \le {\rm poly}(n)$$I$ odwrócić pod warunkiem, że podano .$\pi_n$$t_n$

Znam jednokierunkowe permutacje, które są generowane, więc znalezienie zapadni jest niemożliwe (a jednak zapadnia istnieje). Przykładem, na podstawie RSA-założeniu, podana jest tutaj . Pytanie brzmi,

Czy istnieją (rodziny) kombinacje jednokierunkowe, które nie mają zapadni (zestawu)?

Edycja: (więcej formalizacji)

Załóżmy, że istnieje pewna permutacja jednokierunkowa z (nieskończoną) domeną . Oznacza to, że istnieje probabilistyczny algorytm wielomianowy (który na wejściu indukuje pewien rozkład w zakresie ), taki że dla dowolny przeciwnik w czasie wielomianowym , dowolny i wszystkie wystarczająco duże liczby całkowite :$\pi$$D \subseteq \{0,1\}^*$$\mathcal{D}$$1^n$$D_n=\\{0,1\\}^n \cap D$$\mathcal{A}$$c>0$$n$

$\Pr[x \leftarrow \mathcal{D}(1^n) \colon \quad \mathcal{A}(\pi(x))=x]<n^{-c}$

(Prawdopodobieństwo to przejmuje wewnętrzne rzuty monetą $\mathcal{D}$ i $\mathcal{A}$ .)

Pytanie brzmi, czy możemy zbudować permutację jednokierunkową , dla której istnieje probabilistyczny algorytm wielomianowo-czasowy taki, że dla dowolnej rodziny obwodów , dowolne i wszystkie wystarczająco duże liczby całkowite :$\pi'$$\mathcal{D}'$ $\mathcal{A}'=\{\mathcal{A}'_n\}_{n \in \mathbb{N}}$$c>0$$n$

$\Pr[x \leftarrow \mathcal{D}'(1^n) \colon \quad \mathcal{A}'_n(\pi'(x))=x]<n^{-c}$

(Prawdopodobieństwo jest przejmowane przez rzuty monetą , ponieważ jest deterministyczne).$\mathcal{D}'$$\mathcal{A}'$

Rozważ następujące przypadki:

1) Istnieją permutacje jednokierunkowe (OWP), ale nie istnieją permutacje zapadni (TDP) (tzn. Jesteśmy w wariancie „ minicrypt ” świata Impagliazza ). W takim przypadku wystarczy wziąć OWP, który na pewno istnieje i wiesz, że nie ma zapadni.

2) Istnieją zarówno OWP, jak i TDP. Tutaj masz dwie opcje:

(a) Każdy OWP ma algorytm generowania klucza G, który wyprowadza „publiczny” opis funkcji f wraz z próbkowaną zapadnią t. W takim przypadku rozważ zmodyfikowane generowanie klucza, które generuje tylko f. Daje to OWP, a ponadto nie można znaleźć t danego f (ponieważ w przeciwnym razie masz skuteczny sposób na odwrócenie f). To powinno również dotyczyć wariantu niejednorodnego.

(b) Istnieje OWP f taki, że żaden algorytm G nie może wyprowadzać zarówno f ​​it, tak że t umożliwia odwrócenie f (x) dla losowego x. W tym przypadku f jest OWP, który nie ma klapy.

Jeden z komentarzy w powyższym wątku wydaje się sugerować, że faktycznie pytasz, czy istnienie OWP sugeruje istnienie TDP. Zostało to pokazane, aby nie zawierało konstrukcji / redukcji wrt czarnej skrzynki i jest ogólnie otwarte (patrz mój komentarz w powyższym wątku).

Nie wiem o konstrukcjach z ogólnych założeń, ale możesz uzyskać wiarygodnego kandydata na „jednokierunkową permutację bez zapadni”, używając dyskretnego logarytmu modulo a prime . To znaczy, niech będzie prymitywnym modułem root i zdefiniuj . Zatem jest permutacją liczb całkowitych od do i ogólnie przyjmuje się, że jest jednokierunkowa. W przypadku części „bez zapadni”, przypuszczam, że musisz dokładnie zdefiniować, co to znaczy, ale o ile wiem, nie mamy możliwości skonfigurowania rzeczy, aby umożliwić odwrócenie. (Gdybyśmy to zrobili, to miałoby wiele fajnych (pozytywnych) aplikacji w kryptografii!)$p$$g$$p$$\pi(x) = g^x\!\mod p$$\pi$$1$$p-1$