Złożoność obliczeniowa/Wykład 15: Kryptografia a złożoność

Funkcje jednokierunkowe

W dotychczasowych rozważaniach naszym celem było znalezienie możliwie efektywnego rozwiązania dla zadanych problemów; nadmierna złożoność problemu była przez nas traktowana jako cecha niepożądana, gdyż utrudniająca nasze zadanie. W tym rozdziale nasze podejście będzie odmienne; duża złożoność będzie dla nas cechą bardzo cenną. Będzie nas przy tym w mniejszym niż dotychczas stopniu interesować złożoność pesymistyczna -- w końcu nie satysfakcjonuje nas "gwarancja", mówiąca że "jeżeli osoba podsłuchująca będzie miała pecha to odszyfrowanie wiadomości będzie dla niej zadaniem czasochłonnym". Wolelibyśmy, żeby odszyfrowywanie wiadomości przez osoby nieuprawnione było czasochłonne praktycznie zawsze -- tak, by próba podsłuchiwania dawała szansę sukcesu bardzo bliską zeru. Duża pesymistyczna złożoność nie będzie zatem warunkiem wystarczającym bycia dobrym kryptosystemem; przyda nam się jednak w charakterze warunku koniecznego.

Definicja

Niech $f:\{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$. Mówimy, że $f$ jest funkcją jednokierunkową wtedy i tylko wtedy gdy:

• $f$ jest różnowartościowa,
• istnieje pewna stała $k>1$ taka, że ${\mathrm{\forall }}_{x\in \{0,1{\}}^{\star }}|x{|}^{1/k}\le f(x)\le |x{|}^k$,
• $f$ jest obliczalna w czasie wielomianowym (czyli należy do klasy $FP$),
• nie istnieje wielomianowy algorytm obliczający odwrotność funkcji $f$

-- czyli znajdujący dla słowa $y$ słowo $x$, takie że $f(x)=y$ lub stwierdzający, że takie słowo nie istnieje.

Warto zauważyć, że powyższa definicja niejawnie zakłada prawdziwość zdania $P\ne NP$.

Ćwiczenie

Niech $f$ spełnia pierwsze trzy warunki podane w definicji funkcji jednokierunkowej. Pokaż, że obliczanie odwrotności funkcji $f$ jest problemem z klasy $FNP$.

Rozwiązanie

Z drugiego warunku wiemy, że $f^{-1}(y)$ ma długość co najwyżej $|y{|}^k$. Możemy zatem jako kandydatów na świadków rozpatrywać wszystkie słowa o długości nie większej niż $|y{|}^k$. Takie słowa możemy następnie deterministycznie przekształcić za pomocą funkcji $f$ i sprawdzić, czy otrzymane słowo jest równe $y$.

Z drugiej strony nierówność $P\ne NP$ wcale nie gwaratuje istnienia funkcji jednokierunkowych; jak się okazuje istnienie tego typu funkcji jest ściśle powiązane z pewną klasą złożoności, którą przedstawiamy poniżej.

Definicja Jednoznaczną maszyną Turinga

nazywamy niedeterministyczną maszynę Turinga taką, że dla każdego słowa wejściowego $x$ istnieje co najwyżej jedna akceptująca ścieżka obliczeń.

Definicja

Klasa $UP$ to klasa problemów rozstrzygalnych za pomocą jednoznacznych maszyn Turinga w czasie wielomianowym.

Uwaga

Klasę $UP$, podobnie jak klasę $NP$, można zdefiniować z użyciem pojęcia świadka:

{12pt} $L\in UP⟺{\mathrm{\exists }}_{p(x)-wielomian}{\mathrm{\exists }}_{L^{\prime }\in P}{\mathrm{\forall }}_{n\in \mathbb{\mathbb{N}}}{\mathrm{\forall }}_{w\in \{0,1{\}}^n}[w\in L\Rightarrow ({\mathrm{\exists }!}_{v\in \{0,1{\}}^{p(n)}}⟨w,v⟩\in L^{\prime })]\wedge [w\notin L\Rightarrow (\mathrm{\neg }{\mathrm{\exists }}_{v\in \{0,1{\}}^{p(n)}}⟨w,v⟩\in L^{\prime })]$ {12pt}

W językach z klasy $UL$ każde słowo ma dokładnie jednego świadka. Dowód równoważności powyższych definicji jest analogiczny jak w przypadku klasy $NP$.

Jest jasne, że $P\subseteq UP\subseteq NP$ -- maszyny deterministyczne są specjalnymi przypadkami maszyn jednoznacznych. Dość powszechny jest pogląd, że obie powyższe relacje zawierania są właściwe (to znaczy nie zachodzi równość).

Pokażemy teraz bardzo ciekawy związek pomiędzy klasą $UP$ a funkcjami jednokierunkowymi.

Twierdzenie

Funkcje jednokierunkowe istnieją $⟺UP\ne P$

Dowód

Zaczniemy od dowodu w kierunku $\Rightarrow$. Załóżmy, że istnieje pewna funkcja jednokierunkowa $f$. Możemy wtedy zdefiniować następujący język:

{12pt} $L_f=\{(x,y):{\mathrm{\exists }}_{z}f(z)=y\wedge z\le x\}$ {12pt}

przy czym mówimy, że $z\le x$ wtedy i tylko wtedy gdy

• $|z|\le |y|$, lub
• $|z|=|y|$ i w porządku leksykograficznym $z$ występuje nie później niż

$x$.

Łatwo można zauważyć, że $L_f\in UP$ - maszyna rozwiązująca ten problem najpierw "zgaduje" słowo $z$ o wielkości nie większej niż $|y{|}^k$, po czym sprawdza, czy w ustalonym porządku występuje ono nie później niż $x$ i czy zachodzi $f(z)=y$. Z własności funkcji jednokierunkowych -- konkretnie z różnowartościowości -- wynika, że maszyna ta ma co najwyżej jedną akceptującą ścieżkę postępowania.

Chcemy teraz pokazać, że $L_f\notin P$. Załóżmy zatem nie wprost, że istnieje jakiś wielomianowy algorytm rozwiązujący $L_f$. Wykorzystamy go teraz do obliczenia odwrotności funkcji $f$ w czasie wielomianowym. W pierwszym kroku zapytamy algorytm, czy $(1^{|y{|}^k},y)\in L_f$ (przez $1^{|y{|}^k}$ oznaczamy tutaj ciąg $|y{|}^k$ symboli $1$) - jeżeli otrzymamy odpowiedź "nie" to korzystając z definicji funkcji jednokierunkowej możemy od razu stwierdzić, że nie istnieje słowo $x$ takie, że $f(x)=y$. Jeżeli otrzymamy odpowiedź "tak" to z użyciem co najwyżej $|y{|}^k-1$ zapytań do naszego algorytmu jesteśmy w stanie ustalić długość szukanego słowa $x$ (pytamy kolejno o $(1^{|y{|}^k-1},y)$, $(1^{|y{|}^k-2},y)$, itd. aż do momentu gdy uzyskamy odpowiedź "nie"). Gdy znamy już długość słowa $x$ pozostaje nam już tylko obliczyć kolejne jego bity. Pierwszy bit otrzymamy pytając o parę $(01^{|x|-1},y)$ -- odpowiedź "tak" oznacza, że pierwszym bitem jest 0. Aby uzyskać drugi bit zapytamy -- w zależności od pierwszej odpowiedzi -- o $(001^{|x|-2},y)$ lub $(101^{|x|-2},y)$. Kolejne bity odgadujemy w analogiczny sposób -- łącznie zatem wykonamy algorytm dla $L_{f}O(|y{|}^k)$ razy. W ten sposób uzyskamy deterministycznty algorytm odwracający funkcję $f$ w czasie wielomianowym.

Doszliśmy więc do sprzeczności z definicją funkcji jednokierunkowej, co oznacza, że istnienie funkcji jednokierunkowych implikuje nierówność $P\ne UP$.

Załóżmy teraz, że istnieje język $L\in UP-P$, rozpoznawany przez jednoznaczną maszynę $U$. Zdefiniujmy funkcję $f_U(w)$ w następujący sposób:

• jeżeli $w$ jest zakodowaną parą słów $⟨x,y⟩$ oraz $x$

jest (jedynym) świadkiem przynależności słowa $y$ do $L$, to

{12pt} $f_U(w)=1y$, {12pt}

• w przeciwnym przypadku

{12pt} $f_U(w)=0w$, {12pt}

Widzimy, że pierwszy symbol wartości funkcji gwarantuje nam jej różnowartościowość. Spełniony jest również drugi warunek z definicji funkcji jednokierunkowej -- świadek dla słowa $y$ nie może być nadmiernie długi (bo jego długość jest wielomianowo zależna od długości $y$), a zatem $f_U$ nie może nadmiernie "skracać" słów. Funkcja $f_U$ jest też obliczalna w czasie wielomianowym -- wystarczy deterministycznie zweryfikować świadka, tak jak zrobiłaby to maszyna $U$. Pozostaje nam zatem tylko pokazanie, że funkcja odwrotna do $d$ nie jest obliczalna w czasie wielomianowym. Gdyby tak jednak było, to moglibyśmy rozpoznawać język $L$ w czasie wielomianowym: Aby sprawdzić, czy $y\in L$ wystarczy zastosować odwrotność funkcji $f_U$ do słowa $1y$; jeżeli $y\notin L$ to dostaniemy odpowiedź mówiącą, że $1y$ nie można odwrócić; w przeciwnym przypadku otrzymamy świadka przynależności $y$ do języka $L$.

Na dzień dzisiejszy nie znamy oczywiście funkcji, o której wiedzielibyśmy, że jest jednokierunkowa; istnienie takiej funkcji natychmiastowo implikuje przecież nierówność $P\ne NP$. Jest jednak kilku "kandydatów" na funkcje jednokierunkowe -- to znaczy funkcji, dla których nie znamy efektywnego algorytmu pozwalającego na ich odwrócenie. Jedną z takich funkcji jest funkcja $f_{MUL}$. Argumentami tej funkcji są dwie liczby pierwsze wraz ze swoimi certyfikatami pierwszości. Wartością funkcji jest iloczyn tych dwóch liczb. Bardziej formalnie:

• jeżeli $w=⟨p,C(p),q,C(q)⟩$, gdzie $p<q$ a $C(p)$ i

$C(q)$ to certyfikaty pierwszości odpowiednio dla $p$ i $q$, to

{12pt} $f_{MUL}(w)=1p\cdot q$ {12pt}

• w przeciwnym przypadku

{12pt} $f_{MUL}(w)=0w$ {12pt}

Korzystamy tutaj z faktu, że możemy wymusić jednoznaczną reprezentację certyfikatu pierwszości dla danej liczby, oraz że certyfikaty mają rozmiar wielomianowo zależny od rozmiaru certyfikowanych liczb. $f_{MUL}$ jest zatem różnowartościowa i nie "skraca" nadmiernie słowa wejściowego.

Łatwo zauważyć, gdzie tkwi trudność w odwracaniu tej funkcji -- nie znamy efektywnego algorytmu potrafiącego faktoryzować iloczyn dwóch liczb pierwszych; znane nam obecnie algorytmy stają się niepraktyczne już przy iloczynach liczb pierwszych o długości kilkuset bitów.

Drugi ze znanych nam "kandydatów na funkcję jednokierunkową" również oparty jest na zagadnieniu z dziedziny teorii liczb -- problemie logarytmu dyskretnego. Funkcję tą można zdefiniować w następujący sposób:

• dla $w$ postaci $⟨p,C(p),r,x⟩$, gdzie $p$ jest liczbą

pierwszą, $C(p)$ certyfikatem jej pierwszości, $r$ jest najmniejszym generatorem grupy cyklicznej ${\mathbb{\mathbb{Z}}}_p^{\star }$, a $x$ jest liczbą naturalną z zakresu $[1,p-1]$

{12pt} $f_{EXP}(w)=1⟨p,r,r^{x}modp)⟩$ {12pt}

• dla pozostałych $w$

{12pt} $f_{EXP}(w)=0w$ {12pt}

W tym przypadku aby odwrócić funkcję $f_{EXP}$ musielibyśmy na podstawie liczb $p$, $r$ i $r^{x}modp$ umieć obliczyć wartość $x$. Również dla tego, znanego od wielu lat, problemu nie znamy wydajnego rozwiązania.

Jak zauważyliśmy we wprowadzeniu do tego rozdziału w kryptografii duża złożoność pesymistyczna próby zdekodowania zaszyfrowanej wiadomości nie jest własnością wystarczającą. Z tego powodu przytoczymy alternatywną definicję funkcji jednokierunkowych, lepiej odwzorowującą nasze oczekiwania. Należy pamiętać, że definicja ta jest istotnie różna od definicji podanej wcześniej.

Definicja

Niech $f:\{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$. Mówimy, że $f$ jest funkcją jednokierunkową wtedy i tylko wtedy gdy:

• $f$ jest obliczalna w czasie wielomianowym,
• $f$ nie jest stale równa $ϵ$ (słowu pustemu),
• istnieje pewna stała $k>1$ taka, że ${\mathrm{\forall }}_{x\in \{0,1{\}}^{\star }}f(x)=ϵ\vee |x{|}^{1/k}\le f(x)\le |x{|}^k$,
• jeżeli $x$ i $y$ są słowami nad alfabetem $\{0,1\}$ i $f(x)=f(y)$,

to $x=y$ lub $f(x)=f(y)=ϵ$,

• dla każdej losowej maszyny Turinga $E$ działającej w czasie wielomianowym,

każdej liczby $l$ i dostatecznie dużej liczby $n$, jeżeli $x$ jest losowym słowem ze zbioru $\{x^{\prime }:|x^{\prime }|\le n\wedge f(x^{\prime })\ne ϵ\}$, to

{12pt} $Pr[E(f(x))=x]\le n^{-l}$ {12pt}

W tej definicji zrezygnowaliśmy z wymagania o różnowartościowości funkcji; zamiast tego dopuszczamy, aby różne słowa dawały jako wynik wartość $ϵ$, którą możemy traktować jako odpowiedź mówiącą, że wejście jest nieprawidłowe; dla przykładu przy adaptowaniu funkcji $f_{MUL}$ do powyższej definicji, w przypadku gdy $p$ lub $q$ nie będą liczbami pierwszymi, lub gdy $C(p)$ lub $C(q)$ nie będą odpowiednimi certyfikatami, funkcja zwróci wartość $ϵ$. Zauważmy, że w powyższej definicji interesuje nas tylko trudność odszyfrowania wartości funkcji dla poprawnych wejść -- to znaczy w przypadku $f_{MUL}$ dla par liczb, które są pierwsze i których pierwszość jest potwierdzana przez $C(p)$ i $C(q)$. Funkcje $f_{MUL}$ jak i $f_{EXP}$ -- po odpowiednim ich zmodyfikowaniu w sposób przedstawiony powyżej -- są poważnymi "kandydatami" na funkcje jednokierunkowe również w sensie definicji opisanej w poprzednim paragrafie.

Warto się w tym momencie zastanowić, w jaki sposób funkcje jednokierunkowe mogą się przydać w kryptografii. Otóż widzimy, że jedna ze stron -- zwyczajowo zwana Alicją -- może wydajnie zaszyfrować swoją wiadomość, na przykład używając ją jako argument $x$ do funkcji $f_{EXP}$. Niestety druga strona -- zazwyczaj zwana Bob -- może mieć duże trudności z odszyfrowaniem wiadomości. W tej sytuacji fakt, że osoba podsłuchująca -- Cecylia -- niczego ciekawego się nie dowie, stanowi słabe pocieszenie.

Widzimy zatem, że aby zapewnić poufność komunikacji pochodzącej od Alicji, ale również możliwość odebrania tej wiadomości, Bob musi posiadać pewną tajną wiedzę, pozwalającą na wydajne odwrócenie funkcji szyfrującej. Zdefiniujemy teraz pewną modyfikację pojęcia funkcji jednokierunkowej, mającą szersze zastosowanie w kryptografii.

Definicja

Niech $f:\{0,1{\}}^{\star }\times \{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$. Mówimy, że $f$ jest funkcją z wytrychem wtedy i tylko wtedy gdy istnieje losowa maszyna Turinga $G$ oraz funkcja $h:\{0,1{\}}^{\star }\times \{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$ taka, że:

• funkcje $f$ i $h$ są obliczalne w czasie wielomianowym,
• $G$ oczekuje na wejściu słowa nad alfabetem $\{0,1\}$, zwraca zakodowaną

parę słów nad alfabetem $\{0,1\}$ i działa w czasie wielomianowym,

• istnieje stała $k>1$ taka, że

jeżeli $⟨i,t⟩$ stanowi wynik działania maszyny $M$ dla słowa $1^n$, natomiast $x$ jest słowem o długości nie większej niż $n$, to $|⟨i,x⟩{|}^{1/k}\le |⟨t,f(i,x)⟩|\le |⟨i,x⟩{|}^k$,

• jeżeli $⟨i,t⟩$ stanowi wynik działania maszyny $M$ dla

słowa $1^n$, natomiast $x$ i $y$ są słowami o długości nie większej niż $n$, to $f(i,x)=f(i,y)\Rightarrow x=y$,

• dla każdej losowej maszyny Turinga $E$, każdej liczby $l$ i dostatecznie

dużej liczby $n$, jeżeli $⟨i,t⟩$ stanowi wynik działania maszyny $M$ dla słowa $1^n$, $x$ jest losowym słowem nad alfabetem $\{0,1\}$ nie dłuższym niż $n$, to

{12pt} $Pr[E(i,f(i,x))=x]\le n^{-l}$ {12pt}

• Dla każdego $n$, każdego słowa $x$ nie dłuższego niż $n$ i każdej pary

$⟨i,t⟩$ mogącej być wynikiem działania maszyny $G$ dla słowa wejściowego $1^n$

{12pt} $h(t,f(i,x))=x$ {12pt}

Funkcje z wytrychem mogą zostać wykorzystane w celu stworzenia systemów kryptograficznych z kluczem publicznym. Sposób postępowania jest w tym przypadku następujący:

• Bob ustala długość przekazywanych wiadomości ($n$) oraz parametr

wyznaczający prawdopodobieństwo odszyfrowania pojedynczej wiadomości ($k$),

• Bob uruchamia maszynę $G$ i otrzymuje parę słów $⟨i,t⟩$.

Słowo $i$ staje się dostępnym dla wszystkich kluczem publicznym, natomiast $t$ pozostaje tajemnicą znaną tylko Bobowi,

• Alicja, chcąc wysłać wiadomość do Boba, używa znanego jej klucza

publicznego $i$. Własności funkcji z wytrychem sprawiają, że odszyfrowanie wiadomości jest łatwe dla Boba, natomiast trudne dla osób trzecich nie znających klucza $t$.

Najbardziej znanym systemem kryptograficznym opartym na powyższej zasadzie jest system RSA. Pamiętajmy przy tym, że nie znamy formalnego dowodu, mówiącego, że RSA spełnia warunki określone w definicji funkcji z wytrychem.

Prześledźmy teraz w jaki sposób zdefiniowane są $f$, $h$ i $G$ dla systemu RSA.

Zadaniem maszyny $G$ jest wygenerowanie pary kluczy. W tym celu losuje ona dwie liczby pierwsze $p$ i $q$, z których każda ma długość większą niż $n/2$ (gdzie $n$ to długość przekazywanych wiadomości). Następnie oblicza ona liczbę $N=p\cdot q$ oraz wartość funkcji Eulera dla tej liczby: $\varphi (N)=(p-1)\cdot (q-1)$. W kolejnym kroku znajdowana jest dowolna liczba $e$ z zakresu $[2,N-2]$, względnie pierwsza z $\varphi (N)$. Dla liczby $e$ znajdywana jest następnie liczba $d$ z zakresu $[2,N-2]$ taka, że

{12pt} $d\cdot e=1mod\varphi (N)$ {12pt}

Istnienie takiej liczby spowodowane jest faktem, że $e$ i $\varphi (N)$ są względnie pierwsze; liczbę $d$ można efektywnie obliczyć z użyciem uogólnionego algorytmu Euklidesa.

W tym momencie można już zdefiniować parę kluczy: Kluczem publicznym jest para liczb $e$ oraz $N$. Kluczem prywatnym jest para liczb $d$ oraz $N$. Szyfrowanie słowa $x$ wygląda następująco:

{12pt} $f(⟨e,N⟩,x)=x^{e}modN$ {12pt}

przy czym wiadomość $x$ traktujemy jako binarny zapis pewnej liczby naturalnej. Dekodowanie słowa $y$ określone jest w praktycznie identyczny sposób:

{12pt} $h(⟨d,N⟩,y)=y^{d}modN$ {12pt}

Wystarczy teraz przypomnieć sobie, że iloczyn $d\cdot e$ jest postaci $k\cdot \varphi (N)+1$, dla pewnej liczby całkowitej $k$. W związku z tym

{12pt} $h(⟨d,N⟩,f(⟨e,N⟩,x))=(x^e{)}^{d}modN=x^{k\cdot \varphi (N)+1}modN=x^{k\cdot \varphi (N)}\cdot xmodN=x$ {12pt}

Widzimy zatem, że funkcja $h$ poprawnie dekoduje słowa zaszyfrowane z użyciem funkcji $f$ -- Bob będzie zatem w stanie odtworzyć wiadomość wysłaną przez Alicję.

Systemy dowodów interaktywnych

W ostatnim fragmencie niniejszego kursu zajmiemy się klasą złożoności, będącą uogólnieniem klas $NP$ i $BPP$. W tym celu zdefiniujemy pojęcie systemu dowodów interaktywnych.

Definicja Systemem dowodów interaktywnych

nazywamy parę funkcji $V$ oraz $P$ o sygnaturach:

{12pt} $V:{\mathrm{\Sigma }}^{\star }\times {\mathrm{\Sigma }}^{\star }\times {\mathrm{\Sigma }}^{\star }\to {\mathrm{\Sigma }}^{\star }\cup \{accept,reject\}$ {12pt} $P:{\mathrm{\Sigma }}^{\star }\times {\mathrm{\Sigma }}^{\star }\to {\mathrm{\Sigma }}^{\star }$ {12pt}

taką, że funkcja $V$ jest obliczalna na maszynie Turinga.

Działanie systemu dowodów interaktywnych polega na wymianie komunikatów między funkcjami $V$ i $P$, przy czym funkcja $P$ (z angielskiego prover) stara się "przekonać" funkcję $V$ (verifier) o tym, że słowo wejściowe należy do rozpatrywanego języka, natomiast ostateczna decyzja w tej sprawie należy do $V$.

Komunikacja odbywa się naprzemiennie: Funkcja $V$ generuje wiadomość, przekazywaną funkcji $P$ jako argument; funkcja $P$ z kolei generuje odpowiedź przekazywaną funkcji $V$ w następnej iteracji. Taka komunikacja odbywa się do momentu zaakceptowania lub odrzucenia słowa wejściowego przez funkcję $V$. W każdym kroku obie funkcje mają do dyspozycji zarówno słowo wejściowe, jak również pełną historię przekazanych dotychczas wiadomości.

Określmy teraz, co dokładnie oznaczają argumenty funkcji $V$ i $P$. Argumenty funkcji $V$ będziemy oznaczać w następujący sposób:

{12pt} $V(w,r,m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i)$ {12pt}

Mają one następujące znaczenie:

• $w$ to słowo wejściowe,
• $r$ jest losowym ciągiem bitów,
• $m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i$ to konkatenacja dotychczasowych wiadomości,

które zostały przekazane w procesie komunikacji (wiadomości o indeksach nieparzystych sa wynikami działania funkcji $V$, natomiast wiadomości o indeksach parzystych sa wynikami działania funkcji $P$).

Zwróćmy uwagę, że $V$ ma do dyspozycji losowe słowo $r$; w praktyce oznacza to, że o funkcji $V$ będziemy myśleć jako o pewnej losowej maszynie Turinga.

Zakładamy, że zarówno $w$ jak i $r$ są stałe w kolejnych iteracjach; słowo $r$ jest zatem losowane jednokrotnie, przed rozpoczęciem procesu komunikacji. Warto też zauważyć, że słowa $w$ i $r$ całkowicie determinują działanie systemu.

Argumenty funkcji $P$ będziemy oznaczać następująco:

{12pt} $P(w,m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i)$ {12pt}

Ich znaczenie jest identyczne jak w przypadku argumentów funkcji $V$, nie ma wśród nich jednak słowa losowego.

Możemy w tym momencie zdefiniować klasę $IP$:

Definicja

Niech $L\subseteq {\mathrm{\Sigma }}^{\star }$. Mówimy, że $L\in IP$ wtedy i tylko wtedy gdy istnieje system dowodów interaktywnych $(V,P)$ oraz wielomiany $p(n)$ i $q(n)$ takie, że dla każdego słowa wejściowego $w$ oraz losowego słowa $r$ o długości $p(|x|)$:

• system daje odpowiedź po co najwyżej $p(|x|)$ krokach,
• w każdej iteracji czas działania maszyny obliczającej funkcję $V$ jest

ograniczony od góry przez $q(|x|)$,

• długość każdej wiadomości $m_i$ jest nie większa niż $p(|x|)$,
• jeżeli $w\in L$ to prawdopodobieństwo zaakceptowania słowa przez system

wynosi co najmniej $2/3$,

• jeżeli $w\notin L$ oraz $\overline{P}$ jest dowolną funkcją o sygnaturze zgodnej

z $P$, zwracającą wiadomości nie dłuższe niż $p(|x|)$, to system $(V,\overline{P})$ spełnia powyższe założenia na ilość iteracji, czas działania i długość wiadomości oraz akceptuje słowo $w$ z prawdopodobieństwem nie większym niż $1/3$.

O systemie $(V,P)$ mówimy, że rozpoznaje język $L$ w czasie wielomianowym.

Innymi słowy jeżeli słowo $w$ należy do języka, to $V$ z dużym prawdopodobieństwem da się przekonać o tej przynależności przez pewną ustaloną funkcję $P$. Jeżeli jednak $w$ nie należy do $L$, to $V$ nie da się oszukać żadnej funkcji $\overline{P}$ ze zbyt dużym prawdopodobieństwem.

Uwaga

Zwróćmy jeszcze uwagę, że branie pod uwagę tylko takich funkcji $\overline{P}$, które nie zwracają zbyt długich słów nie jest istotnym ograniczeniem; funkcja $V$ może w każdym kroku sprawdzać, czy odpowiedź funkcji $\overline{P}$ nie jest zbyt długa i jeśli tak to odrzucać słowo. W dalszej części rozdziału będziemy zakładali takie właśnie zachowanie funkcji $V$.

Widzimy zatem, że funkcja $V$ musi być zabezpieczona przed oszustwami; jeżeli $V$ mogłaby zaufać funkcji $P$ to mogłaby rozwiązać każdy problem decyzyjny -- wystarczyłoby po prostu skorzystać z nieograniczonej mocy obliczeniowej $P$. W naszym przypadku jednak nie wystarczy aby $P$ tylko rozwiązała problem decyzyjny -- musi jeszcze przekonać $V$ do swojego rozwiązania.

Przykład

Rozważmy problem $NON-GRAPH-ISO$. Jest on zdefiniowany następująco:

{12pt} $NON-GRAPH-ISO=\{⟨G,H⟩:$ grafy $G$ i $H$ nie są izomorficzne $\}$ {12pt}

Łatwo sie przekonać, że problem izomorfizmu grafów jest w klasie $NP$ -- wystarczy zgadnąć odpowiednią permutację wierzchołków, po czym zweryfikować ją w trywialny sposób. $NON-GRAPH-ISO$ należy zatem do $coNP$. Nie jest jednak obecnie znana odpowiedź na pytanie o przynależność tego problemu do klasy $NP$. Pokażemy teraz, w jaki sposób można rozwiązać $NON-GRAPH-ISO$ za pomocą systemów dowodów interaktywnych, pokazując przynależność tego problemu do klasy $IP$.

System działa w prosty sposób: W kolejnych iteracjach funkcja $V$ wybiera losowo jeden z grafów, a następnie w losowy sposób permutuje jego wierzchołki. Taki graf jest przekazywany jako wiadomość do funkcji $P$. Zadaniem funkcji $P$ jest rozpoznanie, który z wyjściowych grafów został wylosowany i przekształcony przez $V$.

Ćwiczenie

Zdefiniuj, w jakich przypadkach $V$ powinien zaakceptować, a w jakich odrzucić wejściową parę grafów. Oblicz, ile iteracji jest potrzebnych, aby system rozpoznawał język $NON-GRAPH-ISO$ w czasie wielomianowym zgodnie z wcześniejszą definicją.

Rozwiązanie

Zachowanie $V$ powinno być następujące: Jeżeli $P$ pomyli się w odpowiedzi, $V$ powinno odrzucić parę grafów -- czyli stwierdzić, że są izomorficzne. $V$ powinno zaakceptować grafy -- czyli stwierdzić, że nie są izomorficzne -- jeżeli $P$ dwukrotnie poprawnie odgadnie, który graf został wylosowany przez $V$. Pokażemy teraz, że system ten rozpoznaje $NON-GRAPH-ISO$. Załóżmy, że grafy wejściowe nie są izomorficzne. W tym przypadku łatwo wskazać funkcję $P$, która zawsze będzie udzielała prawidłowej odpowiedzi; prawdopodobieństwo akceptacji wyniesie zatem $1$. Pozostaje jeszcze tylko pokazać, że jeżeli grafy nie są izomorficzne, to $V$ nie da się oszukać żadnej funkcji $\overline{P}$. Funkcja $\overline{P}$ nie ma jednak żadnej możliwości sprawdzenia, który graf został wybrany. Niezależnie zatem jak się zachowa, prawdopodobieństwo udzielenia dwóch kolejnych poprawnych odpowiedzi będzie nie większe niż $1/4$, co kończy dowód.

Ćwiczenie

Pokaż, że klasa $BPP$ jest zawarta w klasie $IP$.

Rozwiązanie

Weźmy dowolny problem z klasy $BPP$ oraz program dla probabilistycznej maszyny Turinga, rozwiązujący ten problem w czasie wielomianowym. Wystarczy teraz, by funkcja $V$ po prostu wykonała ten program i udzieliła odpowiedzi bez angażowania $P$.

Ćwiczenie

Rozpatrzmy takie systemy dowodów interaktywnych, w których funkcje $V$ nie zależą od argumentu $r$ (słowa losowego). Jaką klasę języków rozpoznają takie systemy, przy założeniach o złożoności analogicznych jak w przypadku klasy $IP$?

Rozwiązanie

Zauważmy najpierw, że z tak określone protokoły komunikacyjne są w pełni deterministyczne (w tym sensie, że pozbawione są losowości). Zatem dla ustalonego systemu $(V,P)$ i ustalonego słowa wejściowego odpowiedź protokołu zawsze jest taka sama.

Łatwo się przekonać, że za pomocą opisanych powyżej systemów można rozpoznać dowolny język z klasy $NP$. Protokół wygląda w następujący sposób: Dla zadanego słowa wejściowego $w$ funkcja $P$ zwraca świadka jego przynależności do rozważanego języka. Funkcja $V$ następnie weryfikuje świadka w sposób deterministyczny w czasie wielomianowym i na tej podstawie udziela odpowiedzi. Jest jasne, że w przypadku gdy $w$ należy do rozważanego języka, odpowiednia funkcja $P$ jest w stanie przekonać $V$ o tej przynależności -- ponieważ nie ma żadnych restrykcji na złożoność funkcji $P$, może ona po prostu rozważyć wszystkich możliwych kandydatów na świadków o pewnej ustalonej z góry długości. Ponadto jeśli $w$ nie należy do rozważanego języka to $V$ jest w stanie wykryć każdą próbę oszustwa.

Pokażemy teraz, że każdy język rozpoznawalny przez systemy opisane w treści zadania należy do $NP$. Ustalmy zatem pewien język $L$ i rozpoznający go system $(V,P)$. Załóżmy bez straty ogólności, że system ten dla słowa wejściowego $w$ wykonuje dokładnie $p(|w|)$ kroków, oraz że każda przekazywana wiadomość ma długość $p(|w|)$. Zdefiniujmy teraz niedeterministyczną maszynę Turinga $M$, rozpoznającą język $L$. Załóżmy, że maszyna oprócz taśmy roboczej ma też (początkowo pustą) taśmę służącą do przechowywania kolejnych komunikatów. Działanie maszyny $M$ będzie podzielone na fazy; w fazach nieparzystych maszyna będzie symulować działanie funkcji $V$ -- to znaczy $M$ przeczyta historię wysłanych dotychczas wiadomości i słowo wejściowe, i na tej podstawie dopisze kolejną wiadomość. W fazach parzystych maszyna $M$ w sposób niedeterministyczny wygeneruje wiadomość o długości $p(|w|)$ i dopisze ją na taśmę. W przypadku, gdy $w\in L$ łatwo wskazać ścieżkę postępowania dla tej maszyny, która doprowadzi do akceptacji; będzie to ścieżka, w której wygenerowane w fazach parzystych wiadomości pokrywają się z odpowiedziami udzielanymi przez funkcję $P$. Rozważmy teraz przypadek $w\notin L$. Załóżmy nie wprost, że istnieje taka ścieżka postępowania maszyny $M$, która doprowadzi do akceptacji tego słowa. W takim przypadku możemy jednak utworzyć funkcję $\overline{P}$, która będzie zwracała wiadomości wygenerowane w fazach parzystych postępowania maszyny $M$. W tym przypadku funkcja $V$ da się oszukać funkcji $\overline{P}$ dla słowa $w$ z prawdopodobieństwem równym 1 -- a zatem system $(V,P)$ nie będzie rozpoznawał języka $L$, co jest sprzeczne z założeniem.

Pokazaliśmy zatem, że protokoły zdefiniowane w treści ćwiczenia rozpoznają klasę języków $NP$.

Możemy w tym momencie przypuszczać, że klasa $IP$ jest znacząco większa od klasy $NP$. Nie wiemy obecnie czy przypuszczenie to jest prawdziwe; przemawia jednak za nim poniższe twierdzenie.

Twierdzenie

$IP=PSPACE$

Dowód

{{{3}}}

Ćwiczenie

Wyjaśnij, czemu w protokole $\mathrm{\#}SAT(D)$ potrzebowaliśmy ciała o co najmniej $2^n$ elementach.

Rozwiązanie

Widzimy, że aby spełnić wymagania dotyczące prawdopodobieństwa zaakceptowania słowa spoza języka, wystarczy ciało o wielkości $n^3$. W przypadku $\mathrm{\#}SAT(D)$ ciało ${\mathbb{\mathbb{Z}}}_p$ służy nam jednak nie tylko jako dostarczyciel dużej przestrzeni prawdobodobieństwa, lecz również do zliczania ilości spełniających wartościowań dla zadanej formuły logicznej. Z tego powodu potrzebujemy co najmniej $2^m$ liczb -- co oznacza, że w zdegenerowanym przypadku gdy każda zmienna jest używana w dokładnie jednym literale wymagane ciało musi mieć liczność nie mniejszą niż $2^n$.