Dlaczego nie istniał algorytm szyfrowania oparty na znanych problemach NP-Hard?

109

Większość współczesnego szyfrowania, takiego jak RSA, opiera się na faktoryzacji liczb całkowitych, co nie jest uważane za problem trudny dla NP, ale należy do BQP, co czyni go podatnym na komputery kwantowe. Zastanawiam się, dlaczego nie istniał algorytm szyfrowania oparty na znanym problemie NP-trudnym. Brzmi (przynajmniej teoretycznie) tak, jakby był lepszym algorytmem szyfrującym niż ten, który nie jest trudny do NP.

Ken Li
źródło

Odpowiedzi:

76

W najgorszym przypadku Twardość problemów NP-zupełnych nie jest wystarczająca dla kryptografii. Nawet jeśli problemy z kompletną NP są trudne w najgorszym przypadku ( ), nadal można je skutecznie rozwiązać w przeciętnym przypadku. Kryptografia zakłada istnienie nierozwiązywalnych problemów średniej wielkości w NP. Również udowodnienie istnienia trudnych przeciętnie problemów z NP przy założeniu jest dużym otwartym problemem.P N PPNPPNP

Znakomitą lekturą jest klasyk Russella Impagliazza, A Personal View of Average-Case Complexity , 1995.

Doskonałą ankietą jest złożoność średnich przypadków autorstwa Bogdanova i Trevisana, Fundations and Trends in Theoretical Computer Science Vol. 2, nr 1 (2006) 1–106

Mohammad Al-Turkistany
źródło
1
Czy też nie potrzebujemy twardości w najlepszym przypadku? Wszakże wszystkie nasze klucze powinny być bezpieczne. Czy możemy skutecznie (i skutecznie) zapobiec wystąpieniu najlepszego przypadku?
Raphael
7
ponadto powinniśmy być w stanie wygenerować trudne instancje w rozsądnym czasie. Krótko mówiąc, potrzebujemy znacznie więcej niż tylko ness. NP-hard
Kaveh
@ Rafael, powinno wystarczyć, jeśli prawdopodobieństwo uzyskania niepożądanego „dobrego” przypadku jest wystarczająco małe. Jeśli jest to mniej niż prawdopodobieństwo odgadnięcia właściwego klucza pożądanego „złego” przypadku, ryzyko to należy uznać za dopuszczalne IMHO.
quazgar
49

Były.

Jednym z takich przykładów jest kryptosystem McEliece, który opiera się na twardości dekodowania kodu liniowego.

Drugim przykładem jest NTRUEncrypt, który opiera się na najkrótszym problemie wektorowym, który moim zdaniem jest znany jako NP-Hard.

Innym jest uszkodzony kryptosystem plecakowy Merkle-Hellman .

Uwaga: Nie mam pojęcia, czy pierwsze dwa są zepsute / jak dobre są. Wiem tylko, że one istnieją, i mam je z wyszukiwania w Internecie.

Aryabhata
źródło
6
Do celów kryptoanalizy McEliece prawdopodobnie nie powinien być uważany za jeden kryptosystem; dla każdej klasy skutecznie dekodowanych kodów liniowych, które podłączasz, koniecznie musisz wymyślić inną strategię, aby je złamać. Został zepsuty dla niektórych klas kodów, ale (jak mówi artykuł w Wikipedii) nie dla kodów Goppa, które były oryginalną sugestią McEliece'a.
Peter Shor,
Z tej listy powiedziałbym, że NTRU wygląda najbardziej obiecująco, to jeszcze nie zostało gruntownie przetestowane w sposób, w jaki testowano RSA w oparciu o to, o czym czytałem do tej pory.
Ken Li
Kryptosystem Merkle-Hellman nie jest odpowiednim przykładem. Wektory plecakowe Merkle-Hellman są tylko podzbiorem wszystkich wektorów plecakowych, więc problem plecakowy Merkle-Hellman może nie być trudny NP. Nie sądzę, że jest to trudne do NP, przynajmniej nie znam żadnego dokumentu, który to pokazuje.
miracle173
25

Mogę wymyślić cztery główne przeszkody, które nie są całkowicie niezależne:

  • Twardość NP daje jedynie informację o złożoności limitu . W przypadku wielu problemów z NP-zakończeniem istnieją algorytmy, które szybko rozwiązują wszystkie interesujące przypadki (w określonym scenariuszu). Innymi słowy, dla każdego ustalonego rozmiaru problemu (np. Danego „klucza”) problem niekoniecznie jest trudny tylko dlatego, że jest trudny NP.
  • Twardość NP uwzględnia tylko najgorszy przypadek. Wiele, a nawet większość wszystkich instancji może być łatwo rozwiązać za pomocą istniejących algorytmów. Nawet gdybyśmy umieli scharakteryzować trudne przypadki (afaik, nie wiemy), nadal musielibyśmy je znaleźć.
  • 2n(n1)nn
  • Potrzebujesz pewnego rodzaju odwracalności. Na przykład, każda liczba całkowita jest jednoznacznie opisana przez pierwszą faktoryzację. Obraz chcielibyśmy użyć TSP jako metody szyfrowania; biorąc pod uwagę wszystkie najkrótsze trasy, czy możesz (ponownie) skonstruować wykres, z którego pochodzą?

Pamiętaj, że nie mam doświadczenia w kryptografii; są to tylko algorytmiczne wzgl. zastrzeżenia teoretyczne złożoności.

Raphael
źródło
Doskonałe podsumowanie. Pamiętaj jednak, że twardość BQP ma takie same zastrzeżenia jak twoje pierwsze dwa punkty.
Mitch
14

Kryptografia klucza publicznego, jaką znamy dzisiaj, opiera się na jednostronnych permutacjach klap , a klapa jest niezbędna.

Aby protokół był publicznie bezpieczny, potrzebujesz klucza dostępnego dla każdego oraz sposobu szyfrowania wiadomości za pomocą tego klucza. Oczywiście po zaszyfrowaniu odzyskanie oryginalnej wiadomości, znającej jedynie jej szyfr i klucz publiczny, powinno być trudne: szyfr musi być odszyfrowalny tylko z pewnymi dodatkowymi informacjami, a mianowicie kluczem prywatnym.

Mając to na uwadze, łatwo zbudować prymitywny system kryptograficzny oparty na dowolnej jednostronnej permutacji zapadni.

  1. Alice udziela jednoznacznej permutacji opinii publicznej i zatrzymuje zapadnię dla siebie.
  2. Bob umieścił swoje dane wejściowe w permutacji i przekazał dane wyjściowe Alice.
  3. Alice używa zapadni, aby odwrócić permutację z wyjściem Boba.

PNP

PNPNPINPNPNPINP

NPNPNP

Heinz Fiedler
źródło
RSA, tak, to funkcja zapadni. Nie jestem pewien, czy dlog jest TDF (jest jednokierunkowy)
111
Jeśli problem pośredni NP byłby trudny NP, byłyby to NP-zupełne, sprzeczność.
Myria
0

Wystarczy podać heurystyczny argument oparty na doświadczeniu praktycznym.

Prawie wszystkie przypadki prawie wszystkich problemów związanych z NP są łatwe do rozwiązania. Są problemy, w których to nie jest prawda, ale trudno je znaleźć i trudno być przekonanym, że masz taką klasę.

Pojawiło się to kilkakrotnie w praktyce, gdy ludzie próbowali pisać losowe generatory problemów dla niektórych znanych klas NP-zupełnych, takich jak programowanie ograniczeń, SAT czy Traveling Salesman. W późniejszym terminie ktoś znajdzie metodę rozwiązania prawie wszystkich przypadków, które generator losowy generuje w trywialny sposób. Oczywiście, gdyby tak było w przypadku systemu szyfrowania, mielibyśmy poważne kłopoty!

Chris Jefferson
źródło
-1

Kryptosystemy Merkle-Hellman opierają się na problemach plecaków binarnych (suma podzbiorów).

użytkownik13675
źródło
Czy możesz podać referencje?
Raphael
en.wikipedia.org/wiki/Merkle-Hellman_knapsack_cryptosystem ”, a także monografia: Postquantum Cryptography (Springer).
user13675