Cryptosystem Gentry

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 19. joulukuuta 2017 tarkistetusta versiosta . tarkastukset vaativat 78 muokkausta .

Gentry-salausjärjestelmä (luoja Craig Gentryn sukunimestä) on ensimmäinen mahdollinen rakennelma täysin homomorfiselle , hilasalaukseen perustuvalle kryptosysteemille . Craig Gentry ehdotti sitä ensimmäisen kerran vuonna 2009 [1] , ja se oli hänen väitöskirjansa aiheena. Gentry-malli tukee yhteen- ja kertolaskuoperaatioita salakirjoituksessa, minkä ansiosta voit rakentaa renkaita mielivaltaisten laskutoimitusten toteuttamiseksi. Myöhemmin siihen tehtiin monia parannuksia ja muutoksia suorituskyvyn parantamiseksi.

Algoritmin kuvaus

Kaaviossa käytetään [2] ideaalisia hiloja J polynomiketjuissa modulo . Ihanteellisen hilan hermiittisellä normaalimuodolla on muoto [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\\\vpisteet &&&\ddots &\\-[r^{n-1}]_{d}&0&0&0&1\end{array}}\right]$ , missä ja r on modulo d:n juuri. $d=det(J)$ $f_{n}(x)$

Avaimen luominen [2]

Valitaan mielivaltainen n-ulotteinen kokonaislukuhila v, jossa kukin tulo valitaan satunnaisesti t-bittiseksi luvuksi. Tällä vektorilla v polynomi määritellään muodollisesti , samoin kuin vastaava rotaatiomatriisi: $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}\\&&&\ddots &\\-v_{1}&- v_{2}&-v_{3}&&v_{0}\end{array}}\right]$

Käänteisarvo lasketaan modulo , eli polynomi, jonka aste on enintään n-1, joka on . Sitten matriisi $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}\\&&&\ddots &\\-w_{1}&- w_{2}&-w_{3}&&w_{0}\end{array}}\right]$

on käänteisarvo , eli missä on identiteettimatriisi. $V$ $V*W=const*I$ $minä$

Varmistetaan myös, että hermiittisellä normaalimuodolla for on yllä kuvattu muoto, eli kaikki sarakkeet vasenta lukuun ottamatta muodostavat identiteettimatriisin. Tässä tapauksessa koko matriisi voidaan saada käyttämällä elementtejä r ja d. $V$ $V$

Julkinen avain on lukujen r ja d antama matriisi. Yksityinen avain on kaksi polynomia . $V$ $(v, w)$

Salaus [2]

Vaaditaanko sitä hieman salaamaan ${\displaystyle {m\in(0,1)))$

Tulossa on bitti b ja julkinen avain V. Valitaan kohinavektori , jonka komponentit saavat arvot 0,1,-1. Sitten vektori lasketaan ja salateksti lasketaan kaavalla [2] $u$ ${\displaystyle a=2*u+b*e_{1))$ $c=a{\bmod {V}}=a-([a*V^{-1}]*V)$

Tässä avaruuden L kantalle V ja tietylle vektorille c ilmaisua käytetään merkitsemään vektoria siten, että [2] $c{\bmod {V}}$ $c'\in P(V)$ $cc'\in L$

Salauksen purku [2]

Tulossa on vektori C ja matriisit V ja W. Alkuperäinen bitti b saadaan toiminnon tuloksena:

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

Homomorfismi [2]

Salaus on homomorfista yhteen- ja kertolaskuoperaatioiden suhteen. Salatekstien yhteen- tai kertolaskujen suorittamiseksi on tarpeen suorittaa nämä toiminnot pohjassa V

Kestävyys [3]

Gentry perusteli suunnitelmansa turvallisuutta kahdella ongelmalla: ideaalisten hilan salauksen pahimman tapauksen monimutkaisuuden ongelmalla ja osajoukkojen summan ongelmalla. Molemmat ongelmat ovat -kovia, joten järjestelmän vakaus pienenee -kovaksi ongelmaksi. $NP$ $NP$

Vikoja

Tämän menetelmän merkittävä haittapuoli on, että laskelmien suorittaminen johtaa virheiden kertymiseen [4] ja sen ylittyessä viestin salauksen purkaminen tulee mahdottomaksi. Yksi ratkaisu tähän ongelmaan on salata tiedot uudelleen tietyn toimintomäärän jälkeen, mutta tämä vaihtoehto heikentää laskelmien suorituskykyä ja vaatii jatkuvan pääsyn salaiseen avaimeen [3] . $s$

Yksinkertaistettu kaavio Gentrystä

Kaavaa pidetään homomorfisena vain summausoperaation suhteen [4] .

Avaimen sukupolvi

Valitaan numero , jonka modulo järjestelmä toimii. $n$
Valitaan salainen avain - satunnaisluku, paljon suurempi , niin että gcd $sk$ $n$ ${(sk,n)=1}$
Valitaan julkinen avain — joukko suuria lukuja siten, että missä on pieni satunnaisluku, on mielivaltainen satunnaisluku. $pk$ $[a_{1},..a_{i}]$ $a_{i}=r*sk+e*n$ $r$ $e$

Salaus

Syöte sisältää salattavan tekstin ja julkisen avaimen. Salateksti on julkisen avaimen ja selkeän tekstin mielivaltaisen määrän elementtien summa.

salauksen purku

Syöte sisältää salatekstin sekä numerot ja . Salatekstin jakamisen loppuosa lasketaan peräkkäin . Tuloksena on alkuperäinen viesti. $n$ $sk$ $n$ $sk$

homomorfismi

Tekstien ja : n summan saamiseksi riittää, että lisäät salatekstit ja suoritat salauksen purku. Todella: $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}}$

Tämän järjestelmän etuna on toteutuksen helppous ja vähäiset resurssit. Haittoja ovat rajallinen joukko julkisia avaimia ja vain osittainen homomorfismi.

Smart and Wertcauterenin käyttöönotto

Ensimmäisen yrityksen Gentry-järjestelmän toteuttamiseen tekivät vuonna 2010 Smart ja Werkauteren [5] . Toteutusta varten he valitsivat kaavion, jossa käytettiin ihanteellisia hiloja yksinkertaiselle determinantille. Tällaisia rakenteita edustaa kaksi kokonaislukua (riippumatta niiden koosta). Smart ja Wertkauteren ehdottivat salauksen purkumenetelmää, jossa salainen avain on yksi kokonaisluku. Siten tiedemiehet onnistuivat toteuttamaan homomorfisen homogeenisen piirin, mutta he eivät pystyneet toteuttamaan Gentry-tekniikkaa riittävän suurten parametrien tapauksessa, ja siksi he eivät onnistuneet saamaan ladattavaa ja täysin homomorfista piiriä.

Suurin este tässä toteutuksessa oli vaikeus luoda avaimia homogeenisille skeemoille: ensinnäkin skeemojen täytyy tuottaa erittäin suuri määrä "ehdokkaita" löytääkseen avaimen, jonka determinantti on yksinkertainen - ehdokkaisiin asti, kun työskennellään dimensiorakenteiden kanssa. . Lisäksi jopa optimaalisen muunnelman löytämisen jälkeen tätä rakennetta vastaavan salaisen avaimen laskemisen monimutkaisuus on yhtä suuri, ainakin dimensioiden hiloille . Näistä syistä tutkijat eivät ole pystyneet luomaan ulottuvuusavaimia . Lisäksi Smart ja Vercauteren arvioivat, että salauksenpurkupolynomin aste on useita satoja, mikä edellyttää vähintään mittasuhteen hilan käyttöä prosessille parametreineen , mikä ylittää merkittävästi avaimen luontiproseduurin laskentaominaisuudet [ 2] . ${\näyttötyyli {n^{1,5))}$ $n$ ${{\tilde {O}}(n^{2,5}})}$ $n$ ${n>2048}$ ${\näyttötyyli {n=2^{27))}$ ${\displaystyle {(\noin 1,3\kertaa 10^{8)))))$

Gentryn täysin homomorfinen kaava

Vuonna 2011 Craig Gentry esitteli yhdessä Shai Halevin kanssa [2] käytännöllisen toteutuksen täysin homomorfiselle salausjärjestelmälle, joka on samanlainen kuin Smartin ja Wertcauterenin aikaisemmissa teoksissa käytetty. Pääasiallinen optimointi koostuu avainten generointimenetelmästä suhteellisen homomorfiselle perussalaukselle, joka ei vaadi täyttä polynomin inversiota. Tämä vähentää asymptoottista monimutkaisuutta arvohilan kanssa työskennellessä (ja käytännössä lyhentää laskenta-aikaa useista tunteista useisiin minuutteihin). ${{\tilde {O}}(n^{2,5}})}$ ${{\tilde {O}}(n^{1,5}})}$ $n$

Muistiinpanot

↑ Craig Gentry. "A FULLY HOMOMORPHIC ENCRYPTION SCHEME" Arkistoitu 5. helmikuuta 2017 Wayback Machinessa Väitöskirja, joka toimitettiin tietojenkäsittelytieteen laitokselle ja Standfordin yliopiston jatko-opiskelijoiden komitealle, 2009.
↑ 1 2 3 4 5 6 7 8 9 10 Craig Gentry ja Shai Halevi. "Implementing Gentry's Fully-Homomorphic Encryption Scheme" Arkistoitu 22. joulukuuta 2017 Wayback Machine IBM -tutkimukseen.
↑ 1 2 Trubey A.I. HOMOMORFINEN SALAUS: PILVITIETOJEN TURVALLISUUS JA MUUT SOVELLUKSET (ARVONTA). Informatiikka. 2015;(1):90-101.
↑ 1 2 Alumyan A.S., Glazunov I.A., Tishin V.V. "Homomorphic encryption" Arkistoitu 22. joulukuuta 2017 Wayback Machinessa Artikkeli XXI kansainvälisessä tieteellisessä ja käytännön konferenssissa "Scientific Community of Students: INTERDISCIPLINARY RESEARCH" (Venäjä, Novosibirsk, 18. toukokuuta 2017)
↑ NP SmartF. Vercauteren. "Täysin homomorfinen salaus suhteellisen pienillä avaimilla ja salatekstikokoilla" Arkistoitu 22. joulukuuta 2017 Wayback Machinessa , 2010.