Techniky homomorfního šifrování a jejich praktické využití

Rok / Year: 2014

Svazek / Volume: 16

Číslo / Number: 2

Techniky homomorfního šifrování a jejich praktické využití Techniques of homomorphic encryption and their practical usage Petr Dzurenda, Jan Hajný [email protected], [email protected] Fakulta elektrotechniky a komunikačních technologií VUT v Brně

Abstrakt: Článek se zabývá analýzou a přehledem současného stavu kryptografických primitiv umožňujících homomorfní šifrování. Jsou zde představeny vlastnosti homomorfního šifrování a možnosti docílení plně homomorfního šifrování. Dále jsou prezentovány možnosti jeho praktického využití. V závěru jsou pak uvedeny výsledky měření implementovaného schématu podporujícího plně homomorfní šifrování a jeho srovnání s existujícími implementacemi.

Abstract: The paper deals with the analysis and overview of the current state of cryptographic primitives which allows homomorphic encryption. The properties of homomorphic encryption and their possibility of achieving a fully homomorphic encryption are presented in the paper. Next, some practical possibilities of usage are presented. The results of measurements of the implemented scheme supports fully homomorphic encryption and its comparison with existing implementations are presented in end of the article.

VOL.16, NO.2, APRIL 2014

Techniky homomorfního šifrování a jejich praktické využití Petr Dzurenda, Jan Hajný Fakulta elektrotechniky a komunikačních technologií VUT v Brně Email: [email protected], [email protected]

Abstrakt – Článek se zabývá analýzou a přehledem současného stavu kryptografických primitiv umožňujících homomorfní šifrování. Jsou zde představeny vlastnosti homomorfního šifrování a možnosti docílení plně homomorfního šifrování. Dále jsou prezentovány možnosti jeho praktického využití. V závěru jsou pak uvedeny výsledky měření implementovaného schématu podporujícího plně homomorfní šifrování a jeho srovnání s existujícími implementacemi.

1

existují techniky pro zajištění anonymní komunikace na síťové vrstvě modelu TCP-IP, tzn. nedohledatelnost odesilatele či příjemce paketů na základě IP adresy. Touto technikou může být např. TOR (The Onion Routing) [1]. Dále pak existují techniky pro anonymní přístup k poskytovaným službám, které jsou realizovatelné skupinovými podpisy či dokonalejšími atributovými systémy, které umožňují uživateli prokázat vlastnictví určitého atributu, přičemž jeho identita zůstává utajena. Mezi existující schémata patří např. U-Prove společnosti Microsoft [2], Idemix společnosti IBM [3] nebo HM12 [4]. Problém však nastává při poskytování citlivých dat serveru, která musí být určitým způsobem zpracována.

Úvod

Homomorfní šifrování je revoluční technikou v oblasti šifrování dat. Stejně jako klasické šifrování umožňuje utajit potřebnou důvěrnou informaci. Oproti klasickému šifrování, však umožňuje pracovat nad těmito šifrovanými daty, aniž by bylo nutné tato data předem dešifrovat. Díky této vlastnosti je možné provést libovolnou operaci nad šifrovanými daty, která je ekvivalentní k operaci nad daty nešifrovanými. Výsledkem operace je kryptogram, po jehož dešifrování je získána stejná informace, jako kdyby se pracovalo přímo se samotným otevřeným textem, viz obrázek 1.

U klasického šifrování se vychází z toho, že jedna strana důvěřuje druhé, tj. uživatel důvěřuje poskytovateli. Poskytovatel si data může dešifrovat a dále s nimi pracovat. Homomorfní šifrování pak nachází uplatnění v případě, že uživatel nedůvěřuje nikomu ani poskytovateli služby např. cloudu. Na druhou stranu se požaduje, aby server data zpracoval. Příkladem může být umístění zašifrovaných dat na nedůvěryhodný server. Vlastník dat pak zasílá na server zašifrované dotazy, na jejichž základě mu server pošle příslušná data (ty jsou však zašifrována), server nezná obsah dotazu tj. co bylo požadováno a nezná ani obsah dat, která poskytl. Jakmile by vlastník tyto data obdržel, mohl by je dešifrovat a získat tím samotná data v otevřené podobě. Praktické uplatnění si lze představit např. u databázových systémů, u úložišť dat jako je Dropbox, Google disk apod. či samotné vyhledávaní v internetových vyhledávačích, např. Google.

Obrázek 1: Princip homomorfního šifrování

Další možností využití homomorfního šifrování v cloudových službách je potřeba zpracování určitých citlivých údajů, např. poskytnutí zdravotních záznamů pacientů k statistickému vyhodnocování třetí straně, přičemž tato strana nesmí mít přístup k záznamům pacientů a nesmí mít ani povědomí o výsledku vyhodnocení. Dále by bylo pomocí homomorfního šifrování možné detekovat např. spamy v zašifrovaných emailech a mnohé další.

Tento fakt přináší mnohé výhody. Zvláště je-li možné provádět jakékoli operace nad šifrovanými daty. Praktické uplatnění homomorfního šifrování se předpokládá převážně v případech, kdy jsou data uložena a zpracovávána mimo infrastrukturu vlastníka. V současné době jsou typickým příkladem cloudové služby, kde se díky této technice může zajistit vyšší míra ochrany soukromí uživatelů. Nyní již

V současné době existují pouze dva možné způsoby uložení dat na serveru, viz tabulka 1. Data jsou šifrována buď na straně klienta, což zabraňuje práci s daty na straně serveru, jelikož k nim server nemá přístup (nevlastní dešifrovací klíč), a nebo jsou data šifrována na straně serveru, což umožňuje práci s daty avšak za cenu toho, že server získá přístup k těmto datům (vlastní šifrovací i dešifrovací klíč). Homomorfní šifrování přináší třetí variantu uložení

54


dat na serveru, jak je patrné z tabulky 1. Data jsou šifrována na straně klienta, avšak server je s těmito daty schopen pracovat.

implementace schématu [8], která je podobná práci [11] avšak autoři docílili rychlejšího výpočtu soukromého klíče, a také se jim povedlo snížit dešifrovací polynom na stupeň patnáct. Roku 2011 byly publikovány práce [13, 14] popisující další schéma FHE, které mají vůči [8] odlišný přístup k regulaci chyb (”noise”), tzv. metoda učení s chybami LWE (Learning With Errors). Práce [15] se zaměřuje na snížení velikosti veřejného klíče v návrhu [10]. Pro parametry vysoké úrovně zabezpečení (bezpečnostní parametr λ = 72) docílili velikosti veřejného klíče 10,3 MB oproti 2,3 GB u návrhu [12] a 802 MB u návrhu [16]. V práci [17] je představena technika pro vytvoření schématu FHE bez techniky bootstrapping. Práce [18], se zaměřuje na implementaci schématu [17] s mnoha optimalizacemi pro vyšší rychlosti. Vytvořená softwarová knihovna je psána v jazyce C++.

Tabulka 1: Možnosti uložení šifrovaných dat na serveru

šifrování na straně klienta šifrování na straně serveru homomorfní šifrování

2

Šifruje

Server má přístup k datům

klient

NE

Server může pracovat se šifrovanými daty NE

server

ANO

ANO

klient

NE

ANO

3

Vlastnosti homomorfního šifrování

Schémata podporující homomorfní šifrování se rozlišují podle počtu operací, které jsou schopny provádět nad šifrovanými daty. Obecně se schémata rozdělují na částečně homomorfní PHE (Partially Homomorphic Encryption), poněkud homomorfní SWHE (SomeWhat Homomorphic Encryption) a plně homomorfní FHE (Fully Homomorphic Encryption). PHE umožňuje provádět nad šifrovanými daty pouze některé operace např. sčítání (Addition Homomorphic) nebo násobení (Multiplication Homomorphic). Dokáže-li schéma provádět obě operace nad šifrovanými daty, jedná se o SWHE nebo FHE. Všechny současné návrhy jsou v základu SWHE, tzn. umožňují provádět operace sčítání a násobení nad šifrovanými daty, avšak pouze do určité hloubky. Pro přechod z návrhu SWHE do FHE využívají některé ze známých technik popsaných v kapitole 6.1. V principu homomorfní šifrování umožňuje zpracovat šifrovaná data, přičemž výsledkem zpracování je opět kryptogram, po jehož dešifrování, jsou získány stejné výsledky, jako kdyby se pracovalo se samotnými nešifrovanými daty. Každé homomorfní schéma se skládá ze čtyř následujících algoritmů:

Současný stav

S první myšlenkou homomorfismu přišli páni Rivest, Adleman a Dertouzos roku 1978 [5], krátce potom, co představili Rivest, Adleman a Shamir své kryptografické schéma RSA [6]. Právě toto schéma je totiž částečně homomorfní, jelikož umožňuje provádět operaci násobení nad šifrovanými daty, viz kapitola 4. První schéma přibližující se nejvíce vlastnostem plně homomorfnímu šifrování FHE (Fully Homomorphic Encryption) je [7]. Ve schématu je možné provádět libovolný počet operací sčítání avšak pouze maximálně jednu operaci násobení. První FHE představil Craig Gentry ve své dizertační práci [8] a článku [9] roku 2009. Základní návrh je označován jako SWHE (SomeWhat Homomorphic Encryption), jelikož je možné na šifrovaných datech provést pouze určité množství operací (lze provádět operace pouze do určité hloubky). Při každé operaci dochází totiž k vzniku drobné numerické chyby (označované jako ”noise”), způsobující drobnou odchylku šifrovaných dat od svých ideálních hodnot. S každou operací se tato chyba zvětšuje (zvláště u násobení). Dosáhne-li chyba určité míry, nelze kryptogram již dešifrovat. Autor tento nedostatek řeší zavedením tzv. bootstrappingu viz kapitola 6.1. Touto technikou vytváří ze schématu SWHE schéma FHE. Dalším schématem FHE je [10]. Práce vychází z [8] pro vytvoření FHE ze SWHE. Oproti [8], který byl postaven na teorii celočíselných bran (ideálních mříží), je zde postaven problém na teorii čísel, konkrétně problém přibližného GCD (approximate GCD) viz kapitola 5. Oproti efektivitě [8] se schéma příliš neliší, jedná se spíše o koncepční zjednodušení. V práci [11] byla představena optimalizace schématu [8], která představuje novou metodu generování klíčů a šifrování. Tím je docíleno snížení velikosti veřejného klíče a kryptogramu, ale stále není vhodné k praktickému použití. V článku [12] byla představena funkční

1. KeyGen (λ) - algoritmus vytvářející klíče pk (public key) a sk (secret key). Vstupním parametrem je bezpečnostní parametr λ. 2. Encrypt(pk,m) - algoritmus šifrování, vstupním parametrem je pk a otevřený text m = hm1 , . . . , mi i, výstupem je šifrovaný text c = hc1 , . . . , ci i. 3. Evaluate(pk,O,c) - algoritmus operací nad šifrovaným textem. Vstupem je pk, c a obvod O, který definuje operace nad šifrovaným textem. Tento obvod je tvořen sítí bran, které reprezentují operace sčítání a násobení. Výstupem je šifrovaný text ψ. 4. Decrypt(sk,c) - algoritmus dešifrování. Vstupem je soukromý klíč sk a šifrovaný text c nebo ψ. Výstupem je pak otevřený text hm1 , . . . , mi i nebo

55


O hm1 , . . . , mi i. Aby bylo schéma opravdu plně homomorfní, musí platit, ψ ←− Evaluate(pk,O,c), O hm1 , . . . , mi i = Decrypt(sk,ψ).

4

dělitele, při zavedení drobné chyby (approximate GCD). Kryptosystém obsahuje soukromý klíč p, který je dán velkým lichým číslem. Zpráva m je rozdělena na t bitů m = hm1 , m2 , . . . , mt i. Šifruje se bit po bitu. Postup je následující:

Částečně homomorfní schémata

Jsou kryptografická schémata označovaná jako PHE, která mají homomorfní vlastnosti, avšak nesplňují požadavky plně homomorfního schématu FHE. Jsou schopné provádět pouze některé operace nad šifrovanými daty. Typickým zástupcem je kryptografické schéma RSA, které je multiplikativně homomorfní, tzn. že je možné nad šifrovými daty provádět pouze operaci násobení, jelikož platí rovnice (1).

1. Zvolí se náhodné velké liché číslo p (to bude klíč). 2. Zvolí se náhodné velké číslo q. 3. Zvolí se náhodné malé číslo r, které bude reprezentovat zavedenou chybu ”noise”. 4. Šifrování je pak ci = q · p + 2 · r + mi , kde mi je bit zprávy pro i = 1, 2, . . . , t.

c1 = E(pk, m1 ) = me1 mod n, c2 = E(pk, m2 ) = me2 mod n, c12 = c1 · c2 = me1 mod n · me2 mod n

(1)

5. Dešifrování je pak mi = (ci mod p) mod 2.

= (me1 · me2 )mod n = (m1 · m2 )e mod n,

V bodě 3 se úmyslně zavádí chybovost označovaná jako ”noise”. Je to dáno kvůli bezpečnosti systému. Za předpokladu, že by tato chyba nebyla zavedena, bylo by z dvou zpráv možné odvodit soukromý klíč, nalezením největšího společného dělitele GCD, některou ze známých technik (např. Eukleidův algoritmus), viz rovnice (4).

kde c je kryptogram, m je zpráva a pk je veřejný klíč (e - exponent, n-modulus). Dalším PHE schématem je např. multiplikativně homomorfní schéma ElGamal, pro které platí rovnice (2). c1 = E(pk, m1 ) = (g r1 , m1 · hr1 ), c2 = E(pk, m2 ) = (g r2 , m2 · hr2 ), c12 = c1 · c2 = (g r1 , m1 · hr1 ) · (g r2 , m2 · hr2 )

m1 = 0 : c1 = q1 · p + 0

(2)

m2 = 0 : c2 = q2 · p + 0

= (g r1 +r2 , m1 · m2 · hr1 +r2 ),

(4)

p = GCD(q1 · p, q2 · p)

kde pk je veřejný klíč (G, p, g, h), h je pak dáno jako g x , kde x je soukromý klíč. Znak r pak udává náhodné číslo pro které platí r ∈ 0, 1, . . . , q − 1. Pro obě výše uvedená schémata tedy platí, že součinem dvou kryptogramů je kryptogram, jehož dešifrováním se získá stejný výsledek, jako kdyby se vynásobila původní data. Zástupcem aditivního homomorfního schématu (umožňuje provádět nad šifrovanými daty pouze operaci sčítání) je kryptosystém Pailler, pro který platí rovnice (3).

Schéma je SWHE, jelikož umožňuje provádět operace sčítání i násobení nad šifrovanými daty. Nejedná se však o plně homomorfní šifrování, jelikož počet operací nad kryptogramy je omezený. Je to dáno právě zavedením chyby ”noise”, která se s každou operací zvětšuje, čímž degraduje kryptogram. Je-li chyba větší než p/2, dochází k chybě při dešifrování. Schéma je aditivně homomorfní, což je patrné z rovnice (5). Součet dvou kryptogramů je ekvivalentní k operaci XOR příslušných šifrovaných bitů:

c1 = E(pk, m1 ) = r1n · g m1 , c2 = E(pk, m2 ) = r2n · g m2 , c12 = c1 · c2 = r1n · g m1 · r2n · g m2

c1 = q1 · p + 2 · r1 + m1 ,

(3)

c2 = q2 · p + 2 · r2 + m2 ,

= r1n · r2n · g m1 +m2 ,

c12 = c1 + c2 = q1 · p + 2 · r1 + m1 +

kde pk je (n, g), kde n = p · q (p, q jsou velká prvočísla) a g je náhodné číslo pro které platí g ∈ Zn∗2 . Součinem dvou kryptogramů, je kryptogram, jehož dešifrováním je získán stejný výsledek, jako kdyby se sečetla samotná nešifrovaná data.

5

+ q2 · p + 2 · r2 + m2

(5)

= p · (q1 + q2 ) + 2 · (r1 + r2 ) + (m1 + m2 ) , m12 = ((c1 + c2 ) mod p) mod 2 = m1 XOR m2 . Z výše uvedeného je patrné, že chyba ”noise”se při součtu zvětšuje dvojnásobně. Mnohem horší je situace při násobení, kdy se chyba zvětšuje kvadraticky, což je patrné z rovnice (6). Zároveň rovnice představuje důkaz o multiplikativnosti schématu a spolu s rovnicí (5) potvrzuje splnění základní podmínky pro vytvoření SWHE schématu. Součin

Poněkud homomorfní šifrování

Schéma podporující SWHE umožňuje provádět obě operace tj. sčítání i násobení. Příkladem může být jednoduché schéma [10], které vytváří symetrický kryptosystém, založený na problému nalezení největšího společného

56


dvou kryptogramů je ekvivalentní k operaci AND příslušných šifrovaných bitů:

6.1

Jedná se o techniku představenou v [8, 9]. Prováděním operací nad šifrovanými daty roste chybovost vzniklých kryptogramů. Dosáhne-li určité velikosti, dojde k nemožnosti jejich dešifrování. Tento problém lze řešit dešifrováním kryptogramu a jeho opětovném zašifrování. Tím dojde k snížení chyby ”noise”na původní malou hodnotu. To by však znamenalo do procesu operace nad šifrovanými daty zahrnout také soukromý klíč. V praxi by to znamenalo poskytnout druhé straně soukromý klíče, případně by musela protistrana vždy zasílat kryptogramy s velkou chybou na přešifrování uživateli. Ani jedna z těchto dvou úvah však není přípustná. Z tohoto důvodu byla představena technika bootstrappingu [8], která je založena na stejném principu ale data se dešifrují homomorfně. Využívá se algoritmu Evaluate(pk,O,c), kde obvod O tvoří dešifrovací obvod. Tento obvod lze tedy chápat jako rešifrovací. Na obrázku 2 lze vidět rozdíl mezi klasickým a homomorfním dešifrováním. Oproti klasickému dešifrování, kde do obvodu vstupuje soukromý klíč, v homomorfním dešifrování se používá při dešifrování (rešifrování) veřejný klíč, do kterého jsou vloženy určité informace o soukromém klíči. Výstupem obvodu tedy není dešifrovaný otevřený text, ale opět kryptogram avšak s malou chybou ”noise”.

c12 = c1 · c2 = (q1 · p + 2 · r1 + m1 )· · (q2 · p + 2 · r2 + m2 ) = p2 q1 q2 + 2pq1 r2 + pq1 m2 + 2pq2 r1 + 4r1 r2 + + 2r1 m2 + pq2 m1 + 2r2 m1 + m1 m2 = pq1 (pq2 + 2r2 + m2 ) + pq2 (2r1 + m1 )+ + 2(2r1 r2 + r1 m2 + r2 m1 ) + m1 m2

Bootstrapping

(6)

= p(q2 c2 + q2 (2r1 + m1 ))+ + 2(2r1 r2 + r1 m2 + r2 m1 ) + m1 m2 = p(q2 c2 + q2 (c1 − pq1 ))+ + 2(2r1 r2 + r1 m2 + r2 m1 ) + m1 m2 = m1 AN D m2 . V případě kryptosystému s veřejným klíčem je konstrukce schématu obdobná: 1. Zvolí se náhodné velké liché číslo p (to bude soukromý klíč ). 2. Spočte se τ celočíselných prvků, reprezentujících veřejný klíč. Tyto prvky se spočtou šifrováním bitu 0, tj. xi = qi · p + ri , z těchto prvků se nalezne největší, označí se jako x0 . Nesmí platit, že x0 je liché a x0 mod p je sudé. Tím jsou získány klíče sk = p a pk = hx0 , ..., xτ i. 3. Šifrování se provádí tak, že se vybere náhodná podmnožina S ⊆ pk P tj. S ⊆ (x0 , x1 , . . . , xτ ) a provede se jejich součet i∈S xi . 4. Spočte se kryptogramP ci = (mi + 2 · r + 2 · i∈S xi ) mod x0 . 5. Dešifrování je pak mi = (ci mod p) mod 2.

6

Plně homomorfní šifrování

Současná schémata jsou pouze SWHE, kvůli nárůstu chyby ”noise”během provádění operací nad šifrovanými daty. Tudíž je možné provést jen určité množství operací a nelze tedy vytvářet jakkoli složitou funkci. Techniky díky nímž je možné ”noise”snížit na původní ”malou”hodnotu a tím tedy provádět neomezený počet operací nad šifrovanými daty jsou popsány níže. Díky nim je dosaženo plně homomorfního šifrování. Pro realizaci jakékoli složité funkce postačuje, je-li možné provést nad šifrovanými daty operace XOR a AND. Pomocí těchto dvou operací je možné vytvořit jakoukoli jinou složitou operaci viz De Morganovy zákony. Tyto operace se pak označují jako obvod O. Obvod je tvořen libovolným počtem bran, které zastupují celočíselné operace sčítání a násobení v případě schématu [10].

Obrázek 2: Techniky dešifrování (snížení chyby) Pro zajištění bootstapingu lze použít některou z existujících technik jako je Squash [8], která používá pro rešifrování klasický dešifrovací obvod, s tím rozdílem, že místo soukromého klíče je použit veřejný klíč, do kterého jsou přidány informace o soukromém klíči. Technika Chimeric je představena v [19]. Tato technika také zavádí informace o soukromém klíči do veřejného klíče avšak místo klasického dešifrovacího obvodu používá speciální konstrukci dešifrovacího obvodu s omezenou hloubkou. Konkrétně je hloubka obvodu rovna třem.

57


6.2

Vytvoření FHE ze SWHE

problém postaven do oblasti teorie čísel, konkrétně problém určení největšího společného dělitele při zavedení drobné odchylky tzv. problém “approximate-GCD”. Schémata jako [13, 14] jsou pak postavena na problému LWE (Learning with Errors) [21].

Tato podkapitola se zaměřuje na popis vytvoření implementace plně homomorfního šifrování (FHE), přičemž se vychází ze schématu DGHV10 [10]. Princip je obdobný jako při tvorbě schématu SWHE avšak přibývají další algoritmy (Expand a Recrypt). Pro tvorbu bootstrappingu se využívá techniky Squash.

8

1. KeyGen(λ) - klíče se generují stejným způsobem jako předešle tj. platí sk = p a pk = hx0 , ..., xτ i. Dále se provede výpočet xp ← b2κ /pe, zvolí se náhodný vektor o délce Θ bitů s Hammingovou vzdáleností rovno θ. Tímto je získán nový soukromý klíč sk2 = ~s = hs1 , ..., sΘ i. Veřejný klíč se konstruuje tak, že se spočtou náhodná celá čísla o délce 2κ+1 bitů, pro která platí P ui ∈ Z pro i = 1,..., Θ. Dále musí platit, že i∈S ui = xp mod 2κ+1 pro S = {i : si = 1). Z těchto čísel se pak vypočte vektor ~y = hy1 , ..., yΘ i, kde platí yi = ui /2κ pro i = 1, ..., Θ. Veřejný klíč má pak tvar pk2 = (pk, ~y ).

V rámci analýzy současného stavu homomorfního šifrování byla implementována původní varianta FHE schématu [10] v jazyce Java a následně byla provedena měření pro čtyři bezpečnostní úrovně (velmi malá, malá, střední, vysoká) pro stejné hodnoty parametrů jako v [22]. Pro měření byl využit osobní počítač (Intel(R) Core(TM)2 Duo CPU) T6600 2,20 GHz, 4 GB RAM). Tabulka 2 obsahuje parametry systému, pro jednotlivé bezpečnostní úrovně, kde λ je bezpečnostní parametr, ρ je velikost chyby, η velikost soukromého klíče, γ je velikost jednoho čísla veřejného klíče, Θ velikost vektoru soukromého klíče (FHE). Všechny parametry jsou v bitech při velikosti otevřeného textu l = 10, Hammingově vzdálenosti θ = 15, a počtu čísel ve veřejném klíči τ = 2. V tabulce 3 jsou pak konkrétní doby trvání jednotlivých algoritmů schématu podporující plně homomorfní šifrování.

2. Encrypt(pk2 ,m) - stejně jako předešle, se zvolí podmnožina S ⊆ pk tj. S ⊆ hx0 , x1P , . . . , xτ i a spočte se kryptogram ci = (mi + 2 · r + 2 · i∈S xi ) mod x0 . Pro každý kryptogram je unikátní r a S. 3. Evaluate(pk2 ,O,c) - algoritmus operací nad šifrovaným textem. Složen z operací:

Tabulka 2: Parametry systému Bezpečnostní úroveň Velmi malá Malá Střední Velká

Add(pk2 ,c1 ,c2 ) - součet c12 = c1 + c2 (mod x0 ). Ekvivalentní operace k operaci XOR nad otevřeným textem. Mul(pk2 ,c1 ,c2 ) - součin c12 = c1 · c2 (mod x0 ). Ekvivalentní operace k operaci AND nad otevřeným textem. 4. Expand(pk2 ,c) - rozšíření kryptogramu. Spočte se zi ← c · yi (mod 2) pro i = 1, ..., Θ. Výstupem jsou pak tedy vektory rozšíření kryptogramů ~z = hz1 , ..., zΘ i (samostatně pro každý kryptogram).

λ

ρ

η

γ · 10−6

Θ

42 52 62 72

26 41 56 71

988 1558 2128 2698

0,29 1,6 8,5 39

150 555 2070 8713

Tabulka 3: Časová náročnost algoritmů v implementovaném schématu DGHV10 [10]

5. Recrypt(pk2P ,c,z) - pro rešifrování platí, že ψj,i = cj − b i yi · zj,i e (mod 2), pro i = 1, ..., Θ a pro j = 1, ..., |c|.

Bezpečnostní úroveň Velmi malá Malá Střední Velká

6. Decrypt(sk2 ,c,z) P - pro dešifrování platí, že mj,i = cj − b i si · zj,i e (mod 2), pro i = 1, ..., Θ a pro j = 1, ..., |c|.

7

Výpočetní složitost schématu

Generování klíčů 0,14s 4,37s 75,84s 45,25min

Šifrování 0,03s 0,04s 0,14s 0,70s

Rešifrování 0,27s 5,41s 104,31s 30,25min

Dešifrování 0,01s 0,02s 0,09s 0,42s

Bezpečnost jednotlivých schémat Graf na obrázku 3 zobrazuje srovnání vlastní implementace schématu DGHV10 [10] s implementacemi zaměřujícími se na redukci velikosti veřejného klíče. Z grafu je patrné, že velikost veřejného klíče se pomocí různých redukčních technik snižuje. Nicméně i v nejlepším případě dosahuje velikost min. 10,3 MB pro vysokou bezpečnostní úroveň. Srovnání současných nejpoužívanějších kryptografických schémat symetrické kryptografie (bloková šifra AES a proudová šifra RC4) a asymetrické kryptografie

Bezpečnost současných schémat umožňující SWHE či FHE je postavena na současných problémech řešitelnosti úloh. V případě [8] je bezpečnost založena na problému nalezení nejbližšího vektoru CVP (Closest Vector Problem) v ideální mříži [20]. Výhodou schémat založených na problému mříží, je jejich odolnost vůči kvantovým útokům realizovatelných kvantovými počítači. Tyto útoky jsou do budoucna velkým problémem pro některé asymetrické kryptosystémy, jako je např. RSA. V případě návrhu [10] je

58


(RSA) s implementací schématu DGHV10 [10] reprezentující FHE, zachycuje graf na obrázku 4. Z grafu lze vyčíst dosažené výsledky z pohledu rychlosti šifrování dat jednotlivých schémat. Rychlosti dešifrování byly srovnatelné s rychlostmi šifrování. Kromě schématu RSA, což je dáno různou velikostí klíčů (exponentů). U šifrování se používá šifrovací klíč pk o délce 5 bitů (respektive exponent o délce 5 bitů), zatímco u dešifrování se používá dešifrovací klíč sk o délce 1024 (respektive exponent této délky). Rychlost dešifrování u schématu RSA byla přibližně 382,8kb/s.

úrovni schématu, zvláště pak doba generování klíčů a doba rešifrování. Další nevýhodou schémat je velikost veřejného klíče, která je oproti klasickým kryptografickým schématům také neúměrná. I přes optimalizace schémat se velikost veřejného klíče pohybuje okolo 10 MB u schématu CNT12 [15]. Přestože homomorfní šifrování přináší velké možnosti využití, zvláště v oblasti cloudových služeb, neexistuje v současnosti schéma pro praktické použití. Graf na obrázku 4 ukazuje rychlosti šifrování dat nejpoužívanějších kryptografických schémat symetrických (proudová šifra RC4 a bloková šifra AES-128) a asymetrických (DGHV10 a RSA). Pro šifrování dat na straně serveru by bylo ideální kdyby FHE dosahovalo obdobných rychlostí šifrování jako proudové šifry, případně tedy blokové šifry, které se v současnosti využívají právě pro šifrování dat na straně serveru. Konkrétně tedy bloková šifra AES128 v případě Google Cloudu. V grafu na obrázku 4 lze vyčíst, že během 1s je implementované schéma DGHV10 schopné zašifrovat pouze 24 b oproti AES-128, které za stejnou dobu zašifruje 43 MB.

Poděkování Tato práce byla podpořena projektem “Výzkum kryptografických primitiv pro bezpečnou autentizaci a ochranu digitální identity” č. 14-25298P Grantové agentury České republiky.

Obrázek 3: Velikost veřejného klíče v závislosti na bezpečnostní úrovni schémat existujících implementací DGHV10 (DGHV10 [10], CLT13 [22], CMNT11 [16], CNT12 [15])

Literatura [1] Dingledine, R.: Tor Project: Anonymity Online. 2009. URL https://www.torproject.org/ [2] Paquin, C.; Zaverucha, G.: U-prove cryptographic specification v1. 1. Technická zpráva, Microsoft Technical Report, http://connect. microsoft. com/site1188, 2011. [3] Camenisch, J.; aj.: Specification of the identity mixer cryptographic library. Technická zpráva, Tech. rep, 2010. [4] Hajny, J.; Malina, L.: Unlinkable Attribute-Based Credentials with Practical Revocation on SmartCards. In Smart card research and advanced applications, Springer, 2013, s. 62–76.

Obrázek 4: Porovnání současných kryptografických schémat vzhledem k jejich rychlosti šifrování dat. Pro měření byl využit osobní počítač (Intel(R) Core(TM)2 Duo CPU) T6600 2,20 GHz, 4 GB RAM). Softwarová implementace v jazyce Java.

9

[5] Rivest, R. L.; Adleman, L.; Dertouzos, M. L.: On data banks and privacy homomorphisms. Foundations of secure computation, ročník 4, č. 11, 1978: s. 169–180.

Závěr

[6] Rivest, R. L.; Shamir, A.; Adleman, L.: A Method for Obtaining Digital Signatures and Public-key Cryptosystems. Commun. ACM, ročník 21, č. 2, Únor 1978: s. 120–126, ISSN 0001-0782, doi: 10.1145/359340.359342. URL http://doi.acm.org/10.1145/359340. 359342

V článku bylo představeno homomorfní šifrování, současný stav existujících schémat se zaměřením na schémata umožňující FHE a princip jejich fungování. Dále byla provedena implementace původní varianty schématu DGHV10 [10]. Z výsledků měření je patrné, že čas zpracování dat roste neúměrně v závislosti na bezpečnostní

59


[7] Boneh, D.; Goh, E.-J.; Nissim, K.: Evaluating 2-DNF Formulas on Ciphertexts. In Theory of cryptography, Springer, 2005, s. 325–341.

[15] Coron, J.-S.; Naccache, D.; Tibouchi, M.: Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers. In Advances in cryptology - EUROCRYPT 2012 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012, Springer, 2012, s. 446–464.

[8] Gentry, C.: A fully homomorphic encryption scheme. Dizertační práce, Stanford University, 2009. [9] Gentry, C.: Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st annual ACM symposium on Symposium on theory of computing STOC ’09, ACM Press, 2009, s. 169–178.

[16] Coron, J.-S.; Mandal, A.; Naccache, D.; aj.: Fully Homomorphic Encryption over the Integers with Shorter Public Keys. In Advances in cryptology - Crypto 2011, Springer, 2011, s. 487–504.

[10] Dijk, M.; Gentry, C.; Halevi, S.; aj.: Fully Homomorphic Encryption over the Integers. In Advances in cryptology - EUROCRYPT 2010 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30 - June 3, 2010, Springer, 2010, s. 24–43.

[17] Brakerski, Z.; Gentry, C.; Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference on - ITCS ’12, ACM Press, 2012, s. 309–325.

[11] Smart, N. P.; Vercauteren, F.: Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes. In Public key cryptography - PKC 2010 13th International Conference on Practice and Theory of Public-Key Cryptography, Paris, France, May 26-28, 2010, SpringerLink [host], 2010, s. 420–443.

[18] Halevi, S.; Shoup, V.: Design and Implementation of a Homomorphic-Encryption Library. 2012. [19] Gentry, C.; Halevi, S.: Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, IEEE, 2011, s. 107–109.

[12] Gentry, C.; Halevi, S.: Implementing Gentry’s FullyHomomorphic Encryption Scheme. In Advances in Cryptology - EUROCRYPT 2011 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings, Springer Berlin Heidelberg, 2011, s. 129–148.

[20] Micciancio, D.; Regev, O.: Lattice-based Cryptography. In Post-Quantum Cryptography, Springer Berlin Heidelberg, 2009, s. 147–191. [21] Regev, O.: The Learning with Errors Problem (Invited Survey). In Regesta imperii, Böhlau Verlag, 2008, s. 191–204.

[13] Brakerski, Z.; Vaikuntanathan, V.: Efficient Fully Homomorphic Encryption from (Standard) LWE. In 2011 ieee 52nd annual ieee symposium on foundations of computer science, Ieee Press Books, 2011, s. 97–106.

[22] Cheon, J. H.; Coron, J.-S.; Kim, J.; aj.: Batch Fully Homomorphic Encryption over the Integers. In Advances in cryptology – EUROCRYPT 2013 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013, proceedings, Springer, 2013, str. 315.

[14] Brakerski, Z.; Vaikuntanathan, V.: Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. In Advances in cryptology - Crypto 2011, Springer, 2011, s. 505–524.

60

Techniky homomorfního šifrování a jejich praktické využití

Recommend Documents