Teknologian jakaminen

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Oppimisresurssit:
Täyshomomorfinen salaus I: teoria ja perusta (opettaja Yu Yu Shanghai Jiao Tong -yliopistosta)
Täyshomomorfinen salaus II: Täyshomomorfisen salauksen teoria ja rakenne (opettaja Xiang Xie)

---

Nykyään toisen sukupolven (kuten BGV ja BFV) ja kolmannen sukupolven täysin homomorfiset salausjärjestelmät perustuvat kaikki LWE:hen. Nyt kehittyneet täysin homomorfiset salausjärjestelmät perustuvat myös LWE:hen, joten tämä artikkeli tiivistää LWE:n perustiedot.
Harkitse ensin, haluamme salata numeron$s$, nyt käytössä sarja$a_i$oikein$s$Salaa ja hanki$a_{i}s$, itse asiassa se voidaan ratkaista ratkaisemalla suurin yhteinen jakaja GCD$s$ .Kuitenkin, jos satunnainen kohina lisätään$e_i$,saada$a_{i}s+e_i$, sen ratkaiseminen on vaikeaa$s$ arvo. Tämä prosessi on yksinkertainen käsitykseni LWE:stä. Niin kutsuttu virhe on kohina.

Täyshomomorfisen salauksen laskentaprosessi on jaettu kolmeen vaiheeseen: avainten luominen KeyGen, salaus Enc, homomorfinen laskenta Eval ja salauksen purku Dec. ,

KeyGen:

Muodosta ensin yllä oleva yhtälö,$s\cdot A+e=sA+e$ja hanki sitten julkinen avain pk ($-A$ja$sA+e$liitos) ja yksityinen avain sk ($s$ ja 1). Tästä syystä saadaan, että pk:n ja sk:n kertolaskutulos on satunnainen kohina e (lähellä 0:ta).

Enc:

Salaukseen käytetty julkinen avain pk, r on satunnainen vektori, joka sisältää vain 0 tai 1, ja m on salattava tieto (sijoitetaan vektorin alimmalle bitille).

Joulukuu:

Kun olet laskenut salauksen purkamiseen käytetyn yksityisen avaimen sk ja ct:n sisätulon, etsi mod 2 saadaksesi salauksen purkutuloksen.

Todiste oikeellisuudesta:

Kerro sk ja pk saadaksesi 2e (KeyGenin täyttämä ehto) ja tee sitten sisätulo r:llä saadaksesi pieni tasainen kohina. Lopputuloksena on m+ pieni tasainen kohina, joten kohina voidaan poistaa mod 2:lla. Hanki salauksen purkutulos m. Tästä syystä konstruoitu kohina on 2e, ei e Ymmärtääkseni muodostamalla parillinen satunnaiskohina on kätevää käyttää mod 2:ta eliminoimaan kohina salauksen purkamisen aikana.

Turvallisuustodistus:

Kun pk on näennäissatunnainen ja r:llä on riittävän korkea entropia (eli satunnaisuus on vahva?), sekä pk että pk kertaa r ovat näennäissatunnaisia. Kun on lisätty luonnolliset ja vektorit m:llä, salaustulos on myös näennäissatunnainen.

Seuraava on opettaja Xiang Xien kaavakuvaus:
Salauskaava: salateksti c = julkinen avain pk ✖️ satunnainen r + pelkkä teksti m
Salauksen purkukaava: pelkkä teksti m = <salattu teksti sk, yksityinen avain sk> mod q mod 2

Tällä perusteella mod 2:ta voidaan käyttää selkeän tekstin m arvon salauksen purkamiseen. Niin kauan kuin melu on tarpeeksi pieni, tarkkuus voidaan taata.
Tässä on jotain, joka on erotettava toisistaan: edellä mainittu$PK=(A,b=A{s}^{\prime }+2e)$on BGV-ratkaisu, ja BFV on$PK=(A,b=A{s}^{\prime }+e)$, ero on siinä, että BGV koodaa informaatiota pienillä biteillä, kun taas BFV koodaa viestejä korkeilla biteillä (selvitetään BFV:n oppimisen yhteydessä).

Eval (additiivinen homomorfismi ja multiplikatiivinen homomorfismi):

Huomaa, että homomorfinen yhteen- tai kertolasku tuo mukanaan merkittävää kohinan kertymistä ja kertolaskulla on neliöllinen kasvutrendi.
Puhutaan sitten homomorfisen kertolaskutuloksen purkamisesta. Näet seuraavan kaavan: Kahden salatekstin kertominen vastaa salatekstin ja yksityisen avaimen tensoritulon tekemistä ja sitten sisätulon tekemistä. Joten ilmeisesti sekä salateksti että yksityinen avain ovat kaksinkertaistuneet. Esimerkki on todiste vastaavuudesta.

Joten kysymys kuuluu, kuinka palauttaa salatekstin koko ja yksityisen avaimen koko homomorfisen kertolaskun jälkeen? Tämä on ongelma, jonka Key Switching ratkaisee.

Seuraava on opettaja Xiang Xien kuvaus:

Avaimen vaihto

Tavoitteena on palauttaa salatekstin ja yksityisen avaimen koko lineaariseen kokoon.

Etsi nyt salatekstien c1 ja c2 kertolasku:

Yllä oleva prosessi perustuu bittien hajotuksen käsitteeseen:

Seuraava on opettaja Xiang Xien kuvaus:

Avaimenvaihdon tavoite: muuntaa yksityinen avain$\tilde{s}$alas$\tilde{c}$ Muunna yksityiseksi avaimeksi$s$alas$c$,ja$\tilde{c}$ja$c$Ne kaikki on salattu samalla selkeällä tekstillä.
Ydinkonsepti tässä on Key Switching Key (KSK), joka tarkoittaa yksityisen avaimen käyttöä$s$salaamaan$\tilde{s}$。

Avaimenvaihtoprosessin kautta yksityinen avain voidaan johtaa$s\otimes s$muuttui lineaariseksi$s$, kun taas salateksti muuttuu$\tilde{c}$muuttui lineaariseksi$c$ .Ja se voidaan nähdä kaavan viimeisestä rivistä, että avaimenvaihdon jälkeen$⟨c,s⟩$ja alkuperäinen$⟨\tilde{c},s\otimes s⟩$Niiden välillä on meluero$2{\tilde{c}}^T\tilde{e}$ , tämä osa voi olla hyvin suuri! Joten ei ole vieläkään mahdollista toteuttaa avaimenvaihtoa täällä.

Gadget-matriisi G esitellään tässä:

Siksi avaimen vaihtoprosessista tulee seuraava:

Tässä vaiheessa lisätty virhe on hyvin pieni.
Yhteenvetona, Key Switchingin kautta alkuperäinen yksityinen avain$\tilde{s}=s\otimes s$alas$\tilde{c}=c\otimes c$, muunnetaan yksityiseksi avaimeksi$s$alas$c$, kiinnitä huomiota avaimeen avaimen vaihdon jälkeen$s,c$Ne eivät ole alkuperäisiä arvoja (kaksoistarkistus).

BGV:n kohdalla yhteenlaskukohina kasvaa tasaisesti. Vaikka Key Switching voi tukea kertomista (rajoittaa sk:n muuttumista erittäin suureksi), kohina on itse asiassa hyvin pieni kohina, joka lisätään alkuperäiseen kertomeluun on myös erittäin suuri. Siksi tätä melua on vähennettävä edelleen.

Modulus Reduction

Tässä vaiheessa LWE:n kautta on toteutettu homomorfinen kertolasku ja yhteenlasku, joka käyttää uutta avainta laskentasyvyyden syveneessä, joten se ei ole vielä tasoittunut. FHE (voi laskea FHE:n tietyllä syvyydellä).
Nyt toivomme toteuttavamme FHE:n, joka pystyy laskemaan tietyn syvyyden ilman bootstrappingia, mikä vaatii modulomuunnoksen.

En oikein ymmärrä keskellä olevaa prosessia. Lyhyesti sanottuna salateksti c muunnetaan alueesta modulo q verkkotunnukseksi modulo p (p<.
Tässä on konkreettinen esimerkki:
Jos Modulus Reduction -toimintoa ei suoriteta, kohina kasvaa kaksinkertaisena eksponentiaalisesti syvyyden kasvaessa, ja salauksen purkuvirheitä tapahtuu tason >= 3 jälkeen.

Jos moduulin vähennys suoritetaan kullakin tasolla, myös melu pysyy absoluuttisen arvon alueella moduulin jatkuvan pienenemisen kustannuksella.

Joten jos haluat toteuttaa tasaisen FHE:n, voit asettaa moduulin$B^d$, voit laskea syvyyden$d$piiri (missä$B$ on päivitetyn salatekstin kohinan yläraja).Laskettu$d$Syvyyden jälkeen moduuli tulee pienentää$B$ , jotta salauksen purkamisessa ei ole tällä hetkellä virhettä. BGV on vaakasuora FHE.