Formalna definicja funkcji VMPC i problemu jej odwracania

Część treści poniżej stanowi wyciąg z oficjalnej wersji pracy. Wynika stąd wymieszanie języków (polski z angielskim). Praca napisana jest, oczywiście, w języku angielskim, gdyż jest to przyjęty na świecie język stosowany w nauce.

Elementarne własności funkcji VMPC (ich dowody znajdują się w pracy):

Ogólna definicja funkcji jednokierunkowej:

Uproszczone tłumaczenie powyższej definicji na język polski:



V(x)=(P ∘ M₂ ∘ P ∘ M₁ ∘ P)(x)

dla x ∈ {1,2,...,N}, gdzie P i V są permutacjami zbioru {1,2,...,N};
M₁ i M₂ są dowolnymi permutacjami zbioru {1,2,...,N} takimi, że M₁(x) ≠ M₂(x) dla każdego x ∈ {1,2,...,N}.

(Uwaga dla wnikliwych: formalnie stwierdzenie to jest równoważne Lematowi 1, który wynika (dość bezpośrednio) z definicji funkcji, ale jest on (Lemat 1) znacznie bardziej czytelny niż zawarte w anglojęzycznej definicji funkcji warunki, a w zakresie objętym przez poniższy tekst Lemat 1 jest wystarczający do zilustrowania istoty funkcji VMPC. Stąd uproszczenie.)

Przykład funkcji VMPC (tu - na zbiorze {0,1,...,N-1}) dla M₁(x)=x oraz M₂(x)=(x+1) modulo N,
przyjmując, że + oznacza dodawanie modulo N:

V(x)=P(P(P(x))+1)

Co to znaczy, że funkcja jest jednokierunkowa? Ogólnie - jej odwrócenie, a więc znalezienie argumentów (permutacji P) na podstawie wartości (permutacji V), jest obliczeniowo niewykonalne.

W funkcji VMPC permutacje M₁ i M₂ zakłócają strukturę cykli permutacji P, w wyniku czego podczas obliczania wartości V(x)=P(M₂(P(M₁(P(x))))) elementy permutacji P zostają rozlokowane w poszczególnych elementach permutacji V (każdy element V używa dwóch lub trzech elementów P) w sposób przypominający losowy. W efekcie nie ma niezawodnego sposobu na znalezienie dwóch elementów V, które używają dwóch wspólnych elementów P. Odtworzenie P na podstawie V możliwe jest dopiero po zgadnięciu pewnej (zależnej od N) liczby elementów P. Odwrócenie funkcji VMPC sprowadza się do przeszukania wszystkich możliwych kombinacji tych zgadywanych elementów.

Permutacje M₁ i M₂, gdzie M₁(x) ≠ M₂(x), decydują o jednokierunkowości funkcji VMPC. Każde wystąpienie M₁(x)=M₂(x) (wbrew definicji) osłabia jednokierunkowe własności funkcji. Zwykłe złożenie permutacji C(x)=P(P(P(x))) jest funkcją łatwą do odwrócenia. Możemy ją zapisać w terminologii VMPC przy pomocy M₁(x)=M₂(x)=x. Funkcja na zbiorze {0,1,...,N-1}: D(x)=P(P(P(x)+1)+1), gdzie M₁(x)=M₂(x)=(x+1) modulo N, byłaby tak łatwa do odwrócenia, jak C(x)=P(P(P(x))).



Z przeprowadzonych badań wynika, że liczba elementów permutacji P, których zgadnięcie jest niezbędne do odwrócenia funkcji VMPC, rośnie liniowo ze wzrostem rozmiaru permutacji - o 1 zgadywany element na każde 8 elementów permutacji.

Przekłada się to na przybliżony wzór na średnią ilość obliczeń K niezbędną do odwrócenia funkcji VMPC:

K=N! / (N*0,875)!

Dla N=16 mamy: Y=16¹⁰⁰=10^120,4, natomiast K=16!/14!=16*15=240

Dla N=808 mamy: Y=808¹⁰⁰=10^290,7, natomiast K=808!/707!=808*807*...*708=10^290,8

Dla N=1000 mamy: Y=1000¹⁰⁰=10³⁰⁰, natomiast K=1000!/875!=1000*999*...*876=10^371,4

Dowód