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

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 = NP$

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 = NP$

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).

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.

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).

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.