Klasy złożoności dla dowodów wiedzy

Pytanie zadane mi przez Grega Kuperberga. Zastanawiam się, czy są jakieś prace, które definiują i badają złożoność klas języków dopuszczających różnego rodzaju dowody wiedzy . Klasy takie jak SZK i NISZK są niezwykle naturalne z punktu widzenia złożoności, nawet jeśli całkowicie zapomnieliśmy o zerowej wiedzy i po prostu zdefiniowaliśmy je pod kątem ich kompletnych problemów z obietnicą. Z drugiej strony, w przypadku „dowodów wiedzy Google”, byłem zaskoczony, że nie znalazłem żadnych artykułów ani notatek z wykładów omawiających tę cudowną koncepcję w kategoriach złożoności.

Podam kilka przykładów: co można powiedzieć o podklasie SZK∩MA∩coMA składającej się ze wszystkich języków L, które dopuszczają statystyczne dowody zerowej wiedzy dla x∈L lub x∉L, które są również dowodami wiedzy świadka dowodzącego x ∈L czy x∉L? Oczywiście klasa ta zawiera takie elementy, jak log dyskretny, ale nie mogliśmy udowodnić, że zawiera izomorfizm grafów bez umieszczenia GI w coMA. Czy klasa obejmuje wszystkie SZK∩MA∩coMA? Można również zapytać: jeśli istnieją funkcje jednokierunkowe, to czy każdy język L∈MA∩coMA dopuszcza obliczeniowy dowód zerowej wiedzy, to także dowód znajomości świadka potwierdzającego x∈L lub x∉L? (Przepraszam, jeśli jedno lub oba z nich mają banalne odpowiedzi - staram się tylko zilustrować coś, co można zrobić zapytaj, gdy raz zdecydujesz się spojrzeć na PoK w kategoriach złożoności).

To nie jest rzeczywista odpowiedź; Po prostu udostępniam niektóre wyniki (które nie pasują do jednego komentarza).

1. Goldreich, Micali i Wigderson ( J. ACM, 1991 ) udowodnili, że każdy język w NP ma zerowy dowód przynależności do języka (zakładając, że istnieją MFW). W tym celu przedstawili dowód ZK na 3-kolorową grafikę. Później Bellare i Goldreich ( CRYPTO '92 ) udowodnili, że ten dowód ZK jest również dowodem wiedzy ZK (PoK). Stosując redukcje Levina (patrz przypis 12 poprzedniego artykułu), każdy język w NP ma ZK PoK (zakładając, że OWF istnieją).
2. Itoh i Sakurai ( ASIACRYPT '91 ) piszą o teoretycznych wynikach złożoności dotyczących relacji o stałej okrągłej ZK PoK.
3. To pozornie niezwiązany wynik, choć nie mogę nie zauważyć pewnych podobieństw. W jakiś sposób wydaje mi się (nie formalne), że dowód członkostwa vs. dowód wiedzy jest podobny do decyzji vs. wyszukiwania . Być może w tym sensie można również przytoczyć prace Bellare i Goldwassera ( J. Computing, 1994 ), gdzie (warunkowo) udowadniają, że nie wszystkie języki w NP mają redukcję z wyszukiwania do decyzji.

Niektóre otwarte problemy (być może rozwiązane, ale nie takie, o których wiem) dotyczące teoretycznych aspektów złożoności PoK:

1. Różne miary wydajności dla ZK PoK określonej relacji o określonej złożoności (np. Relacji w AM):

   • Złożoność komunikacyjna dowodu
   • Złożoność obliczeniowa stron
   • Szczelność wiedzy (tj. Stosunek (oczekiwanego) czasu działania symulatora do czasu działania weryfikatora w rzeczywistej interakcji)

2. Złożoność relacji dopuszczających ZK PoK z pewnymi ograniczeniami, powiedzmy, że ograniczone okrągłe złożoności (Itoh i Sakurai biorą pod uwagę tylko stałe okrągłe ZK PoK). Innym przykładem jest czas wielomianu: nie może zastosować redukcji do 3-kolorowalności, ponieważ nie może rozwiązać relacji NP-zupełnych. Wszystkie problemy z uzupełnianiem NP mają redukcję Cooka od wyszukiwania do decyzji. Jednak według przytoczonego wyżej wyniku Bellare-Goldwasser takie redukcje niekoniecznie istnieją dla wszystkich języków / relacji NP.

3. Inne interesujące wyniki dotyczące PoK, które niekoniecznie są ZK, ale których złożoność wiedzy jest w inny sposób ograniczona. Patrz Goldreich i Petrank ( Comput. Complex., 1999 ).

Przed zakończeniem, pozwól mi wspomnieć, że w rzeczywistości istnieje kilka definicji PoK, z których niektóre są cytowane poniżej:

1) Wczesne próby: Feige, Fiat i Shamir ( J. Cryptology, 1988 ), Tompa and Woll ( FOCS 1987 ) oraz Feige and Shamir ( STOC 1990 ).

2) Standard de facto: Bellare i Goldreich ( CRYPTO '92 ). W tym artykule analizuje się wczesne próby zdefiniowania PoK, obserwuje ich niedociągnięcia i sugeruje nową definicję, którą można uznać za „definicję” PoK. Ta definicja ma charakter czarnej skrzynki (ekstraktor wiedzy ma dostęp czarnej skrzynki do oszusta).

3) Konserwatywne PoK: Zdefiniowane przez Halevi i Micali ( ePrint Archive: Report 1998/015 ), definicja ta uzupełnia poprzednią definicję, aby zagwarantować wykonalność. Podaje także definicję znajomości jednego przysłowia, co jest dobre, gdy odpowiada się na pytanie „co to znaczy powiedzieć, że P coś wie?”.

4) Argumenty wiedzy bez ekstrakcji czarnej skrzynki: Jak wspomniano powyżej, standardową definicją PoK jest czarna skrzynka, co uniemożliwia resetowanie dowodów zerowych (lub argumentów) wiedzy dla języków nietrywialnych. Barak i in. ( FOCS 2001 ) podają definicję nie czarnej skrzynki, która opiera się na (ale różni się) od definicji Feige i Shamir (STOC 1990) cytowanej powyżej.