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

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.

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 $P \ne NP$$P \ne NP$

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

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.

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źć.
• $2^{n(n-1)}$$n$$n$
• 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.

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.

$\mathsf{P} \ne \mathsf{NP}$

$\mathsf{P} \ne \mathsf{NP}$$\mathsf{NPI}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NPI}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

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!

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