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...
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 .
źródło
Odpowiedzi:
Dwie odpowiedzi, których nauczyłem się podczas pisania postu na blogu na temat tego pytania
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.
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 .
źródło
Na wysokim poziomie CHKPRR buduje dystrybucję w instancjach końcowych, w których znalezienie rozwiązania wymaga:
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:
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ć.
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.
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.
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:
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.
źródło