Kungenzeka yini ukukhiqiza izinombolo ezingahleliwe uma singathembani? Ingxenye 2

Sawubona Habr!

В ingxenye yokuqala Kulesi sihloko, sixoxisane ngokuthi kungani kungase kudingeke ukukhiqiza izinombolo ezingahleliwe zabahlanganyeli abangathembani, yiziphi izidingo ezibekwa phambili kubakhiqizi bezinombolo abangahleliwe, futhi kubhekwe izindlela ezimbili zokusetshenziswa kwazo.

Kule ngxenye ye-athikili, sizobheka kabanzi enye indlela esebenzisa amasignesha e-threshold.

I-cryptography encane

Ukuze uqonde ukuthi amasignesha e-threshold asebenza kanjani, udinga ukuqonda i-cryptography encane eyisisekelo. Sizosebenzisa imiqondo emibili: ama-scalar, noma izinombolo nje, esizozisho ngezinhlamvu ezincane (x, y) futhi sikhomba ijika eliyi-elliptic, esizolichaza ngosonhlamvukazi.

Ukuze uqonde izisekelo zamasiginesha e-threshold, awudingi ukuqonda ukuthi amajika ama-elliptic asebenza kanjani, ngaphandle kwezinto ezimbalwa eziyisisekelo:

1. Amaphuzu akujiko eliyielliptic angangezwa futhi aphindaphindwe ngesikala (sizosho ukuphindaphinda ngesikala njenge xG, nakuba i-notation Gx futhi evame ukusetshenziswa ezincwadini). Umphumela wokwengeza nokuphindaphinda nge-scalar iphuzu elikujiko eliyi-elliptic.

2. Ukwazi iphuzu kuphela G nomkhiqizo wayo onesikala xG ayikwazi ukubalwa x.

Sizosebenzisa nomqondo we-polynomial p(x) degrees k-1. Ikakhulukazi, sizosebenzisa le mpahla elandelayo yama-polynomials: uma silazi inani p(x) nganoma yisiphi k различных x (futhi asinalo olunye ulwazi mayelana p(x)), singabala p(x) kunoma ubani omunye x.

Kuyathakazelisa ukuthi kunoma iyiphi i-polynomial p(x) futhi iphuzu elithile ejikeni Gukwazi incazelo p(x)G nganoma yisiphi k izincazelo ezahlukene x, singabala futhi p(x)G nganoma yisiphi x.

Lolu ulwazi olwanele lokumba emininingwaneni yokuthi amasiginesha e-threshold asebenza kanjani nokuthi angawasebenzisa kanjani ukukhiqiza izinombolo ezingahleliwe.

Ijeneretha yenombolo engahleliwe kumasiginesha emngceleni

Ake sisho lokho n ababambiqhaza bafuna ukwenza inombolo engahleliwe, futhi sifuna noma ubani abambe iqhaza k kwakukhona okwanele kubo ukukhiqiza inombolo, kodwa ukuze abahlaseli abalawulayo k-1 noma abambalwa ababambiqhaza abakwazanga ukubikezela noma ukuthonya inombolo ekhiqiziwe.

Ake sithi kukhona i-polynomial enjalo p(x) degrees k-1 lokho akwaziyo umhlanganyeli wokuqala p (1), owesibili uyazi p(2), njalo njalo (n- uyazi p(n)). Siphinde sicabange ukuthi ngephuzu elithile elinqunywe kusengaphambili G wonke umuntu uyazi p(x)G kuwo wonke amanani x. Sizofona p(i) "ingxenye yangasese" ith umhlanganyeli (ngoba kuphela iumhlanganyeli th uyamazi), futhi p(i)G "ingxenye yomphakathi" i-umhlanganyeli (ngoba bonke ababambiqhaza bayamazi). Njengoba ukhumbula, ulwazi p(i)G akwanele ukubuyisela p (i).

Ukudala i-polynomial enjalo ukuze kuphela i-Umhlanganyeli wokuqala futhi akekho omunye owayazi ingxenye yakhe yangasese - lena ingxenye eyinkimbinkimbi kakhulu futhi ethakazelisayo yephrothokholi, futhi sizoyihlaziya ngezansi. Okwamanje, ake sicabange ukuthi sine-polynomial enjalo futhi bonke ababambiqhaza bayazazi izingxenye zabo eziyimfihlo.

Singayisebenzisa kanjani i-polynomial enjalo ukuze sikhiqize inombolo engahleliwe? Okokuqala, sidinga intambo ethile engakaze isetshenziswe njengokufaka kujeneretha. Endabeni ye-blockchain, i-hashi yebhulokhi yokugcina h uyikhandidethi elihle lomugqa onjalo. Vumela ababambiqhaza ukuthi bafune ukudala inombolo engahleliwe besebenzisa h njengembewu. Abahlanganyeli baguqula kuqala h ukuya endaweni ethile ejikeni usebenzisa noma yimuphi umsebenzi ochazwe ngaphambilini:

H = scalarToPoint(h)

Bese kuba umhlanganyeli ngamunye i ibala futhi ishicilele Sawubona = p(i)H, bangenzani ngoba bayazi p (i) kanye no-H. Ukudalula Hangibavumeli abanye ababambiqhaza ukuthi babuyisele ingxenye yangasese ith umhlanganyeli, ngakho-ke isethi eyodwa yezingxenye eziyimfihlo ingasetshenziswa ukusuka kubhulokhi kuye kwelinye. Ngakho-ke, i-algorithm ebizayo yesizukulwane se-polynomial echazwe ngezansi idinga ukwenziwa kanye kuphela.

Nini k abahlanganyeli bahlolwe isidumbu Sawubona = p(i)H, wonke umuntu angakwazi ukubala Hx = p(x)H kwabo bonke x sibonga impahla yama-polynomials esixoxile ngayo esigabeni sokugcina. Ngalesi sikhathi, bonke ababambiqhaza bayabala H0 = p(0)H, futhi lena inombolo engahleliwe ewumphumela. Sicela uqaphele ukuthi akekho owaziyo p(0), ngakho-ke ukuphela kwendlela yokubala p(0)H - lokhu ukuhumusha p(x)H, okungenzeka kuphela uma k amanani p(i)H eyaziwayo. Ivula noma yiliphi inani elincane p(i)H ayinikezi nganoma yiluphi ulwazi mayelana p(0)H.

Ijeneretha engenhla inazo zonke izici esizifunayo: abahlaseli abalawula kuphela k-Abahlanganyeli abangu-1 noma ngaphansi abanalo ulwazi noma ithonya esiphethweni, kuyilapho bekhona k ababambiqhaza bangakwazi ukubala inombolo ewumphumela, nanoma iyiphi isethi engaphansi ye k abahlanganyeli bayohlala befika kumphumela ofanayo wembewu efanayo.

Kunenkinga eyodwa esiyigweme ngokucophelela ngenhla. Ukuze ukuhumusha kusebenze, kubalulekile ukuthi inani Hi eyashicilelwa ngumhlanganyeli ngamunye i kwakufana ngempela p(i)H. Njengoba kungekho muntu ngaphandle i-th umhlanganyeli akazi p(i), akekho ngaphandle i-umhlanganyeli akakwazi ukukuqinisekisa lokho Hi empeleni kubalwe ngendlela efanele, futhi ngaphandle kobufakazi be-cryptographic bokulunga Hmina umhlaseli angashicilela noma yiliphi inani njenge Hi, futhi ibe nomthelela ngokunganaki kokukhishwa kwenombolo engahleliwe:

Amanani ahlukile we-H_1 athunyelwe umhlanganyeli wokuqala aholela kumphumela ohlukile othi H_0

Kunezindlela okungenani ezimbili zokufakazela ukunemba Hi, sizozicabangela ngemuva kokuhlaziya isizukulwane se-polynomial.

Isizukulwane se-polynomial

Esigabeni sokugcina sicabange ukuthi sine-polynomial enjalo p(x) degrees k-1 ukuthi umhlanganyeli i uyazi p(i), futhi akekho omunye onolwazi mayelana naleli nani. Esigabeni esilandelayo sizophinde sikudinge lokho ngephuzu elithile elinqunywe kusengaphambili G wonke umuntu wayazi p(x)G kwabo bonke x.

Kulesi sigaba sizothatha ngokuthi umhlanganyeli ngamunye endaweni unokhiye oyimfihlo xi, ukuze wonke umuntu azi ukhiye womphakathi ohambisanayo Xi.

Iphrothokholi eyodwa engenzeka ye-polynomial generation imi kanje:

1. Umhlanganyeli ngamunye i endaweni idala i-polynomial engafanele pi(x) degree k-1. Bese bethumela umhlanganyeli ngamunye j okusho pi(j), ibethelwe ngokhiye womphakathi Xj. Ngakho kuphela i-th и j-th umhlanganyeli uyazi pngi(j). Umhlanganyeli i futhi iyamemezela esidlangalaleni ipi(j)G kwabo bonke j kusukela 1 ukuze k konke.

2. Bonke abahlanganyeli basebenzisa ukuvumelana okuthile ukuze bakhethe k abahlanganyeli okuzosetshenziswa ama-polynomials. Njengoba abanye ababambiqhaza kungenzeka ukuthi abaxhunyiwe ku-inthanethi, asikwazi ukulinda kuze kube yilapho wonke umuntu n abahlanganyeli bazoshicilela ama-polynomials. Umphumela walesi sinyathelo isethi Z ehlanganisa okungenani k ama-polynomials adalwe esinyathelweni (1).

3. Abahlanganyeli baqinisekisa ukuthi amanani abawaziyo pi(j) ihambisane nokumenyezelwe esidlangalaleni ipi(j)G. Ngemva kwalesi sinyathelo Z ama-polynomials kuphela adluliselwa ngasese pi(j) ihambisane nokumenyezelwe esidlangalaleni ipi(j)G.

4. Umhlanganyeli ngamunye j ibala ingxenye yayo yangasese p(j) njengesamba pi(j) kubo bonke i в Z. Umhlanganyeli ngamunye futhi ubala wonke amanani p(x)G njengesamba pi(x)G yabo bonke i в Z.

Uyacelwa ukuthi uqaphele lokho p(x) - ngempela i-polynomial k-1, ngoba iyisamba somuntu ngamunye pi(x), ngayinye eyi-polynomial of degree k-1. Bese, qaphela ukuthi ngenkathi umhlanganyeli ngamunye j uyazi p(j), abanalo ulwazi mayelana p(x) ngoba x j. Ngempela, ukubala leli nani, badinga ukwazi konke i-pi(x), futhi inqobo nje uma umhlanganyeli j ayazi okungenani eyodwa yamapholynomi akhethiwe, ayinalo ulwazi olwanele mayelana nayo p(x).

Lena yonke inqubo yokukhiqiza i-polynomial ebidingeka esigabeni sokugcina. Izinyathelo 1, 2 kanye no-4 ngenhla zinokusebenza okusobala. Kodwa isinyathelo sesi-3 asiyona into encane.

Ngokucacile, sidinga ukwazi ukufakazela lokho kubethelwe pi(j) ihambelana ngempela naleyo eshicilelwe ipi(j)G. Uma singeke sikuqinisekise, umhlaseli i ingase ithumele udoti esikhundleni pi(j) kubahlanganyeli j, kanye nomhlanganyeli j ngeke ikwazi ukuthola inani langempela pi(j), futhi ngeke ikwazi ukubala ingxenye yayo yangasese.

Kukhona i-cryptographic protocol ekuvumela ukuthi udale umlayezo owengeziwe ubufakazii(j), ukuze noma yimuphi umhlanganyeli, onenani elithile e, noma kunjalo ubufakazi(j) и pi(j)G, ingakuqinisekisa endaweni lokho e - kunjalo ngempela pi(j), kubethelwe ngokhiye wombambi qhaza j. Ngeshwa, ubukhulu bobufakazi obunjalo bukhulu ngokumangalisayo, futhi njengoba kudingekile ukuba bushicilelwe O(nk) Ubufakazi obunjalo abukwazi ukusetshenziselwa le njongo.

Esikhundleni sokufakazela lokho i-pi(j) соответствует pi(j)G singabeka isikhathi eside kakhulu kuphrothokholi ye-polynomial generation, lapho bonke ababambiqhaza behlola okubethelwe okutholiwe. pi(j), futhi uma umlayezo osusiwe ungahambisani nomphakathi pi(j)G, bashicilela ubufakazi be-cryptographic bokuthi umlayezo obethelwe abawutholile awulungile. Fakazela ukuthi umyalezo hhayi соответствует i-pi(G) kulula kakhulu kunokufakazela ukuthi kuyahambisana. Kumele kuqashelwe ukuthi lokhu kudinga ukuthi umhlanganyeli ngamunye avele ku-inthanethi okungenani kanye ngesikhathi esabelwe ukudala ubufakazi obunjalo, futhi kuncike ekucabangeni ukuthi uma beshicilela ubufakazi obunjalo, buzofinyelela bonke abanye ababambiqhaza ngesikhathi esifanayo esabelwe.

Uma umhlanganyeli engavelanga ku-inthanethi ngalesi sikhathi, futhi okungenani ube nengxenye eyodwa engalungile, lowo mbambi qhaza ngeke akwazi ukubamba iqhaza ekukhiqizeni izinombolo ezengeziwe. Iphrothokholi, nokho, isazosebenza uma ikhona okungenani k ababambiqhaza abasanda kuthola izingxenye ezilungile noma abakwazile ukushiya ubufakazi bokungalungile ngesikhathi esibekiwe.

Ubufakazi bokulunga kwe-H_i

Ingxenye yokugcina okusamele kuxoxwe ngayo yindlela yokuqinisekisa ukufaneleka kokushicilelwe Hi, okungukuthi Sawubona = p(i)H, ngaphandle kokuvula p (i).

Masikhumbule ukuthi amagugu H, G, p(i)G esidlangalaleni futhi kwaziwa yiwo wonke umuntu. Thola ukusebenza p(i) ukwazi p(i)G и G ebizwa ngokuthi i-discrete logarithm, noma dlog, futhi sifuna ukufakazela ukuthi:

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

ngaphandle kokudalula p(i). Ukwakhiwa kobufakazi obunjalo bukhona, isibonelo I-Schnorr Protocol.

Ngalo mklamo, umhlanganyeli ngamunye, kanye Hi ithumela ubufakazi bokunemba ngokuvumelana nomklamo.

Uma inombolo engahleliwe seyikhiqiziwe, ngokuvamile idinga ukusetshenziswa abahlanganyeli ngaphandle kwalabo abayikhiqizile. Abahlanganyeli abanjalo, kanye nenombolo, kufanele bathumele bonke Hi nobufakazi obuhlobene.

Umfundi othanda ukwazi angase abuze: njengoba inombolo yokugcina engahleliwe ingu H0, futhi p(0)G - Lolu ulwazi olusesidlangalaleni, kungani sidinga ubufakazi bomuntu ngamunye Hi, kungani ungathumeli ubufakazi bokuthi esikhundleni salokho

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

Inkinga ukuthi ubufakazi obunjalo abukwazi ukudalwa kusetshenziswa i-Schnorr Protocol ngoba akekho owazi inani p (0), okudingekayo ukuze udale ubufakazi, futhi ngaphezu kwalokho, yonke i-generator yenombolo engahleliwe isekelwe eqinisweni lokuthi akekho owazi leli nani. Ngakho-ke kuyadingeka ukuba nawo wonke amanani Hi kanye nobufakazi babo ngabanye bokufakazela ukunemba H0.

Kodwa-ke, uma bekunokusebenza okuthile kumaphoyinti kumajika ama-elliptic afana nokuphindaphinda, ubufakazi bokulunga. H0 kungaba yinto encane, sizovele siqinisekise ukuthi

HI-0 × G = p(0)G × H

Uma ijika elikhethiwe lisekela i-elliptic curve pairings, lobu bufakazi buyasebenza. Esimweni esinjalo H0 akukhona nje okukhiphayo kwejeneretha yenombolo engahleliwe, engaqinisekiswa yinoma yimuphi umhlanganyeli owaziyo G, H и p(0)G. H0 futhi iyisiginesha emyalezweni owasetshenziswa njengembewu, okuqinisekisa lokho k и n abahlanganyeli basayine lo mlayezo. Ngakho, uma imbewu - i-hash ye-block ku-protocol ye-blockchain, ke H0 kokubili kuyisignesha eminingi kubhulokhi kanye nenombolo engahleliwe enhle kakhulu.

Ekuphethweni

Lesi sihloko siyingxenye yochungechunge lwebhulogi lobuchwepheshe CISHE. I-NEAR iphrothokholi ye-blockchain kanye nenkundla yokuthuthukisa izinhlelo zokusebenza ezihlukaniselwe izindawo ngokugcizelela ekuthuthukisweni okulula kanye nokusebenziseka kalula kubasebenzisi bokugcina.

Ikhodi yephrothokholi ivuliwe, ukuqaliswa kwethu kubhalwe ku-Rust, ingatholakala lapha.

Ungabona ukuthi intuthuko ye-NEAR ibukeka kanjani futhi uzame ku-IDE eku-inthanethi lapha.

Ungakwazi ukulandela zonke izindaba in Russian at iqembu le-telegram futhi ku iqembu ku-VKontakte, nangesiNgisi esemthethweni twitter.

Sizobonana maduze!

Source: www.habr.com