Homomorfní šifrování

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. března 2015; kontroly vyžadují 44 úprav .

Homomorfní šifrování  je forma šifrování , která vám umožňuje provádět určité matematické operace se šifrovaným textem a získat zašifrovaný výsledek, který odpovídá výsledku operací prováděných s prostým textem . Například jedna osoba mohla přidat dvě zašifrovaná čísla, aniž by znala dešifrovaná čísla, a další osoba by pak mohla dešifrovat zašifrovaný součet – získat dešifrovanou částku, aniž by měla dešifrovaná čísla. Homomorfní šifrování by umožnilo poskytovat různé služby bez poskytování veřejných uživatelských dat pro každou službu.

Existují kryptosystémy částečně homomorfní a plně homomorfní. Částečně homomorfní kryptosystém umožňuje provádět pouze jednu z operací – buď sčítání nebo násobení . Plně homomorfní kryptosystém podporuje obě operace, to znamená, že splňuje vlastnosti homomorfismu s ohledem na násobení i sčítání.

Historie

Koncept „homomorfního šifrování“ byl poprvé vytvořen [1] v roce 1978 Ronaldem Rivestem , Leonardem Adlemanem a Michaelem Dertouzosem  , autory algoritmu RSA rok po vývoji algoritmu. Navrhli možnost provádět libovolné operace se zašifrovanými daty bez jejich dešifrování.

Pokusy o vytvoření zcela homomorfního kryptosystému tehdy nebyly úspěšné. Například v roce 1982 Shafi Goldwasser a Silvio Micali navrhli šifrovací systém, který je homomorfní při násobení a je schopen šifrovat pouze jeden bit. Další homomorfní kryptosystém s ohledem na násobení byl navržen v roce 1999 Pascalem Peyetem .

V roce 2005 Dan Bone , Yu Jin Guo a Kobi Nissim navrhli [2] kryptosystém založený na použití bilineárního párování na eliptických křivkách , umožňující neomezený počet operací sčítání a jednu operaci násobení.

Problém vytvoření kryptosystému, který je homomorfní s ohledem na operace sčítání i násobení, zůstal nevyřešen již více než 30 let.

V roce 2009 Craig Gentry , postgraduální student na Stanfordské univerzitě a stážista v IBM , teoreticky zdůvodnil základní možnost vytvoření zcela homomorfního šifrovacího kryptosystému a navrhl jeden takový systém . Navržený systém lze použít k zajištění důvěrnosti dat během jakéhokoli zpracování dat v nedůvěryhodných prostředích, například v cloudu nebo distribuovaných výpočtech.

Brzy se objevily práce navrhující modifikace gentryho kryptosystému zlepšující výkon .

Kryptografové pracují na alternativních způsobech, jak vybudovat plně homomorfní kryptosystémy, jako je použití symetrického šifrování místo šifrování veřejným klíčem, používání polynomů v jedné nebo více proměnných, používání maticových polynomů.

Celkový pohled na homomorfní šifrování

Homomorfní šifrování je forma šifrování, která umožňuje provedení specifické algebraické operace na otevřeném textu provedením algebraické operace na šifrovaném textu.

Nechť být  šifrovacím klíčem,  být prostým textem (zprávou) , který má být zašifrován, a být  funkcí, která provádí šifrování.

Funkce se nazývá homomorfní s ohledem na operaci " " (sčítání nebo násobení) nad holým textem (zprávami) a pokud existuje účinný algoritmus (vyžadující polynomiální počet zdrojů a běžící v polynomiálním čase ), který po obdržení libovolného páru ciphertexts for a as input , produkuje zašifrovaný text (ciphertext, cryptogram) takový, že když dešifruje , bude získán čistý text [3] .

V praxi je častěji zvažován následující speciální případ homomorfního šifrování.

Nechť pro danou šifrovací funkci a operaci „ “ na prostých textech a na šifrovaných textech existuje operace „ “, takže prostý text je extrahován ze šifrovaného textu, když je dešifrován . To vyžaduje, aby dané , , , ale s neznámým klíčem , bylo nemožné efektivně zkontrolovat, že šifrový text byl získán z a .

Jakýkoli standardní šifrovací systém lze popsat popisem tří operací: operace generování klíče ( keyGen ), operace šifrování ( encypt ) a operace dešifrování ( decrypt ) [4] .

Pro popis homomorfního šifrovacího systému je kromě tří výše uvedených operací nutné popsat výpočetní operaci ( eval ). Použití homomorfního šifrování znamená použití sekvence čtyř operací: generování klíče, šifrování, výpočet, dešifrování:

  1. generování klíče - generování veřejného klíče ( public key )  klientem (pro dešifrování zašifrovaného prostého textu) a tajného klíče ( tajný klíč ) (pro šifrování prostého textu);
  2. šifrování  - klientské šifrování čistého textu ( prostého textu ) pomocí tajného klíče  - výpočet šifrovaného textu ( šifrovaný text ) ; odeslání klientského šifrového textu a veřejného klíče na server;
  3. výpočet  - přijímání funkce serverem , používání a provádění výpočtů na šifrovaném textu ; odeslání výsledku serverem klientovi;
  4. decryption  - dešifrování klientem hodnoty přijaté ze serveru pomocí .

Nechť  je šifrovací funkce;  - expanzní funkce; a  — prosté texty; symboly „ “ a „ “ označují operace násobení a sčítání na šifrovaných textech, odpovídající operacím násobení a sčítání na prostém textu.

Šifrovací systém je homomorfní s ohledem na operaci násobení (má multiplikativní homomorfní vlastnosti), pokud

Šifrovací systém je homomorfní s ohledem na operaci sčítání (má aditivní homomorfní vlastnosti), jestliže

Šifrovací systém je homomorfní s ohledem na operace násobení a sčítání, to znamená zcela homomorfní (má multiplikativní i aditivní homomorfní vlastnosti), pokud

Jestliže kryptosystém s těmito vlastnostmi může zašifrovat dva bity, pak protože operace sčítání a násobení tvoří Turingovu úplnou základnu nad bity, je možné vypočítat jakoukoli booleovskou funkci a tedy jakoukoli jinou vypočitatelnou funkci .

Aplikace

Cloud computing

Homomorfní šifrování otevírá nové možnosti pro zachování integrity, dostupnosti a důvěrnosti dat při jejich zpracování v cloudových systémech. V cloud computingu , kde je výkon nejvyšší prioritou, by měly být použity různé algoritmy, z nichž každý nejlépe plní daný úkol. Například pro operace násobení šifrovaných dat je vhodné použít algoritmus RSA nebo algoritmus ElGamal a navíc algoritmus Peye . V případě použití zcela homomorfního šifrovacího systému by měl být počet operací, které lze s daty provádět, omezen, protože v důsledku výpočtů se hromadí určitá chyba . Pokud chybová hodnota překročí hodnotu tajného parametru , je možné, že data nelze správně dešifrovat.

Elektronické hlasování

Elektronické hlasování  je další slibnou oblastí použití pro homomorfní šifrování. Systém bude schopen šifrovat hlasy voličů a provádět výpočty na zašifrovaných datech při zachování anonymity voličů. Například ve schématu elektronického hlasování Benalo zahrnuje proces hlasování následující kroky [5] :

  1. každý hlasující účastník schématu rozdělí svůj hlas (tajemství) do složek (dílčích tajemství) podle odpovídajícího schématu sdílení tajného tajemství s přidáním vlastnosti homomorfismus a rozesílá dílčí tajemství voleným zástupcům;
  2. zastupitelé sečtou své hlasy; schéma je navíc homomorfní, proto jsou součty hlasů částečným tajemstvím odpovídajícího volebního výsledku;
  3. hlavní správce vypočítá konečný celkový počet hlasů pomocí souboru dílčích hlasů, které mu dali zvolení zástupci.

Zvažte příklad, jak lze tento přístup implementovat.

Nechť je množina kandidátů, ze které se tvoří seznam zařazený do hlasování. Iniciátor hlasování má kryptosystém, který je homomorfní s ohledem na operaci sčítání, rozděluje mezi účastníky tajného hlasování veřejný klíč homomorfního šifrovacího systému a hlasovací lístek jako vektor , kde  je příjmení -tého kandidáta. Každý z voličů vytvoří vektor preferencí , kde poté každý z voličů pomocí veřejného klíče zašifruje vektor prvek po prvku a odešle jej iniciátorovi hlasování. Aby shrnul výsledky hlasování, provede výpočty na odpovídajících prvcích přijatých preferenčních vektorů a dešifruje pomocí tajného klíče . Protože kryptosystém je homomorfní s ohledem na operaci sčítání, indexy největších prvků výsledného vektoru budou indexy vítězných kandidátů.

Zabezpečené vyhledávání informací

Homomorfní šifrování může uživatelům poskytnout možnost extrahovat informace z vyhledávačů při zachování důvěrnosti: služby budou moci přijímat a zpracovávat požadavky, stejně jako výsledky zpracování problémů, aniž by analyzovaly a opravovaly jejich skutečný obsah. Například způsob extrahování záznamů z databáze podle jejich indexů může být znázorněn následovně.

Dovolit  je index záznamu, který má být načten; ;  - všechny indexované záznamy z databáze.

Poté, aby bylo možné vybrat požadovaný záznam, je nutné vypočítat následující funkci :

Pokud jsou všechny zašifrovány homomorfním kryptosystémem, lze počítat homomorfně přes šifrované texty. K tomu stačí, aby klient bit po bitu zašifroval index požadovaného záznamu a poslal jej na server. Výsledkem homomorfního vyhodnocení funkce nad šifrovými texty bude požadovaná šifrová hodnota položky požadované klientem. Je zřejmé, že kryptosystém musí mít multiplikativní i aditivní homomorfní vlastnosti.

Ochrana bezdrátových decentralizovaných komunikačních sítí

Bezdrátové decentralizované samoorganizující se sítě ( MANET ) jsou sítě tvořené mobilními zařízeními. Každé takové zařízení se může nezávisle pohybovat v libovolném směru a v důsledku toho se často přeruší a vytvoří spojení se sousedními zařízeními. Jedním z hlavních problémů při budování MANETu je zajištění bezpečnosti přenášených dat. K vyřešení tohoto problému lze použít homomorfní šifrování, které je zabudováno do směrovacích protokolů pro zlepšení bezpečnosti. V tomto případě lze operace se šifrovými texty bezpečně provádět pomocí mezilehlých uzlů. Zejména pro nalezení optimální cesty mezi dvěma uzly je nutné provádět lineární operace se šifrovanými daty bez jejich dešifrování. Přítomnost homomorfního šifrování neumožňuje útočníkovi najít spojení mezi zprávami vstupujícími do uzlu a zprávami opouštějícími uzel. Není tedy možné sledovat cestu zprávy pomocí analýzy provozu [6] .

Outsourcingové služby pro čipové karty

Současným trendem je vývoj univerzálních karet s vlastním operačním systémem , které mohou vykonávat různé funkce a komunikovat s více poskytovateli služeb. Spekulovalo se, že některé aplikace mohou běžet mimo mapu na homomorfně zašifrovaných datech. Externí úložná zařízení a externí _ _ _ _ procesory , výkonnější než procesor zabudovaný v kartě.

Systémy zpětné vazby

Homomorfní šifrování lze použít například v tzv. bezpečných systémech homomorfní zpětné vazby, kdy je potřeba zachovat anonymitu uživatele a skrýt mezivýsledky výpočtů .  Systémy pomáhají anonymně sbírat zpětnou vazbu (komentáře) od studentů nebo učitelů k jejich práci. Takto přijatá zpětná vazba je zašifrována a uložena pro následné výpočty. Systémy zpětné vazby lze použít ke zvýšení povědomí o stavu věcí a ke zlepšení výkonnosti. Bylo stanoveno, že spolehlivou zpětnou vazbu jakéhokoli systému nebo procesu lze poskytnout pouze v případech zachování anonymity uživatele, neměnnosti shromážděných dat a zajištění bezpečnosti interních operací pro analýzu dat.

Zmatek k ochraně softwarových produktů

Hlavním účelem mlžení je ztížit pochopení fungování programu. Protože všechny tradiční počítačové architektury používají binární řetězce, použitím plně homomorfního šifrování přes bity lze vypočítat jakoukoli funkci. Proto je možné homomorfně zašifrovat celý program tak, aby si zachoval svoji funkčnost.

Částečně homomorfní systémy

Částečně homomorfní kryptosystémy jsou kryptosystémy, které jsou homomorfní s ohledem pouze na jednu operaci, buď operaci sčítání nebo operaci násobení. V příkladech níže tento výraz označuje použití šifrovací funkce k zašifrování otevřeného textu (zprávy) .

Kryptosystém RSA

Kryptosystém RSA je kryptografické schéma s veřejným klíčem, které je homomorfní v násobení. Nechť je  modul RSA,  prostý text  a veřejný klíč (pro šifrování prostého textu). Funkce šifrování vypadá takto . Ukažme homomorfismus násobením:

Cryptosystem of ElGamal

Kryptosystém ElGamal je alternativou ke kryptosystému RSA a se stejnou hodnotou klíče poskytuje stejné kryptografické zabezpečení . ElGamal vylepšil Diffie-Hellmanův algoritmus a získal algoritmy pro šifrování a pro poskytování autentizace. Kryptosystém je pravděpodobnostní šifrovací kryptosystém. Jeho šifrovací funkce je homomorfní s ohledem na operaci násobení otevřeného textu: součinový kryptogram lze vypočítat jako (párový) součin kryptogramů faktorů. Nechť  je šifrovací funkce; a  — prosté texty. Pokud a potom lze získat ve formuláři .

Kryptosystém Goldwasser-Micali

V kryptosystému Goldwasser-Micali platí, že pokud je modul veřejným klíčem, je funkce bitového šifrování určena pro náhodný prvek . Pak je tento kryptosystém homomorfní pro operaci násobení: kde symbol „ “ označuje operaci sčítání modulo 2 .

Peyeův kryptosystém

V kryptosystému Peye , pokud je veřejný klíč modulo a  je náhodné číslo, pak je funkce šifrování zprávy (prostého textu) reprezentována jako náhodná proměnná . Pak se homomorfismus sčítáním dokáže takto:

Cryptosystem of Benalo

V kryptosystému Benalo , pokud je veřejným klíčem modul , pak je funkce šifrování prostého textu reprezentována jako náhodná . Pak se homomorfismus sčítáním dokáže takto:

Jiné částečně homomorfní kryptosystémy

Plně homomorfní šifrování

Částečně homomorfní kryptosystémy umožňují provádění homomorfních výpočtů pouze pro jednu operaci (buď sčítání nebo násobení) otevřeného textu. Kryptosystém, který podporuje jak sčítání, tak násobení (takže zachovává kruhovou strukturu prostého textu ), je známý jako plně homomorfní šifrování a je výkonnější. Pomocí takového systému lze homomorfně vyhodnotit jakékoli schéma, což umožňuje efektivní vytváření programů, které lze spouštět se vstupním šifrováním a vytvářet šifrování výstupu. Protože takový program nikdy nedešifruje svůj vstup, může jej spustit nedůvěryhodná strana, aniž by ukazoval svůj vstup a vnitřní stav. Existence efektivního a plně homomorfního kryptografického systému by měla velké praktické důsledky při outsourcingu soukromých počítačů, například v kontextu cloud computingu [7] . Homomorfní šifrování by umožnilo kombinovat různé služby do jedné bez poskytování dat pro každou službu. Například sdružování služeb různých společností by mohlo konzistentně vypočítat daň, použít aktuální směnný kurz, podat žádost o transakci, aniž by se pro každou z těchto služeb poskytovaly skutečné údaje [8] . Homomorfní vlastnost různých kryptografických systémů lze využít k vytvoření bezpečných hlasovacích systémů [9] , hašovacích funkcí odolných proti kolizím, proprietárních informací vyhledávačů a umožnit široké využití veřejného cloud computingu tím, že zaručí důvěrnost zpracovávaných dat.

Problémy s výkonem a řešení

Jedním z významných problémů známých plně homomorfních kryptosystémů je jejich extrémně nízký výkon. V současné době existují dva hlavní způsoby, jak zlepšit výkon: použití „omezeného plně  homomorfního šifrování[10] a použití takzvané „metody sbalení šifrovaného textu“ [11] . První zahrnuje kryptosystém, který může provádět operace sčítání a násobení, ale v omezeném počtu. Podstatou druhého je, že do jednoho šifrového textu je zapsáno několik otevřených textů najednou a zároveň během jediné operace takového dávkového šifrového textu jsou všechny šifrové texty v něm obsažené zpracovány současně.

Viz také

Poznámky

  1. Ronald L. Rivest, Len Adleman, Michael L. Dertouzos. O databankách a homomorfismech soukromí . Academic Press (1978). Archivováno z originálu 25. května 2013.  
  2. Dan Boneh, Eu-Jin Goh, Kobbi Nissim. Vyhodnocení 2-DNF vzorců na  šifrových textech . Springer-Verlag (2005). Archivováno z originálu 25. května 2013.
  3. Varnovskij, N. P.  Homomorfní šifrování / N. P. Varnovskij, A. V. Shokurov // Sborník Institutu pro systémové programování Ruské akademie věd. — 2006.
  4. Přehled různých homomorfních šifrovacích algoritmů a schémat / PV Parmar [et al.] // Intern. J. počítačových aplikací. - 2014. - Sv. 91, č.p. osm.
  5. Shenets, N. N.  Modular secret sharing and electronic voting system / N. N. Shenets // Bulletin of BSU. Ser. 1. - 2011. - č. 1.
  6. Gabidulin, E. M.  Informační bezpečnost v telekomunikačních sítích / E. M. Gabidulin, N. I. Pilipchuk, O. V. Trushina // Sborník Moskevského fyzikálního a technologického institutu. - 2013. - V. 5, č. 3.
  7. Daniele Micciancio. A First Glimpse of Cryptography's Holy Grail  (Angl.) 96. Association for Computing Machinery (1. března 2010). Archivováno z originálu 24. května 2013.
  8. Craig Stuntz. Co je homomorfní šifrování a proč by mě to mělo zajímat?  (anglicky) (18. března 2010). Archivováno z originálu 24. května 2013.
  9. Ron Rivest. Poznámky k přednášce 15: Voting, Homomorphic Encryption  (anglicky) (29. října 2002). Archivováno z originálu 24. května 2013.
  10. Brakerski Z., Gentry C., Vaikuntanathan V. (Leveled) plně homomorfní šifrování bez bootstrappingu  //  Theoretical Computer Science. - 2012. - S. 309-325 .
  11. Burtyka F. B. Paketové symetrické plně homomorfní šifrování založené na maticových polynomech  // Proceedings of the Institute of System Programming. Ročník 26. - 2014. - č. 5 . - S. 99-115 .

Literatura

Odkazy