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).
źródło
Odpowiedzi:
To nie jest rzeczywista odpowiedź; Po prostu udostępniam niektóre wyniki (które nie pasują do jednego komentarza).
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:
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ść 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.
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.
źródło