Kryptografia bez założeń - szukanie przeglądu

25

Załóżmy, że i jutro pojawi się szybki algorytm czasu liniowego dla SAT. Nagle RSA jest niepewny, znaczna część naszego nowoczesnego systemu komunikacji jest zepsuta i musimy ponownie rozważyć, jak zachować przed sobą tajemnice.P.=N.P.

Pytanie: Czy istnieje dobre pojedyncze odniesienie (lub krótka lista), aby uzyskać ogólny obraz tego, co jest możliwe w kryptografii (i w pokrewnym polu „bezpieczeństwa”) bez założeń niemożności? Mogłoby to uratować cywilizację pewnego dnia, a tymczasem miło byłoby ją przejrzeć.

Dyskusja: Większość zadań kryptograficznych, które obecnie badamy (OWF, PRG, PKE) jest niemożliwie niemożliwa w świecie (świecie nazwanym „Algorytmica” w wpływowym eseju Impagliazzo), ale pewne rzeczy pozostają możliwe: komunikacja z wkład jednorazowy ; rozproszone tajne udostępnianie ; wyszukiwanie prywatnych informacji ; i kilka innych fajnych rzeczy. (Przydatne mogą być również pewne mechanizmy fizyczne, takie jak zamknięte skrzynki , urządzenia realizujące nieświadomy transfer i stany kwantowe . Oczywiście zawsze istnieje jakieś fizyczne przypuszczenie, kto może zobaczyć, jakie informacje.)P.=N.P.

Można odróżnić bezpieczeństwo teoretyczne informacji (które działa przeciwko obliczeniowo niepowiązanemu przeciwnikowi) i bezpieczeństwo „bezwarunkowe” (które może wymagać ograniczonego przeciwnika, ale nadal wykazuje bezpieczeństwo bez żadnych niepotwierdzonych założeń). Najbardziej interesuje mnie sprawa teoretyczna.

Na początek, oto jedna bibliografia bezpieczeństwa teoretycznego (która, moim zdaniem, jest niemożliwie długa i odmienna).

Andy Drucker
źródło
Ładne pytanie, to nie jest tak naprawdę odpowiedź, ale może być interesujące. Alfred Menezes i Neal Koblitz mają fajną serię artykułów „Another Look”, w których zadają pytania podobne do twoich, ale także podążają w kierunku „modeli bezpieczeństwa”. Omówiłem to krótko w tej odpowiedzi , ale nie jestem pewien, czy to podejście jest zbyt stosowane.
Artem Kaznatcheev
3
Podejrzewam, że można użyć takiego algorytmu SAT do znalezienia alternatywy dla obecnych PKC i bezwarunkowo bezpiecznych systemów.
T ....
Zauważ, że RSA nie jest NP-Complete, więc wymaganie P = NP do wzięcia pod uwagę może być przesadą.
user834
duża część współczesnych kryptowalut opiera się na założeniach trudnych do uproszczenia / wygody, ale ponieważ nie są dostępne lepsze wyniki / możliwe do udowodnienia limity z teorii złożoności (szczególnie średnia złożoność przypadków) ... zobacz także crypto.se
vzn
3
Oto przegląd przez Ueli Maurer, które choć trochę przestarzałe, jest dość dobrze poinformowany: ftp.inf.ethz.ch/pub/crypto/publications/Maurer99.pdf

Odpowiedzi:

16

Kluczowe frazy, których prawdopodobnie szukasz, to „kryptografia teoretyczna” i „kryptografia kwantowa”. Przeszukanie literatury na te tematy przyniesie wiele pracy tego rodzaju, którego szukasz. Poniżej niektóre przykłady:

  • Dla zachowania poufności: jednorazowa podkładka, kanał podsłuchowy Wynera, tajne udostępnianie, wymiana kluczy kwantowych itp.

  • Dla integralności i uwierzytelnienia: uniwersalne funkcje skrótu.

  • Dla anonimowości: anonimowa komunikacja (np. Sieci prądu stałego, schematy oparte na cebuli, sieci p2p oparte na szybkim mieszaniu losowych spacerów), protokoły ograniczania odległości.

  • Dla bezpieczeństwa opartego na fizycznych założeniach: PUF (funkcje fizycznie nieklonowalne), kody integralności (Capkun i in.), Kryptografia kwantowa, bezpieczeństwo z wykorzystaniem TPM lub sprzętu odpornego na manipulacje.

Istnieje wiele artykułów na te tematy; zbyt wielu, aby streścić wszystkie wyniki w literaturze.

DW
źródło
Dzięki DW Wiem, że to zbyt wiele powodów, by podsumować w odpowiedzi; Mam nadzieję znaleźć przydatne książki lub ankiety.
Andy Drucker,
@AndyDrucker, moim zaleceniem byłoby przeczytanie przełomowych lub najnowocześniejszych artykułów na interesujące Cię tematy. Nie jestem pewien, czy znajdziesz książkę, która obejmie całą pracę w tej dziedzinie (niektóre z nich wydarzyły się w ciągu ostatnich 5-10 lat). Nawet jeśli będziesz mieć szczęście i odkryjesz jakąś książkę, zacznie ona pozostawać w tyle za najnowszą literaturą badawczą, zanim pojawi się na półkach z książkami.
DW
2
Nie aspiruję nawet do najnowocześniejszych rozwiązań. Nie ma naprawdę aktualnego podręcznika dla jakiegokolwiek obszaru TCS; jednak wciąż można podnieść książki Goldreicha i zorientować się w podstawowych wynikach i koncepcjach kryptografii opartej na złożoności. Zastanawiałem się, czy coś podobnego nie pojawiło się po stronie teorii informacji.
Andy Drucker,
4

To dość złożone pytanie, ponieważ tak naprawdę nie mamy dobrego przeglądu tego obszaru. Częściowo wynika to z faktu, że teoria informacji i społeczność kryptograficzna pracują nad podobnymi tematami, ale tak naprawdę nie współpracują wystarczająco ze sobą. Wiele dobrych punktów podano powyżej. Chciałbym tylko dodać kilka dodatkowych obserwacji:

  • Mamy duży zakres prac dotyczących problemu tajnego klucza (i bezpiecznej komunikacji) z daną konfiguracją. Tutaj konfiguracja oznacza na przykład, że strony w systemie (powiedzmy Alice, Bob i przeciwniczka Eve) dzielą się pewnymi skorelowanymi informacjami pochodzącymi z trójstronnego rozkładu prawdopodobieństwa. Alternatywna konfiguracja może składać się z głośnych kanałów (np. Alicja może wysyłać informacje do Boba i Ewy za pośrednictwem głośnych kanałów). Ponadto Alice i Bob są połączeni kanałem komunikacji (który może być uwierzytelniony lub nie). Ta linia pracy rozpoczęła się od Aarona Wynera w latach 70., który wprowadził model kanału Wiretap, a następnie został oczyszczony przez Maurera i innych w latach 90. Ponadto wiele technik w tym obszarze (wzmocnienie prywatności, uzgadnianie informacji) ostatecznie zostało użyte w ustawieniu QKD (Quantum Key-Distribution). Nawet do tej pory wykonuje się sporo pracy, na przykład w powiązanych obszarach, takich jak wyciągi niematerialne itp. Model przechowywania ograniczonego jest również ustawieniem innym niż powyższe, ale wykorzystuje podobne techniki i ma podobne cele

  • Oprócz tajnego udostępniania znajdziesz wiele prac dotyczących teoretycznie bezpiecznych obliczeń wielostronnych (MPC). W szczególności linia prac zainicjowana protokołem BGW jest całkowicie teoretyczna.

  • Nie jestem też pewien, jak daleko sięga zakres pytania: jeśli na przykład P = NP rzeczywiście się utrzymuje, ale możemy jakoś uzasadnić obecność przypadkowej wyroczni na niebie, to kryptografia symetryczna jest nadal możliwa. Czasami takie modele są rzeczywiście używane do udowodnienia bezpieczeństwa niektórych konstrukcji kryptograficznych (takich jak funkcje skrótu lub szyfry blokowe), a techniki te są całkowicie teoretyczne.

  • Teoretyczne techniki informatyczne w kryptografii często pojawiają się jako pośrednie narzędzie w wynikach teoretycznych złożoności, ale myślę, że jest to poza zakresem pytania. (Zobacz pracę Maurera na temat układów losowych i wzmocnienia nierozróżnialnego jako przykład tego rodzaju pracy).

Stefano Tessaro
źródło
„możemy jakoś usprawiedliwić obecność przypadkowej wyroczni na niebie” o czym dokładnie tutaj mówisz? Jak możliwa jest tutaj symetryczna krypta klucza publicznego?
T ....
1
@JA Wierzę, że ma na myśli losowy model wyroczni Bellare i Rogaway, patrz np . Cseweb.ucsd.edu/~mihir/papers/ro.html . Ten model jest heurystyczny, często przydatny, ale istnieją uzasadnione powody do sceptycyzmu: arxiv.org/abs/cs/0010019
Sasho Nikolov
ic .. co dokładnie tu się dzieje? masz pomysł na konkretnym poziomie? Wszystkie teoretyczne schematy kluczy symetrycznych, które widziałem, oparte są na wydobywaniu wspólnych informacji ze skorelowanych i dlatego prawdopodobnie nie można ich przekształcić w wersję klucza publicznego. Czy istnieje tutaj podstawowa idea, która umożliwia wykonalne rozwiązanie kryptograficzne z kluczem publicznym, które jest teoretycznie bezpieczne?
T ....
2
Pozwól mi rozwinąć: w modelu losowej wyroczni, w której wszystkie strony mają dostęp do losowej wyroczni RO, uczciwe strony posiadające tajny klucz SK mogą bezpiecznie zaszyfrować wiadomość M jako (R, M + RO (SK || R)), gdzie R jest przypadkowością szyfrowania (i jest generowane na nowo przy każdym szyfrowaniu), + oznacza bitor xor (tutaj zakładamy, że długość wyjściowa RO jest równa długości wiadomości). Bezpieczeństwo tego schematu zależy tylko od losowości wyroczni. Z kolei w pracy Impagliazzo i Rudicha wiadomo, że szyfrowanie kluczem publicznym nie jest możliwe w modelu losowo-wyroczni.
Stefano Tessaro,
3

Niektóre grupy badawcze w Europie kontynuowały tę linię badań; dokładniej, ze względu na moje zainteresowanie teorią informacji natknąłem się na pracę Ueli Maurera i jego szkoły, co jest zarówno istotne z czysto teoretycznego punktu widzenia (z którym jestem bardziej zaznajomiony), jak i oferuje pewne praktyczne podejścia do informacji teoretyczne bezpieczeństwo.

W związku z powyższą linią pracy niektóre miejsca, które warto rozważyć, to praca doktorska Christiana Cachina, a także Renato Renner (więcej kwantowy).

Oczywiście istnieje zupełnie inne podejście do słów kluczowych, w tym BB84, Preskill-Shor, Artur Ekert itp.

Powyższe oczywiście odzwierciedla tylko moje ograniczone doświadczenie i na pewno jest o wiele więcej podejść i interesujących kierunków pracy.

Mohammad Bavarian
źródło