Czy istnieją algorytmy kryptograficzne klucza publicznego, które są udowodnione NP-trudne do pokonania? [zamknięte]

Zaproponowano kilka kryptosystemów bazujących na problemach np-hard (takich jak kryptosystem Merkle-Hellman bazujący na problemie sumy podzbioru oraz kryptosystem Nacache-Stern knapsack bazujący na problemie plecaka), ale wszystkie zostały złamane. Dlaczego? Wykład 16 Scott Aaronson ' S Great Ideas in Theoretical Computer Science mówi coś o tym, co myślę, że powinieneś przyjąć jako ostateczne. To, co mówi, jest następujące:

Idealnie, my chciałby skonstruować [kryptograficzny Generator Pseudorandomu] lub kryptosystem, którego bezpieczeństwo opierało się na problemie np-complete. Niestety, problemy np-complete są zawsze o najgorszym przypadku. W kryptografii przekładałoby się to na stwierdzenie w stylu "istnieje wiadomość, która jest trudna do dekodowania", co nie jest dobrą gwarancją dla systemu kryptograficznego! Wiadomość powinna być trudna do odszyfrowania z przytłaczającym prawdopodobieństwem. Pomimo dziesięcioleci starań, nie ma jeszcze możliwości odkryto, że odnosi się najgorszy przypadek do przeciętnego przypadku problemów NP-kompletnych. I dlatego, jeśli chcemy obliczeniowo bezpiecznych kryptosystemów, musimy przyjąć silniejsze założenia niż P≠NP.

To było pytanie otwarte w 1998 roku:

Na możliwość oparcia kryptografii na założeniu, że P != NP autor: Oded Goldreich, Rehovot Israel, Shafi Goldwasser

Z abstraktu: "nasz wniosek jest taki, że pytanie pozostaje otwarte".

--ciekawe czy to się zmieniło w ostatniej dekadzie?

Edit:

Z tego, co wiem, pytanie jest wciąż otwarte, z niedawnym postępem w kierunku odpowiedzi na żaden taki algorytm nie istnieje.

Adi Akavia, Oded Goldreich, Shafi Goldwasser i Dana Moshkovitz opublikowali ten artykuł w ACM w 2006 roku: na podstawie funkcji jednokierunkowych na twardości NP "nasze główne ustalenia są następujące dwa negatywne wyniki"

Strona stanford Complexity Zoo jest pomocna w rozszyfrowaniu tego, co oznaczają te dwa negatywne wyniki.

Podczas gdy wiele formularzy zostało złamanych, sprawdź Merkle-Hellman , bazując na formie np-complete 'problem z plecakiem'.

Kryptografia kratowa oferuje (nad)uogólniony komunikat, że rzeczywiście można zaprojektować kryptosystemy, w których złamanie przeciętnego przypadku jest tak trudne ,jak rozwiązanie konkretnego problemu NP-hard (Zwykle najkrótszy Problem wektora lub najbliższy problem wektora).

Mogę polecić przeczytanie sekcji wprowadzającej http://eprint.iacr.org/2008/521 a potem szukanie odniesień do kryptosystemów.

Zobacz też notatki z wykładu na http://www.cs.ucsd.edu / ~ daniele / CSE207C / , i poszukaj linków do książki, jeśli chcesz.

Googling for np-complete and Public key encryption finds False positives ... to naprawdę niepewne. Ten rysunkowy pdf wydaje się pokazywać algorytm kodowania klucza publicznego oparty na problemie minimium dominującego zestawu . Czytając dalej przyznaje się następnie do kłamstwa, że algorytm jest bezpieczny ... podstawowym problemem jest np-Complete, ale jego użycie w algorytmie PK nie zachowuje trudności.

Kolejny fałszywie pozytywny wynik Google: Kryptoanaliza kryptosystem Goldreich-Goldwasser-Halevi z Crypto '97. Z abstraktu:

Na Crypto '97, Goldreich, Goldwasser i Halevi zaproponowali kryptosystem klucza publicznego oparty na najbliższym problemie wektorowym w sieci, który jest znany jako np-hard. Pokazujemy, że istnieje poważna wada w projektowaniu schematu, która ma dwie implikacje: każdy szyfertext przecieka informacje na zwykłym tekście, a problem deszyfrowania szyfrów można sprowadzić do specjalnego najbliższego problemu wektorowego co jest o wiele łatwiejsze niż ogólny problem.

Istnieje strona internetowa, która może być istotna dla Twoich zainteresowań: Kryptografia Post-kwantowa .

Oto moje rozumowanie. Popraw mnie, jeśli się mylę.

(i) "złamanie" kryptosystemu jest koniecznie problemem w NP i co-np. (Złamanie kryptosystem polega na odwróceniu funkcji szyfrowania, która jest jeden do jednego i obliczalna w czasie wielomianowym. Tak więc, biorąc pod uwagę tekst szyfrowy, tekst jawny jest certyfikatem, który można zweryfikować w czasie wielomianowym. Tak więc odpytywanie tekstu jawnego na podstawie tekstu szyfrowego jest w NP i w co-np.)

(ii) jeśli występuje problem np-hard W NP i co-NP, następnie NP = co-np. (Problem ten byłby np-kompletny i w co-np. Ponieważ każdy język NP jest redukowalny do tego języka co-NP, NP jest podzbiorem co-NP. Teraz użyj symetrii: każdy język L w co-np ma-L (jego komplement) w NP, gdzie-L jest w co-np---czyli L = --L jest w NP.)

(iii) i myślę że powszechnie uważa się, że NP != co-np, ponieważ w przeciwnym razie istnieją dowody wielomianowe, że wzory boolowskie nie są spełnione.

Wniosek: złożoność-teoria przypuszczenia sugerują, że kryptosystemy np-hard nie istnieją.

(W Przeciwnym Razie masz problem np-hard W NP i co-np, skąd NP = co-np - - - co jest uważane za fałszywe.)

Podczas gdy RSA i inne powszechnie stosowane algorytmy kryptograficzne są oparte na trudności faktoryzacji całkowitej (która nie jest znana jako np-complete), istnieją pewne algorytmy kryptograficzne klucza publicznego oparte na problemach np-complete. Wyszukiwanie w google "klucz publiczny "i" np-complete " ujawni niektóre z nich.

(błędnie powiedziałem wcześniej, że komputery kwantowe przyspieszą np-kompletne problemy, ale to nieprawda. Przyznaję się do błędu.)

Jak wskazuje wiele innych plakatów, możliwe jest oparcie kryptografii na problemach np-hard lub np-complete.

Jednak popularne metody kryptografii będą oparte na trudnej matematyce (czyli trudnej do złamania). Prawda jest taka, że łatwiej jest serializować liczby jako tradycyjny klucz niż tworzyć znormalizowany ciąg, który rozwiązuje problem np-hard. Dlatego praktyczna krypto opiera się na problemach matematycznych, które nie zostały jeszcze udowodnione jako np-hard lub Np-kompletny (więc można sobie wyobrazić, że niektóre z tych problemów są w P).

W szyfrowaniu ElGamal lub RSA złamanie go wymaga złamania logarytmu dyskretnego, więc spójrz na ten artykuł wikipedia .

Nie jest znany wydajny algorytm obliczania ogólnych dyskretnych logarytmów logbg. Naiwnym algorytmem jest podnoszenie b do wyższych i wyższych potęg k, aż do znalezienia pożądanego g; jest to czasami nazywane mnożeniem próbnym. Algorytm ten wymaga czasu pracy liniowy w wielkości grupy G, a tym samym wykładniczy w liczbie cyfr w wielkości grupy. Istnieje efektywny algorytm kwantowy dzięki Peterowi Shorowi ( http://arxiv.org/abs/quant-ph/9508027).

Obliczanie logarytmów dyskretnych jest najwyraźniej trudne. Nie tylko nie jest znany efektywny algorytm dla najgorszego przypadku, ale średnia złożoność przypadku może być pokazana jako co najmniej tak trudne, jak najgorszy przypadek przy użyciu losowej samo-redukcyjności.

W w tym samym czasie odwrotnym problemem wykładnictwa dyskretnego nie jest (można go obliczyć efektywnie za pomocą wykładnictwa przez kwadrat, na przykład). Asymetria ta jest analogiczna do tej między faktoryzacją całkowitą a mnożeniem całkowitym. Obie asymetrie zostały wykorzystane w budowie systemów kryptograficznych.

Powszechne jest przekonanie, że są one np-kompletne, ale może nie można tego udowodnić. Zauważ, że komputery kwantowe mogą skutecznie łamać krypto!

Ponieważ nikt naprawdę nie odpowiedział na pytanie, muszę dać Ci podpowiedź: "McEliece". Przeszukaj go. To sprawdzony algorytm szyfrowania np-Hard. Potrzebuje O (N^2) szyfrowania i czasu deszyfrowania. Ma też klucz publiczny o rozmiarze O (N^2), co jest złe. Ale są ulepszenia, które obniżają wszystkie te granice.