જો આપણે એકબીજા પર વિશ્વાસ ન કરીએ તો શું રેન્ડમ નંબરો જનરેટ કરવાનું શક્ય છે? ભાગ 2

હે હબર!

В પ્રથમ ભાગ આ લેખમાં, અમે ચર્ચા કરી હતી કે એકબીજા પર વિશ્વાસ ન કરતા સહભાગીઓ માટે રેન્ડમ નંબર્સ જનરેટ કરવા શા માટે જરૂરી છે, આવા રેન્ડમ નંબર જનરેટર્સ માટે કઈ જરૂરિયાતો આગળ મૂકવામાં આવે છે અને તેના અમલીકરણ માટે બે અભિગમો ધ્યાનમાં લેવામાં આવે છે.

લેખના આ ભાગમાં, અમે થ્રેશોલ્ડ હસ્તાક્ષરોનો ઉપયોગ કરતા અન્ય અભિગમને નજીકથી જોઈશું.

થોડી ક્રિપ્ટોગ્રાફી

થ્રેશોલ્ડ હસ્તાક્ષર કેવી રીતે કાર્ય કરે છે તે સમજવા માટે, તમારે થોડી મૂળભૂત ક્રિપ્ટોગ્રાફી સમજવાની જરૂર છે. અમે બે વિભાવનાઓનો ઉપયોગ કરીશું: સ્કેલર અથવા ફક્ત સંખ્યાઓ, જેને આપણે લોઅરકેસ અક્ષરો દ્વારા સૂચવીશું (x, y) અને લંબગોળ વળાંક પરના બિંદુઓ, જેને આપણે મોટા અક્ષરો દ્વારા દર્શાવીશું.

થ્રેશોલ્ડ હસ્તાક્ષરોની મૂળભૂત બાબતોને સમજવા માટે, તમારે એ સમજવાની જરૂર નથી કે લંબગોળ વણાંકો કેવી રીતે કાર્ય કરે છે, કેટલીક મૂળભૂત બાબતો સિવાય:

1. લંબગોળ વળાંક પરના બિંદુઓને સ્કેલર દ્વારા ઉમેરી અને ગુણાકાર કરી શકાય છે (અમે સ્કેલર દ્વારા ગુણાકારને આ રીતે સૂચવીશું xG, જોકે નોટેશન Gx ઘણીવાર સાહિત્યમાં પણ વપરાય છે). સ્કેલર દ્વારા ઉમેરા અને ગુણાકારનું પરિણામ એ લંબગોળ વળાંક પર એક બિંદુ છે.

2. માત્ર બિંદુ જાણવું G અને તેનું ઉત્પાદન સ્કેલર સાથે xG ગણતરી કરી શકાતી નથી x.

આપણે બહુપદીના ખ્યાલનો પણ ઉપયોગ કરીશું p(x) ડિગ્રી k-1. ખાસ કરીને, આપણે બહુપદીના નીચેના ગુણધર્મનો ઉપયોગ કરીશું: જો આપણે મૂલ્ય જાણીએ p(x) કોઈપણ માટે k વિવિધ x (અને અમારી પાસે તેના વિશે વધુ માહિતી નથી p(x)), અમે ગણતરી કરી શકીએ છીએ p(x) બીજા કોઈ માટે x.

તે રસપ્રદ છે કે કોઈપણ બહુપદી માટે p(x) અને વળાંક પર અમુક બિંદુ Gઅર્થ જાણીને p(x)જી કોઈપણ માટે k વિવિધ અર્થો x, આપણે પણ ગણતરી કરી શકીએ છીએ p(x)જી કોઈપણ માટે x.

થ્રેશોલ્ડ હસ્તાક્ષરો કેવી રીતે કાર્ય કરે છે અને રેન્ડમ નંબરો જનરેટ કરવા માટે તેનો ઉપયોગ કેવી રીતે કરવો તેની વિગતોમાં ખોદવા માટે આ પૂરતી માહિતી છે.

થ્રેશોલ્ડ સહીઓ પર રેન્ડમ નંબર જનરેટર

ચાલો તે કહીએ n સહભાગીઓ રેન્ડમ નંબર જનરેટ કરવા માંગે છે, અને અમે ઈચ્છીએ છીએ કે કોઈપણ ભાગ લે k સંખ્યા જનરેટ કરવા માટે તેમાંના પૂરતા હતા, પરંતુ જેથી હુમલાખોરો જેઓ નિયંત્રણ કરે છે k-1 અથવા તેનાથી ઓછા સહભાગીઓ જનરેટ થયેલ સંખ્યાની આગાહી અથવા પ્રભાવિત કરી શક્યા નથી.

ધારો કે આવી બહુપદી છે p(x) ડિગ્રી k-1 પ્રથમ સહભાગી શું જાણે છે પી (1), બીજો જાણે છે p(2), અને તેથી વધુ (n-મને ખબર છે p(n)). અમે કેટલાક પૂર્વનિર્ધારિત બિંદુ માટે પણ ધારીએ છીએ G બધા જાણે છે p(x)જી બધા મૂલ્યો માટે x. અમે ફોન કરીશું p(i) "ખાનગી ઘટક" iમી સહભાગી (કારણ કે માત્ર iમી સહભાગી તેણીને જાણે છે), અને p(i)જી "જાહેર ઘટક" i-મો સહભાગી (કારણ કે બધા સહભાગીઓ તેણીને જાણે છે). જેમ તમને યાદ છે, જ્ઞાન p(i)જી પુનઃસ્થાપિત કરવા માટે પૂરતું નથી p(i).

આવી બહુપદી બનાવવી જેથી માત્ર i-પ્રથમ સહભાગી અને અન્ય કોઈ તેના ખાનગી ઘટકને જાણતું ન હતું - આ પ્રોટોકોલનો સૌથી જટિલ અને રસપ્રદ ભાગ છે, અને અમે નીચે તેનું વિશ્લેષણ કરીશું. હમણાં માટે, ચાલો ધારીએ કે આપણી પાસે આવો બહુપદી છે અને બધા સહભાગીઓ તેમના ખાનગી ઘટકોને જાણે છે.

રેન્ડમ નંબર બનાવવા માટે આપણે આવા બહુપદીનો ઉપયોગ કેવી રીતે કરી શકીએ? સાથે શરૂ કરવા માટે, અમને કેટલીક સ્ટ્રિંગની જરૂર છે જે અગાઉ જનરેટરમાં ઇનપુટ તરીકે ઉપયોગમાં લેવામાં આવી ન હોય. બ્લોકચેનના કિસ્સામાં, છેલ્લા બ્લોકની હેશ h આવી લાઇન માટે સારો ઉમેદવાર છે. સહભાગીઓ ઉપયોગ કરીને રેન્ડમ નંબર બનાવવા માંગે છે h બીજ જેવું. સહભાગીઓ પ્રથમ કન્વર્ટ થાય છે h કોઈપણ પૂર્વવ્યાખ્યાયિત કાર્યનો ઉપયોગ કરીને વળાંક પરના બિંદુ સુધી:

H = scalarToPoint(h)

પછી દરેક સહભાગી i ગણતરી કરે છે અને પ્રકાશિત કરે છે Hi = p(i)H, તેઓ શું કરી શકે છે કારણ કે તેઓ જાણે છે p(i) અને H. ડિસ્ક્લોઝર Hહું અન્ય સહભાગીઓને ખાનગી ઘટક પુનઃસ્થાપિત કરવાની મંજૂરી આપતો નથી ith સહભાગી, અને તેથી ખાનગી ઘટકોનો એક સમૂહ બ્લોકથી બ્લોક સુધી વાપરી શકાય છે. આમ, નીચે વર્ણવેલ ખર્ચાળ બહુપદી જનરેશન અલ્ગોરિધમ માત્ર એક જ વાર ચલાવવાની જરૂર છે.

જ્યારે k સહભાગીઓનું શબપરીક્ષણ કરવામાં આવ્યું હતું Hi = p(i)H, દરેક વ્યક્તિ ગણતરી કરી શકે છે Hx = p(x)H બધા માટે x બહુપદીની મિલકત માટે આભાર જેની આપણે છેલ્લા વિભાગમાં ચર્ચા કરી છે. આ ક્ષણે, બધા સહભાગીઓ ગણતરી કરે છે H0 = p(0)H, અને આ પરિણામી રેન્ડમ નંબર છે. મહેરબાની કરીને નોંધ કરો કે કોઈને ખબર નથી p(0), અને તેથી ગણતરી કરવાનો એકમાત્ર રસ્તો p(0)H - આ પ્રક્ષેપ છે p(x)H, જે ત્યારે જ શક્ય છે જ્યારે k મૂલ્યો p(i)એચ જાણીતા કોઈપણ નાની માત્રા ખોલવી p(i)એચ વિશે કોઈ માહિતી આપતું નથી p(0)એચ.

ઉપરોક્ત જનરેટરમાં અમને જોઈતી તમામ મિલકતો છે: હુમલાખોરો ફક્ત નિયંત્રિત કરે છે k-1 કે તેથી ઓછા સહભાગીઓ પાસે નિષ્કર્ષ પર કોઈ માહિતી અથવા પ્રભાવ નથી, જ્યારે કોઈપણ k સહભાગીઓ પરિણામી સંખ્યા અને કોઈપણ સબસેટની ગણતરી કરી શકે છે k સહભાગીઓ હંમેશા સમાન બીજ માટે સમાન પરિણામ પર આવશે.

એક સમસ્યા છે જેને આપણે ઉપર ધ્યાનપૂર્વક ટાળી છે. પ્રક્ષેપ કાર્ય કરવા માટે, તે મૂલ્ય છે તે મહત્વનું છે Hi જે દરેક સહભાગી દ્વારા પ્રકાશિત કરવામાં આવી હતી i તે ખરેખર સમાન હતું p(i)એચ. કારણ કે સિવાય કોઈ નથી i-મા સહભાગીને ખબર નથી p(i), સિવાય કોઈ નહીં i-સહભાગી તે ચકાસી શકતા નથી Hi વાસ્તવમાં સાચી ગણતરી કરી છે, અને કોઈપણ ક્રિપ્ટોગ્રાફિક સચોટતાના પુરાવા વિના Hહું એક હુમલાખોર તરીકે કોઈપણ મૂલ્ય પ્રકાશિત કરી શકે છે હાય, અને રેન્ડમ નંબર જનરેટરના આઉટપુટને મનસ્વી રીતે પ્રભાવિત કરે છે:

પ્રથમ સહભાગી દ્વારા મોકલવામાં આવેલ H_1 ના વિવિધ મૂલ્યો વિવિધ પરિણામી H_0 તરફ દોરી જાય છે

સચ્ચાઈ સાબિત કરવાની ઓછામાં ઓછી બે રીતો છે Hi, બહુપદીની પેઢીનું વિશ્લેષણ કર્યા પછી અમે તેમને ધ્યાનમાં લઈશું.

બહુપદી પેઢી

છેલ્લા વિભાગમાં આપણે ધાર્યું કે આપણી પાસે આવી બહુપદી છે p(x) ડિગ્રી k-1 કે સહભાગી i જાણે છે p(i), અને અન્ય કોઈની પાસે આ મૂલ્ય વિશે કોઈ માહિતી નથી. આગળના વિભાગમાં આપણે કેટલાક પૂર્વનિર્ધારિત મુદ્દા માટે પણ તેની જરૂર પડશે G દરેકને ખબર હતી p(x)જી બધા માટે x.

આ વિભાગમાં અમે ધારીશું કે દરેક સહભાગી પાસે સ્થાનિક રીતે કેટલીક ખાનગી કી છે xi, જેથી દરેકને અનુરૂપ સાર્વજનિક કી ખબર હોય Xi.

એક સંભવિત બહુપદી જનરેશન પ્રોટોકોલ નીચે મુજબ છે:

1. દરેક સહભાગી i સ્થાનિક રીતે મનસ્વી બહુપદી બનાવે છે pi(x) ડિગ્રી k-1. પછી તેઓ દરેક સહભાગીને મોકલે છે j અર્થ pi(j), સાર્વજનિક કી સાથે એન્ક્રિપ્ટેડ એક્સજે. આમ માત્ર i-વાય и j-વાય સહભાગી જાણે છે pi(j). સહભાગી i જાહેરમાં પણ જાહેરાત કરે છે pi(j)G બધા માટે j થી 1 માટે k સમાવિષ્ટ

2. બધા સહભાગીઓ પસંદ કરવા માટે કેટલીક સર્વસંમતિનો ઉપયોગ કરે છે k સહભાગીઓ જેમના બહુપદીનો ઉપયોગ કરવામાં આવશે. કેટલાક સહભાગીઓ ઑફલાઇન હોઈ શકે છે, તેથી અમે દરેક જણ સુધી રાહ જોઈ શકતા નથી n સહભાગીઓ બહુપદી પ્રકાશિત કરશે. આ પગલાનું પરિણામ સમૂહ છે Z ઓછામાં ઓછા સમાવેશ થાય છે k પગલામાં બનાવેલ બહુપદીઓ (1).

3. સહભાગીઓ ખાતરી કરે છે કે તેઓ જે મૂલ્યો જાણે છે pi(j) જાહેરમાં જાહેર કરેલ અનુરૂપ pi(j)G આ પગલા પછી Z માત્ર બહુપદીઓ જેના માટે ખાનગી રીતે પ્રસારિત થાય છે pi(j) જાહેરમાં જાહેર કરેલ અનુરૂપ pi(j)G

4. દરેક સહભાગી j તેના ખાનગી ઘટકની ગણતરી કરે છે p(j) રકમ તરીકે pi(j) બધા માટે i в Z. દરેક સહભાગી તમામ મૂલ્યોની ગણતરી પણ કરે છે p(x)જી રકમ તરીકે બધા i માટે pi(x)G в Z.

તે નોંધ લો p(x) - તે ખરેખર બહુપદી છે k-1, કારણ કે તે વ્યક્તિનો સરવાળો છે pi(x), જેમાંથી દરેક ડિગ્રીની બહુપદી છે k-1. પછી, નોંધ કરો કે જ્યારે દરેક સહભાગી j જાણે છે p(j), તેમની પાસે કોઈ માહિતી નથી p(x) માટે x ≠ જે. ખરેખર, આ મૂલ્યની ગણતરી કરવા માટે, તેમને બધું જાણવાની જરૂર છે pi(x), અને જ્યાં સુધી સહભાગી છે j ઓછામાં ઓછા એક પસંદ કરેલ બહુપદીને જાણતા નથી, તેમની પાસે તેના વિશે પૂરતી માહિતી નથી p(x).

આ સમગ્ર બહુપદી જનરેશન પ્રક્રિયા છે જેની છેલ્લા વિભાગમાં જરૂર હતી. ઉપરોક્ત પગલાં 1, 2 અને 4 માં એકદમ સ્પષ્ટ અમલીકરણ છે. પરંતુ પગલું 3 એટલું તુચ્છ નથી.

ખાસ કરીને, અમારે તે એનક્રિપ્ટેડ સાબિત કરવામાં સમર્થ હોવું જરૂરી છે pi(j) ખરેખર પ્રકાશિત થયેલાઓને અનુરૂપ છે pi(j)G જો અમે તેને સાબિત કરી શકતા નથી, તો હુમલાખોર i તેના બદલે કચરો મોકલી શકે છે pi(j) સહભાગીને j, અને સહભાગી j વાસ્તવિક અર્થ મેળવી શકશે નહીં pi(j), અને તેના ખાનગી ઘટકની ગણતરી કરી શકશે નહીં.

એક ક્રિપ્ટોગ્રાફિક પ્રોટોકોલ છે જે તમને વધારાનો સંદેશ બનાવવાની મંજૂરી આપે છે સાબિતીi(j), જેમ કે કોઈ પણ સહભાગી, અમુક મૂલ્ય ધરાવે છે e, અને પણ સાબિતી(જે) и pi(j)G, સ્થાનિક રીતે તે ચકાસી શકે છે e - તે ખરેખર pi(j), સહભાગીની કી સાથે એન્ક્રિપ્ટેડ j. કમનસીબે, આવા પુરાવાનું કદ અવિશ્વસનીય રીતે મોટું છે, અને તે જોતાં તે પ્રકાશિત કરવું જરૂરી છે. O(nk) આ હેતુ માટે આવા પુરાવાનો ઉપયોગ કરી શકાતો નથી.

તે સાબિત કરવાને બદલે pi(j) соответствует pi(j)G અમે બહુપદી જનરેશન પ્રોટોકોલમાં ઘણો લાંબો સમય ફાળવી શકીએ છીએ, જે દરમિયાન તમામ સહભાગીઓ પ્રાપ્ત થયેલ એનક્રિપ્ટેડ તપાસે છે. pi(j), અને જો ડિક્રિપ્ટેડ સંદેશ જાહેર જનતાને અનુરૂપ ન હોય pi(j)G, તેઓ ક્રિપ્ટોગ્રાફિક સાબિતી પ્રકાશિત કરે છે કે તેઓને મળેલો એનક્રિપ્ટેડ સંદેશ ખોટો છે. તે સંદેશ સાબિત કરો નથી соответствует pi(G) તે મેળ ખાય છે તે સાબિત કરવા કરતાં ઘણું સરળ. એ નોંધવું જોઈએ કે આ માટે દરેક સહભાગીએ આવા પુરાવા બનાવવા માટે ફાળવેલ સમય દરમિયાન ઓછામાં ઓછા એક વખત ઑનલાઇન હાજર થવું જરૂરી છે, અને તે ધારણા પર આધાર રાખે છે કે જો તેઓ આવા પુરાવા પ્રકાશિત કરે છે, તો તે સમાન ફાળવવામાં આવેલા સમયમાં અન્ય તમામ સહભાગીઓ સુધી પહોંચશે.

જો કોઈ સહભાગી આ સમયગાળા દરમિયાન ઓનલાઈન દેખાયો નહિ, અને તેની પાસે ઓછામાં ઓછો એક ખોટો ઘટક હશે, તો તે ચોક્કસ સહભાગી આગળની સંખ્યા જનરેશનમાં ભાગ લઈ શકશે નહીં. પ્રોટોકોલ, જો કે, ઓછામાં ઓછું હોય તો પણ કાર્ય કરશે k સહભાગીઓ કે જેમણે હમણાં જ યોગ્ય ઘટકો પ્રાપ્ત કર્યા છે અથવા ફાળવેલ સમયની અંદર અયોગ્યતાનો પુરાવો છોડવામાં વ્યવસ્થાપિત છે.

H_i ની સાચીતાના પુરાવા

છેલ્લો ભાગ જેની ચર્ચા કરવાનું બાકી છે તે એ છે કે પ્રકાશિતની સાચીતા કેવી રીતે સાબિત કરવી Hહું, એટલે કે Hi = p(i)H, ખોલ્યા વિના p(i).

ચાલો યાદ રાખો કે મૂલ્યો H, G, p(i)G જાહેર અને દરેક માટે જાણીતું. ઓપરેશન મેળવો p(i) જાણવું p(i)જી и G સ્વતંત્ર લઘુગણક કહેવાય છે, અથવા dlog અને અમે તે સાબિત કરવા માંગીએ છીએ:

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

જાહેરાત વિના p(i). ઉદાહરણ તરીકે, આવા પુરાવા માટે બાંધકામો અસ્તિત્વમાં છે શ્નોર પ્રોટોકોલ.

આ ડિઝાઇન સાથે, દરેક સહભાગી, સાથે Hi ડિઝાઇન અનુસાર શુદ્ધતાનો પુરાવો મોકલે છે.

એકવાર રેન્ડમ નંબર જનરેટ થઈ જાય, તે પછી તેને જનરેટ કરનારાઓ સિવાય અન્ય સહભાગીઓ દ્વારા તેનો ઉપયોગ કરવાની જરૂર પડે છે. આવા સહભાગીઓ, નંબર સાથે, બધાને મોકલવાના રહેશે Hi અને સંબંધિત પુરાવા.

એક જિજ્ઞાસુ વાચક પૂછી શકે છે: કારણ કે અંતિમ રેન્ડમ નંબર છે H0, અને p(0)જી - આ જાહેર માહિતી છે, શા માટે અમને દરેક વ્યક્તિ માટે પુરાવાની જરૂર છે Hહું, તેના બદલે પુરાવા કેમ ન મોકલો

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

સમસ્યા એ છે કે શ્નોર પ્રોટોકોલનો ઉપયોગ કરીને આવી સાબિતી બનાવી શકાતી નથી કારણ કે કોઈ તેની કિંમત જાણતું નથી પી (0), સાબિતી બનાવવા માટે જરૂરી છે, અને વધુ શું છે, સમગ્ર રેન્ડમ નંબર જનરેટર એ હકીકત પર આધારિત છે કે આ મૂલ્ય કોઈને ખબર નથી. તેથી તમામ મૂલ્યો હોવા જરૂરી છે Hi અને સચ્ચાઈ સાબિત કરવા માટે તેમના વ્યક્તિગત પુરાવા H0.

જો કે, જો લંબગોળ વણાંકો પરના બિંદુઓ પર અમુક કામગીરી હોય જે અર્થપૂર્ણ રીતે ગુણાકારની સમાન હોય, તો સાચીતાનો પુરાવો H0 તુચ્છ હશે, અમે ફક્ત તેની ખાતરી કરીશું

H0 × G = p(0)G × H

જો પસંદ કરેલ વળાંક આધાર આપે છે લંબગોળ વળાંકની જોડી, આ સાબિતી કામ કરે છે. આ બાબતે H0 એ ફક્ત રેન્ડમ નંબર જનરેટરનું આઉટપુટ નથી, જે કોઈપણ સહભાગી દ્વારા ચકાસી શકાય છે જે જાણે છે જી, એચ и p(0)જી. એચ0 એ સંદેશ પર એક સહી પણ છે જેનો ઉપયોગ બીજ તરીકે કરવામાં આવ્યો હતો, તેની પુષ્ટિ કરે છે k и n સહભાગીઓએ આ સંદેશ પર હસ્તાક્ષર કર્યા. આમ, જો બીજ - પછી બ્લોકચેન પ્રોટોકોલમાં બ્લોકની હેશ છે H0 બ્લોક પરની બહુ-સહી અને ખૂબ સારી રેન્ડમ સંખ્યા બંને છે.

અંતમા

આ લેખ તકનીકી બ્લોગ શ્રેણીનો એક ભાગ છે NEAR. NEAR એ બ્લોકચેન પ્રોટોકોલ અને અંતિમ વપરાશકર્તાઓ માટે વિકાસની સરળતા અને ઉપયોગમાં સરળતા પર ભાર સાથે વિકેન્દ્રિત એપ્લિકેશનો વિકસાવવા માટેનું પ્લેટફોર્મ છે.

પ્રોટોકોલ કોડ ખુલ્લો છે, અમારું અમલીકરણ રસ્ટમાં લખાયેલું છે, તે શોધી શકાય છે અહીં.

તમે NEAR માટે વિકાસ કેવો દેખાય છે તે જોઈ શકો છો અને ઓનલાઈન IDE માં પ્રયોગ કરી શકો છો અહીં.

તમે રશિયનમાંના તમામ સમાચારને અહીં અનુસરી શકો છો ટેલિગ્રામ જૂથ અને અંદર VKontakte પર જૂથ, અને સત્તાવારમાં અંગ્રેજીમાં પક્ષીએ.

ફરી મળ્યા!

સોર્સ: www.habr.com