Onko mahdollista tuottaa satunnaisia ​​lukuja, jos emme luota toisiimme? Osa 2

Hei Habr!

В ensimmäinen osa Tässä artikkelissa pohdimme, miksi saattaisi olla tarpeen luoda satunnaislukuja osallistujille, jotka eivät luota toisiinsa, mitä vaatimuksia tällaisille satunnaislukugeneraattoreille asetetaan, ja tarkastelimme kahta lähestymistapaa niiden toteuttamiseen.

Tässä artikkelin osassa tarkastelemme lähemmin toista lähestymistapaa, joka käyttää kynnysallekirjoituksia.

Vähän kryptografiaa

Ymmärtääksesi, kuinka kynnysallekirjoitukset toimivat, sinun on ymmärrettävä vähän perussalausta. Käytämme kahta käsitettä: skalaarit tai yksinkertaisesti numerot, jotka merkitään pienillä kirjaimilla (x, y) ja pisteet elliptisellä käyrällä, jotka merkitään isoilla kirjaimilla.

Ymmärtääksesi kynnysmerkintöjen perusteet sinun ei tarvitse ymmärtää elliptisten käyrien toimintaa, lukuun ottamatta muutamia perusasioita:

1. Pisteet elliptisellä käyrällä voidaan lisätä ja kertoa skalaarilla (merkitsimme kertomista skalaarilla xG, vaikka merkintä Gx käytetään myös usein kirjallisuudessa). Skalaarilla laskemisen ja kertomisen tulos on piste elliptisellä käyrällä.

2. Tietäen vain pointin G ja sen tulo skalaarilla xG ei voida laskea x.

Käytämme myös polynomin käsitettä p(x) astetta k-1. Käytämme erityisesti seuraavaa polynomien ominaisuutta: jos tiedämme arvon p(x) mille tahansa k eri x (ja meillä ei ole enempää tietoa p(x)), voimme laskea p(x) kenellekään muulle x.

On mielenkiintoista, että mille tahansa polynomille p(x) ja jossain pisteessä käyrässä Gtietäen merkityksen p(x)G mille tahansa k erilaisia ​​merkityksiä x, voimme myös laskea p(x)G mille tahansa x.

Tämä on tarpeeksi tietoa kynnysallekirjoitusten toiminnan yksityiskohtiin perehtymiseen ja niiden käyttämiseen satunnaislukujen luomiseen.

Satunnaislukugeneraattori kynnysallekirjoituksissa

Sanotaanpa niin n osallistujat haluavat luoda satunnaisluvun, ja haluamme kaikkien osallistuvan k niitä oli tarpeeksi luomaan numero, mutta niin, että hyökkääjät hallitsevat k-1 tai vähemmän osallistujaa ei voinut ennustaa tai vaikuttaa luotuun määrään.

Oletetaan, että on olemassa tällainen polynomi p(x) astetta k-1 mitä ensimmäinen osallistuja tietää p (1), toinen tietää p(2), ja niin edelleen (n- se tietää p(n)). Oletamme myös sen jollekin ennalta määrätylle kohdalle G kaikki tietävät p(x)G kaikille arvoille x. Soitamme p(i) "yksityinen komponentti" iosallistuja (koska vain iosallistuja tuntee hänet) ja sika "julkinen komponentti" i-th osallistuja (koska kaikki osallistujat tuntevat hänet). Kuten muistat, tieto sika ei riitä palauttamiseen p(i).

Tällaisen polynomin luominen niin, että vain i-Ensimmäinen osallistuja eikä kukaan muu tiennyt hänen yksityistä komponenttiaan - tämä on protokollan monimutkaisin ja mielenkiintoisin osa, ja analysoimme sen alla. Oletetaan nyt, että meillä on tällainen polynomi ja kaikki osallistujat tietävät yksityiset komponenttinsa.

Kuinka voimme käyttää tällaista polynomia satunnaisluvun luomiseen? Aluksi tarvitsemme jonkin merkkijonon, jota ei ole aiemmin käytetty generaattorin syötteenä. Lohkoketjun tapauksessa viimeisen lohkon hash h on hyvä ehdokas sellaiselle linjalle. Anna osallistujien haluta luoda satunnaisluku käyttämällä h kuin siemen. Osallistujat muuntavat ensin h käyrän pisteeseen käyttämällä mitä tahansa ennalta määritettyä funktiota:

H = skalaaripisteeseen(h)

Sitten jokainen osallistuja i laskee ja julkaisee Hi = p(i)H, mitä he voivat tehdä, koska he tietävät p(i) ja H. julkistaminen Hen salli muiden osallistujien palauttaa yksityistä komponenttia ith osallistuja, ja siksi yhtä joukkoa yksityisiä komponentteja voidaan käyttää lohkosta lohkoon. Siten alla kuvattu kallis polynomin generointialgoritmi tarvitsee suorittaa vain kerran.

Kun k osallistujille ruumiinavattiin Hi = p(i)H, jokainen osaa laskea Hx = p(x)H kaikille x kiitos polynomien ominaisuuden, josta keskustelimme viimeisessä osassa. Tällä hetkellä kaikki osallistujat laskevat H0 = p(0)H, ja tämä on tuloksena saatu satunnaisluku. Huomaa, että kukaan ei tiedä p(0), ja siksi ainoa tapa laskea p(0)H – tämä on interpolointia p(x)H, mikä on mahdollista vain kun k arvot p(i)H tiedossa. Pienemmän määrän avaaminen p(i)H ei anna mitään tietoa aiheesta p(0)H.

Yllä olevalla generaattorilla on kaikki haluamamme ominaisuudet: vain hyökkääjät hallitsevat k-1 tai vähemmän osallistujilla ei ole tietoa tai vaikutusta johtopäätökseen, kun taas millään k osallistujat voivat laskea tuloksena olevan luvun ja minkä tahansa osajoukon k osallistujat pääsevät aina samaan tulokseen samalla siemenellä.

On yksi ongelma, jonka vältimme huolellisesti edellä. Jotta interpolointi toimisi, on tärkeää, että arvo Hi, jonka jokainen osallistuja on julkaissut i se oli todella sama p(i)H. Koska kukaan muu kuin i- osallistuja ei tiedä p(i), ei kukaan paitsi i-osallistuja ei voi vahvistaa sitä Hi todella laskettu oikein ja ilman mitään kryptografista todistetta oikeasta HHyökkääjä voi julkaista minkä tahansa arvon muodossa Hei, ja mielivaltaisesti vaikuttaa satunnaislukugeneraattorin ulostuloon:

Ensimmäisen osallistujan lähettämät erilaiset H_1-arvot johtavat eri tulokseen H_0

On ainakin kaksi tapaa todistaa oikea Hi, tarkastelemme niitä sen jälkeen, kun olemme analysoineet polynomin generoinnin.

Polynomi sukupolvi

Viimeisessä osiossa oletimme, että meillä on tällainen polynomi p(x) astetta k-1 että osallistuja i hän tietää p(i), eikä kenelläkään muulla ole tietoa tästä arvosta. Seuraavassa osiossa tarvitsemme sitä myös johonkin ennalta määrättyyn kohtaan G kaikki tiesivät p(x)G kaikille x.

Tässä osiossa oletetaan, että jokaisella osallistujalla on paikallisesti yksityinen avain xi, siten, että kaikki tietävät vastaavan julkisen avaimen Xi.

Yksi mahdollinen polynomin generointiprotokolla on seuraava:

1. Jokainen osallistuja i luo paikallisesti mielivaltaisen polynomin pi(x) aste k-1. Sitten he lähettävät jokaisen osallistujan j значение pi(j), salattu julkisella avaimella Xj. Vain siis i-th и j-th osallistuja tietää pi(j). Osallistuja i ilmoittaa myös julkisesti pi(j)G kaikille j alkaen 1 до k osallisuutta.

2. Kaikki osallistujat käyttävät jonkinlaista konsensusta valinnassa k osallistujat, joiden polynomeja käytetään. Koska jotkut osallistujat voivat olla offline-tilassa, emme voi odottaa, kunnes kaikki n osallistujat julkaisevat polynomeja. Tämän vaiheen tulos on sarja Z koostuu vähintään k vaiheessa (1) luodut polynomit.

3. Osallistujat varmistavat, että arvot he tietävät pi(j) vastaavat julkisesti ilmoitettua pi(j)G. Tämän askeleen jälkeen Z vain polynomit, jotka lähetetään yksityisesti pi(j) vastaavat julkisesti ilmoitettua pi(j)G.

4. Jokainen osallistuja j laskee sen yksityisen komponentin p(j) summana pi(j) kaikille i в Z. Jokainen osallistuja laskee myös kaikki arvot p(x)G summana pi(x)G kaikille i в Z.

Huomaa, että p(x) – se on todella polynomi k-1, koska se on yksilön summa pi(x), joista jokainen on astepolynomi k-1. Huomaa seuraavaksi, että vaikka jokainen osallistuja j hän tietää p(j), heillä ei ole tietoa p(x) varten x ≠ j. Itse asiassa tämän arvon laskemiseksi heidän on tiedettävä kaikki pi(x), ja niin kauan kuin osallistuja j ei tunne vähintään yhtä valituista polynomeista, heillä ei ole tarpeeksi tietoa siitä p(x).

Tämä on koko polynomin generointiprosessi, jota tarvittiin viimeisessä osassa. Yllä olevilla vaiheilla 1, 2 ja 4 on melko ilmeinen toteutus. Mutta vaihe 3 ei ole niin triviaali.

Erityisesti meidän on pystyttävä todistamaan, että se on salattu pi(j) vastaavat todella julkaistuja pi(j)G. Jos emme pysty todistamaan sitä, hyökkääjä i voi lähettää roskia sen sijaan pi(j) osallistujalle j, ja osallistuja j ei voi saada todellista arvoa pi(j), eikä pysty laskemaan sen yksityistä osaa.

On olemassa salausprotokolla, jonka avulla voit luoda lisäviestin todistei(j), siten, että mikä tahansa osallistuja, jolla on jokin arvo e, sekä todiste(j) и pi(j)G, voi varmistaa sen paikallisesti e - se on todella pi(j), salattu osallistujan avaimella j. Valitettavasti tällaisten todisteiden koko on uskomattoman suuri, ja koska se on julkaistava O (nk) Tällaisia ​​todisteita ei voida käyttää tähän tarkoitukseen.

Sen sijaan, että sen todistaisi pi(j) соответствует pi(j)G voimme allokoida polynomin generointiprotokollassa hyvin pitkän ajanjakson, jonka aikana kaikki osallistujat tarkistavat vastaanotetun salatun pi(j), ja jos salauksesta purettu viesti ei vastaa julkista pi(j)G, he julkaisevat kryptografisen todisteen siitä, että heidän vastaanottamansa salattu viesti on virheellinen. Todista, että viesti ei соответствует sika) paljon helpompaa kuin todistaa, että se vastaa. On huomattava, että tämä edellyttää jokaisen osallistujan esiintyvän verkossa vähintään kerran tällaisten todisteiden luomiseen varatun ajan kuluessa, ja se perustuu oletukseen, että jos he julkaisevat tällaisen todisteen, se tavoittaa kaikki muut osallistujat samassa ajassa.

Jos osallistuja ei ilmestynyt verkkoon tänä aikana ja hänellä oli ainakin yksi virheellinen komponentti, kyseinen osallistuja ei voi osallistua numeron luomiseen. Protokolla toimii kuitenkin edelleen, jos ainakin on olemassa k osallistujia, jotka joko saivat juuri oikeat komponentit tai onnistuivat jättämään todisteen virheellisyydestä varatun ajan kuluessa.

Todisteet H_i:n oikeellisuudesta

Viimeinen osa, josta on vielä keskusteltava, on se, kuinka todistetaan julkaistujen oikeellisuus Hminä, nimittäin tuo Hi = p(i)H, ilman avaamista p(i).

Muistakaamme, että arvot H, G, p(i)G julkinen ja kaikkien tiedossa. Vastaanottotoiminto p(i) tietäen sika и G kutsutaan diskreetiksi logaritmiksi tai dlog, ja haluamme todistaa, että:

dlog(p(i)G, G) = dlog(Hi, H)

ilman paljastamista p(i). Tällaisia ​​todisteita varten on olemassa esimerkiksi konstruktioita Schnorrin pöytäkirja.

Tällä suunnittelulla jokainen osallistuja sekä Hi lähettää todistuksen suunnitelman mukaisesta oikeellisuudesta.

Kun satunnaisluku on luotu, muiden osallistujien kuin sen luoneiden on usein käytettävä sitä. Tällaisten osallistujien ja numeron on lähetettävä kaikki Hi ja siihen liittyvät todisteet.

Utelias lukija voi kysyä: koska lopullinen satunnaisluku on H0 ja p(0)G – Tämä on julkista tietoa, miksi tarvitsemme todisteita jokaisesta yksilöstä HMiksi en lähettäisi todisteita siitä

dlog(p(0)G, G) = dlog(H0, H)

Ongelmana on, että tällaista todistetta ei voida luoda Schnorr-protokollalla, koska kukaan ei tiedä sen arvoa p (0), tarvitaan todisteen luomiseen, ja mikä parasta, koko satunnaislukugeneraattori perustuu siihen tosiasiaan, että kukaan ei tiedä tätä arvoa. Siksi on välttämätöntä saada kaikki arvot Hi ja heidän henkilökohtaiset todisteensa oikeellisuuden osoittamiseksi H0.

Kuitenkin, jos elliptisten käyrien pisteissä olisi jokin operaatio, joka on semanttisesti samanlainen kuin kertolasku, oikea todiste H0 olisi triviaalia, varmistaisimme sen vain

H0 × G = p(0)G × H

Jos valittu käyrä tukee elliptisten käyrien parit, tämä todiste toimii. Tässä tapauksessa H0 ei ole vain satunnaislukugeneraattorin tulos, jonka jokainen osaava osallistuja voi tarkistaa G, H. и p(0)G. H0 on myös allekirjoitus viestissä, jota käytettiin siemenenä, mikä vahvistaa sen k и n osallistujat allekirjoittivat tämän viestin. Eli jos siemen - on lohkon tiiviste lohkoketjuprotokollassa H0 on sekä moniallekirjoitus lohkossa että erittäin hyvä satunnaisluku.

lopuksi

Tämä artikkeli on osa teknistä blogisarjaa NEAR. NEAR on lohkoketjuprotokolla ja alusta hajautettujen sovellusten kehittämiseen painottaen kehittämisen helppoutta ja helppokäyttöisyyttä loppukäyttäjille.

Protokollakoodi on avoin, toteutuksemme on kirjoitettu ruosteella, se löytyy täällä.

Voit nähdä miltä NEAR-kehitys näyttää ja kokeilla online-IDE:ssä täällä.

Voit seurata kaikkia uutisia venäjäksi osoitteessa sähkeryhmä ja ryhmä VKontaktessa, ja englanniksi virallisessa viserrys.

Nähdään pian!

Lähde: will.com