Kryptosystém Gentry

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é 19. prosince 2017; kontroly vyžadují 78 úprav .

Kryptosystém Gentry (z příjmení tvůrce Craiga Gentryho) je první možnou konstrukcí pro plně homomorfní kryptosystém založený na mřížkové kryptografii . Poprvé ji navrhl Craig Gentry v roce 2009 [1] a byla předmětem jeho doktorské disertační práce. Schéma Gentry podporuje operace sčítání a násobení na šifrovém textu, což vám umožňuje vytvářet kruhy pro implementaci libovolných výpočtů. Následně prošel mnoha vylepšeními a úpravami s cílem zlepšit jeho výkon.

Popis algoritmu

Schéma využívá [2] ideální svazy J v řetězcích polynomů modulo . Hermitovská normální forma ideální mřížky má tvar [2] : $f_{n}(x)=x^{n}+1$

$HNF(J)=\quad \left[{\begin{array}{ccccc}d&0&0&0&0\\-r&1&0&0&0\\-[r^{2}]_{d}&0&1&0&0\\-[r^{2 }]_{d}&0&0&0&0\\\vdots &&&\ddots &\\-[r^{n-1}]_{d}&0&0&0&1\end{array}}\right]$ , kde a r je kořen pro modulo d. $d=det(J)$ $f_{n}(x)$

Generování klíče [2]

Je zvolena libovolná n-rozměrná celočíselná mřížka v, kde každý vstup je vybrán náhodně jako t-bitové číslo. S tímto vektorem v je polynom formálně definován , stejně jako odpovídající rotační matice: $v_{i}$ ${\displaystyle v(x)=\sum _{i\mathop {=} 0}^{n-1}v_{i}x^{i))$

$V=\quad \left[{\begin{array}{ccccc}v_{0}&v_{1}&v_{2}&&v_{n-1}\\-v_{n-1}&v_{0} &v_{1}&&v_{n-2}\\-v_{n-2}&v_{n-1}&v_{0}&&v_{n-3}\\&&&\dtečky &\\-v_{1}&- v_{2}&-v_{3}&&v_{0}\end{array}}\right]$

Inverzní for se vypočítá modulo , tedy polynom stupně nejvýše n-1, což je . Pak matrice $v(x)$ $f_{n}(x)$ $w(x)$ $v(x)*w(x)=const{\bmod {f}}_{n}(x)$

$W=\quad \left[{\begin{array}{ccccc}w_{0}&w_{1}&w_{2}&&w_{n-1}\\-w_{n-1}&w_{0} &w_{1}&&w_{n-2}\\-w_{n-2}&w_{n-1}&w_{0}&&w_{n-3}\\&&&\dtečky &\\-w_{1}&- w_{2}&-w_{3}&&w_{0}\end{array}}\right]$

je inverzní k , tj . kde je matice identity. $PROTI$ $V*W=const*I$ $já$

Je také ověřeno, že hermitovská normální forma pro má tvar uvedený výše, totiž všechny sloupce kromě levého tvoří matici identity. V tomto případě lze celou matici získat pomocí prvků r a d. $PROTI$ $PROTI$

Veřejný klíč bude matice daná čísly r a d. Soukromý klíč budou dva polynomy . $PROTI$ $(v,w)$

Šifrování [2]

Nechť je potřeba trochu zašifrovat ${\displaystyle {m\in(0,1)))$

Na vstupu je bit b a veřejný klíč V. Je zvolen šumový vektor , jehož složky nabývají hodnot 0,1,-1. Poté se vypočítá vektor a šifrový text se vypočítá podle vzorce [2] $u$ ${\displaystyle a=2*u+b*e_{1))$ $c=a{\bmod {V}}=a-([a*V^{-1}]*V)$

Zde, pro bázi V prostoru L a daný vektor c, se výraz používá k označení vektoru tak, že [2] $c{\bmod {V}}$ $c'\in P(V)$ $cc'\in L$

Dešifrování [2]

Vstup má vektor C a matice V a W. Původní bit b se získá jako výsledek operace:

$b=a{\bmod {2}}=(c{\bmod {V}}){\bmod {2}}=(c*(W/d)){\bmod {2}}$

homomorfismus [2]

Šifrování je homomorfní s ohledem na operace sčítání a násobení. Aby bylo možné provádět sčítání nebo násobení šifrových textů, je nutné tyto operace provádět v základu V

Vytrvalost [3]

Gentry zdůvodnil bezpečnost svého schématu dvěma problémy: problémem složitosti nejhoršího případu kryptografie na ideálních svazech a problémem součtu podmnožin. Oba problémy jsou -těžké, takže stabilita systému je redukována na -těžký problém. $NP$ $NP$

Nedostatky

Významnou nevýhodou tohoto schématu je, že provádění výpočtů vede k hromadění chyb [4] a po jejich překročení je nemožné zprávu dešifrovat. Jedním z řešení tohoto problému je opětovné zašifrování dat po určitém počtu operací, nicméně tato možnost snižuje výkon výpočtů a vyžaduje neustálý přístup k tajnému klíči [3] . $p$

Zjednodušený diagram Gentryho

Schéma je považováno za homomorfní pouze s ohledem na operaci sčítání [4] .

Generování klíčů

Je vybráno číslo , jehož modul bude schéma fungovat. $n$
Je vybrán tajný klíč - náhodné číslo, mnohem větší , například gcd $sk$ $n$ ${(sk,n)=1}$
Je vybrán veřejný klíč — množina velkých čísel tak, že , kde je malé náhodné číslo, je libovolné náhodné číslo. $pk$ $[a_{1},..a_{i}]$ $a_{i}=r*sk+e*n$ $r$ $E$

Šifrování

Vstup obsahuje text, který má být zašifrován, a veřejný klíč. Šifrovaný text bude součtem libovolného počtu prvků veřejného klíče a otevřeného textu.

dešifrování

Vstup obsahuje šifrovaný text a čísla a . Zbytek dělení šifrového textu a by se vypočítává postupně . Výsledkem bude původní zpráva. $n$ $sk$ $n$ $sk$

homomorfismus

Pro získání součtu textů a , stačí sečíst šifrované texty a provést operaci dešifrování. Opravdu: $m_{{1}}$ $m_{{2}}$ ${D(E(m_{1},pk)+E(m_{2},pk))=D(m_{1}+m_{2}+\sum _{i\mathop {=} 0 }^{n}C_{i}pk_{i})=D(m_{1}+m_{2}+C_{1}^{'}sk+C_{2}^{'}n)=m_{ 1}+m_{2}}$

Výhodou tohoto schématu je snadná implementace a nízké nároky na zdroje. Mezi nevýhody patří konečná množina veřejných klíčů a pouze částečný homomorfismus.

Implementace Smart a Wertcauteren

První pokus o implementaci Gentryho schématu provedli v roce 2010 Smart a Werkauteren [5] . Pro implementaci zvolili schéma využívající ideální svazy pro jednoduchý determinant. Takové struktury jsou reprezentovány dvěma celými čísly (bez ohledu na jejich velikost). Smart a Wertkauteren navrhli metodu dešifrování, ve které je tajný klíč jedno celé číslo. Vědcům se tedy podařilo implementovat homomorfní homogenní obvod, ale nedokázali implementovat Gentryho techniku v případě dostatečně velkých parametrů, a proto se jim nepodařilo získat zatížitelný a zcela homomorfní obvod.

Hlavní překážkou této implementace byla obtížnost generování klíčů pro homogenní schémata: schémata musí především generovat velmi velké množství „kandidátů“ na nalezení klíče, pro který je determinant jednoduchý – až po kandidáty při práci s dimenzemi . . Navíc i po nalezení optimální varianty je složitost výpočtu tajného klíče odpovídající této struktuře stejná, alespoň pro svazy dimenzí . Z těchto důvodů vědci nebyli schopni generovat rozměrové klíče . Smart a Vercauteren navíc odhadli, že dešifrovací polynom bude mít stupeň několik stovek, a to vyžaduje použití mřížky alespoň rozměrů pro proceduru s jejich parametry , což výrazně převyšuje výpočetní možnosti procedury generování klíče [ 2] . ${n^{1,5))$ $n$ ${{\tilde {O}}(n^{2,5}})}$ $n$ ${n>2048}$ ${n=2^{27))$ ${\displaystyle {(\cca 1,3\krát 10^{8)))))$

Gentryho plně homomorfní schéma

V roce 2011 Craig Gentry spolu se Shai Halevi představil [2] praktickou implementaci pro plně homomorfní šifrovací schéma, podobné tomu, které bylo použito v dřívějších pracích Smarta a Wertcauterena. Hlavní optimalizace spočívá v metodě generování klíče pro základní relativně homomorfní šifrování, které nevyžaduje plnou polynomiální inverzi. To snižuje asymptotickou složitost z na při práci s dimenzionálními mřížemi (a v praxi snižuje dobu výpočtu z mnoha hodin na několik minut). ${{\tilde {O}}(n^{2,5}})}$ ${{\tilde {O}}(n^{1,5}})}$ $n$

Poznámky

↑ Craig Gentry. "PLNĚ HOMOMORPHICKÉ SCHÉMA ŠIFROVÁNÍ" Archivováno 5. února 2017 na Wayback Machine Disertační práce předložená katedře informatiky a komisi pro postgraduální studenty Standfordské univerzity, 2009.
↑ 1 2 3 4 5 6 7 8 9 10 Craig Gentry a Shai Halevi. "Implementing Gentry's Fully-Homomorphic Encryption Scheme" Archivováno 22. prosince 2017 ve výzkumu Wayback Machine IBM.
↑ 1 2 Trubey A.I. HOMOMORFNÍ ŠIFROVÁNÍ: ZABEZPEČENÍ CLOUD COMPUTING A DALŠÍ APLIKACE (RECENZE). Informatika. 2015;(1):90-101.
↑ 1 2 Alumyan A.S., Glazunov I.A., Tishin V.V. "Homomorfní šifrování" Archivováno 22. prosince 2017 na Wayback Machine Článek pro XXI mezinárodní vědeckou a praktickou konferenci "Vědecká komunita studentů: INTERDISCIPLINÁRNÍ VÝZKUM" (Rusko, Novosibirsk, 18. května 2017)
↑ NP SmartF. Vercauteren. "Plně homomorfní šifrování s relativně malými velikostmi klíče a šifrovaného textu" Archivováno 22. prosince 2017 na Wayback Machine , 2010.