इंटरएक्टिव सबूत और शून्य-ज्ञान पर: एक प्राइमर

सेबस्टियन गजक के साथ संयुक्त काम

आप पढ़ने से क्या उम्मीद कर सकते हैं

  • शून्य-ज्ञान, ध्वनि और पूर्णता और इस प्रकार zkSNARKs, zkSTARKs, या zkNIZKs के मूलभूत गुणों सहित प्रूफ सिस्टम के गुणों की बुनियादी समझ
  • सिमुलेशन प्रतिमान, कम्प्यूटेशनल अविभाज्यता और साक्षी निष्कर्षण
  • Schnoor का प्रोटोकॉल, जिसमें ध्वनि, शून्य-ज्ञान और पूर्णता के प्रदर्शन के प्रमाण शामिल हैं
तस्वीर को Volkan Olmez से मान्यता प्राप्त है
व्यवहार्य अभिकलन की बहुत धारणा के लिए इंटरएक्टिव साक्ष्य आवश्यक अवधारणाएं हैं - स्मार्ट अनुबंध, कार्यक्रम या डेटाबेस निष्पादन की कम्प्यूटेशनल अखंडता को आश्वस्त करने के लिए एक शक्तिशाली क्रिप्टोग्राफ़िक टूल। सबसे महत्वपूर्ण बात यह है कि संवादात्मक साक्ष्यों का सिद्धांत गैर-संवादात्मक शून्य-ज्ञान प्रमाणों (NIZKs), ज्ञान के आत्म-संवादात्मक गैर-संवादात्मक तर्कों (ज्ञान (STARKs), या ज्ञान के सुस्पष्ट पारदर्शी तर्कों) के लिए आधार प्रदान करता है। इस लेख में हम इंटरैक्टिव प्रूफ सिस्टम के पीछे मूलभूत सिद्धांत का वर्णन करते हैं और नए लोगों के लिए SNARKs और STARKs के बहुत ही रोमांचक और आशाजनक क्षेत्र में प्रवेश को आसान बनाने की उम्मीद करते हैं।

1। परिचय

प्रूफ सिस्टम ने हाल ही में कम्प्यूटेशन की अखंडता का आकलन करने के संदर्भ में जबरदस्त रुचि प्राप्त की है। उदाहरण के लिए, वे यह प्रमाणित करने के लिए "क्रिप्टोग्राफिक" ऑडिटर को लागू करने में मदद कर सकते हैं कि डेटाबेस पर खोज क्वेरी की तरह एक गणितीय फ़ंक्शन वास्तव में गणना की गई थी, इस प्रकार संभावित रूप से दुर्भावनापूर्ण डेटाबेस मालिक के प्रकाश में आउटपुट की शुद्धता को लागू करना। शून्य-ज्ञान गणना की गोपनीयता की गारंटी के लिए प्रूफ सिस्टम की एक अद्भुत संपत्ति है। यह डेटा के बारे में किसी भी आंशिक जानकारी को प्रकट किए बिना डेटासेट पर गणना को सत्यापित करने में सक्षम बनाता है। इस पृष्ठभूमि के खिलाफ, शून्य-ज्ञान प्रणालियां गोपनीयता-संवेदनशील डोमेन जैसे अनाम पहचान, डेटाबेस सेट सदस्यता क्वेरी या ब्लॉकचेन भुगतानों में आवेदन प्राप्त करती हैं।

१.१ एक प्रमाण प्रणाली क्या है?

कम्प्यूटेशनल जटिलता सिद्धांत में, एक इंटरैक्टिव प्रूफ सिस्टम एक अमूर्त मशीन है जो दो पक्षों के बीच संदेशों के आदान-प्रदान के रूप में गणना करता है। पार्टियों, जो कि प्रोवर पी और वेरिफायर वी के रूप में जानी जाती हैं, यह पता लगाने के लिए संदेशों का आदान-प्रदान करती हैं कि क्या एक बयान सही है।

यह कहावत सर्व-शक्तिशाली है और असीमित कम्प्यूटेशनल संसाधनों के पास है, लेकिन इस पर भरोसा नहीं किया जा सकता है, जबकि सत्यापनकर्ता ने कम्प्यूटेशनल शक्ति को बाध्य किया है। संदेश सत्यापनकर्ता और नीतिवचन के बीच भेजे जाते हैं जब तक कि सत्यापनकर्ता किसी कथन को मान्य या गलत कर सकता है। सभी इंटरैक्टिव प्रूफ सिस्टम में दो प्रमुख गुण होते हैं:

पूर्णता: यदि कथन सत्य है, तो ईमानदार सत्यापनकर्ता (जो कि प्रोटोकॉल का ठीक से पालन कर रहा है) एक ईमानदार कहावत से इस तथ्य के बारे में आश्वस्त हो सकता है।

ध्वनि: यदि कथन गलत है, तो कोई भी धोखा / दुर्भावनापूर्ण कहावत ईमानदार सत्यापनकर्ता को आश्वस्त नहीं कर सकती है कि यह सच है, कुछ नगण्य संभावना के अलावा।

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

1.2 शून्य-ज्ञान के माध्यम से गोपनीयता

शून्य-ज्ञान (इंटरेक्टिव) प्रूफ सिस्टम के पास दावे की वैधता से परे कुछ भी नहीं होने की उल्लेखनीय अतिरिक्त संपत्ति है। ध्यान दें कि संपत्ति केवल तभी समझ में आती है, अगर ज़ेवर में कुछ गुप्त जानकारी होती है - ज़र्क-ज़र्गन में गवाह के रूप में संदर्भित - और चाहता है कि सत्यापनकर्ता इसके बारे में कोई आंशिक जानकारी न सीखे। इसलिए, प्रूफ सिस्टम की तीसरी जादुई संपत्ति को संक्षेप में प्रस्तुत किया जा सकता है

शून्य-ज्ञान: यदि कथन सत्य है, तो कोई भी धोखा देने वाला सत्यापनकर्ता इस तथ्य के अलावा कुछ नहीं सीखता है।

शून्य-ज्ञान साहित्य में संपत्ति की व्याख्या करने के लिए एक विहित उदाहरण है। इस उदाहरण में, एक गुफा है जिसका मार्ग दो में विभाजित है। ये दो रास्ते एक दरवाजे से जुड़े हुए हैं जिन्हें केवल एक गुप्त शब्द से खोला जा सकता है। एक व्यक्ति, जिसे एलिस कहा जाता है, एक अन्य व्यक्ति बॉब को साबित करना चाहता है कि वह गुप्त शब्द को बिना धोखा दिए जानता है। इसके लिए, दोनों पक्ष पहले गुफा के प्रवेश द्वार पर खुद को रखते हैं। फिर एलिस प्रवेश करती है और दो रास्तों में से एक का अनुसरण करती है - जो उसके ऊपर है। बॉब प्रवेश द्वार से नहीं बता सकता कि एलिस ने किस रास्ते को चुना।

शून्य-ज्ञान में अली बाबा की गुफा

फिर बॉब गुफा में प्रवेश करता है और कांटा चलाता है। वह दो में से एक रास्ता चुनता है और इस गुफा में बुलाता है। एलिस का काम बॉब के लिए इस रास्ते से गुजरना है। यदि वह सफल होती है, तो वह बॉब को साबित करने के लक्ष्य के करीब एक कदम है कि वह गुप्त शब्द जानता है।

यदि ऐलिस ने बॉब को जो रास्ता चुना, उसे गुप्त शब्द की आवश्यकता नहीं है। केवल अगर उसने विपरीत रास्ता चुना, तो उसे सही रास्ते पर आने के लिए दरवाजे से गुजरना होगा। इसका मतलब यह है कि एक दुर्भावनापूर्ण ऐलिस, जो गुप्त शब्द से अनजान है, केवल बॉब को इस प्रोटोकॉल के एक रन में 50% तक मना सकता है। (यही कारण है कि ऐलिस और बॉब दोहराव त्रुटि की संभावना को कम करने के लिए प्रोटोकॉल को दोहराएंगे।) प्रोटोकॉल एक शून्य-ज्ञान प्रमाण है, क्योंकि ऐलिस और बॉब कितनी बार इस प्रक्रिया को दोहराते हैं, ऐलिस, अगर वह गुप्त शब्द जानता है, तो हमेशा रहेगा। बॉब द्वारा चुने गए मार्ग का अनुसरण करें। इस बीच बॉब रहस्य [1] के बारे में कुछ नहीं सीखता।

1.3 दैनंदिन अनुप्रयोग: पहचान योजनाएँ

शून्य-ज्ञान इंटरैक्टिव प्रूफ सिस्टम के पहले आवेदन में से एक पहचान योजनाएं हैं। एक पहचान योजना में, एक पार्टी जिसे प्रोवर ऐलिस कहा जाता है, का लक्ष्य किसी अन्य पार्टी को समझाने वाला है, बॉब, यह एक विशेष पार्टी है। इकाई प्रमाणीकरण की यह प्रक्रिया पार्टी को कुछ विशेष सेवा प्रदान करने के लिए एक घटक है, जैसे गेम्स ऑफ थ्रोन्स के सबसे हाल के एपिसोड तक पहुंच क्योंकि सामग्री प्रदाता ने पार्टी को एक प्रीमियम सदस्य के रूप में पहचाना। यह अंत करने के लिए पार्टी एक गुप्त गवाह के कब्जे में है, जैसे कि एक क्रिप्टोग्राफिक कुंजी या पासवर्ड, सामग्री प्रदाता सहित किसी अन्य पार्टी को इसकी जानकारी नहीं है। आइए अब हम गेम्स ऑफ थ्रोंस स्ट्रीमिंग मामले में तीन गुणों का उदाहरण देते हैं।

  • संपूर्णता की गारंटी देता है कि ऐलिस एक प्रीमियम ग्राहक है, इसे प्रीमियम सामग्री तक पहुंच मिलेगी।
  • साउंडनेस गारंटी देता है कि कोई अन्य पार्टी ऐलिस होने का दावा नहीं कर सकती और प्रीमियम सामग्री तक पहुंच प्राप्त कर सकती है।
  • शून्य-ज्ञान यह सुनिश्चित करता है कि सामग्री प्रदाता सहित कोई अन्य पार्टी गुप्त गवाह नहीं सीखती है और भविष्य की पहचान में ऐलिस को प्रतिरूपण कर सकती है। शून्य-ज्ञान की धारणा का अर्थ है कि पहचान का प्रमाण गैर-हस्तांतरणीय है।

पहचान योजनाओं के तल पर यह विचार निहित है कि ऐलिस कुछ रहस्य जानता है (सीधे उसकी पहचान से जुड़ा हुआ है) और वह गुप्त के बॉब ज्ञान को साबित करता है। भविष्य में एक दुर्भावनापूर्ण बॉब को ऐलिस को लागू करने से रोकने के लिए, प्रोटोकॉल से उम्मीद करें कि बॉब को ऐलिस के रहस्य के बारे में कोई आंशिक जानकारी नहीं है। इसके विपरीत, ऐलिस के पक्ष में एक पार्टी एक वैध सबूत का उत्पादन नहीं करेगा और GoT धाराओं तक पहुंच प्राप्त करेगा।

2. औपचारिक परिभाषाएँ: शैतान विस्तार में है

हालांकि एक प्रूफ सिस्टम के गुणों को सहजता से परिभाषित किया जा सकता है, पूर्णता, स्पष्टता या शून्य-ज्ञान को एक कठोर और गणितीय रूप से ध्वनि के रूप में परिभाषित करना अनुसंधान समुदाय के दशकों तक ले गया। गुणों को औपचारिक बनाने के लिए हमें दो कम्प्यूटिंग उपकरणों के बीच एक इंटरैक्शन को व्यक्त करने के लिए गणना के एक मॉडल की आवश्यकता होगी। क्रिप्टोग्राफी में कंप्यूटर विज्ञान एलन ट्यूरिंग के "पिता" के नाम पर ट्यूरिंग मशीनों को पसंदीदा विकल्प दिया जाता है।

2.1 इंटरएक्टिव ट्यूरिंग मशीन

एक इंटरेक्टिव ट्यूरिंग मशीन (ITM) एक (निर्धारक) मल्टी-टेप ट्यूरिंग मशीन है (चित्र 1 देखें)। टेप एक रीड-ओनली इनपुट टेप, रीड-ओनली रैंडम टेप, रीड-एंड-राइट वर्क टेप, राइट-ओनली आउटपुट टेप, कम्यूनिकेशन टेप की जोड़ी और रीड-एंड-राइट स्विच टेप से युक्त होते हैं। एक एकल कोशिका। एक संचार टेप केवल-पढ़ने के लिए है, और दूसरा केवल-लेखन है। प्रत्येक ITM एक सा जुड़ा होता है, जिसे उसकी पहचान कहा जाता है। एक आईटीएम को एक कॉन्फ़िगरेशन में सक्रिय कहा जाता है, अगर उसके स्विच टेप की सामग्री मशीन की पहचान के बराबर है। अन्यथा मशीन को निष्क्रिय कहा जाता है। निष्क्रिय होने के दौरान, मशीन की स्थिति, विभिन्न टेपों पर उसके सिर के स्थान, और आईटीएम के लेखन योग्य टेप की सामग्री को संशोधित नहीं किया जाता है।

चित्र 1: दो इंटरेक्टिव ट्यूरिंग मशीनों का चित्रण।

इनपुट टेप की सामग्री को इनपुट कहा जाता है, यादृच्छिक टेप की सामग्री को यादृच्छिक इनपुट कहा जाता है, और समाप्ति पर आउटपुट टेप की सामग्री को आउटपुट कहा जाता है। एक (समय) अवधि के दौरान केवल-लेखन संचार टेप पर लिखी गई सामग्री जिसमें मशीन सक्रिय है, उस अवधि में भेजा गया संदेश कहलाता है। इसी तरह, एक सक्रिय अवधि के दौरान केवल-पढ़ने के लिए संचार टेप से पढ़ी गई सामग्री को उस समय प्राप्त संदेश कहा जाता है। (सामान्यता के नुकसान के बिना, दोनों संचार टेपों पर मशीन की गतिविधियां केवल एक दिशा में होती हैं, उदा। बाएं से दाएं।)

अब आप क्रमशः इंटरेस्टिंग ट्यूरिंग मशीन M pro the prover P और Mifier the verifier V को कॉल करना चाह सकते हैं। मनुष्यों की तरह, मशीनों को ठीक से बातचीत करने के लिए एक भाषा L को समझने की आवश्यकता होती है। हम यहां भाषा सिद्धांत और जटिलता में गहरा गोता लगाने की योजना नहीं बनाते हैं। हमें जो कुछ भी जानना है वह यह है कि नीतिवचन पी को यह कथन सिद्ध करना चाहिए - बहुत ही शिष्ट रूप से बोलना - किसी विशेष भाषा में एनकोडेड होना। के साथ (x, w) and L और (x, w) express L हम एक सही / गलत प्रमाण कथन व्यक्त करते हैं या दूसरे शब्दों में जोड़ी (x, w) भाषा का एक सदस्य है L. आमतौर पर मान x सार्वजनिक है और नीतिवचन और सत्यापनकर्ता और पैरामीटर w (जिसे गवाह कहा जाता है) दोनों के लिए जाना जाता है, यह निजी और कहावत के लिए जाना जाता है।

औपचारिक रूप से एक भाषा L को कुछ परिमित वर्णमाला पर तार के एक सेट (संभवतः अनंत) के रूप में परिभाषित किया जाता है और नियमों के एक विशिष्ट सेट के लिए गठित किया जाता है। उदाहरण के लिए वर्णमाला पर एक भाषा L 0 = {0, 1, 2, -, =} में निम्नलिखित व्याकरण हो सकते हैं:

  • प्रत्येक गैर-रिक्त स्ट्रिंग में "-" या "=" नहीं होता है और "0" से शुरू नहीं होता है जो एल में है
  • "=" युक्त एक स्ट्रिंग L में है अगर और केवल अगर एक "=" है, और यह L के दो वैध तारों को अलग करता है

इन नियमों के तहत, स्ट्रिंग "2–1 = 1" एल में है, लेकिन स्ट्रिंग "= 21 = 0-" नहीं है। संचार प्रोटोकॉल के सेटअप चरण के दौरान, बातचीत करने वाले पक्ष अक्सर विशिष्ट नियमों के साथ एक विशिष्ट भाषा पर सहमत होते हैं।

2.2 इंटरएक्टिव प्रूफ सिस्टम

इंटरैक्टिव ट्यूरिंग मशीन (P, V) की एक जोड़ी को भाषा L के लिए एक इंटरेक्टिव प्रूफ सिस्टम कहा जाता है यदि मशीन V बहुपद-काल है और निम्नलिखित दो स्थितियाँ पकड़ती हैं:

  • पूर्णता: भाषा L में सभी (x, w) के लिए, एक संभावना P जो ईमानदार V को मना सकता है, वह महत्वपूर्ण है। अर्थात्,
) (X, w): L: Pr [(P (x, w), V (x) ≤ = 1] 1 1 - negl
  • साउंडनेस (कमजोर संस्करण उर्फ ​​अनफॉरगेटबिलिटी): सभी के लिए (x, w) भाषा L में नहीं, संभावना है कि एक धोखा देने वाला P 'एक ईमानदार सत्यापनकर्ता V को मना सकता है, नगण्य है। अर्थात्,
) (X, w): L: Pr ['P '(x), V (x)⟩ = 1] 1 नगण्य
  • विशेष ध्वनि (मजबूत संस्करण उर्फ ​​ज्ञान निकालने की क्षमता):

भाषा L में प्रत्येक (x, w) के लिए, एक बहुपद-काल एल्गोरिथ्म E (एक्सट्रैक्टर) मौजूद है जैसे कि गवाह w को prover P और verifier V के साथ मान्य वार्तालाप से निकाला जा सकता है।

) (X, w), L,: E: Pr [E (P (x, w), V (x) x = w] - 1 - negl

ध्वनि दो स्वादों में आती है। ध्वनिहीनता की कमजोर धारणा एक अप्रभावी संपत्ति का थोड़ा अंतर्ज्ञान पकड़ती है। वास्तव में, प्रूफ सिस्टम और डिजिटियल हस्ताक्षर में बहुत कुछ है। फिएट-शमीर परिवर्तन के माध्यम से एक प्रोटोकॉल के एक वर्ग को सिग्मा प्रोटोकॉल के रूप में जाना जाता है जो डिजिटल हस्ताक्षर में बदल सकते हैं। हम एक आगामी लेख में तकनीक पर चर्चा करते हैं। मजबूत धारणा को अक्सर साक्षी निष्कर्षण संपत्ति के रूप में जाना जाता है। संपत्ति को संतुष्ट करने वाले प्रोटोकॉल को ज्ञान का प्रमाण कहा जाता है। अनिवार्य रूप से एक एल्गोरिथम तरीके से एक्सट्रैक्टर फ़्रेम का अस्तित्व कम्प्यूटेशनल ज्ञान का विचार है। मान लीजिए कि प्रोवर गवाह डब्ल्यू को जानता है। तब उसने प्रोटोकॉल के निष्पादन के दौरान गवाह का इस्तेमाल किया होगा (और इस प्रकार इसे किसी तरह से प्रोटोकॉल संदेशों में एन्कोड किया गया) ताकि सत्यापनकर्ता को सफलतापूर्वक समझा जा सके। तो मान लें कि हमारे पास एक जादुई परी है, चिमटा है, पी के पीछे की ओर देख रहा है और प्रोटोकॉल निष्पादन में गवाह के उपयोग को ध्यान में रखता है। स्पष्ट रूप से यह गवाह के ज्ञान का एक मजबूत सबूत होगा। कम्प्यूटेशनल विश्व स्वर्गदूतों में दुख की बात नहीं है। बल्कि पी और वी ट्यूरिंग मशीन हैं और इसलिए एक्सट्रैक्टर ई है। "पी की पीठ को देखने" के अंतर्ज्ञान को पकड़ने के लिए, हम एक्सट्रक्टर को गवाह को पी और वेरिफायर की बातचीत के अवलोकन से गणना करते हैं। वी। को दूसरे शब्दों में कहें। यदि आप गवाह को P से बाहर निकाल सकते हैं, तो यह किसी न किसी तरह से होना चाहिए। यहां जिस बिंदु पर जोर दिया जाना चाहिए वह यह है कि बातचीत का एक सरल निष्क्रिय ईवेंट साक्षी के बारे में कोई आंशिक जानकारी लीक नहीं करता है। अन्यथा सत्यापनकर्ता साक्षी डब्ल्यू सीखता है और प्रोटोकॉल शायद ही शून्य-ज्ञान के किसी भी रूप को संतुष्ट करता है। चिमटा ई (सत्यापनकर्ता के विपरीत) इसलिए कुछ अतिरिक्त शक्ति दी जाती है! नीचे दिए गए आगामी उदाहरण में, हम देखेंगे कि अतिरिक्त शक्ति, प्रोवर पी को रिवाइंड करने की क्षमता है। रिवाइंडिंग एक ऐसी तकनीक है जो कार्यक्रमों के मूल विचार को दर्शाती है: एक प्रोग्राम को कई बार निष्पादित कर सकता है (फ़ंक्शन को कॉल करने के बारे में सोचें) और यह आउटपुट करता है। नियतात्मक परिणाम, यदि कोई प्रोग्राम के यादृच्छिक टेप / इनपुट को नियंत्रित करता है। आगे देख रहे हैं, प्रोवर पी को रिवाइंड करते हुए (विशेष रूप से, Schnorr के प्रोटोकोल को दो बार निष्पादित करते हुए, विशेष रूप से दूसरी एक्जिट से पहले किसी विशेष राज्य में प्रोवेर को रिवाइंड करते हुए) पहले से ही साक्षी निष्कर्षण के लिए सभी संबंधित जानकारी एकत्र करने के लिए पर्याप्त है। फिर से ध्यान दें कि प्रोटोकॉल के लिए शून्य-ज्ञान को संतुष्ट करने के लिए सत्यापनकर्ता के पास अतिरिक्त अतिरिक्त शक्ति की कमी होनी चाहिए।

  • शून्य-ज्ञान: एल भाषा में हर (x, w) के लिए, सभी वेरिफ़ायर्स के लिए मौजूद है एक सिम्युलेटर एस ऐसा है कि कोई भी बहुपद-काल भेद डी घेरने वाले प्रोटोकॉल के निष्पादन को प्रो पी के बीच वास्तविक बातचीत से अलग नहीं कर सकता है। और सत्यापनकर्ता वी। यह है कि,
) (X, w) ,L, ∃V PrS: Pr [D (P (x, w), V (x) 1 = 1] - Pr [D⟨S (x) w = 1] l negl

हमें सबसे पहले सिमुलेशन तंत्र को समझने के लिए कम्प्यूटेशनल इंडिस्टिनिशिबिलिटी की बहुत धारणा को याद करने की आवश्यकता है। Indistinguishability कंप्यूटर विज्ञान के कई क्षेत्रों में एक शक्तिशाली अवधारणा है। यह एक कुशलतापूर्वक कम्प्यूटेशनल निर्णय लेने वाले एल्गोरिथ्म द्वारा औपचारिक रूप से औपचारिक है, अंतर डी, जो दो सेटों में से एक स्ट्रिंग के इनपुट पर तय करता है कि इसे किस सेट से लिया गया था। विचार-विमर्श में आसानी के लिए, निम्नलिखित मानसिक प्रयोग पर विचार करें। मान लीजिए कि एक मानव और मानव को अनुकरण करने वाली एक मशीन एक थिएटर में पर्दे के पीछे छिपी हुई है और दर्शक पर्दे के माध्यम से दोनों में से किसी एक के साथ बातचीत करते हैं। एक लंबी बातचीत के बाद, अगर दर्शक मशीन से मानव को अलग नहीं कर सकते (जैसे हमारे पास 50:50 निर्णय था), तो हम निष्कर्ष निकालेंगे कि मशीन "मानव के रूप में अच्छी है" या "लगता है / दिखता है / जैसा व्यवहार करता है"।

अब उस मामले पर विचार करें जहां हम प्रोवर पी और वेरिफ़ायर वी की बातचीत की तुलना निष्पादन के साथ एक सिम्युलेटर एस निम्नलिखित कैवेट के साथ करते हैं। प्रोवर और वेरिफायर के बीच वास्तविक बातचीत में, पी स्पष्ट रूप से अपने गवाह डब्ल्यू का उपयोग करता है जबकि सिम्युलेटर एस को केवल सार्वजनिक सूचना एक्स दिया जाता है। जानकारी के नुकसान के बावजूद, मान लें कि सिम्युलेटर एक प्रतिलेख उत्पन्न करता है जो "ऐसा दिखता है" प्रोवर और सत्यापनकर्ता के बीच एक बातचीत (चित्र 2 देखें)।

चित्र 2: शून्य-ज्ञान की धारणा का चित्रण।

तब यह मामला होना चाहिए कि असली प्रोटोकॉल ट्रांसक्रिप्ट नकली सूचना के रूप में ज्यादा जानकारी लीक करता है। ध्यान दें ऐसा होना चाहिए। अन्यथा निष्पादन अलग-अलग थे। निर्माण के द्वारा, हालांकि, सिम्युलेटेड प्रतिलेख शून्य-ज्ञान है: यह गवाह w के बारे में कोई आंशिक जानकारी लीक नहीं करता है। वास्तव में, सिम्युलेटर किसी भी जानकारी को लीक नहीं कर सकता है क्योंकि यह गवाह के कब्जे में नहीं है। निष्कर्ष यह होना चाहिए कि वास्तविक प्रोटोकॉल प्रतिलेख गवाह के बारे में कोई भी जानकारी लीक नहीं करता है, क्योंकि नकली प्रतिलेख अप्रभेद्य है, जो वास्तविक रूप में उतना ही अच्छा है। इसलिए वास्तविक प्रोटोकॉल शून्य-ज्ञान है।

3. सिनोरर्स प्रोटोकॉल उर्फ ​​"हैलो वर्ल्ड" ईमानदार-वेरिफायर जीरो-नॉलेज प्रूफ सिस्टम

ज्ञान के सबसे सरल और सबसे अधिक उपयोग किए जाने वाले प्रमाणों में से एक, असतत लघुगणक के ज्ञान का प्रमाण, क्लॉस पी। स्कोरोर के कारण है। वह एक जर्मन गणितज्ञ और क्रिप्टोग्राफर थे। उनके प्रोटोकॉल में तीन राउंड हैं और जेनरेटर जी के साथ क्रम क्यू के चक्रीय समूह जी पर परिभाषित किया गया है। शून्य-ज्ञान को साबित करने के लिए भाषा L = {(x, w): x = g prove} जहां साक्षी w हार्ड-टू-कंप्यूट डिस्क्रीट लॉग एक्सपोनेंट है, वहीं प्रॉवर सत्यापनकर्ता के साथ चित्र 3 में चित्रित किया गया है।

3.1 प्रमाण प्रणाली विशिष्टता

चित्र 3: श्नेचर्स प्रोटोकॉल। ध्यान दें कि प्रोटोकॉल के कई प्रकार मौजूद हैं। हम उस प्रोटोकॉल के संस्करण को चुनना पसंद करते हैं जहां चुनौती ई को {0, .., q-1} से नमूना लिया जाता है।

सेट अप:

  • कहावत P में गुप्त इनपुट w और सार्वजनिक इनपुट x = g secret है।
  • सत्यापनकर्ता V के पास केवल सार्वजनिक इनपुट x = gifier है।
  • P और V दोनों के पास सामान्य सार्वजनिक पैरामीटर g और q है।

मसविदा बनाना:

  1. प्रोवर पी एक यादृच्छिक समूह तत्व एच उत्पन्न करता है और एक यादृच्छिक पूर्णांक आर का नमूना लेता है। वह सत्यापनकर्ता V को यादृच्छिक मान a = gʳ भेजता है।
  2. सत्यापनकर्ता V, यादृच्छिक चुनौती e V {0, .. q-1} चुनता है और इसे Pver में भेजता है।
  3. P को उत्तर z = r + ew के साथ चुनौती पर प्रतिक्रिया दें।
  4. सत्यापनकर्ता V प्रतिक्रिया को स्वीकार करता है (और इस प्रकार प्रमाण के प्रति आश्वस्त होता है), अगर और केवल अगर gᶻ axᵉ के बराबर है।

3.2 सुरक्षा विश्लेषण

अब हम Schnorr proof सिस्टम का विश्लेषण करते हैं और तर्क देते हैं कि यह उपरोक्त गुणों को पूरा कर रहा है।

संपूर्णता को एक सरल तुल्यता सुधार द्वारा दिखाया गया है:

∀r, e: gᶻ = gʳ⁺ᵉʷ = gʷ (gᵉ) ᵉ = ax,

एक्सट्रैक्टर ई को सही गवाह डब्ल्यू की गणना करके चित्रा 4 में विशेष ध्वनि दिखाया गया है और इस प्रकार असतत लॉग धारणा को तोड़ दिया गया है (अर्थात इसे साक्ष्य w = xʷ g in की गणना करने के लिए एक कम्प्यूटेशनल रूप से कठिन समस्या माना जाता है, इस प्रकार उल्लंघन होता है) कमजोर लगने वाली संपत्ति। दूसरे शब्दों में, हम एक्सट्रैक्टर ई की मदद से असतत लॉग समस्या के लिए प्रोटोकॉल ध्वनि को कम करते हैं।

चित्र 4: विशेष ध्वनि के लिए प्रूफ के दौरान चलने वाले सिमुलेशन का चित्रण।

काम करने के लिए निष्कर्षण के लिए, ई, पी और पी * के रूप में चिह्नित, प्रोवर के दो उदाहरण चलाता है। सिमुलेशन के दौरान चिमटा दो उदाहरणों के लिए सत्यापनकर्ता V के रूप में कार्य करता है और निम्न रणनीति के माध्यम से गवाह की गणना करता है:

  1. एक्सट्रैक्टर ई, सार्वजनिक इनपुट x = g and (और रैंडम सिक्कों को अपने यादृच्छिक टेपों को बेहतर बनाने के लिए) के साथ पहला प्रोवर उदाहरण P खिलाता है और पहला प्रोवर संदेश a = gʳ प्राप्त करने के लिए प्रतीक्षा करता है।
  2. चिमटा ई एक यादृच्छिक बिट ई E {0, .. q-1} चुनता है, प्रो पी को ई भेजता है और प्रतिक्रिया z = r + ew प्राप्त करने के लिए प्रतीक्षा करता है।
  3. अब यह prover P को चरण 2 में फिर से शामिल करता है (तकनीकी रूप से एक्सट्रैक्टर समान इनपुट (x, r) के साथ दूसरा प्रोवर इंस्टेंस P * देता है। तथ्य यह है कि हम प्रोवेर को उसी रैंडमनेस आर के साथ इनवॉइस करते हैं, जिससे यह सुनिश्चित होता है कि वह समान है (यादृच्छिक) ) विकल्प के रूप में पी पहले संदेश के लिए किया था। इसलिए हमने पी को उलटा किया।)
  4. एक्सट्रैक्टर ई एक अलग ई चुनता है, इसे पी * पर भेजता है और उत्तर प्राप्त करने के लिए प्रतीक्षा करता है।
  5. अंतिम रूप से गवाह डब्ल्यू को चुनौती-प्रतिक्रिया जोड़े के मतभेदों की गणना के माध्यम से निकाला जाता है।
(z-z ') / (e-e') = ((r + ew) - (r + e'w)) / (e-e ') = (e-e') / (e-e ') · डब्ल्यू = डब्ल्यू

शून्य-ज्ञान: एक प्रोटोकॉल को शून्य ज्ञान माना जाता है यदि किसी भी सत्यापनकर्ता V के लिए एक सिम्युलेटर मौजूद है जो कि समान वितरण के साथ बातचीत बना सकता है, जो कि प्रोवर और वेरिफायर के बीच बातचीत के रूप में है। हम इस बात पर जोर देते हैं कि शिनोर का प्रोटोकॉल (जैसा कि ऊपर बताया गया है) शून्य-ज्ञान नहीं है। सभी सत्यापनकर्ताओं के लिए एक सिम्युलेटर बनाने में असमर्थता का कारण है: संदेश ई के अप्रत्याशित विकल्पों के साथ दुर्भावनापूर्ण सत्यापनकर्ताओं के लिए अनुकरण कम हो जाता है। सिमुलेशन के माध्यम से जाने के लिए, हालांकि, सिम्युलेटर को पहले से चुनौती ई का अनुमान लगाना चाहिए। ई के घातीय नमूने के स्थान को देखते हुए, इस घटना के होने की संभावना नगण्य है।

हालांकि, Schnorr का प्रोटोकॉल एक कमजोर गोपनीयता धारणा को संतुष्ट करता है जिसे ईमानदार सत्यापनकर्ता शून्य-ज्ञान के रूप में जाना जाता है। इस मॉडल में, सत्यापनकर्ता प्रोटोकॉल के निष्पादन को आँख बंद करके अनुसरण करता है और उपरोक्त प्रोटोकॉल विनिर्देश से विचलित नहीं होता है। इस सरलीकरण के तहत सिम्युलेटर को सत्यापनकर्ता के मनमाने ढंग से और इस तरह के कठिन-से-पूर्वानुमान व्यवहार की आशा करने की कोई आवश्यकता नहीं है। बल्कि सिम्युलेटर अब चुनौती संदेश के यादृच्छिक विकल्प को समय से पहले ई-मेल कर सकता है, जैसे कि - धारणा से - एक ईमानदार सत्यापनकर्ता ठीक उसी तरह का व्यवहार करेगा। किसी भी दिए गए मान को लेना संभव है और फिर एक वार्तालाप का उत्पादन करें जहां ई चुनौती के रूप में होता है। दूसरे शब्दों में, सिम्युलेटर को स्वयं को चुनने पर जोर देने की आवश्यकता नहीं है, यह इनपुट के रूप में ई-मूल्य ले सकता है। यह अनुकरण को मजबूत बनाता है, क्योंकि यह सांख्यिकीय रूप से भ्रष्ट सत्यापनकर्ताओं की उपस्थिति में शून्य-ज्ञान दिखाता है। इसे देखने के लिए, हम निम्नलिखित तरीके से सार्वजनिक इनपुट x = g the दिए गए सिम्युलेटर S का निर्माण करते हैं:

  1. सिम्युलेटर एस यादृच्छिक रूप से z चुनता है और चुनौती ई ईमानदार सत्यापनकर्ता जारी करेगा।
  2. सिम्युलेटर एस ने नीतिवचन के प्रारंभिक संदेश को = gᶻ / x the के रूप में गणना की है। इसके अलावा यह ई के साथ सत्यापनकर्ता के चुनौती संदेश का अनुकरण करता है।
  3. अंत में, सिम्युलेटर एस तीसरे संदेश z का अनुकरण करता है।

सिमुलेशन का विश्लेषण करते हुए, हम देखते हैं कि सिम्युलेटर एस प्रोवर और वेरिफायर का एक वैध इंटरैक्शन बनाता है। सत्यापनकर्ता नकली प्रोटोकॉल संदेशों को स्वीकार करता है क्योंकि वह इसे धारण करता है

a · x · = (gᶻ / xᵉ) · xᶻ = g (

सिमुलेशन (ए, ई, जेड) में वास्तविक प्रोवर और ईमानदार सत्यापनकर्ता के बीच वास्तविक बातचीत के समान ही संभावना वितरण है। (हालांकि यह साबित करना बाकी है।)

4. सिग्मा-प्रोटोकॉल और NIZK पर निष्कर्ष और आउटलुक

कोई यह तर्क दे सकता है कि ईमानदार सत्यापनकर्ता शून्य-ज्ञान एक उपयोगी संपत्ति नहीं है, क्योंकि यह मानने का अभ्यास नहीं करता है कि सत्यापनकर्ता ईमानदार है। हालांकि, मुद्दा यह है कि इस कमजोर संपत्ति वाले प्रोटोकॉल का उपयोग अक्सर निर्माण में ब्लॉकों के रूप में किया जा सकता है जो वास्तव में सक्रिय रूप से धोखा देने के खिलाफ सुरक्षित हैं, जैसा कि हम देखेंगे। ऐसे प्रोटोकॉल जिनमें तीन-चाल की संरचना (प्रतिबद्धता, चुनौती, प्रतिक्रिया) होती है जैसे कि स्चनोर के प्रोटोकॉल को s-प्रोटोकॉल कहा जाता है। कुशल सिग्मा प्रोटोकॉल विभिन्न बयानों को साबित करने के लिए मौजूद हैं, जैसे कि लघुगणक असतत करने के लिए। इसके अलावा, फिएट-शमीर परिवर्तन के माध्यम से वे कुशलता से ज्ञान के गैर-संवादात्मक शून्य-ज्ञान प्रमाण (NIZKs) में बदल सकते हैं।

हमने अगले लेख में NIZK निर्माण के कुछ ठोस उदाहरणों के साथ सिग्मा-प्रोटोकॉल, फिएट-शमीर परिवर्तन के बारे में लिखने की योजना बनाई है। बने रहें!

आगे की पढाई

इंटरएक्टिव प्रूफ सिस्टम का सिद्धांत इस लेख में हमने जो व्यवहार किया है, उससे कहीं अधिक विस्तृत है। यहां उन पत्रों की एक सूची दी गई है, जिन्हें हम इस रोमांचक क्षेत्र में गहराई से गोता लगाने की सलाह देते हैं।

  • क्लॉस पी। स्कोरोर: स्मार्ट कार्ड के लिए कुशल हस्ताक्षर पीढ़ी। क्रिप्टोलॉजी का जर्नल, 4 (3): 239-252, 1991।
  • मिहिर बेलारे और ओडेड गोल्डरिच: ज्ञान के परिभाषित प्रमाण पर। Crypto'92।
  • ओडेड गोदरेज: क्रिप्टोग्राफी के मूलाधार - मूल उपकरण। कैम्ब्रिज यूनिवर्सिटी प्रेस, 2001।