27.10.2018







Projekt VMPC:


Badania nad funkcją VMPC i problemem matematycznym "czy P=NP?"
pieknafunkcja.pl



Aplikacja do szyfrowania danych VMPCrypt
szyfrowanie.com



Gra Permutu na bazie funkcji VMPC
permutu.pl







Zobacz także:


Gra komputerowa Urban



Multimedialne kursy do nauki języka angielskiego
ADL Publishing




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 ∘ M2 ∘ P ∘ M1 ∘ P)(x)

dla x ∈ {1,2,...,N}, gdzie P i V są permutacjami zbioru {1,2,...,N};
M1 i M2 są dowolnymi permutacjami zbioru {1,2,...,N} takimi, że M1(x) ≠ M2(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 M1(x)=x oraz M2(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 M1 i M2 zakłócają strukturę cykli permutacji P, w wyniku czego podczas obliczania wartości V(x)=P(M2(P(M1(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 M1 i M2, gdzie M1(x) ≠ M2(x), decydują o jednokierunkowości funkcji VMPC. Każde wystąpienie M1(x)=M2(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 M1(x)=M2(x)=x. Funkcja na zbiorze {0,1,...,N-1}: D(x)=P(P(P(x)+1)+1), gdzie M1(x)=M2(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)!

Powtórzmy, jest to wzór przybliżony, który oddaje istotę zjawiska i rząd wielkości liczby K. Wzór jest określony dla N podzielnych przez 8.



Jednokierunkowość funkcji precyzyjniej definiujemy następująco: Funkcja VMPC byłaby jednokierunkowa, gdyby średnia ilość obliczeń niezbędna do odtworzenia N-elementowej losowo wybranej permutacji P na podstawie permutacji V była niewielomianowym przekształceniem liczby N.

Obrazowo - przekształcenie niewielomianowe to takie, którego wartości gwałtownie rosną. Intuicyjnie sens definicji jest taki, że funkcja jednokierunkowa to taka, której trudność odwrócenia (mierzona ilością obliczeń) rośnie gwałtownie (niewielomianowo) ze wzrostem wielkości zadania (u nas - ze wzrostem rozmiaru permutacji P mierzonego liczbą N).

Gdyby odwrócenie funkcji wymagało średnio np. N100 obliczeń, to mimo że jest to liczba ogromna, funkcja taka nie byłaby jednokierunkowa, gdyż N100 jest przekształceniem wielomianowym.

Dopiero gdyby odwrócenie funkcji wymagało średnio np. 2N albo N! obliczeń, funkcja taka byłaby jednokierunkowa, bowiem funkcja potęgowa (2N) czy silnia (N!) są przekształceniami niewielomianowymi.

Zawsze da się znaleźć odpowiednio duże N, dla którego wartość przekształcenia niewielomianowego (np. N!) jest większa niż wartość przekształcenia wielomianowego Na.



Szacowana średnia ilość obliczeń niezbędna do odwrócenia funkcji VMPC K=N!/(N*0,875)! jest przekształceniem niewielomianowym. Aby to zilustrować, porównajmy jego wartości z wartościami przykładowego wielomianowego przekształcenia Y=N100.

Wzór K=N! / (N*0,875)! opisuje iloczyn N/8 kolejnych liczb: N*(N-1)*(N-2)*...*(N*7/8+1).

Dla małych N liczba Y będzie znacznie większa od K:

Dla N=16 mamy: Y=16100=10120,4, natomiast K=16!/14!=16*15=240

Wartość Y to ponad 1 i 120 zer, a nasze "wielkie niewielomianowe" K ma wartość zaledwie 240. Zwiększmy jednak N:

Dla N=808 mamy: Y=808100=10290,7, natomiast K=808!/707!=808*807*...*708=10290,8

Dla N=808 wartość K=10290,8, która jest tu iloczynem 101 liczb, przewyższyła już wartość Y=10290,7 (będącą zawsze iloczynem 100 liczb). Jeśli zwiększymy N jeszcze bardziej:

Dla N=1000 mamy: Y=1000100=10300, natomiast K=1000!/875!=1000*999*...*876=10371,4

Dla N=1000 wartość K jest już 1071,4 (ponad sto biliardów kwadryliardów kwadryliardów) razy większa niż Y. K jest tu iloczynem 125 liczb, a Y wciąż pozostaje iloczynem 100 liczb. Niewielomianowa wartość K będzie się coraz bardziej oddalać od wielomianowego Y dla coraz większych N. I tak właśnie, niewielomianowo, rośnie złożoność odwrócenia funkcji VMPC. Dlatego właśnie funkcja ta jest jednokierunkowa.



Wyniki symulacji odwracania funkcji VMPC wykonanych przy pomocy różnych algorytmów ostatecznie prowadzą do takich samych wyników, zaprezentowanych w tabeli poniżej. Tabela pokazuje ilości elementów permutacji P, których zgadnięcie jest konieczne, oraz wynikające z nich średnie ilości obliczeń niezbędne do odwrócenia funkcji VMPC dla kilku przykładowych rozmiarów permutacji:

N: rozmiar permutacji G: liczba zgadywanych elementów L: średnia ilość obliczeń R = (G-2) / N
8 3 25,5 1/8 = 0,125
16 4 211,5 1/8 = 0,125
32 6 224 1/8 = 0,125
64 10 253 1/8 = 0,125
128 18 2117 1/8 = 0,125
256 34 2260 1/8 = 0,125


Średnie ilości obliczeń wynikające z symulacji (kolumna L w tabeli) są nieco większe od wartości szacowanych niewielomianowym wzorem K=N! / (N*0,875)!. Wynika to z faktu, że wzór nie uwzględnia pierwszych dwóch zgadywanych elementów P (np. dla N=8 wzór zwraca wartość K=8, co odpowiada jednemu zgadywanemu elementowi, podczas gdy wg symulacji dla N=8 zgadywane są 3 elementy P). W wyniku tego uproszczenia wzór ma klarowniejszą postać, a odwrócenie funkcji jest jeszcze trudniejsze niż wzór podaje.


Dowód




Od roku 2015 pracuję nad zapisaniem formalnego dowodu jednokierunkowości funkcji VMPC. Sam dowód tworzyłem na brudno w latach 2004-2015. Tak wygląda kompletny brudnopis zawierający wyniki mojej pracy:

Przełożenie tego na formalny język matematyki i zapisanie na czysto w pracy naukowej jest bardzo mozolnym i czasochłonnym zadaniem. Proces ten jest już jednak na ukończeniu. Praca na czysto ma obecnie ponad 70 stron A4. Zapisywanie głównego toku rozumowania zostało ukończone w połowie 2016. Od tamtego czasu trwa etap szlifowania pracy, którego dominującym elementem jest formalne uściślanie wszystkich użytych w dowodzie faktów dotyczących funkcji VMPC.

Tutaj można znaleźć prowadzony przeze mnie od 2015 roku

nieformalny blog z przebiegu pisania pracy.

Uzyskane w dowodzie prawdopodobieństwo odwrócenia funkcji jest o wiele wyższe niż to, które zostało zilustrowane w tekście powyżej i które pochodzi z najefektywniejszego algorytmu odwracania funkcji, jaki znam. Oznacza to, że w praktycznej rzeczywistości (cokolwiek ona dla matematyka oznacza...) funkcja VMPC jest jeszcze trudniejsza do odwrócenia niż to, co mówi dowód.

Dowód opisuje szereg zjawisk kombinatorycznych wynikających z konstrukcji funkcji VMPC, które pozwalają wyznaczyć maksymalną wartość prawdopodobieństwa (będącego odwrotnością niewielomianowej funkcji rozmiaru permutacji, N), z jakim dowolny algorytm odwracania funkcji może wygenerować prawidłowy wynik (znaleźć jakąkolwiek permutację P, dla której przy zadanej wartości V zachodzi VMPC(P)=V).

Mówiąc ilustracyjnie i nieformalnie, dowód określa maksymalną "wydajność" jakiegokolwiek algorytmu odwracania funkcji. Podobnie, jak nie możemy przekroczyć prędkości światła, tak żaden algorytm nie może odwrócić funkcji VMPC z wyższym prawdopodobieństwem niż to wykazane w dowodzie.

Dowód ten, jeśli zostanie uznany za prawidłowy, będzie oznaczał rozwiązanie problemu "czy P=NP" przez wykazanie, że P ≠ NP, co jest konsekwencją istnienia funkcji jednokierunkowej. Clay Mathematics Institute zaliczył ten problem jako jeden z 7 największych nierozwiązanych problemów matematyki.

Jak dotąd nie jest znana na świecie żadna funkcja jednokierunkowa, której jednokierunkowość byłaby udowodniona, a nie tylko domniemana.

Funkcja VMPC byłaby pierwszą udowadnialną funkcją jednokierunkową na świecie, a rozwiązanie problemu "czy P=NP" byłoby tylko (pozytywnym!) efektem ubocznym tego faktu.



Ilustracyjne i nieformalne przedstawienie, skąd pochodzi nazwa funkcji VMPC - Variably Modified Permutation Composition (Zmiennie Modyfikowane Złożenie Permutacji).
  • P oznacza permutację.
  • P(P(P(x))) to złożenie permutacji, czyli jedna z podstawowych operacji na permutacjach.
  • P(M(P(M(P(x))))) to modyfikowane złożenie permutacji - elementy permutacji podczas składania są modyfikowane przez dodatkową permutację M.
  • P(M2(P(M1(P(x))))) to Zmiennie Modyfikowane Złożenie Permutacji, czyli funkcja VMPC. Elementy permutacji podczas składania są modyfikowane przez dwie różne permutacje M1 i M2 (co ściśle oznacza tu słowo "różne" - patrz formalna definicja funkcji).







FSE 2004
Publikacja na konferencji Międzynarodowego Stowarzyszenia Badań Kryptologicznych (IACR) FSE 2004


Konferencje Enigma
Publikacje na Krajowej Konferencji Zastosowań Kryptografii Enigma w Warszawie


WCTT
Nagroda Wrocławskiego Centrum Transferu Technologii przy Politechnice Wrocławskiej


Software Developer's Journal
Rekomendowany projekt magazynu Software Developer's Journal


Copyright © 1999-2018 by Bartosz Żółtak
Aktualizacja: 27.10.2018