Kryptosystem Pailliera

Kryptosystem Pailliera , wynaleziony i nazwany na cześć Pascala Pailliera w 1999 roku, jest probabilistycznym algorytmem asymetrycznym do kryptografii klucza publicznego . Uważa się , że problem obliczenia n -tych klas reszt jest trudny obliczeniowo. Założenie decyzyjnej złożonej resztowości jest hipotezą trudności , na której opiera się ten kryptosystem.

Schemat jest addytywnym homomorficznym kryptosystemem ; oznacza to, że mając tylko klucz publiczny i szyfrowanie i m $\ displaystyle m_ {2}$$}$ można obliczyć szyfrowanie $displaystyle m_ {1}+m_{2}}$ .

Algorytm

Schemat działa w następujący sposób:

Generowanie klucza

1. $Wybierz$${\ displaystyle \ gcd ( pq,(p-1)(q-1))=1}$ duże liczby pierwsze $i$ niezależnie od siebie tak, że . Ta właściwość jest zapewniona, jeśli obie liczby pierwsze są równej długości.
2. Oblicz ${\ Displaystyle n = pq}$ i ${\ Displaystyle \ lambda = \ operatorname {lcm} (p-1, q-1)}$ . lcm oznacza najmniejszą wspólną wielokrotność .
3. ${$ całkowitą gdzie $Z} _ {n ^ {2}} ^ {*}}$
4. Upewnij się, że dzieli rząd ${\ displaystyle$$g} ,$ istnienie następującej modułowej odwrotności multiplikatywnej : ${\ displaystyle \ mu = (L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}}$ ,

gdzie funkcja jest zdefiniowana jako $($${n}}}$ .

$b},$ że notacja nie oznacza modularnego mnożenia $displaystyle$$modułową$ multiplikatywną odwrotność b raczej iloraz ${\ Displaystyle a}$$a \ geq vb}$$przez$ , . największą liczbę całkowitą, spełnić relację $Displaystyle$ .

• Klucz publiczny (szyfrujący) to ${\ Displaystyle (n, g)}$ .
• Klucz prywatny (odszyfrowywania) to ${\ Displaystyle (\ lambda, \ mu).}$

W przypadku użycia p, q o równoważnej długości, prostszym wariantem powyższych etapów generowania klucza byłoby ustawienie ${\ displaystyle g = n + 1, \ lambda = \ varphi ( n)}$ i ${\ Displaystyle \ mu = \ varphi (n) ^ {- 1} {\ bmod {n}}}$ , gdzie ${\ Displaystyle \ varphi (n) = (p-1) (q-1)}$ . Prostszy wariant jest zalecany do celów implementacyjnych, ponieważ w postaci $ogólnej$ czas obliczeń może bardzo długi przy wystarczająco dużych liczbach pierwszych p, q.

Szyfrowanie

1. Niech będzie wiadomością do zaszyfrowania gdzie $<n}$$równoważnik$
2. Wybierz losowo gdzie $0 <r <n}$$displaystyle$$n) = 1}$ 1
3. Oblicz zaszyfrowany tekst jako: ${\ Displaystyle c = g ^ {m} \ cdot r ^ {n} {\ bmod {n}} ^ {2}}$

Deszyfrowanie

1. Niech ${\ displaystyle c}$ będzie tekstem zaszyfrowanym do odszyfrowania, gdzie do $\ in \ mathbb {Z} _ {n ^ {2}} ^ {*}}$
2. Oblicz wiadomość w postaci zwykłego tekstu jako: ${\ Displaystyle m = L (c ^ {\ lambda} {\ bmod {n}} ^ {2}) \ cdot \ mu { \bmod {n}}}$

Jak wskazuje oryginalny artykuł, deszyfrowanie to „w zasadzie jedno potęgowanie modulo ${\ displaystyle n ^ {2}}$ ”.

Właściwości homomorficzne

Godną uwagi cechą kryptosystemu Pailliera są jego homomorficzne właściwości wraz z niedeterministycznym szyfrowaniem (patrz Głosowanie elektroniczne w Aplikacjach do użytku). Ponieważ funkcja szyfrowania jest addytywnie homomorficzna, można opisać następujące tożsamości:

• Homomorficzne dodawanie tekstów jawnych

Iloczyn dwóch zaszyfrowanych tekstów zostanie odszyfrowany do sumy odpowiadających im tekstów jawnych,

${\ Displaystyle D (E (m_ {1}, r_ {1}) \ cdot E (m_ {2}, r_ {2}) {\ bmod {n}} ^ {2}) = m_ {1} + m_ {2}{\bmod {n}}.\,}$

Iloczyn tekstu zaszyfrowanego z podniesieniem tekstu jawnego $odszyfrowany$ do sumy odpowiednich tekstów jawnych,

${\ Displaystyle D (E (m_ {1}, r_ {1}) \ cdot g ^ {m_ {2}} {\ bmod {n}} ^ {2}) = m_ {1} + m_ {2} \bmod {n}}.\,}$

• Homomorficzne mnożenie tekstów jawnych

Zaszyfrowany tekst podniesiony do potęgi tekstu jawnego zostanie odszyfrowany do iloczynu dwóch tekstów jawnych,

${\ Displaystyle D (E ( m_{1},r_{1})^{m_{2}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n}},\,}$

${\ Displaystyle D (E (m_ {2}, r_ {2}) ^ {m_ {1}} {\ bmod {n}} ^ {2}) = m_ {1} m_ {2} {\ bmod {n }}.\,}$

Mówiąc bardziej ogólnie, tekst zaszyfrowany podniesiony do stałej k zostanie odszyfrowany do iloczynu tekstu jawnego i stałej,

${\ Displaystyle D (E (m_ {1}, r_ {1}) ^ {k} {\ bmod {n}} ^ {2}) = km_ {1} {\ bmod {n}}. \,}$

Jednak biorąc pod uwagę szyfrowanie Pailliera dwóch wiadomości, nie ma znanego sposobu obliczenia szyfrowania iloczynu tych wiadomości bez znajomości klucza prywatnego.

Tło

Kryptosystem Pailliera wykorzystuje fakt, że pewne dyskretne logarytmy można łatwo obliczyć.

Na przykład przez twierdzenie dwumianowe ,

${\ Displaystyle (1 + n) ^ {x} = \ suma _ {k=0}^{x}{x \choose k}n^{k}=1+nx+{x \choose 2}n^{2}+{\text{wyższe potęgi }}n}$

Oznacza to, że:

${\ Displaystyle (1 + n) ^ {x} \ równoważnik 1 + nx {\ pmod {n ^ {2}}}}$

Dlatego jeśli:

${\ Displaystyle y = (1 + n) ^ {x} {\ bmod {n}} ^ {2}}$

Następnie

${\ Displaystyle x \ równoważnik {\ Frac {y-1} {n}} {\ pmod {n}}}$ .

Zatem:

${\ Displaystyle L ((1 + n) ^ {x} \ bmod {n}} ^ {2}) \ równoważnik x {\ pmod {n}}}$ ,

gdzie funkcja jest zdefiniowana jako $($${\ Displaystyle L (u) = {\ Frac {u-1} {n}}$ iloraz dzielenie całkowite) i ${\ Displaystyle x \ w \ mathbb {Z} _ {n}}$ .

Bezpieczeństwo semantyczne

Oryginalny system kryptograficzny pokazany powyżej zapewnia bezpieczeństwo semantyczne przed atakami z użyciem wybranego tekstu jawnego ( IND-CPA ). Zdolność do pomyślnego rozróżnienia tekstu zaszyfrowanego prowokacji jest zasadniczo równoznaczna ze zdolnością do decydowania o złożonej pozostałości. , że tak zwane decyzyjne założenie złożonej resztowości (DCRA) jest trudne do rozwiązania.

Jednak ze względu na wyżej wymienione właściwości homomorficzne system jest plastyczny , a zatem nie ma najwyższego poziomu bezpieczeństwa semantycznego, ochrony przed atakami adaptacyjnego wybranego tekstu zaszyfrowanego ( IND-CCA2 ). Zwykle w kryptografii pojęcie plastyczności nie jest postrzegane jako „zaleta”, ale w niektórych zastosowaniach, takich jak bezpieczne głosowanie elektroniczne i kryptosystemy progowe , ta właściwość może być rzeczywiście konieczna.

Paillier i Pointcheval zaproponowali jednak ulepszony kryptosystem, który zawiera kombinację mieszania wiadomości m z losowym r . Podobnie jak w kryptosystemie Cramera-Shoupa , haszowanie uniemożliwia atakującemu, któremu podano tylko c, zmianę m w znaczący sposób. Dzięki tej adaptacji można wykazać, że ulepszony schemat jest bezpieczny dla IND-CCA2 w losowym modelu wyroczni .

Aplikacje

Głosowanie elektroniczne

0 Bezpieczeństwo semantyczne nie jest jedyną kwestią. Istnieją sytuacje, w których plastyczność może być pożądana. Powyższe homomorficzne właściwości mogą być wykorzystane przez bezpieczne elektroniczne systemy głosowania. Rozważ proste głosowanie binarne („za” lub „przeciw”). Niech m wyborców odda głos 1 (za) lub (przeciw). Każdy głosujący szyfruje swój wybór przed oddaniem głosu. Urzędnik wyborczy bierze iloczyn m zaszyfrowanych głosów, a następnie odszyfrowuje wynik i otrzymuje wartość n , czyli suma wszystkich głosów. Urzędnik wyborczy wie wtedy, że n osób głosowało za i mn osób głosowało przeciw . Rola losowego r gwarantuje, że dwa równoważne głosy zostaną zaszyfrowane do tej samej wartości tylko z znikomym prawdopodobieństwem, zapewniając w ten sposób prywatność wyborcy.

Elektroniczna gotówka

Inną cechą wymienioną w artykule jest pojęcie samooślepiania . Jest to możliwość zamiany jednego zaszyfrowanego tekstu na inny bez zmiany treści jego deszyfrowania. Ma to zastosowanie do rozwoju ecash , inicjatywy, której oryginalnie zainicjował David Chaum . Wyobraź sobie, że płacisz za przedmiot online, a sprzedawca nie musi znać numeru Twojej karty kredytowej, a tym samym Twojej tożsamości. Celem zarówno elektronicznego głosowania gotówkowego, jak i elektronicznego głosowania jest zapewnienie ważności e-monety (podobnie jak e-głosowania), przy jednoczesnym nieujawnianiu tożsamości osoby, z którą jest aktualnie powiązana.

Kryptosystem progowy

Homomorficzna właściwość kryptosystemu Pailliera jest czasami wykorzystywana do budowy podpisu Threshold ECDSA.

Zobacz też

• Kryptosystem Naccache – Sterna i kryptosystem Okamoto – Uchiyama są historycznymi poprzednikami Pailliera.
• Damgårda -Jurika jest uogólnieniem Pailliera.

• Paillier, Pascal (1999). „Kryptosystemy klucza publicznego oparte na klasach pozostałości stopnia złożonego” (PDF) . Postępy w kryptologii — EUROCRYPT '99. EUROKRYPT . Skoczek. doi : 10.1007/3-540-48910-X_16 .
• Paillier, Pascal; Pointcheval, David (1999). „Wydajne systemy kryptograficzne z kluczem publicznym, które są bezpiecznie zabezpieczone przed aktywnymi przeciwnikami” . AZJAKRYPT . Skoczek. s. 165–179. doi : 10.1007/978-3-540-48000-6_14 .
• Paillier, Pascal (1999). Cryptosystems Based on Composite Residuosity (praca doktorska). École Nationale Supérieure des Télécommunications.
• Paillier, Pascal (2002). „Kryptografia oparta na pozostałościach kompozytowych: przegląd” (PDF) . CryptoBytes . 5 (1). Zarchiwizowane od oryginału (PDF) w dniu 20 października 2006 r.

Notatki

Linki zewnętrzne

• Homomorphic Encryption Project implementuje kryptosystem Pailliera wraz z jego homomorficznymi operacjami.
• Encounter: biblioteka typu open source zapewniająca implementację kryptosystemu Pailliera i opartą na nim konstrukcję liczników kryptograficznych.
• python-paillier biblioteka do częściowego szyfrowania homomorficznego w Pythonie, w tym pełna obsługa liczb zmiennoprzecinkowych.
• Interaktywny symulator kryptosystemu Paillier demonstruje aplikację do głosowania.
• Interaktywna demonstracja kryptosystemu Paillier.
• Weryfikacja koncepcji implementacji Javascript kryptosystemu Paillier z interaktywną demonstracją .
• Film googletechtalk na temat głosowania przy użyciu metod kryptograficznych.
• Ruby implementacja dodatku homomorficznego Pailliera i protokół dowodu zerowej wiedzy ( dokumentacja )