Kryptosystém Paillier - Paillier cryptosystem

The Kryptosystém Paillier, vynalezený a pojmenovaný po Pascalovi Paillierovi v roce 1999, je pravděpodobnostní asymetrický algoritmus pro kryptografie veřejného klíče. Problém výpočtu n-tá třída reziduí je považována za výpočetně obtížnou. The předpoklad rozhodující složené reziduaity je nepoddajnost hypotéza, na které je tento kryptosystém založen.

Tento režim je aditivní homomorfní kryptosystém; to znamená, že vzhledem k veřejnému klíči a šifrování ${ displaystyle m_ {1}}$ a ${ displaystyle m_ {2}}$, lze vypočítat šifrování ${ displaystyle m_ {1} + m_ {2}}$.

Algoritmus

Schéma funguje následovně:

Generování klíčů

1. Vyberte dvě velká prvočísla p a q náhodně a nezávisle na sobě tak, že ${ displaystyle gcd (pq, (p-1) (q-1)) = 1}$. Tato vlastnost je zajištěna, pokud mají obě prvočísla stejnou délku.^[1]
2. Vypočítat ${ displaystyle n = pq}$ a ${ displaystyle lambda = operatorname {lcm} (p-1, q-1)}$. lcm znamená nejméně společný násobek.
3. Vyberte náhodné celé číslo ${ displaystyle g}$ kde ${ displaystyle g in mathbb {Z} _ {n ^ {2}} ^ {*}}$
4. Zajistit ${ displaystyle n}$ rozdělí pořadí ${ displaystyle g}$ kontrolou existence následujících položek modulární multiplikativní inverzní: ${ displaystyle mu = (L (g ^ { lambda} { bmod {n}} ^ {2})) ^ {- 1} { bmod {n}}}$,

kde funkce ${ displaystyle L}$ je definován jako ${ displaystyle L (x) = { frac {x-1} {n}}}$ .

Všimněte si, že notace ${ displaystyle { frac {a} {b}}}$ neoznačuje modulární násobení ${ displaystyle a}$ krát modulární multiplikativní inverzní z ${ displaystyle b}$ ale spíše kvocient z ${ displaystyle a}$ děleno ${ displaystyle b}$, tj. největší celočíselná hodnota ${ displaystyle v geq 0}$ uspokojit vztah ${ displaystyle a geq vb}$.

• Veřejný (šifrovací) klíč je ${ displaystyle (n, g)}$.
• Soukromý (dešifrovací) klíč je ${ displaystyle ( lambda, mu).}$

Pokud použijete p, q ekvivalentní délky, bude třeba nastavit jednodušší variantu výše uvedených kroků generování klíčů ${ displaystyle g = n + 1, lambda = varphi (n),}$ a ${ displaystyle mu = varphi (n) ^ {- 1} { bmod {n}}}$, kde ${ displaystyle varphi (n) = (p-1) (q-1)}$ .^[1]

Šifrování

1. Nechat ${ displaystyle m}$ být zpráva, která má být zašifrována ${ displaystyle 0 leq m$
2. Vyberte náhodně ${ displaystyle r}$ kde ${ displaystyle 0$ a ${ displaystyle r in mathbb {Z} _ {n} ^ {*}}$ (tj. zajistit ${ displaystyle gcd (r, n) = 1}$)
3. Vypočítat šifrovací text jako: ${ displaystyle c = g ^ {m} cdot r ^ {n} { bmod {n}} ^ {2}}$

Dešifrování

1. Nechat ${ displaystyle c}$ být šifrovacím textem k dešifrování, kde ${ displaystyle c in mathbb {Z} _ {n ^ {2}} ^ {*}}$
2. Vypočítat holou zprávu jako: ${ displaystyle m = L (c ^ { lambda} { bmod {n}} ^ {2}) cdot mu { bmod {n}}}$

Jako originál papír poukazuje na to, že dešifrování je „v podstatě jedno exponenciální modulo ${ displaystyle n ^ {2}}$."

Homomorfní vlastnosti

Pozoruhodná vlastnost kryptosystému Paillier je jeho homomorfní vlastnosti spolu s jeho nedeterministickým šifrováním (viz Elektronické hlasování v Aplikacích pro použití). Protože je funkce šifrování aditivně homomorfní, lze popsat následující identity:

• Homomorfní sčítání holých textů

Produkt dvou ciphertexts bude dešifrovat na součet odpovídajících holých textů,

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

Produkt ciphertextu s otevřeným prostým textem ${ displaystyle g}$ dešifruje na součet odpovídajících prostých textů,

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

• Homomorfní násobení holých textů

Šifrovaný holý text zvýšený na sílu jiného holého textu bude dešifrovat na produkt dvou holých textů,

${ 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 }}. ,}$

Obecněji řečeno, zašifrovaný prostý text povýšený na konstantu k dešifruje na produkt prostého textu a konstanty,

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

Vzhledem k šifrování dvou zpráv podle Pailliera však není znám žádný způsob, jak vypočítat šifrování produktu těchto zpráv bez znalosti soukromého klíče.

Pozadí

Kryptosystém Paillier využívá skutečnost, že jisté diskrétní logaritmy lze snadno vypočítat.

Například tím, že binomická věta,

${ displaystyle (1 + n) ^ {x} = součet _ {k = 0} ^ {x} {x zvolit k} n ^ {k} = 1 + nx + {x zvolit 2} n ^ {2 } + { text {vyšší pravomoci}} n}$

To naznačuje, že:

${ displaystyle (1 + n) ^ {x} equiv 1 + nx { pmod {n ^ {2}}}}$

Proto pokud:

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

pak

${ displaystyle x equiv { frac {y-1} {n}} { pmod {n ^ {2}}}}$.

Tím pádem:

${ displaystyle L ((1 + n) ^ {x} { bmod {n}} ^ {2}) equiv x { pmod {n}}}$,

kde funkce ${ displaystyle L}$ je definován jako ${ displaystyle L (u) = { frac {u-1} {n}}}$ (podíl celočíselného dělení) a ${ displaystyle x in mathbb {Z} _ {n}}$.

Sémantická bezpečnost

Původní kryptosystém, jak je uvedeno výše, poskytuje sémantická bezpečnost proti útokům typu vybraný holý text (IND-CPA ). Schopnost úspěšně odlišit šifrovací text výzvy se v zásadě rovná schopnosti rozhodnout o složené reziduuity. Takzvaný předpoklad rozhodující složené reziduaity (DCRA) je považován za neřešitelný.

Kvůli výše uvedeným homomorfním vlastnostem však systém je tvárný, a proto si neužije nejvyšší úroveň sémantického zabezpečení, která chrání před adaptivními útoky zvoleného šifrovacího textu (IND-CCA2 ). V kryptografii se pojem tvárnosti obvykle nepovažuje za „výhodu“, ale za určitých aplikací, jako je zabezpečené elektronické hlasování a prahové kryptosystémy, tato vlastnost může být skutečně nezbytná.

Paillier a Pointcheval však dále navrhli vylepšený kryptosystém, který zahrnuje kombinovaný hash zpráv m s náhodným r. Podobně v záměru s Kryptosystém Cramer – Shoup, hašování brání útočníkovi, pouze je uvedeno C, od možnosti změny m smysluplným způsobem. Prostřednictvím této úpravy lze ukázat, že vylepšené schéma je IND-CCA2 zabezpečit v náhodný věštecký model.

Aplikace

Elektronické hlasování

Sémantická bezpečnost není jediným hlediskem. Existují situace, za nichž může být tvárnost žádoucí. Výše uvedené homomorfní vlastnosti lze využít zabezpečenými elektronickými hlasovacími systémy. Zvažte jednoduchý binární hlas („pro“ nebo „proti“). Nechat m voliči hlasovali buď pro 1 (pro) nebo 0 (proti). Každý volič si před hlasováním zašifruje svoji volbu. Volební úředník má produkt m šifrované hlasy a poté dešifruje výsledek a získá hodnotu n, což je součet všech hlasů. Volební úředník to pak ví n lidé hlasovali pro a m-n lidé hlasovali proti. Role náhodného r zajišťuje, že dva ekvivalentní hlasy budou šifrovány na stejnou hodnotu pouze se zanedbatelnou pravděpodobností, a tím zajistí soukromí voličů.

Elektronická hotovost

Další funkcí pojmenovanou v článku je pojemoslepující. Jedná se o schopnost změnit jeden šifrový text na jiný, aniž by se změnil obsah jeho dešifrování. To má uplatnění na vývoj ecash, úsilí původně vedené David Chaum. Představte si, že platíte za položku online, aniž byste museli prodejce znát číslo vaší kreditní karty, a tedy vaši identitu. Cílem v elektronické hotovosti i v elektronickém hlasování je zajistit, aby e-mince (rovněž e-hlasování) byly platné, a zároveň nezveřejňovat totožnost osoby, s níž je aktuálně spojena.

Viz také

• The Naccache – Sternův kryptosystém a Kryptosystém Okamoto – Uchiyama jsou historickými předchůdci Pailliera.
• The Kryptosystém Damgård – Jurik je zobecněním Pailliera.

Reference