यदि हम एक-दूसरे पर भरोसा नहीं करते हैं तो क्या यादृच्छिक संख्याएँ उत्पन्न करना संभव है? भाग 2

हे हबर!

В पहले भाग इस लेख में, हमने चर्चा की कि उन प्रतिभागियों के लिए यादृच्छिक संख्याएं उत्पन्न करना क्यों आवश्यक हो सकता है जो एक-दूसरे पर भरोसा नहीं करते हैं, ऐसे यादृच्छिक संख्या जनरेटरों के लिए क्या आवश्यकताएं रखी जाती हैं, और उनके कार्यान्वयन के दो तरीकों पर विचार किया।

लेख के इस भाग में, हम थ्रेशोल्ड सिग्नेचर का उपयोग करने वाले एक अन्य दृष्टिकोण पर करीब से नज़र डालेंगे।

क्रिप्टोग्राफी का थोड़ा सा ज्ञान

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

थ्रेशोल्ड सिग्नेचर की मूल बातें समझने के लिए, आपको यह समझने की आवश्यकता नहीं है कि दीर्घवृत्तीय वक्र कैसे काम करते हैं, कुछ बुनियादी बातों को छोड़कर:

1. एक दीर्घवृत्तीय वक्र पर बिंदुओं को एक अदिश से जोड़ा और गुणा किया जा सकता है (हम एक अदिश से गुणन को इस प्रकार निरूपित करेंगे) xG, हालांकि संकेतन Gx (साहित्य में भी अक्सर इस्तेमाल किया जाता है) एक अदिश द्वारा जोड़ और गुणा का परिणाम एक दीर्घवृत्तीय वक्र पर एक बिंदु होता है।

2. केवल बिंदु जानना G और इसका उत्पाद एक अदिश राशि के साथ xG गणना नहीं की जा सकती x.

हम बहुपद की अवधारणा का भी उपयोग करेंगे p (x) डिग्री k-1. विशेष रूप से, हम बहुपदों के निम्नलिखित गुण का उपयोग करेंगे: यदि हम मान जानते हैं p (x) किसी भी k विभिन्न x (और हमारे पास इसके बारे में अधिक जानकारी नहीं है p (x)), हम गणना कर सकते हैं p (x) किसी अन्य के लिए x.

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

यह जानकारी यह जानने के लिए पर्याप्त है कि थ्रेशोल्ड सिग्नेचर किस प्रकार काम करते हैं तथा यादृच्छिक संख्याएं उत्पन्न करने के लिए उनका उपयोग किस प्रकार किया जाता है।

थ्रेशोल्ड सिग्नेचर पर रैंडम नंबर जनरेटर

चलिए मान लेते हैं कि n प्रतिभागी एक यादृच्छिक संख्या उत्पन्न करना चाहते हैं, और हम चाहते हैं कि हर कोई भाग ले k उनमें से एक संख्या उत्पन्न करने के लिए पर्याप्त थे, लेकिन इतना कि हमलावर जो नियंत्रण करते हैं k-1 या इससे कम प्रतिभागी उत्पन्न संख्या का पूर्वानुमान नहीं लगा सकते थे या उसे प्रभावित नहीं कर सकते थे।

आइए मान लें कि ऐसा एक बहुपद है p (x) डिग्री k-1, पहला प्रतिभागी क्या जानता है पी (1), दूसरा जानता है पी(2), और इसी तरह (n-वें जानता है पी(एन)) आइए हम यह भी मान लें कि किसी पूर्व निर्धारित बिंदु के लिए G सब जानते हैं पी(x)जी सभी मानों के लिए xहम कॉल करेंगे पी(आई) "निजी घटक" i-वें प्रतिभागी (क्योंकि केवल i-वें प्रतिभागी उसे जानता है), और सुअर "सार्वजनिक घटक" i-वें प्रतिभागी (क्योंकि सभी प्रतिभागी यह जानते हैं)। जैसा कि आपको याद होगा, ज्ञान सुअर बहाल करने के लिए पर्याप्त नहीं पी(आई).

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

हम इस तरह के बहुपद का उपयोग यादृच्छिक संख्या उत्पन्न करने के लिए कैसे कर सकते हैं? सबसे पहले, हमें कुछ स्ट्रिंग की आवश्यकता है जिसका उपयोग जनरेटर में इनपुट के रूप में पहले नहीं किया गया है। ब्लॉकचेन के मामले में, अंतिम ब्लॉक का हैश h — ऐसी स्ट्रिंग के लिए एक अच्छा उम्मीदवार है। प्रतिभागियों को एक यादृच्छिक संख्या उत्पन्न करने के लिए उपयोग करने दें h बीज के रूप में। प्रतिभागी पहले परिवर्तित होते हैं h किसी भी पूर्वनिर्धारित फ़ंक्शन का उपयोग करके वक्र पर किसी बिंदु पर:

H = स्केलरटूपॉइंट(h)

फिर प्रत्येक प्रतिभागी i गणना और प्रकाशन हाय = पी(आई)एच, वे क्या कर सकते हैं क्योंकि वे जानते हैं पी(i) और एच. प्रकटीकरण Hi अन्य प्रतिभागियों को निजी घटक को पुनर्स्थापित करने की अनुमति नहीं देता है i-वें प्रतिभागी, और इसलिए निजी घटकों का एक सेट ब्लॉक से ब्लॉक तक इस्तेमाल किया जा सकता है। इस प्रकार, नीचे वर्णित महंगी बहुपद पीढ़ी एल्गोरिथ्म को केवल एक बार निष्पादित करने की आवश्यकता है।

जब k प्रतिभागियों को उजागर किया गया हाय = पी(आई)एच, हर कोई इसका पता लगा सकता है Hएक्स = पी(एक्स)एच सभी के लिए x बहुपदों के गुण के कारण, जिस पर हमने पिछले अनुभाग में चर्चा की थी। इस बिंदु पर, सभी प्रतिभागी गणना करते हैं H0 = पी(0)एच, और यह परिणामी यादृच्छिक संख्या है। ध्यान दें कि कोई नहीं जानता पी(0), और इसलिए गिनती करने का एकमात्र तरीका पी(0)एच – यह एक अंतर्वेशन है पी(एक्स)एच, जो तभी संभव है जब k मूल्यों पी(आई)एच ज्ञात है। किसी भी छोटी मात्रा का उद्घाटन पी(आई)एच के बारे में कोई जानकारी नहीं देता पी(0)एच.

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

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

पहले प्रतिभागी द्वारा भेजे गए H_1 के विभिन्न मान भिन्न परिणामी H_0 की ओर ले जाते हैं

सत्यता सिद्ध करने के कम से कम दो तरीके हैं Hi, हम बहुपद की पीढ़ी का विश्लेषण करने के बाद उन पर विचार करेंगे।

बहुपद पीढ़ी

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

इस अनुभाग में हम यह मान लेंगे कि प्रत्येक भागीदार के पास स्थानीय स्तर पर कुछ निजी कुंजी है। ग्यारहवीं, ताकि हर कोई संबंधित सार्वजनिक कुंजी को जान सके Xi.

एक संभावित बहुपद निर्माण प्रोटोकॉल इस प्रकार है:

1. प्रत्येक प्रतिभागी i स्थानीय रूप से एक मनमाना बहुपद बनाता है डिग्री k-1 का pi(x)। फिर वे इसे प्रत्येक प्रतिभागी को भेजते हैं j मूल्य pi(j), सार्वजनिक कुंजी से एन्क्रिप्ट किया गया एक्सजे. तो केवल i-वें и j-वें प्रतिभागी जानता है pi(j).प्रतिभागी i सार्वजनिक रूप से यह भी घोषणा की पीआई(जे)जी सभी के लिए j से 1 से k समावेशी।

2. सभी प्रतिभागी किसी न किसी रूप में आम सहमति से चुनाव करते हैं k जिन प्रतिभागियों के बहुपदों का उपयोग किया जाएगा। चूँकि कुछ प्रतिभागी ऑफ़लाइन हो सकते हैं, इसलिए हम तब तक प्रतीक्षा नहीं कर सकते जब तक कि सभी n प्रतिभागी बहुपद प्रकाशित करेंगे। इस चरण का परिणाम एक सेट है Z कम से कम k चरण (1) में बनाए गए बहुपद.

3. प्रतिभागियों को विश्वास है कि वे जो मूल्य जानते हैं, वे सही हैं pi(j) सार्वजनिक रूप से घोषित के अनुरूप है पीआई(जे)जी. इस कदम के बाद Z केवल बहुपद जिसके लिए निजी तौर पर प्रेषित pi(j) सार्वजनिक रूप से घोषित के अनुरूप है पीआई(जे)जी.

4. प्रत्येक प्रतिभागी j अपने निजी घटक की गणना करता है पी(जे) एक राशि के रूप में pi(j) सभी के लिए i в Zप्रत्येक प्रतिभागी सभी मानों की गणना भी करता है पी(x)जी एक राशि के रूप में सभी i के लिए pi(x)G в Z.

ध्यान दें कि पी(एक्स) – यह वास्तव में डिग्री का एक बहुपद है के-1, क्योंकि यह व्यक्ति का योग है pi(x), जिनमें से प्रत्येक डिग्री का एक बहुपद है k-1. फिर, ध्यान दें कि प्रत्येक भागीदार j वह जानता है कि पी(जे), उनके पास कोई जानकारी नहीं है p (x) के लिए एक्स ≠ जेदरअसल, इस मूल्य की गणना करने के लिए उन्हें सब कुछ जानना होगा पाई(एक्स), और जबकि प्रतिभागी j चयनित बहुपदों में से कम से कम एक को नहीं जानते हैं, उनके पास पर्याप्त जानकारी नहीं है पी(एक्स).

यह बहुपद उत्पन्न करने की पूरी प्रक्रिया है जिसकी पिछले अनुभाग में आवश्यकता थी। ऊपर दिए गए चरण 1, 2 और 4 का कार्यान्वयन काफी सरल है। हालाँकि, चरण 3 इतना आसान नहीं है।

विशेष रूप से, हमें यह साबित करने में सक्षम होना चाहिए कि एन्क्रिप्टेड pi(j) प्रकाशित वाले के अनुरूप हैं पीआई(जे)जी. यदि हम इसे साबित नहीं कर सकते तो हमलावर i इसके बजाय कचरा भेज सकते हैं pi(j) प्रतिभागी j, और प्रतिभागी j वास्तविक अर्थ नहीं समझ पाओगे पीआई(जे), और इसके निजी घटक की गणना करने में सक्षम नहीं होगा.

एक क्रिप्टोग्राफ़िक प्रोटोकॉल है जो आपको एक अतिरिक्त संदेश बनाने की अनुमति देता है प्रमाणi(j), ऐसा कि कोई भी भागीदार, जिसका कुछ मूल्य हो e, तथा प्रमाण(जे) и pi(j)G, स्थानीय रूप से सत्यापित कर सकता है कि e - वह वाकई में पीआई(जे), प्रतिभागी की कुंजी से एन्क्रिप्ट किया गया j. दुर्भाग्यवश, ऐसे साक्ष्यों का आकार अविश्वसनीय रूप से बड़ा है, और इसे प्रकाशित करने की आवश्यकता है। ओ(एनके) इस उद्देश्य के लिए ऐसे साक्ष्य का उपयोग नहीं किया जा सकता।

यह साबित करने के बजाय कि पीआई(जे) से मेल खाती है pi(j)G हम बहुपद पीढ़ी प्रोटोकॉल में समय की एक बहुत बड़ी अवधि आवंटित कर सकते हैं, जिसके दौरान सभी प्रतिभागी प्राप्त एन्क्रिप्टेड फ़ाइल की जांच करते हैं पीआई(जे), और यदि डिक्रिप्ट किया गया संदेश सार्वजनिक संदेश से मेल नहीं खाता pi(j)G, वे एक क्रिप्टोग्राफ़िक प्रमाण प्रकाशित करते हैं कि उन्हें प्राप्त एन्क्रिप्टेड संदेश गलत है। साबित करें कि संदेश नहीं से मेल खाती है सुअर) यह साबित करने से कहीं ज़्यादा आसान है कि ऐसा होता है। ध्यान दें कि इसके लिए प्रत्येक प्रतिभागी को ऐसे प्रूफ़ बनाने के लिए आवंटित समय के दौरान कम से कम एक बार ऑनलाइन होना ज़रूरी है, और यह इस धारणा पर निर्भर करता है कि अगर वे ऐसा प्रूफ़ प्रकाशित करते हैं, तो यह आवंटित समय के भीतर सभी अन्य प्रतिभागियों तक पहुँच जाएगा।

यदि कोई प्रतिभागी इस अवधि के दौरान ऑनलाइन नहीं आया, और वास्तव में उसके पास कम से कम एक गलत घटक था, तो वह विशेष प्रतिभागी आगे की संख्या निर्माण में भाग नहीं ले पाएगा। हालाँकि, प्रोटोकॉल तब भी काम करेगा जब कम से कम एक घटक गलत हो। k जिन प्रतिभागियों को या तो सही घटक प्राप्त हुए या जो आवंटित समय के भीतर गलत घटक का सबूत छोड़ने में कामयाब रहे।

H_i की सत्यता के प्रमाण

चर्चा के लिए बचा हुआ अंतिम भाग यह है कि प्रकाशित सामग्री की सत्यता को कैसे सिद्ध किया जाए। Hमैं, अर्थात कि हाय = पी(आई)एच, बिना खोले पी(आई).

आइए हम याद रखें कि मूल्य एच, जी, पी(आई)जी यह सार्वजनिक है और सभी को ज्ञात है। प्राप्त ऑपरेशन पी(आई) जानने सुअर и G असतत लघुगणक कहा जाता है, या डीलॉग, और हम यह साबित करना चाहते हैं कि:

डीलॉग(पी(आई)जी, जी) = डीलॉग(एचi, H)

बिना खुलासा किये पी(आई)ऐसे प्रमाणों के लिए निर्माण मौजूद हैं, उदाहरण के लिए श्नोर प्रोटोकॉल.

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

एक बार जब कोई यादृच्छिक संख्या उत्पन्न हो जाती है, तो अक्सर इसे उत्पन्न करने वाले लोगों के अलावा अन्य प्रतिभागियों द्वारा उपयोग करने की आवश्यकता होती है। इन प्रतिभागियों को सभी यादृच्छिक संख्याएँ भेजने की आवश्यकता होती है। Hi और समर्थन साक्ष्य.

एक जिज्ञासु पाठक पूछ सकता है: चूंकि अंतिम यादृच्छिक संख्या है H0, और पी(0)जी – यह सार्वजनिक जानकारी है, हमें प्रत्येक व्यक्ति के लिए प्रमाण की आवश्यकता क्यों है? Hमैं, इसके बजाय सबूत क्यों नहीं भेजता कि

डीलॉग(पी(0)जी, जी) = डीलॉग(एच0, H)

समस्या यह है कि आप श्नोर प्रोटोकॉल का उपयोग करके ऐसा प्रमाण नहीं बना सकते क्योंकि कोई भी इसका मूल्य नहीं जानता है। पी (0), प्रमाण बनाने के लिए आवश्यक है, और इससे भी अधिक, संपूर्ण यादृच्छिक संख्या जनरेटर इस तथ्य पर आधारित है कि कोई भी इस मान को नहीं जानता है। इसलिए सभी मानों का होना आवश्यक है Hi और सत्यता साबित करने के लिए उनके व्यक्तिगत साक्ष्य H0.

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

H0 × G = पी(0)जी × एच

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

अंत में

यह लेख एक तकनीकी ब्लॉग श्रृंखला का हिस्सा है NEARNEAR एक ब्लॉकचेन प्रोटोकॉल और विकेन्द्रीकृत अनुप्रयोगों को विकसित करने के लिए मंच है, जिसका ध्यान अंतिम उपयोगकर्ताओं के लिए विकास में आसानी और उपयोग में आसानी पर है।

प्रोटोकॉल कोड खुला है, हमारा कार्यान्वयन रस्ट में लिखा गया है, इसे पाया जा सकता है यहां.

आप देख सकते हैं कि NEAR के लिए विकास कैसा दिखता है और ऑनलाइन IDE में प्रयोग कर सकते हैं यहां.

आप यहां रूसी भाषा में सभी समाचारों का अनुसरण कर सकते हैं टेलीग्राम समूह और VKontakte पर समूह, और आधिकारिक में अंग्रेजी में चहचहाना.

जल्द मिलते हैं!

स्रोत: www.habr.com