Homomorfní šifrování

V kryptografii , je homomorfní šifra je šifra , která má určité algebraické vlastnosti, které jej způsobují, aby spínač s matematickou operaci, to znamená, že dešifrování důsledku této operace na šifrovaných dat poskytuje stejný výsledek jako tento provoz na nešifrovaná data ; tato vlastnost umožňuje svěřit výpočty externímu agentovi, aniž by tomuto agentovi byla přístupná data nebo výsledky.

Příkladem použití homomorfního šifrování pro delegování výpočtů by mohl být případ, kdy by uživatel chtěl provést nákladný výpočet - na který nemusí nutně mít prostředky - a chtěl by zavolat na cloud služeb, který nemusí nutně důvěřovat provádění svých výpočtů.

Homomorfní šifrování je aktivní oblastí výzkumu.

Definice

Vzhledem k prostoru šifer, prostoru zpráv a prostoru vyhodnotitelných funkcí definujeme homomorfní šifru na kvadrupletu algoritmů, jako jsou: $VS$ $M$ $F$ $F$ ${\ displaystyle ({\ mathcal {K}}, {\ mathcal {E}}, {\ mathcal {D}}, {\ mathsf {Eval}})}$

${\ displaystyle {\ mathcal {K}}: \ mathbb {N} \ na PK \ krát SK}$ : funkce generování klíčů ;
${\ displaystyle {\ mathcal {E}}: {\ mathcal {M}} \ do {\ mathcal {C}}}$ je funkce šifrování;
${\ displaystyle {\ mathcal {D}}: {\ mathcal {C}} \ do {\ mathcal {M}}}$ je dešifrovací funkce;
${\ displaystyle {\ mathsf {Eval}}: F \ times {\ mathcal {C}} \ times {\ mathcal {C}} \ až {\ mathcal {C}}}$ je vyhodnocovací funkce.

Chceme mít následující vlastnosti:

Oprava : ; ${\ displaystyle {\ mathcal {D}} ({\ mathcal {E}} (m)) = m}$
Homomorphism : . ${\ displaystyle \ forall f \ in F, ~ {\ mathcal {D}} ({\ mathsf {Eval}} (f, C_ {1}, C_ {2})) = f ({\ mathcal {D}} (C_ {1}), {\ mathcal {D}} (C_ {2}))}$

Z důvodu jednoduchosti čtení jsme popsali jako funkci arity 2, ale můžeme popsat prostor funkcí jakékoli arity. $F$ $F$

Částečně homomorfní systémy

O kryptosystému řekneme, že je částečně homomorfní, když jeho prostor hodnotitelných funkcí je omezením prostoru vypočítatelných funkcí .

Například kryptosystém veřejného klíče RSA je částečně homomorfní s ohledem na násobení . Ve skutečnosti, pokud je dvojice celých čísel, máme následující rovnost: $(x, y)$

${\ displaystyle {\ begin {aligned} {\ mathcal {E}} (x) \ cdot {\ mathcal {E}} (y) & = x ^ {e} \ cdot y ^ {e} {\ bmod {N }} \\ & = (x \ cdot y) ^ {e} {\ bmod {N}} \\ & = {\ mathcal {E}} (x \ cdot y) \ end {zarovnáno}}}$

Můžeme tedy říci, že kryptosystém RSA dojíždí s operací vynásobení celých čísel v modulárním kruhu ℤ / N ℤ , kde N je semi-prime .

Plně homomorfní systémy

V předchozí části popsané kryptosystémy umožňují homomorfně provádět pouze jeden typ operace , například pro RSA je to multiplikace. V případě, že prostor hodnotitelných funkcí je prostorem vypočítatelných funkcí (definovaných například ve formě obvodu ), pak řekneme, že šifrování je zcela homomorfní ( Fully Homomorphic Encryption nebo FHE ).

Existují také takzvané „ téměř homomorfní“ konstrukce ( v angličtině poněkud homomorfní ), kde jsou možné operace sčítání a násobení, ale ne nutně pro libovolný počet operací. Například systém Boneh-Goh-Nissim založený na vazbách , který umožňuje vyhodnotit maximálně jednu násobení (pro libovolný počet sčítání).

Od roku 2017 jsou jediné kryptosystémy, které podporují homomorfní hodnocení pro všechny obvody, založeny na euklidovských sítích . Tyto budovy byly nejprve systémy téměř homomorfní (multiplikativní hloubka obvodu byla omezena), než tento problém vyřešil Craig Gentry pomocí restartu ( bootstrap anglicky). Tato metoda je založena na následující myšlence: protože kvalita šifry se v průběhu násobení zhoršuje, pokud dokážeme šifru dešifrovat homomorfně, získáme novou čistou šifru až po homomorfní vyhodnocení. Nevýhodou této metody je, že je stále drahá. Součástí výzkumu homomorfního šifrování v roce 2017 je omezení dopadu této fáze restartu, a to buď pokusem se jí co nejvíce vyhnout, nebo zlepšením jejího výkonu, aby byla méně ochromující.

Aplikace

Jedním ze zájmů homomorfního šifrování je, že třetí strana může provádět výpočty šifrovaných zpráv bez jejich dešifrování a že výsledek je použitelný, to znamená, že může být dekódován.

Dějiny

Jedním z hlavních hráčů ve vývoji homomorfních šifer je Craig Gentry .

Poznámky a odkazy

„ Zaměření na homomorfní šifrování “ , Le Monde Informatique ,2. září 2020
Gentry 2009 , 2.1 Základní definice, str. 27.
Gentry 2009 .
Gentry, Sahai a Waters 2013 .
Boneh, Goh a Nissim 2005 .
Ducas a Micciancio 2015 .
Benhamouda a kol. 2017 .
„ Alice a Bob v šifrovacím prostoru “, americký vědec , sv. 100, n o 5, září 2012( DOI 10.1511 / 2012.98.1 , číst online ).

Dodatky

Související články

Bibliografie

[Benhamouda a kol. 2017] (cs) Fabrice Benhamouda, Tancrède Lepoint, Claire Mathieu a Hang Zhou, „ Optimalizace bootstrappingu v obvodech “ , SODA ,2017.
[Delahaye 2015] Jean-Paul Delahaye , „ Delegování výpočtu bez zveřejnění vašich údajů “, Pour la Science ,října 2015.
[Ducas and Micciancio 2015] (en) Léo Ducas a Daniele Micciancio, „ FHEW: Bootstrapping Homomorphic Encryption in less than a second “ , Eurocrypt ,2015.
[Gentry 2009] (en) Craig Gentry, Plně homomorfní šifrování pomocí ideálních svazů (disertační práce),2009, 196 s. ( číst online [PDF] ).
[Gentry, Sahai and Waters 2013] (en) Craig Gentry, Amit Sahai a Brent Waters, „ Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based “ , Crypto ,2013( číst online ).
[Yi a kol. 2014] (en) X. Yi et al. , Homomorfní šifrování a aplikace , Springer ,2014.
[Boneh, Goh a Nissim 2005] (en) Dan Boneh , Eu-Jin Goh a Kobbi Nissim, „ Evaluating 2-DNF Formulas on Ciphertexts “ , TCC ,2005.