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

16

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

Scott Aaronson
źródło
2
Interesujące pytanie! Czy te pytania nie są podobne do pytania kontra D P ? W rzeczywistości, zapytania o M A c o M A wydaje się być prawie dokładnie taki (lub a) losowo wersja N P c o N P w porównaniu z D P . N.P.dooN.P.reP.M.ZAdooM.ZAN.P.dooN.P.reP.
Joshua Grochow
Gdzie wchodzi w historię? Czy ktoś wykazał, że charakteryzuje on dowody wiedzy lub coś takiego? reP.
Scott Aaronson,
1
Myślę, że jest to po prostu analogia. W obu przypadkach ( vs D P i M A c o M A w porównaniu z klasą, którą sugerujesz), masz dwie klasy zdefiniowane przez warunki na weryfikatorze i porównujesz przecięcie dwóch złożoności klasy do zestawu języków, które mają jednego weryfikatora spełniającego oba warunki jednocześnie. (Jeśli dobrze zrozumiałem.)N.P.dooN.P.reP.M.ZAdooM.ZA
Joshua Grochow,

Odpowiedzi:

10

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.

MS Dousti
źródło