Formalna definicja funkcji VMPC i problemu jej odwracania

VMPC to skrót od Variably Modified Permutation Composition (Zmiennie Modyfikowane Złożenie Permutacji).^*1

Funkcja VMPC jest przekształceniem permutacji P według wzoru:

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

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

Przykład funkcji VMPC dla M₁(x)=x oraz M₂(x)=(x+1) modulo N:

V(x)=P(P(P(x))+1)
przyjmując, że + oznacza dodawanie modulo N.

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.

Odwracanie funkcji VMPC przypomina znajdowanie części wspólnych N zbiorów zawierających po 3 losowo wybrane liczby spośród {0,1,...,N-1}. Nie ma niezawodnego sposobu na wybranie zbioru, w którym znajdują się dwie liczby występujące również w innym zbiorze.

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 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