PPAD i kwant

Dziś w Nowym Jorku i na całym świecie obchodzone są urodziny Christosa Papadimitriou. To dobra okazja, aby zapytać o relacje między klasą złożoności Christosa PPAD (i jego innymi klasami pokrewnymi) a komputerami kwantowymi. W swoim słynnym artykule z 1994 r. Papadimitriou wprowadził i systematycznie studiował kilka ważnych klas złożoności, takich jak PLS, PPAD i inne. (Artykuł Papadimitriou opierał się na kilku wcześniejszych artykułach, aw szczególności, jak zauważył Aviad, PLS został wprowadzony przez Johnson-Papadimitriou-Yannakakis w 1988 r.)

Moje główne pytanie brzmi:

Czy komputery kwantowe dają jakieś korzyści w przypadku problemów z ? lub w ? lub w ? itp...$PPAD$$PLS$$PLS \cap PPAD$

Kolejne pytanie dotyczy tego, czy istnieją jakieś analogi kwantowe PLS i PPAD oraz inne klasy Christosa.

Zauważam, że w tych artykułach znaleziono ostatnie niezwykłe powiązania PPAD z kryptografią: O twardości kryptograficznej znalezienia równowagi Nasha według N Bitansky'ego, O Paneth, A Rosen i Czy twardość PPAD może być oparta na standardowych założeniach kryptograficznych? autor: A Rosen, G Segev, I Shahaf, a znalezienie równowagi Nasha nie jest łatwiejsze niż przełamanie Fiata-Shamira autorstwa Arki Rai Choudhuri, Pavela Hubacka, Chethana Kamatha, Krzysztofa Pietrzaka, Alona Rosen, Guy Rothbluma. Zauważam również, że moim zdaniem zajęcia Christosa są szczególnie zbliżone do matematyki i dowodów matematycznych.

Aktualizacja: Ron Rothblum skomentował (nad FB), że wyniki Choudhuri, Hubacek, Kamath, Pietrzak, Rosen i G. Rothblum sugerują, że PPAD jest prawdopodobnie poza mocą komputerów kwantowych. (Będę szczęśliwy widząc wyjaśnioną odpowiedź.)

Jeszcze jeden komentarz: powiązane miłe pytanie dotyczy tego, czy znalezienie zlewu w unikalnej orientacji pojedynczej kostki ma wydajny algorytm kwantowy. (Myślę, że to zadanie jest łatwiejsze niż ale nie jestem pewien, w jaki sposób jest ono powiązane z .) Jest to związane z poszukiwaniem kwantowej przewagi dla patrz https://cstheory.stackexchange.com/a/767/712 . $n$$PLS$$PPAD$$LP$

Wszystkiego najlepszego, Christos!

Dwie odpowiedzi, których nauczyłem się podczas pisania postu na blogu na temat tego pytania

1. Nie : W wariantach czarnej skrzynki kwantowa złożoność zapytań / komunikacji oferuje kwadratowe przyspieszenie Grovera, ale nie więcej. Jak podkreśla Ron, rozciąga się to na złożoność obliczeniową przy realistycznych założeniach.

2. Może : Równowaga Nasha jest prawdopodobnie flagowym problemem „klas Christosa”. Zapewnienie graczom dostępu do splątania kwantowego sugeruje tutaj nową koncepcję rozwiązania „równowagi skorelowanej kwantowo”, która uogólnia równowagę Nasha. Jego złożoność jest nadal otwarta. Zobacz ten fajny artykuł Alana Deckelbauma.

I jedna historyczna notatka: PLS została faktycznie wprowadzona przez Johnson-Papadimitriou-Yannakakis w 1988 roku .

$\mathsf{PPAD}$

Na wysokim poziomie CHKPRR buduje dystrybucję w instancjach końcowych, w których znalezienie rozwiązania wymaga:

• przełamać solidność systemu dowodowego uzyskanego przez zastosowanie heurystyki Fiata-Shamira do słynnego protokołu sumcheck, lub
• $\sharp \mathsf{P}$

$\sharp \mathsf{SAT}$$\mathsf{PPAD}$

$\sum_{\vec z \in \{0,1\}^n} f(\vec z) = x$$f$$n$$\mathbb{F}$, który działałby idealnie w tym ustawieniu: protokół sumcheck . Przekształcanie dowodu interaktywnego w nieinteraktywny (przy zachowaniu publicznej weryfikowalności i zwartości) jest dokładnie tym, co robi heurystyka Fiat-Shamir.

Tworzenie instancji Fiat-Shamir

Heurystyka Fiat-Shamir jest bardzo prosta: napraw niektóre funkcje skrótu, zacznij od interaktywnego dowodu monety publicznej i zamień każdą losową wiadomość weryfikatora na skrót całej dotychczasowej transkrypcji. Powstaje zatem pytanie, w oparciu o którą właściwość funkcji skrótu możemy udowodnić, że wynikowy protokół jest nadal poprawny (zauważ, że nie może być już statystycznie poprawny; istnieje nadzieja, że ​​pozostanie on poprawny obliczeniowo).

Zanim rozwiążę tę kwestię, pozwól mi odnieść się do twojego komentarza:

Nadal nie rozumiem 1. Z pewnością istnieją kryptograficzne założenia twardości, które nie mają zastosowania w przypadku kwantowym. Co sprawia, że ​​„łamanie Fiata-Shamira” jest trudne dla QC, w przeciwieństwie do „łamania RSA”.

Mam nadzieję, że opis wysokiego poziomu, który podałem, powinien wyjaśnić, że „łamanie Fiata-Shamira” i „łamanie RSA” nie są tak naprawdę porównywalnymi problemami. RSA jest konkretnym, konkretnym założeniem twardości, a jeśli możesz uwzględnić duże liczby całkowite, możesz je złamać.

$\mathsf{PPAD}$podstawowej funkcji skrótu. Na poziomie intuicyjnym nie jest to, w czym komputery kwantowe są dobre, ponieważ jest to problem, który nie musi mieć silnej struktury, którą mógłby wykorzystać (w przeciwieństwie do np. Logarytmu dyskretnego i RSA): funkcje skrótu mogą być zazwyczaj bardzo „nieustrukturyzowany”.

Mówiąc bardziej konkretnie, istnieją dwie naturalne alternatywy przy wybieraniu funkcji skrótu w celu utworzenia instancji Fiat-Shamir:

Heurystyczne, konkretnie skuteczne podejście:

wybierz swoją ulubioną funkcję skrótu, powiedzmy SHA-3. Nie mamy oczywiście żadnego dowodu, że utworzenie Fiat-Shamir z SHA-3 stanowi dla nas poważny problem; ale nie wiemy też o żadnym nietrywialnym ataku na solidność systemów dowodowych uzyskanym przez zastosowanie Fiata-Shamira z SHA-3 w nie-zdegenerowanym interaktywnym systemie dowodowym. Dotyczy to również ustawienia kwantowego: nie znamy żadnego ataku kwantowego, który działałby lepiej niż zwykłe przyspieszenie kwadratowe zapewniane przez algorytm Grovera. Po dziesięcioleciach prób kryptoanalizy, konsensus w społeczności kryptograficznej jest taki, że algorytm kwantowy nie wydaje się , o ile nam wiadomo, zapewniać superpolinomalnych przyspieszeń dla prymitywów typu „Minicrypt” (funkcje skrótu, PRG, szyfry blokowe itp.) Bez niektóre silne leżące u podstaw struktury algebraiczne - takie jak SHA-2, SHA-3, AES itp.

Sprawdzone podejście bezpieczeństwa:

tutaj celem jest wyodrębnienie czystej właściwości funkcji skrótu, która tworzy heurystyczny dźwięk Fiata-Shamira, oraz zbudowanie funkcji skrótu, która spełnia te właściwości przy prawdopodobnych założeniach kryptograficznych.

$R$$K$$x$$(x, H_K(x)) \in R$$R$$R$

Pytanie brzmi teraz, jak zbudować funkcje skrótu nieobowiązujące korelacji dla relacji, na których nam zależy - i w tym konkretnym kontekście dla relacji związanej z protokołem sumcheck. W tym przypadku niedawna linia prac (zasadniczo 1 , 2 , 3 , 4 , 5 , 6 ) pokazała, że ​​dla wielu interesujących relacji można faktycznie zbudować korelację trudnych funkcji skrótu przy założeniach opartych na sieci.

$\mathsf{PPAD}$

W rzeczywistości nie jesteśmy tam dokładnie. Niedawny przełomowy wynik Peikerta i Shiehiana (ostatni artykuł z listy, którą wcześniej podałem) pokazał, że w przypadku ważnych relacji możemy zbudować funkcję skrótu trudną do korelacji w ramach dobrze znanych problemów z siecią, takich jak uczenie się z błędem lub problem SIS ; jednak relacja sumcheck nie jest przechwytywana przez tę pracę.

Mimo to, CHKPRR, opierając się na tych pracach, pokazał, że można zbudować funkcję skrótu niepodatną na korelację, zakładając, że dowolna z wielu konkretnych konstrukcji w pełni homomorficznych schematów szyfrowania ma quasi-optymalne okrągłe bezpieczeństwo przed superpolinomalnymi atakami czasowymi.

Przełammy to założenie:

• W pełni homomorficzne szyfrowanie (FHE) to prymityw, który wiemy, jak budować przy różnych założeniach sieci. Jeśli schemat musi oceniać tylko obwody o ograniczonych rozmiarach, wiemy w rzeczywistości, jak je zbudować w ramach standardowego uczenia z założeniem błędu.
• Okrągłe zabezpieczenia stwierdzają, że FHE powinien być trudny do złamania, nawet jeśli jest używany do szyfrowania własnego tajnego klucza. Jest to silniejsze niż zwykłe pojęcie bezpieczeństwa, które nie pozwala na wiadomości zależne od klucza. Poważnym i od dawna otwartym problemem jest zbudowanie FHE o okrągłym zabezpieczeniu przy standardowych założeniach sieci, takich jak LWE. Mimo to, dekadę po pierwszej budowie Gentry FHE i wielu próbach kryptoanalizy, okrągłe bezpieczeństwo uznanych kandydatów na FHE samo w sobie stało się względnie bezpiecznym założeniem (nawet wobec komputerów kwantowych) i nie wiemy o żadnym ataku wykorzystującym klucz -zależne szyfrowanie w nietrywialny sposób.
• $2^{\omega(\log \lambda) - \lambda}$$\lambda$$2^{c\lambda}$$c < 1$$2^{-c \lambda}$$c < 1$
• Wreszcie, chcemy, aby wszystkie powyższe nadal obowiązywały, jeśli pozwolimy atakującemu na wielobiegunowy czas działania. Jest to nadal zgodne z tym, co mogą osiągnąć znane algorytmy.

$\mathsf{PPAD}$

Oczywiście, jednym z głównych otwartych pytań pozostawionych przez CHKPRR jest zbudowanie funkcji skrótu trudnej do korelacji dla relacji sumcheck przy lepszym założeniu opartym na sieci - najlepiej przy założeniu LWE. Wydaje się to nietrywialne, ale nie nieprawdopodobne, biorąc pod uwagę, że jest to najnowszy kierunek prac, w którym osiągnięto już wiele zaskakujących wyników w przypadku innych interesujących relacji.