Próg w pełni homomorficzne kryptosystemy

9

ostatnio Craig Gentry opublikował pierwszy schemat szyfrowania klucza publicznego (na przestrzeni tekstu jawnego {0,1}), który jest w pełni homomorficzny, co oznacza, że można skutecznie i kompaktowo oceniać AND i XOR na zaszyfrowanych tekstach jawnych bez znajomości tajnego klucza odszyfrowywania.

Zastanawiam się, czy istnieje jakiś oczywisty sposób na przekształcenie tego kryptosystemu klucza publicznego w progowy kryptosystem klucza publicznego, tak aby każdy mógł szyfrować ORAZ i XOR, ale odszyfrowanie jest możliwe tylko wtedy, gdy niektóre (wszystkie) osoby współużytkują klucz.

Byłbym zainteresowany wszelkimi pomysłami na ten temat.

Z góry dziękuję

fw

cr.crypto-security circuit-complexity homomorphic-encryption

2

Jest to bardziej ciekawostka i nie dotyczy bezpośrednio twojego pytania. Co ciekawe, ponieważ schemat jest w pełni homomorficzny, partia może homomorficznie i rekurencyjnie tworzyć pary klucz publiczny-prywatny.

— Ross Snider,

1

Bliżej odpowiedzi na twoje pytanie, ale wciąż za mało, aby opublikować odpowiedź: FHE jest całkowicie nowy - istnieją tylko dwa proponowane schematy (oba przez Gentry). Według mojej wiedzy nie opublikowano żadnej pracy na temat Threshold FHE. Mogą jednak wystąpić prace nad częściowo homomorficznymi systemami (takimi jak Paillier, Goldwasser itp.). Zacznę szukać tam, czy wyniki można łatwo „przenieść” do FHE.

— Ross Snider,

6

Nowy artykuł Stevena Myersa, Mony Sergi i Abhi Shelat na temat eprint, „ Próg w pełni homomorficznego szyfrowania i bezpiecznych obliczeń ”, twierdzi, że ma próg w pełni homomorficznego schematu szyfrowania.

Z ich streszczenia:

...

Gentry [Gen09a] pokazuje, jak połączyć oba pomysły z całkowicie homomorficznym szyfrowaniem, aby zbudować bezpieczny protokół wielopartyjny, który umożliwia ocenę funkcji $f$ za pomocą komunikacji niezależnej od opisu obwodu $f$ i obliczenia wielomianowe w $|f|$ . Ten artykuł dotyczy głównych wad podejścia Gentry'ego: eliminujemy stosowanie metod innych niż czarne skrzynki, które są nieodłączne od kompilatora Naor i Nissim.

W tym celu pokazujemy, jak zmodyfikować w pełni homomorficzną konstrukcję szyfrowania van Dijk i in. [vDGHV10] ma być progiem w pełni homomorficznych schematów szyfrowania.

...

Podsumowując, tworzymy pierwszy bezpieczny, wielostronny protokół obliczeniowy czarnej skrzynki, który umożliwia ocenę funkcji $f$ za pomocą komunikacji niezależnej od opisu obwodu $f$ .

— użytkownik686
źródło

3

Nie znam specyfiki schematu Gentry'ego, ale wszystkie inne kryptosystemy progowe wymagają dwóch homomorfizmów (trzeci implikowany) odnoszących się do kluczy publicznych i tajnych:

${\sf KG}(sk1)\otimes{\sf KG}(sk2)={\sf KG}(sk1\oplus sk2)$
$c={\sf Enc}_{pk1}({\sf Enc}_{pk2}(m,r))={\sf Enc}_{pk1\otimes pk2}(m,r)$
$m={\sf Dec}_{sk1}({\sf Dec}_{sk2}(c))={\sf Dec}_{sk1\oplus sk2}(c)$

( ${\sf KG}$ jest funkcją, która podając tajny klucz, zwraca klucz publiczny: $pk={\sf KG}(sk)$ .)

Jeśli te warunki się utrzymują, w przypadku niektórych operacji $\oplus$ i $\otimes$ , jest trywialnie możliwe wykonanie rozproszonego (n-out-of-n) deszyfrowania i może być możliwe zastosowanie progu (m-out-of-n), jeśli operacja $\oplus$ jest na przykład wystarczający do interpolacji wielomianu.

Na przykład w progu Elgamal $\oplus$ jest dodatkiem i umożliwia interpolację.

Chociaż nikt nie odpowiedział na pierwotne pytanie, być może ktoś może odpowiedzieć na następujące pytania: (1) Czy FHE Gentry pasuje do powyższego planu (pod względem ${\sf KG}$ , ${\sf Enc}$ , ${\sf Dec}$ ). (2) Czy takie homomorfizmy istnieją między kluczem publicznym a kluczem tajnym? (3) Jeśli tak, jakie są operacje?

Nie mówię też, że te warunki są konieczne, aby mieć kryptosystem progowy. Brak takiego homomorfizmu nie oznacza (o ile wiem), że deszyfrowanie progów jest niemożliwe.

— PulpSpy
źródło