यदि हामी एकअर्कालाई विश्वास गर्दैनौं भने के अनियमित संख्याहरू उत्पन्न गर्न सम्भव छ? भाग 2

हे हाबर!

В पहिलो भाग यस लेखमा, हामीले एकअर्कालाई विश्वास नगर्ने सहभागीहरूका लागि अनियमित संख्याहरू उत्पन्न गर्न किन आवश्यक हुन सक्छ, त्यस्ता अनियमित संख्या जनरेटरहरूका लागि के आवश्यकताहरू राखिन्छन्, र तिनीहरूको कार्यान्वयनका लागि दुईवटा दृष्टिकोणहरू विचार गर्यौं।

लेखको यस भागमा, हामी थ्रेसहोल्ड हस्ताक्षरहरू प्रयोग गर्ने अर्को दृष्टिकोणलाई नजिकबाट हेर्नेछौं।

अलिकति क्रिप्टोग्राफी

थ्रेसहोल्ड हस्ताक्षरहरूले कसरी काम गर्छ भनेर बुझ्नको लागि, तपाईंले थोरै आधारभूत क्रिप्टोग्राफी बुझ्न आवश्यक छ। हामी दुई अवधारणाहरू प्रयोग गर्नेछौं: स्केलरहरू, वा साधारण संख्याहरू, जसलाई हामीले सानो अक्षरहरू (एक्स, वाई) र अण्डाकार वक्रमा बिन्दुहरू, जसलाई हामी ठूला अक्षरहरूद्वारा बुझाउनेछौं।

थ्रेसहोल्ड हस्ताक्षरहरूको आधारभूत कुराहरू बुझ्न, तपाईंले केही आधारभूत चीजहरू बाहेक, अण्डाकार वक्रहरू कसरी काम गर्छन् भनेर बुझ्न आवश्यक छैन:

1. अण्डाकार वक्रमा बिन्दुहरू थप्न सकिन्छ र स्केलरद्वारा गुणन गर्न सकिन्छ (हामी स्केलरद्वारा गुणनलाई बुझाउनेछौं। xG, यद्यपि नोटेशन Gx साहित्यमा पनि प्रयोग गरिन्छ)। एक स्केलर द्वारा जोड र गुणन को परिणाम एक अण्डाकार वक्र मा एक बिन्दु हो।

2. बिन्दु मात्र थाहा छ G र एक स्केलर संग यसको उत्पादन xG गणना गर्न सकिँदैन x.

हामी बहुपदको अवधारणा पनि प्रयोग गर्नेछौं p (x) डिग्री k-१। विशेष गरी, हामी बहुपदहरूको निम्न गुण प्रयोग गर्नेछौं: यदि हामीलाई मान थाहा छ p (x) कुनै पनि लागि k विभिन्न x (र हामीसँग थप जानकारी छैन p (x)), हामी गणना गर्न सक्छौं p (x) अरू कसैको लागि x.

यो कुनै पनि बहुपद को लागी रोचक छ p (x) र वक्र मा केहि बिन्दु Gअर्थ थाहा छ p(x)G कुनै पनि लागि k विभिन्न अर्थ x, हामी पनि गणना गर्न सक्छौं p(x)G कुनै पनि लागि x.

थ्रेसहोल्ड हस्ताक्षरहरूले कसरी काम गर्छ र अनियमित संख्याहरू उत्पन्न गर्न तिनीहरूलाई कसरी प्रयोग गर्ने भन्ने विवरणहरू खोल्न यो पर्याप्त जानकारी हो।

थ्रेसहोल्ड हस्ताक्षरहरूमा अनियमित संख्या जनरेटर

त्यो भनौं n सहभागीहरू अनियमित संख्या उत्पन्न गर्न चाहन्छन्, र हामी कोही पनि सहभागी भएको चाहन्छौं k त्यहाँ एक संख्या उत्पन्न गर्न पर्याप्त थिए, तर नियन्त्रण गर्ने आक्रमणकारीहरू k-१ वा सोभन्दा कम सहभागीहरूले उत्पन्न भएको सङ्ख्याको अनुमान वा प्रभाव पार्न सकेनन्।

मानौं यस्तो बहुपद छ p (x) डिग्री k-1 पहिलो सहभागीलाई के थाहा छ p (१), दोस्रोलाई थाहा छ p(2), र यस्तै (n- थाहा छ p(n))। हामी पनि केहि पूर्वनिर्धारित बिन्दु को लागी मान्नुहुन्छ G सबैलाई थाहा छ p(x)G सबै मानहरूको लागि x। हामी कल गर्नेछौं p(i) "निजी घटक" iवें सहभागी (किनभने मात्र iसहभागीले उनलाई चिनेको छ), र p(i) G "सार्वजनिक घटक" i-औं सहभागी (किनभने सबै सहभागीहरूले उनलाई चिन्छन्)। जसरी तिमी सम्झन्छौ, ज्ञान p(i) G पुनर्स्थापना गर्न पर्याप्त छैन p(i)

यति मात्रै बहुपद बनाउने i-पहिलो सहभागी र अरू कसैलाई उसको निजी घटक थाहा थिएन - यो प्रोटोकलको सबैभन्दा जटिल र रोचक भाग हो, र हामी यसलाई तल विश्लेषण गर्नेछौं। अहिलेको लागि, मानौं कि हामीसँग यस्तो बहुपद छ र सबै सहभागीहरूलाई उनीहरूको निजी घटकहरू थाहा छ।

हामी कसरी अनियमित संख्या उत्पन्न गर्न यस्तो बहुपद प्रयोग गर्न सक्छौं? सुरु गर्नको लागि, हामीलाई केही स्ट्रिङ चाहिन्छ जुन पहिले जेनेरेटरमा इनपुटको रूपमा प्रयोग गरिएको थिएन। ब्लकचेनको अवस्थामा, अन्तिम ब्लकको ह्यास h यस्तो लाइन को लागी एक राम्रो उम्मेदवार हो। सहभागीहरूलाई प्रयोग गरेर अनियमित संख्या सिर्जना गर्न चाहन्छु h बीउ जस्तै। सहभागीहरू पहिले रूपान्तरण गर्छन् h कुनै पनि पूर्वनिर्धारित प्रकार्य प्रयोग गरेर वक्रमा बिन्दुमा:

H = scalarToPoint(h)

त्यसपछि प्रत्येक सहभागी i गणना र प्रकाशित गर्दछ Hi = p(i)H, तिनीहरूले के गर्न सक्छन् किनभने तिनीहरू जान्दछन् p(i) र H। खुलासा Hम अन्य सहभागीहरूलाई निजी कम्पोनेन्ट पुनर्स्थापना गर्न अनुमति दिँदैन iवें सहभागी, र त्यसैले निजी कम्पोनेन्टहरूको एक सेट ब्लक देखि ब्लकमा प्रयोग गर्न सकिन्छ। तसर्थ, तल वर्णन गरिएको महँगो बहुपद पुस्ता एल्गोरिदम एक पटक मात्र कार्यान्वयन गर्न आवश्यक छ।

कहिले k सहभागीहरूको पोस्टमार्टम गरियो Hi = p(i)H, सबैले गणना गर्न सक्छन् Hx = p(x)H सबैको लागि x हामीले अन्तिम खण्डमा छलफल गरेका बहुपदहरूको गुणलाई धन्यवाद। यस क्षणमा, सबै सहभागीहरूले गणना गर्छन् H0 = p(0) H, र यो परिणामस्वरूप अनियमित संख्या हो। कृपया ध्यान दिनुहोस् कि कसैलाई थाहा छैन p(0), र त्यसैले गणना गर्न एक मात्र तरिका p(0)H - यो interpolation हो p(x)H, जुन तब मात्र सम्भव छ k मानहरू p(i) H ज्ञात। कुनै पनि सानो मात्रा खोल्दै p(i) H बारे कुनै जानकारी प्रदान गर्दैन p(0)H

माथिको जेनेरेटरमा हामीले चाहेका सबै गुणहरू छन्: आक्रमणकारीहरू मात्र नियन्त्रण k-1 सहभागी वा कमसँग निष्कर्षमा कुनै जानकारी वा प्रभाव छैन, जबकि कुनै पनि k सहभागीहरूले नतिजा संख्या, र को कुनै पनि उपसेट गणना गर्न सक्छन् k सहभागीहरू सधैं एउटै बीउको लागि समान परिणाममा आउनेछन्।

हामीले माथि ध्यान दिएर बेवास्ता गरेको एउटा समस्या छ। इन्टरपोलेसन काम गर्नको लागि, यो महत्त्वपूर्ण छ कि मूल्य Hi जुन प्रत्येक सहभागी द्वारा प्रकाशित गरिएको थियो i यो वास्तवमै उस्तै थियो p(i) H किनकि बाहेक कोही छैन i- सहभागीलाई थाहा छैन p(i), बाहेक कोही छैन i-सहभागीले यसलाई प्रमाणित गर्न सक्दैन Hi वास्तवमा सही रूपमा गणना गरिएको छ, र शुद्धताको कुनै क्रिप्टोग्राफिक प्रमाण बिना Hम एक आक्रमणकारीले कुनै पनि मान प्रकाशित गर्न सक्छ नमस्ते, र अनियन्त्रित रूपमा अनियमित संख्या जनरेटरको उत्पादनलाई प्रभाव पार्छ:

पहिलो सहभागीले पठाएको H_1 को विभिन्न मानहरूले H_0 परिणामहरू फरक पार्छ

सही प्रमाणित गर्न कम्तिमा दुई तरिकाहरू छन् Hi, हामीले बहुपदको जेनेरेशनको विश्लेषण गरेपछि हामी तिनीहरूलाई विचार गर्नेछौं।

बहुपद पुस्ता

अन्तिम खण्डमा हामीले मानेका थियौं कि हामीसँग यस्तो बहुपद छ p (x) डिग्री k-१ कि सहभागी i थाहा छ p(i), र अरू कसैसँग यो मानको बारेमा कुनै जानकारी छैन। अर्को खण्डमा हामीलाई केही पूर्वनिर्धारित बिन्दुको लागि पनि आवश्यक हुनेछ G सबैलाई थाहा थियो p(x)G सबैको लागि x.

यस खण्डमा हामी प्रत्येक सहभागीसँग स्थानीय रूपमा केही निजी कुञ्जी छ भनी अनुमान गर्नेछौं xi, यसरी सबैलाई सम्बन्धित सार्वजनिक कुञ्जी थाहा छ Xi.

एक सम्भावित बहुपद पुस्ता प्रोटोकल निम्नानुसार छ:

1. प्रत्येक सहभागी i स्थानीय रूपमा एक स्वैच्छिक बहुपद सिर्जना गर्दछ pi(x) डिग्री k-1। त्यसपछि तिनीहरूले प्रत्येक सहभागीलाई पठाउँछन् j अर्थ pi(j), सार्वजनिक कुञ्जीसँग इन्क्रिप्ट गरिएको Xj। यसरी मात्र i-th и j-th सहभागीलाई थाहा छ pi(j)। सहभागी i सार्वजनिक रूपमा पनि घोषणा गर्दछ pi(j)G सबैको लागि j देखि 1 गर्न k समावेशी।

2. सबै सहभागीहरूले छनौट गर्न केही सहमति प्रयोग गर्छन् k बहुपदहरू प्रयोग गरिने सहभागीहरू। केही सहभागीहरू अफलाइन हुन सक्ने हुनाले, हामी सबैजनासम्म पर्खन सक्दैनौं n सहभागीहरूले बहुपदहरू प्रकाशित गर्नेछन्। यस चरणको परिणाम एक सेट हो Z कम से कम सम्मिलित k चरणमा बनाइएका बहुपदहरू (१).

3. सहभागीहरूले उनीहरूलाई थाहा भएको मानहरू सुनिश्चित गर्छन् pi(j) सार्वजनिक रूपमा घोषणा गरिएको अनुरूप pi(j)G यो चरण पछि Z केवल बहुपदहरू जसका लागि निजी रूपमा प्रसारित pi(j) सार्वजनिक रूपमा घोषणा गरिएको अनुरूप pi(j)G

4. प्रत्येक सहभागी j यसको निजी कम्पोनेन्ट गणना गर्दछ p(j) योगफलको रूपमा pi(j) सबैका लागि i в Z। प्रत्येक सहभागीले सबै मानहरू पनि गणना गर्दछ p(x)G योगफलको रूपमा pi(x)G सबै i को लागी в Z.

त्यो नोट गर्नुहोस् p(x) - यो साँच्चै एक बहुपद हो k-1, किनभने यो व्यक्तिको योगफल हो pi(x), जसमध्ये प्रत्येक डिग्रीको बहुपद हो k-१। त्यसपछि, ध्यान दिनुहोस् कि प्रत्येक सहभागी हुँदा j थाहा छ p(j), उनीहरुलाई कुनै जानकारी छैन p (x) लागि x ≠ j। वास्तवमा, यो मूल्य गणना गर्न, तिनीहरूले सबै कुरा जान्न आवश्यक छ pi(x), र जबसम्म सहभागी j चयन गरिएका बहुपदहरू मध्ये कम्तिमा एउटा थाहा छैन, तिनीहरूसँग पर्याप्त जानकारी छैन p(x)।

यो सम्पूर्ण बहुपद पुस्ता प्रक्रिया हो जुन अन्तिम खण्डमा आवश्यक थियो। माथिको चरण 1, 2 र 4 मा एकदम स्पष्ट कार्यान्वयन छ। तर चरण 3 यति सानो छैन।

विशेष रूपमा, हामीले त्यो इन्क्रिप्टेड प्रमाणित गर्न सक्षम हुन आवश्यक छ pi(j) वास्तवमा प्रकाशित भएकाहरूसँग मेल खान्छ pi(j)G यदि हामीले यो प्रमाणित गर्न सकेनौं भने, आक्रमणकारी i बरु फोहोर पठाउन सक्छ pi(j) सहभागीलाई j, र सहभागी j वास्तविक मूल्य प्राप्त गर्न सक्षम हुनेछैन pi(j), र यसको निजी घटक गणना गर्न सक्षम हुनेछैन.

त्यहाँ एक क्रिप्टोग्राफिक प्रोटोकल छ जसले तपाईंलाई थप सन्देश सिर्जना गर्न अनुमति दिन्छ प्रमाणi(j), जस्तो कि कुनै पनि सहभागी, केहि मूल्य भएको e, र पनि प्रमाण (j) и 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 и G असतत लॉगरिथम भनिन्छ, वा dlog, र हामी प्रमाणित गर्न चाहन्छौं कि:

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

खुलासा बिना p(i)। त्यस्ता प्रमाणहरूको लागि निर्माणहरू अवस्थित छन्, उदाहरणका लागि Schnorr प्रोटोकल.

यस डिजाइनको साथ, प्रत्येक सहभागी, साथमा Hi डिजाइन अनुसार शुद्धता को प्रमाण पठाउँछ।

एक पटक अनियमित संख्या उत्पन्न भएपछि, यो प्रायः यसलाई उत्पन्न गर्नेहरू बाहेक अन्य सहभागीहरूले प्रयोग गर्न आवश्यक छ। त्यस्ता सहभागीहरूले नम्बर सहित, सबैलाई पठाउनु पर्छ Hi र सम्बन्धित प्रमाण।

एक जिज्ञासु पाठकले सोध्न सक्छ: अन्तिम अनियमित संख्या हो H०, र p(0)G - यो सार्वजनिक जानकारी हो, किन हामीलाई प्रत्येक व्यक्तिको लागि प्रमाण चाहिन्छ Hम, यसको सट्टा प्रमाण किन नपठाउनुहोस्

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

समस्या यो छ कि यस्तो प्रमाण Schnorr प्रोटोकल प्रयोग गरेर सिर्जना गर्न सकिँदैन किनभने कसैलाई मान थाहा छैन p (१), प्रमाण सिर्जना गर्न आवश्यक छ, र थप के छ, सम्पूर्ण अनियमित संख्या जेनेरेटर यो मूल्य कसैलाई थाहा छैन भन्ने तथ्यमा आधारित छ। त्यसैले सबै मानहरू हुनु आवश्यक छ Hi र तिनीहरूको व्यक्तिगत प्रमाण शुद्धता प्रमाणित गर्न H0.

यद्यपि, यदि त्यहाँ अण्डाकार वक्रहरूमा बिन्दुहरूमा केही अपरेशनहरू थिए जुन गुणनसँग समान रूपमा मिल्दोजुल्दो छ, शुद्धताको प्रमाण। H0 मामूली हुनेछ, हामी केवल यो सुनिश्चित गर्नेछौं

H0 × G = p(0)G × H

यदि चयन गरिएको वक्र समर्थन गर्दछ अण्डाकार वक्र जोडीहरू, यो प्रमाण काम गर्दछ। यस मामला मा H० भनेको अनियमित संख्या जनरेटरको आउटपुट मात्र होइन, जसलाई थाहा हुने कुनै पनि सहभागीद्वारा प्रमाणित गर्न सकिन्छ। जी, एच и p(0)G एच0 सन्देशमा हस्ताक्षर पनि हो जुन बीजको रूपमा प्रयोग गरिएको थियो, पुष्टि गर्दै k и n सहभागीहरूले यो सन्देशमा हस्ताक्षर गरे। यसरी, यदि बीउ - ब्लकचेन प्रोटोकलमा ब्लकको ह्यास हो, त्यसपछि H0 ब्लकमा बहु-हस्ताक्षर र धेरै राम्रो अनियमित संख्या दुवै हो।

निष्कर्षमा

यो लेख प्राविधिक ब्लग श्रृंखला को एक भाग हो निकट। NEAR एक ब्लकचेन प्रोटोकल र विकेन्द्रीकृत अनुप्रयोगहरू विकास गर्नको लागि प्लेटफर्म हो जसले विकासको सहजता र अन्त प्रयोगकर्ताहरूका लागि प्रयोगको सहजतामा जोड दिन्छ।

प्रोटोकल कोड खुला छ, हाम्रो कार्यान्वयन Rust मा लेखिएको छ, यो फेला पार्न सकिन्छ यहाँ.

तपाईंले NEAR को विकास कस्तो देखिन्छ र अनलाइन IDE मा प्रयोग गर्न सक्नुहुन्छ यहाँ.

तपाईं रूसी मा सबै समाचार पालन गर्न सक्नुहुन्छ टेलिग्राम समूह र भित्र VKontakte मा समूह, र आधिकारिक मा अंग्रेजी मा ट्वीटर.

Встреч скорых встреч!

स्रोत: www.habr.com