Zaciemnianie nierozróżnialności

W kryptografii zaciemnianie nieodróżnialności (w skrócie IO lub iO ) jest rodzajem zaciemniania programowego z definiującą właściwością, że zaciemnianie dowolnych dwóch programów, które obliczają tę samą funkcję matematyczną , skutkuje programami, których nie można odróżnić od siebie. Nieformalnie takie zaciemnianie ukrywa implementację programu, jednocześnie umożliwiając użytkownikom jego uruchomienie. Formalnie IO spełnia właściwość, że zaciemnienia dwóch obwodów tego samego rozmiaru, które realizują tę samą funkcję, są obliczeniowo nie do odróżnienia .

Zaciemnianie nierozróżnialności ma kilka interesujących właściwości teoretycznych. Po pierwsze, iO jest „najlepszym możliwym” zaciemnianiem (w tym sensie, że każdy sekret programu, który może być ukryty przez dowolny zaciemniacz, może być również ukryty przez iO). Po drugie, iO może służyć do konstruowania prawie całej gamy prymitywów kryptograficznych , w tym zarówno przyziemnych, takich jak kryptografia z kluczem publicznym, jak i bardziej egzotycznych, takich jak szyfrowanie deniable i szyfrowanie funkcjonalne (które są rodzajami kryptografii, o których nikt wcześniej nie wiedział, jak skonstruować), ale z godnym uwagi wyjątkiem odporności na kolizje funkcji haszujących . Z tego powodu został on określony jako „krypto-kompletny”. Wreszcie, w przeciwieństwie do wielu innych rodzajów kryptografii, zaciemnianie nierozróżnialności nadal istnieje, nawet jeśli P = NP (choć w tym przypadku musiałoby to być skonstruowane inaczej), chociaż niekoniecznie oznacza to, że iO istnieje bezwarunkowo.

Chociaż idea zaciemniania oprogramowania kryptograficznego istnieje od 1996 roku, zaciemnianie nieodróżnialności zostało po raz pierwszy zaproponowane przez Baraka i in. (2001), który udowodnił, że iO istnieje, jeśli P=NP. W przypadku P! = NP (który jest trudniejszy, ale także bardziej prawdopodobny), postęp był wolniejszy: Garg et al. (2013) zaproponowali konstrukcję iO opartą na obliczeniowym założeniu twardości odnoszącym się do map wieloliniowych , ale to założenie zostało później obalone. Konstrukcja oparta na „dobrze uzasadnionych założeniach” (założenia dotyczące twardości, które zostały dobrze zbadane przez kryptografów, a zatem powszechnie uważane za bezpieczne) musiała poczekać, aż Jain, Lin i Sahai (2020). (Mimo to jedno z tych założeń zastosowanych we wniosku 2020 nie jest bezpieczne przed komputerami kwantowymi ).

Obecnie znane kandydatury zaciemniania nierozróżnialności są bardzo dalekie od praktycznych. Jak zmierzono w artykule z 2017 r. ^{[ wymaga aktualizacji ]} , nawet zaciemnienie funkcji zabawki , która generuje logiczną koniunkcję jej trzydziestu dwóch danych wejściowych typu Boolean, tworzy program o wielkości prawie tuzina gigabajtów .

Definicja formalna

Niech $będzie$ jakimś jednolitym probabilistycznym algorytmem . Wtedy nazywany jest zaciemniaczem nieodróżnialności wtedy i tylko wtedy, gdy spełnia oba z następujących dwóch stwierdzeń: ${\ Displaystyle {\ mathcal {iO}}}$

Kompletność lub funkcjonalność : dla dowolnego obwodu boolowskiego C o długości wejściowej n i wejściu mamy ${\ Displaystyle x \ in \ {0,1 \} ^ {n}}$ ${\ Displaystyle \ Pr [C' (x) = C (x): C '\ leftarrow {\ mathcal { iO}}(C)]=1.}$
Nierozróżnialność : $} \mathcal {iO}} (C_ {0}) \}}$ każdej pary obwodów tym samym rozmiarze k , które $C_ {0}$ samą funkcjonalność, dystrybucje do , ${\ Displaystyle \ {{\ mathcal {iO}} (C_ {1}) \}}$ ja są obliczeniowo nie do odróżnienia. $/$ $displaystyle 1/p (k)}$ przeciwnika A w czasie wielomianowym istnieje pomijalna funkcja tj . Funkcja, która ostatecznie rośnie wolniej niż dla dowolnego wielomianu p ) takiego, że dla każdej pary obwodów tego samego rozmiaru ${0}, C_ {1}}$ k , które implementują tę samą funkcjonalność, mamy ${\ Displaystyle | \ Pr [A ({\ mathcal {iO}} (C_ {0})) = 1] - \ Pr [A ({\ mathcal {iO}} (C_ {1})) = 1] | \leq \varepsilon (k).}$

Historia

Źródłem tego pomysłu był Amit Sahai w 1996 roku od pojęcia dowodu z wiedzą zerową .

W 2001 roku Barak i in., wykazując, że zaciemnianie czarnej skrzynki jest niemożliwe, również zaproponowali ideę zaciemniania nierozróżnialności i skonstruowali nieefektywny. Chociaż koncepcja ta wydawała się stosunkowo słaba, Goldwasser i Rothblum (2007) wykazali, że skuteczna zaciemniacz byłby najlepszym możliwym zaciemniaczem, a każdy najlepszy możliwy zaciemniacz byłby zaciemniaczem nierozróżnialności. (Jednakże w przypadku nieefektywnych zaciemniaczy nie istnieje żaden najlepszy możliwy zaciemniacz, chyba że hierarchia wielomianów spadnie do drugiego poziomu).

Konstrukcje kandydujące

Baraka i in. (2001) udowodnili, że nieefektywny zaciemniacz nierozróżnialności; to znaczy leksykograficznie pierwszy obwód, który oblicza tę samą funkcję. Jeśli P = NP zachodzi, to istnieje zaciemniacz nieodróżnialności, mimo że nie istniałby również żaden inny rodzaj kryptografii.

Kandydat na konstrukcję IO z możliwym do udowodnienia bezpieczeństwem przy konkretnych założeniach dotyczących twardości odnoszących się do map wieloliniowych został opublikowany przez Garga i in. (2013), ale to założenie zostało później unieważnione. (Wcześniej Garg, Gentry i Halevi (2012) skonstruowali kandydującą wersję mapy wieloliniowej w oparciu o założenia heurystyczne.)

Począwszy od 2016 roku Lin zaczął eksplorować konstrukcje IO oparte na mniej ścisłych wersjach map wieloliniowych, konstruując kandydata na mapach stopnia do 30, a ostatecznie kandydata na mapach stopnia do 3. Ostatecznie w 2020 roku Jain, Lin i Sahai zaproponowali konstrukcję IO opartą na symetrycznych zewnętrznych założeniach Diffie-Helmana , uczeniu się z błędami i uczeniu plus szum , a także na istnieniu superliniowego generatora pseudolosowości z rozciągnięciem w klasie funkcji NC ⁰ . (Istnienie generatorów pseudolosowych w NC ⁰ (nawet przy rozciągnięciu podliniowym) był od dawna otwartym problemem do 2006 r.) Możliwe, że tę konstrukcję można złamać za pomocą obliczeń kwantowych , ale istnieje alternatywna konstrukcja, która może być zabezpieczona nawet przed tym (chociaż ta ostatnia opiera się na mniej ugruntowanych założeniach dotyczących bezpieczeństwa). ^{[ spekulacje? ]}

Praktyczność?

Były próby wdrożenia i porównania kandydatów IO. Na przykład od 2017 r. Zaciemnianie funkcji na poziomie bezpieczeństwa ${\ Displaystyle x_ {1} \ klin x_ {2} \ klin \ kropki \ klin x_ {32}}$ wytworzenie 80 bitów zajęło 23,5 minuty i zmierzyło 11,6 GB, przy czasie oceny 77 ms. Dodatkowo zaciemnienie Advanced Encryption Standard na poziomie bezpieczeństwa 128 bitów mierzyłoby 18 PB i miałoby czas oceny około 272 lat.

oprogramowania typu open source kandydata na IO powstała w 2015 roku.

Istnienie

Przydatne jest podzielenie kwestii istnienia iO za pomocą „pięciu światów” Russella Impagliazzo , które są pięcioma różnymi hipotetycznymi sytuacjami dotyczącymi złożoności przeciętnego przypadku :

Algorytmika : W tym przypadku P = NP , ale istnieje iO.
Heurystyka : W tym przypadku problemy NP są średnio łatwe; iO nie istnieje. ^{[ wątpliwe – dyskutuj ]}
Pessiland $przypadku$ tym funkcje nie istnieją w rezultacie iO nie istnieje.
Minicrypt : W tym przypadku istnieją funkcje jednokierunkowe , ale nie ma bezpiecznej kryptografii z kluczem publicznym ; iO nie istnieje (ponieważ znane są jawne konstrukcje kryptografii klucza publicznego z iO i funkcje jednokierunkowe).
Cryptomania : W tym przypadku istnieje bezpieczna kryptografia z kluczem publicznym ; ale iO nie istnieje.
Obfustopia : W tym przypadku uważa się, że iO istnieje.

Potencjalne aplikacje

Zaciemniacze nieodróżnialności, jeśli istnieją, mogą być używane w ogromnej gamie aplikacji kryptograficznych , do tego stopnia, że określa się je jako „centralne centrum” kryptografii, „klejnot koronny kryptografii” lub „krypto-kompletny” . Konkretnie, zaciemniacz nierozróżnialności (z dodatkowym założeniem istnienia funkcji jednokierunkowych ) mógłby zostać użyty do skonstruowania następujących rodzajów kryptografii:

Zaciemnianie nierozróżnialności dla programów w modelu RAM i dla maszyn Turinga
IND-CCA – bezpieczna kryptografia z kluczem publicznym
Krótkie podpisy cyfrowe
IND-CCA – bezpieczne schematy enkapsulacji klucza
Doskonale zerowej wiedzy nieinteraktywne dowody zerowej wiedzy i zwięzłe nieinteraktywne argumenty
Równoczesne protokoły zerowej wiedzy o stałej rundzie
Mapy wieloliniowe z ograniczonymi stopniami wielomianu
Funkcje zapadni iniekcyjnej
W pełni homomorficzne szyfrowanie
Szyfrowanie świadków
Szyfrowanie funkcjonalne
Tajne udostępnianie dla dowolnego monotonnego języka NP
Półszczery nieświadomy transfer
Szyfrowanie z możliwością odmowy (zarówno z możliwością odmowy nadawcy, jak i z pełną odmową)
Wielostronna, nieinteraktywna wymiana kluczy
Adaptacyjnie zabezpiecz zwięzłą, zniekształconą pamięć RAM
Korelacja trudnych funkcji
Szyfrowanie oparte na atrybutach
Niepozorny przelew
Śledzenie zdrajcy
Stopniowane schematy kodowania

Dodatkowo, jeśli istnieją iO i funkcje jednokierunkowe, to problemy w klasie złożoności PPAD są trudne do udowodnienia.

Jednak zaciemniania nierozróżnialności nie można użyć do skonstruowania każdego możliwego protokołu kryptograficznego: na przykład żadna konstrukcja czarnej skrzynki nie może przekształcić zaciemniacza nierozróżnialności w odporną na kolizje rodzinę funkcji skrótu , nawet z permutacją zapadni , chyba że z wykładniczą utratą bezpieczeństwa.

Zobacz też

Zaciemnianie czarnej skrzynki , silniejsza forma zaciemniania, okazała się niemożliwa