Czy do nieświadomego wykonania kodu można zastosować w pełni homomorficzne szyfrowanie?

Po przeczytaniu tej odpowiedzi jakiś czas temu zainteresowałem się w pełni homomorficznym szyfrowaniem. Po przeczytaniu wstępu pracy Gentry'ego zacząłem się zastanawiać, czy jego schemat szyfrowania może zostać użyty do nieświadomego wykonania kodu, jak określono w trzecim akapicie.

W całkowicie homomorficznym schemacie szyfrowania zazwyczaj szyfrujemy niektóre dane, wysyłamy je do wrogiego środowiska, w którym określona funkcja jest obliczana na danych, których wynik jest następnie odsyłany (zaszyfrowany), bez przeciwnika sprawdzania, jakie otrzymane dane lub wynikiem tej funkcji jest.

Przez nieświadome wykonanie kodu mam na myśli to, że szyfrujemy kawałek kodu zaprojektowanego w celu rozwiązania problemu i wysłania go do wrogiego środowiska. Przeciwnik chce użyć do rozwiązania , ale nie chcemy, aby wiedział, jak działaJeśli ma wejście dla , może zaszyfrować a następnie użyć (jakiś schemat szyfrowania na) z , który następnie zwraca (nieszyfrowane) wyjście (rozwiązanie dla wejścia $C$ $P$ $C$ $P$ $C$ $I$ $P$ $I$ $C$ $I$ $O$ $P$ $I$ ). Schemat szyfrowania gwarantuje, że przeciwnik nigdy nie dowie się, jak działa fragment kodu, tzn. Dla niego działa on tak, jak działa wyrocznia.

Głównym praktycznym zastosowaniem (o czym myślę) takiego schematu szyfrowania byłoby utrudnienie, a nawet uniemożliwienie piractwa.

Myślę, że powodem tego może być w pełni homomorficzny schemat szyfrowania, ponieważ możemy wykonywać dowolne obwody na zaszyfrowanych danych, w szczególności uniwersalną maszynę Turinga. Możemy wtedy zaszyfrować kod, tak jakby to były dane, a następnie użyć obwodu dla uniwersalnej maszyny Turinga na tych zaszyfrowanych danych, aby wykonać kod.

Postawiam to jako pytanie, ponieważ nie wiem, czy ten pomysł jest użyteczny: nigdy nie posunąłem się dalej niż wprowadzenie tezy Gentry'ego, a moja wiedza na temat kryptografii jest ograniczona. Nie wiem też, czy istnieje już często używany termin nieświadomego wykonania kodu: próbowałem wyszukać pomysł w Google, ale nie znając właściwego terminu nic nie znalazłem.

Myślę o wielu problemach, które mogą powodować problemy z tym podejściem. Po pierwsze, jeśli użyjemy w pełni homomorficznego szyfrowania bez modyfikacji, wynik obliczenia ( ) zostanie zaszyfrowany. Byłoby zatem bezużyteczne dla przeciwnika, który chce wykorzystać swój kod, aby rozwiązać . Choć może to być przydatne, powiedzmy, w chmurze obliczeniowej, nie chcę tego osiągnąć. $O$ $P$

Po drugie, ponieważ używamy obwodów, a nie arbitralnych maszyn Turinga, nie możemy używać dowolnych ilości pamięci: jesteśmy ograniczeni do z góry określonej ilości pamięci. Oznacza to, że jeśli chcemy uruchomić program w ten sposób, jego ślad pamięci będzie zawsze taki sam, a mianowicie szczytowe wykorzystanie pamięci.

Wreszcie, zaangażowane stałe prawie na pewno zabiłyby jakiekolwiek praktyczne zastosowanie takiego systemu, ale myślę, że pomysł jest jednak interesujący.

cr.crypto-security homomorphic-encryption obfuscation Alex ten Brink
źródło

czy jesteś pewien terminu „Nieświadome wykonanie kodu”? Szukałem przez chwilę i nic nie dostałem!

Deyaa,

Wcale nie: sam wymyśliłem ten termin, ponieważ nie znałem odpowiedniego terminu. Zaciemnianie i zaciemnianie są najwyraźniej regularnymi terminami dla tego pojęcia.

Alex ten Brink

Odpowiedzi:

Niestety istnieje skutek, który teoretycznie zabrania „nieświadomego wykonania kodu”:

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan i Ke Yang. O (Im) możliwościach zaciemniania programów , ADVANCES IN CRYPTOLOGY - CRYPTO 2001.

Oto linki:

Streszczenie brzmi:

Nieoficjalnie „obfuscator jest (wydajnym, probabilistycznym) „kompilatorem”, który przyjmuje jako dane wejściowe program (lub obwód) i tworzy nowy program który ma taką samą funkcjonalność jak ale „nieczytelny” " w pewnym sensie. Obfuscatory, jeśli istnieją, miałyby szeroką gamę aplikacji kryptograficznych i teorii złożoności, od ochrony oprogramowania przez szyfrowanie homomorficzne do teoretycznych analogii twierdzenia Rice'a. Większość tych aplikacji opiera się na interpretacji warunku „nieczytelności” w zaciemnieniu, co oznacza, że jest „wirtualną czarną skrzynką” w tym sensie, że wszystko, co można skutecznie obliczyć, biorąc pod uwagę $\cal O$ $P$ $\cal O(P)$ $P$ $\cal O(P)$ $\cal O(P)$ Jeden może również skutecznie obliczyć podane oracle dostęp do . $P$

W tej pracy inicjujemy teoretyczne badanie zaciemnienia. Naszym głównym wynikiem jest to, że nawet przy bardzo słabych sformalizacjach powyższej intuicji zaciemnianie jest niemożliwe. Udowodnimy to przez konstruowanie rodzinę funkcji , które są z natury unobfuscatable w następującym sensie: jest orzecznikiem takie, że (a) biorąc pod uwagę każdy program, który oblicza funkcję w , wartość można efektywnie obliczyć, ale (b) uzyskać dostęp do wyroczni do (losowo wybranej) funkcji w , żaden skuteczny algorytm nie może obliczyć znacznie lepiej niż losowe zgadywanie. $\cal F$ $\pi$ $f$ $\cal F$ $\pi(f)$ $f$ $\cal F$ $\pi(f)$

Rozszerzamy naszą niemożliwość na wiele sposobów, w tym nawet zaciemniacze, które (a) niekoniecznie są obliczalne w czasie wielomianowym, (b) tylko w przybliżeniu zachowują funkcjonalność i (c) muszą pracować tylko dla bardzo ograniczonych modeli obliczeń ). Wykluczamy także kilka potencjalnych zastosowań zaciemniaczy, konstruując schematy podpisów, schematy szyfrowania i rodziny funkcji pseudolosowych. $\rm{TC}$ $0$

MS Dousti
źródło

Ten rodzaj tłumi rzeczy. Właśnie przeczytałem, jak udowodnili swoje wyniki: byłem szczególnie zaskoczony, gdy przeczytałem, że zakłada się, że obfuscator ma dostęp do kodu źródłowego programu przeciwnika! (chociaż mogłem po prostu źle zrozumieć gazetę)

Alex ten Brink

Rozumiem, że wyniki te odnoszą się tylko do „starego” (nieudanego) modelu zaciemniania za pomocą wirtualnych czarnych skrzynek i że teraz badacze w tej dziedzinie szukają słabszego pojęcia zaciemniania z nadzieją na pewne gwarancje. Jednym z kierunków badań jest przyjęcie w pełni homomorficznego szyfrowania, dlatego powiedziałbym, że pytanie jest otwarte. Pamiętam, jak tego lata rozmawiałem z Microsoft Research na temat zaciemniaczy stałoprzecinkowych i wirtualnych czarnych skrzynek, w których badacz właśnie to zauważył.

Ross Snider,

Czy badacz w tej dziedzinie (lub jedna z imponujących nazwisk z listy autorów) może komentować?

Ross Snider,

@ Ross: Tak, chciałbym, aby inni badacze w tej dziedzinie również skomentowali ...

MS Dousti

@ Ross, Sadeq: Niektórzy autorzy odwiedzają stronę od czasu do czasu, mam nadzieję, że zauważą tag. Pomocne może być także umieszczenie pytania na stronach z polecanymi pytaniami.

Kaveh

Rzeczywiście, podczas gdy w pełni homomorficzne szyfrowanie jest bardzo przydatne do wykonywania kodu między wieloma niezaufanymi podmiotami (patrz na przykład ten artykuł ), potrzebujesz pewnego rodzaju interakcji, gdy podmiot obliczający zaszyfrowane dane wyjściowe wysyła je do strony znającej tajny klucz .

Pojęcie, którego szukasz, wydaje się podejrzanie bliskie zaciemnieniu oprogramowania, dla którego udowodniliśmy, że wynik niemożliwości jest wspomniany powyżej. Raz napisałem też nieformalny przegląd tego artykułu, który może się przydać niektórym osobom.

Biorąc pod uwagę ten wynik niemożliwości, można rozluźnić definicję na dwa (nierozłączne) sposoby: albo ograniczając klasy programów / funkcji, które należy zaciemnić, albo podając luźniejsze pojęcie bezpieczeństwa.

Drugie podejście jest być może możliwe i zwracamy uwagę na pewne słabe pojęcia podobne do zaciemniania w naszym artykule. Pamiętaj jednak, że nasz atak całkowicie odzyskuje oryginalny kod źródłowy jakiegoś programu, bez względu na to, jak jest zaciemniony. Trzeba więc w jakiś sposób stworzyć definicję bezpieczeństwa, która trywializuje w przypadku naszych kontrprzykładów.

Pierwsze podejście zostało zastosowane dla każdej ograniczonej funkcjonalności (np. Funkcji punktowej), ale znowu trzeba upewnić się, że klasa nie zawiera naszego kontrprzykładu, co z grubsza oznacza, że nie powinna zawierać funkcji pseudolosowych.

Boaz Barak
źródło