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. $\pi \colon \{0,1\}^* \to \{0,1\}^*$ $\pi$ $\pi$

Na przykład funkcja NOT jest jedną z takich permutacji:

funkcja NOT (x)
    Niech y = x
    Dla i = 1 do | x |
        Odwróć i-ty kawałek y
    zwróć y

$\pi_k(\cdot)$ , zdefiniowany poniżej, to kolejny przypadek:

funkcja pi_k (x)
    return x + k (mod 2 ^ | x |)

Moje pytanie dotyczy specjalnej klasy permutacji, zwanych permutacjami jednokierunkowymi . Mówiąc nieformalnie, są to permutacje, które są łatwe do obliczenia, ale trudne do odwrócenia (dla maszyny ). Samo istnienie permutacji jednokierunkowych jest od dawna otwartym problemem w kryptografii i teorii złożoności, ale w pozostałej części założymy, że istnieją. $\rm{BPP}$

Jako przykład przypuszczalnej permutacji jednokierunkowej można rozważyć RSA : Niech będzie liczbą całkowitą Bluma , a niech . Permutacja jednokierunkowa jest zdefiniowana przez: . $n = pq$ $e = 65537$ $\pi_n(x) = x^e \bmod n$

Zauważ, że RSA jest zdefiniowane w domenie skończonej . W rzeczywistości, aby uzyskać nieskończoną permutację domeny, należy wziąć pod uwagę rodzinę permutacji RSA , gdzie jest nieskończonym zestawem liczb całkowitych Blum. Zauważ, że jest opisem rodziny i z definicji jest nieskończony. $\mathbb{Z}_n$ $\{\pi_n\}_{n\in D}$ $D$ $D$

Moje pytanie brzmi (zakładając istnienie permutacji jednokierunkowych):

Czy istnieją jednokierunkowe permutacje opisu skończonego w nieskończonej domenie ?

Odpowiedź może być różna: może być pozytywna, negatywna lub otwarta ( może być pozytywna lub negatywna ).

tło

Pytanie pojawiło się, gdy czytałem artykuł ASIACRYPT 2009 . Tam autor niejawnie (i w kontekście jakiegoś dowodu) założył, że istnieją takie kombinacje jednokierunkowe.

Będę szczęśliwy, jeśli rzeczywiście tak jest, chociaż nie mogłem znaleźć dowodu.

cc.complexity-theory co.combinatorics cr.crypto-security descriptive-complexity one-way-function MS Dousti
źródło

Czy nie możemy ostatecznie opisać ? Istnieje algorytm skończony szukający najmniejszej liczby Blum większej niż pewna liczba wejściowa, więc obliczenie można opisać na przykład jako „znajdź najmniejszą liczbę Blum większą niż , a następnie oblicz ”. Jednak nie jest dla mnie oczywiste, że funkcja, którą uzyskasz, sklejając ze sobą nieskończoną liczbę , będzie koniecznie permutacją. Czy możesz wytłumaczyć?

D

$D$

π (x)

$\pi(x)$

b

$b$

x

$x$

π_{b} (x)

$\pi_b(x)$

π_{b}

$\pi_b$

Karolina Sołtys,

@Karolina: Dzięki za odpowiedź. Myślę, że algorytm „znajdź najmniejszą liczbę Bluma większą niż , a następnie oblicz ” będzie koniecznie wyświetlał dodatkowe informacje o , takie jak jego rozkład na czynniki. Dlatego takiego algorytmu nie można użyć do opisania permutacji jednokierunkowych . Czy sie zgadzasz?

b

$b$

x

$x$

π_{b} (x)

$\pi_b(x)$

b

$b$

MS Dousti,

Ok, myślę, że rozumiem - chcesz, aby skończony opis opisywał funkcję w sposób łatwy do obliczenia. Myślę, że moglibyśmy zakodować część „znajdź najmniejszy numer Bluma ...” bez ujawniania jakichkolwiek informacji o (po prostu zaimplementuj wyszukiwanie ), ale wtedy nie byłoby to wydajnie obliczalne.

b

$b$

b

$b$

Karolina Sołtys,

Może to pytanie pomoże w pomysłach: cstheory.stackexchange.com/questions/1378

Matt Groff

@Matt: Dzięki. W tym pytaniu warunek „łatwy do obliczenia, ale trudny do odwrócenia” nie dotyczy maszyn z ograniczeniami czasowymi.

MS Dousti,

Artykuł „ Konstruowanie funkcji jednokierunkowych 1-1” autorstwa Goldreicha, Levina i Nisana pokazuje, jak konstruować funkcje 1-1 zachowujące długość z nieskończonymi domenami i skończonym opisem. Twardość odwracania funkcji opiera się na popularnych założeniach, takich jak twardość odwracania RSA lub znajdowanie dyskretnych logarytmów.

Ich konstrukcja jest zwrotem prostej idei przekształcenia rodziny , funkcji jednokierunkowych w jedną funkcję jednokierunkową poprzez ustawienie gdzie jest losowość wykorzystywane do pobierania indeks i jest losowość używany do wyboru wejściowego (biorąc pod uwagę indeks ). $\{f_i\}_i$ $f(r,s) = f_i(x)$ $r$ $i$ $s$ $x$ $i$

Problem z powyższym pomysłem polega na tym, że niekoniecznie oznacza 1-1. Poprawiają ten problem, nieznacznie modyfikując i argumentując, że pod pewnymi warunkami dla rodziny , nowa konstrukcja jest rzeczywiście 1-1. Następnie pokazują, że te warunki są spełnione przez funkcje oparte na logach RSA / Discrete-log. $f(r,s)$ $f(r,s)$ $\{f_i\}_i$

Alon Rosen
źródło

Dzięki Alon za wspaniałą odpowiedź. Off-topic: Cieszę się, że cię tu widzę. Uwielbiam twoją książkę i artykuły na temat równoczesnej wiedzy zerowej !

MS Dousti,

Dzięki, Sadeq. Cieszę się, że Ci się podoba :-)

Alon Rosen

Skończona jednokierunkowa permutacja z nieskończoną domeną

tło

Odpowiedzi: