Ĉu eblas generi hazardajn nombrojn se ni ne fidas unu la alian? Parto 2

Hej Habr!

В la unua parto En ĉi tiu artikolo, ni diskutis kial eble necesus generi hazardajn nombrojn por partoprenantoj, kiuj ne fidas unu la alian, kiaj postuloj estas prezentitaj por tiaj hazardaj nombrogeneratoroj, kaj konsideris du alirojn al ilia efektivigo.

En ĉi tiu parto de la artikolo, ni pli detale rigardos alian aliron, kiu uzas sojlaj subskriboj.

Iom da kriptografio

Por kompreni kiel funkcias sojlaj subskriboj, vi devas kompreni iom bazan kriptografion. Ni uzos du konceptojn: skalarojn, aŭ simple nombrojn, kiujn ni signos per minusklaj literoj (x, y) kaj punktoj sur la elipsa kurbo, kiun ni signos per majuskloj.

Por kompreni la bazojn de sojlaj subskriboj, vi ne bezonas kompreni kiel funkcias elipsaj kurboj, krom kelkaj bazaj aferoj:

1. Poentoj sur elipsa kurbo povas esti aldonitaj kaj multobligitaj per skalaro (ni signos multiplikon per skalaro kiel xG, kvankam la notacio Gx ankaŭ ofte uzata en la literaturo). La rezulto de adicio kaj multipliko per skalaro estas punkto sur elipsa kurbo.

2. Sciante nur la punkton G kaj ĝia produkto kun skalaro xG ne povas esti kalkulita x.

Ni ankaŭ uzos la koncepton de polinomo p(x) gradoj k-1. Precipe, ni uzos la jenan econ de polinomoj: se ni konas la valoron p(x) por iu ajn k malsamaj x (kaj ni ne havas pliajn informojn pri p(x)), ni povas kalkuli p(x) por iu ajn alia x.

Estas interese, ke por iu ajn polinomo p(x) kaj iu punkto sur la kurbo Gsciante la signifon p(x)G por iu ajn k malsamaj signifoj x, ni povas ankaŭ kalkuli p(x)G por iu ajn x.

Ĉi tio estas sufiĉa informo por enfosi la detalojn pri kiel funkcias sojlaj subskriboj kaj kiel uzi ilin por generi hazardajn nombrojn.

Hazarda nombrogeneratoro sur sojlaj subskriboj

Ni diru tion n partoprenantoj volas generi hazardan nombron, kaj ni volas ke iu ajn partoprenu k estis sufiĉe da ili por generi nombron, sed tiel ke la atakantoj kiuj kontrolas k-1 aŭ malpli da partoprenantoj ne povis antaŭdiri aŭ influi la nombron generitan.

Supozu ke ekzistas tia polinomo p(x) gradoj k-1 kion la unua partoprenanto scias p (1), la dua scias p(2), kaj tiel plu (n-th scias p(n)). Ni ankaŭ supozas ke por iu antaŭdeterminita punkto G ĉiu scias p(x)G por ĉiuj valoroj x. Ni vokos p(i) "privata komponanto" ila partoprenanto (ĉar nur ila-a partoprenanto konas ŝin), kaj p(i)G "publika ero" i-th partoprenanto (ĉar ĉiuj partoprenantoj konas ŝin). Kiel vi memoras, scio p(i)G ne sufiĉas por restarigi p(i).

Kreante tian polinomon tiel ke nur i-La unua partoprenanto kaj neniu alia konis sian privatan komponanton - ĉi tio estas la plej kompleksa kaj interesa parto de la protokolo, kaj ni analizos ĝin sube. Nuntempe, ni supozu, ke ni havas tian polinomon kaj ĉiuj partoprenantoj konas siajn privatajn komponantojn.

Kiel ni povas uzi tian polinomon por generi hazardan nombron? Komence, ni bezonas iun ŝnuron, kiu antaŭe ne estis uzata kiel enigo al la generatoro. En la kazo de blokĉeno, la hash de la lasta bloko h estas bona kandidato por tia linio. Lasu partoprenantojn volas krei hazardan nombron uzante h kiel semo. Partoprenantoj unue konvertas h al punkto sur la kurbo uzante ajnan antaŭdifinitan funkcion:

H = skalaroAlPunkto(h)

Poste ĉiu partoprenanto i kalkulas kaj publikigas Hi = p(i)H, kion ili povas fari ĉar ili scias p (i) kaj H. Malkaŝado Hmi ne permesas aliajn partoprenantojn restarigi la privatan komponanton ith partoprenanto, kaj tial unu aro de privataj komponantoj povas esti uzata de bloko al bloko. Tiel, la multekosta polinoma genera algoritmo priskribita malsupre nur devas esti efektivigita unufoje.

Kiam k partoprenantoj estis nekropsiitaj Hi = p(i)H, ĉiuj povas kalkuli Hx = p(x)H por ĉiuj x danke al la eco de polinomoj, kiun ni diskutis en la lasta sekcio. En ĉi tiu momento, ĉiuj partoprenantoj kalkulas H0 = p(0)H, kaj ĉi tiu estas la rezulta hazarda nombro. Bonvolu noti, ke neniu scias p(0), kaj tial la sola maniero por kalkuli p(0)H – ĉi tio estas interpolado p(x)H, kio eblas nur kiam k valoroj p(i)H konata. Malfermante ajnan pli malgrandan kvanton p(i)H ne provizas ajnan informon pri p(0)H.

La generatoro supre havas ĉiujn ecojn, kiujn ni volas: atakantoj kontrolante nur k-1 partoprenantoj aŭ malpli havas neniun informon aŭ influon sur la konkludo, dum iu ajn k partoprenantoj povas kalkuli la rezultan nombron, kaj ajnan subaron de k partoprenantoj ĉiam venos al la sama rezulto por la sama semo.

Estas unu problemo, kiun ni zorge evitis supre. Por ke interpolado funkciu, gravas ke la valoro Hi kiu estis publikigita de ĉiu partoprenanto i vere estis la sama p(i)H. Ĉar neniu krom i-a partoprenanto ne scias p(i), neniu krom i-la partoprenanto ne povas kontroli tion Hi efektive kalkulite ĝuste, kaj sen ajna ĉifrika pruvo de ĝusteco Hi atakanto povas publikigi ajnan valoron kiel Saluton, kaj arbitre influas la produktadon de la hazarda nombrogeneratoro:

Malsamaj valoroj de H_1 senditaj de la unua partoprenanto kondukas al malsama rezulta H_0

Estas almenaŭ du manieroj pruvi ĝustecon Hi, ni konsideros ilin post kiam ni analizos la generacion de la polinomo.

Polinoma generacio

En la lasta sekcio ni supozis ke ni havas tian polinomon p(x) gradoj k-1 ke la partoprenanto i scias p(i), kaj neniu alia havas informojn pri ĉi tiu valoro. En la sekva sekcio ni ankaŭ bezonos tion por iu antaŭdeterminita punkto G ĉiuj sciis p(x)G por ĉiuj x.

En ĉi tiu sekcio ni supozos, ke ĉiu partoprenanto loke havas iun privatan ŝlosilon xi, tia ke ĉiuj konas la respondan publikan ŝlosilon Xi.

Unu ebla polinoma generacioprotokolo estas kiel sekvas:

1. Ĉiu partoprenanto i loke kreas arbitran polinomon pi(x) grado k-1. Ili tiam sendas ĉiun partoprenanton j signifo pi(j), ĉifrita per publika ŝlosilo Xj. Tiel nur i-th и j-th partoprenanto scias pi(j). Partoprenanto i ankaŭ publike anoncas pi(j)G por ĉiuj j el 1 por k inkluziva.

2. Ĉiuj partoprenantoj uzas iom da konsento por elekti k partoprenantoj, kies polinomoj estos uzataj. Ĉar iuj partoprenantoj povas esti eksterrete, ni ne povas atendi ĝis ĉiuj n partoprenantoj publikigos polinomojn. La rezulto de ĉi tiu paŝo estas aro Z konsistanta el almenaŭ k polinomoj kreitaj en paŝo (1).

3. Partoprenantoj certigas, ke la valoroj ili konas pi(j) respondas al publike anoncita pi(j)G. Post ĉi tiu paŝo en Z nur polinomoj por kiuj private transdonitaj pi(j) respondas al publike anoncita pi(j)G.

4. Ĉiu partoprenanto j kalkulas ĝian privatan komponanton p(j) kiel sumo pi(j) por ĉiuj i в Z. Ĉiu partoprenanto ankaŭ kalkulas ĉiujn valorojn p(x)G kiel sumo pi(x)G por ĉiuj i в Z.

notu tion p(x) – ĝi estas vere polinomo k-1, ĉar ĝi estas la sumo de la individuo pi(x), ĉiu el kiuj estas polinomo de grado k-1. Tiam, notu ke dum ĉiu partoprenanto j scias p(j), ili ne havas informojn pri p(x) por x ≠ j. Efektive, por kalkuli ĉi tiun valoron, ili bezonas scii ĉion pi(x), kaj tiel longe kiel la partoprenanto j ne konas almenaŭ unu el la elektitaj polinomoj, ili ne havas sufiĉajn informojn pri p(x).

Ĉi tio estas la tuta polinoma genera procezo, kiu estis bezonata en la lasta sekcio. Paŝoj 1, 2 kaj 4 supre havas sufiĉe evidentan efektivigon. Sed paŝo 3 ne estas tiel bagatela.

Specife, ni devas povi pruvi tion ĉifrita pi(j) vere respondas al la publikigitaj pi(j)G. Se ni ne povas pruvi tion, la atakanto i eble sendi rubon anstataŭe pi(j) al partoprenanto j, kaj partoprenanto j ne povos akiri la veran signifon pi(j), kaj ne povos kalkuli ĝian privatan komponanton.

Estas kripta protokolo, kiu permesas krei plian mesaĝon pruvoi(j), tia ke iu ajn partoprenanto, havanta ian valoron e, siavice pruvo(j) и pi(j)G, povas loke kontroli tion e - estas vere pi(j), ĉifrite per la ŝlosilo de la partoprenanto j. Bedaŭrinde, la grandeco de tiaj pruvoj estas nekredeble granda, kaj konsiderante ke necesas publikigi O (nk) Tia pruvo ne povas esti uzata por ĉi tiu celo.

Anstataŭ pruvi tion pi(j) соответствует pi(j)G ni povas asigni tre longan tempon en la polinoma generacioprotokolo, dum kiu ĉiuj partoprenantoj kontrolas la ricevitan ĉifritan. pi(j), kaj se la deĉifrita mesaĝo ne respondas al la publiko pi(j)G, ili publikigas kriptografan pruvon ke la ĉifrita mesaĝo kiun ili ricevis estas malĝusta. Pruvu ke la mesaĝo ne соответствует pi(G) multe pli facile ol pruvi, ke ĝi kongruas. Oni devas rimarki, ke tio postulas, ke ĉiu partoprenanto aperu interrete almenaŭ unufoje dum la tempo asignita por krei tiajn pruvojn, kaj dependas de la supozo, ke se ili publikigos tian pruvon, ĝi atingos ĉiujn aliajn partoprenantojn en la sama asignita tempo.

Se partoprenanto ne aperis interrete dum tiu ĉi tempodaŭro, kaj li ja havis almenaŭ unu malĝustan komponanton, tiam tiu aparta partoprenanto ne povos partopreni en plua nombrogenerado. La protokolo tamen ankoraŭ funkcios se almenaŭ ekzistas k partoprenantoj, kiuj aŭ ĵus ricevis la ĝustajn komponantojn aŭ sukcesis lasi pruvon de neĝusteco en la asignita tempo.

Pruvoj de ĝusteco de H_i

La lasta parto, kiu restas por diskuti, estas kiel pruvi la ĝustecon de eldonita Hi, nome tio Hi = p(i)H, sen malfermo p(i).

Ni memoru ke la valoroj H, G, p(i)G publikaj kaj konataj de ĉiuj. Ricevu operacion p(i) sciante p(i)G и G nomita diskreta logaritmo, aŭ dlog, kaj ni volas pruvi tion:

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

sen malkaŝo p(i). Konstruoj por tiaj pruvoj ekzistas, ekzemple Protokolo Schnorr.

Kun ĉi tiu dezajno, ĉiu partoprenanto, kune kun Hi sendas pruvon de ĝusteco laŭ la dezajno.

Post kiam hazarda nombro estas generita, ĝi ofte devas esti uzata de partoprenantoj krom tiuj, kiuj generis ĝin. Tiaj partoprenantoj, kune kun la nombro, devas sendi ĉiujn Hi kaj rilata evidenteco.

Sciema leganto povas demandi: ĉar la fina hazarda nombro estas H0, kaj p(0)G – Ĉi tio estas publika informo, kial ni bezonas pruvon por ĉiu individuo Hmi, kial ne sendi pruvon tion anstataŭe

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

La problemo estas, ke tia pruvo ne povas esti kreita per la Schnorr-Protokolo ĉar neniu scias la valoron p (0), necesa por krei la pruvon, kaj kio estas pli, la tuta hazarda nombrogeneratoro baziĝas sur tio, ke neniu konas ĉi tiun valoron. Tial necesas havi ĉiujn valorojn Hi kaj ilia individua pruvo por pruvi ĝustecon H0.

Tamen, se ekzistus iu operacio sur punktoj sur elipsaj kurboj kiu estas semantike simila al multipliko, la pruvo de ĝusteco H0 estus bagatela, ni simple certigus tion

H0 × G = p(0)G × H

Se la elektita kurbo subtenas elipsaj kurbaj paroj, ĉi tiu pruvo funkcias. Tiuokaze H0 estas ne nur la eligo de hazarda nombrogeneratoro, kiu povas esti kontrolita de iu ajn partoprenanto kiu scias G, H и p(0)G. H0 ankaŭ estas subskribo sur la mesaĝo kiu estis uzata kiel semo, konfirmante tion k и n partoprenantoj subskribis ĉi tiun mesaĝon. Tiel, se semo - estas la haŝo de la bloko en la protokolo de blokĉeno, do H0 estas kaj multsubskribo sur bloko kaj tre bona hazarda nombro.

En konkludo

Ĉi tiu artikolo estas parto de teknika blogserio PROKSIME. NEAR estas blokĉena protokolo kaj platformo por disvolvi malcentralizitajn aplikojn kun emfazo de facileco de disvolviĝo kaj facileco de uzo por finaj uzantoj.

La protokola kodo estas malfermita, nia efektivigo estas skribita en Rust, ĝi troveblas tie.

Vi povas vidi kiel aspektas evoluo por NEAR kaj eksperimenti en la reta IDE tie.

Vi povas sekvi ĉiujn novaĵojn en la rusa ĉe telegrama grupo kaj en grupo ĉe VKontakte, kaj en la angla en la oficiala twitter.

Ĝis baldaŭ!

fonto: www.habr.com