गारबल्ड परिपथ

गारबल्ड (विकृत) परिपथ एक क्रिप्टोग्राफ़िक प्रोटोकॉल है जो दो-पक्षीय सुरक्षित संगणना को सक्षम करता है जिसमें दो अविश्वास करने वाले पक्ष एक विश्वसनीय तृतीय पक्ष की उपस्थिति के बिना अपने निजी इनपुट पर संयुक्त रूप से एक फ़ंक्शन का मूल्यांकन कर सकते हैं। गारबल्ड परिपथ प्रोटोकॉल में, फ़ंक्शन को बूलियन परिपथ के रूप में वर्णित किया जाना चाहिए।

गारबल्ड परिपथ (सर्किट) का इतिहास जटिल है। गारबल्ड परिपथ के आविष्कार का श्रेय एंड्रयू याओ को दिया गया, क्योंकि याओ ने कंप्यूटर विज्ञान की नींव'86 में एक पत्र की मौखिक प्रस्तुति में इस विचार को प्रस्तुत किया था। यह 2003 में ओडेड गोल्ड्रेइच द्वारा प्रलेखित किया गया था। इस तकनीक के बारे में पहला लिखित दस्तावेज़ कम्प्यूटिंग के सिद्धांत पर परिचर्चा'87 में गोल्ड्रेइच, मिकाली और एवी विगडरसन द्वारा दिया गया था। गारबल्ड परिपथ शब्द का पहली बार उपयोग कम्प्यूटिंग के सिद्धांत पर परिचर्चा'90 में बीवर, मिकाली और फिलिप रोगवे द्वारा किया गया था। याओ के मिलियनैर की समस्या को हल करने वाला याओ का प्रोटोकॉल सुरक्षित संगणना का प्रारम्भिक उदाहरण था, फिर भी यह गारबल्ड परिपथ से सीधे संबंधित नहीं है।

पृष्ठभूमि

ओब्लिवियस स्थानांतरण

गारबल्ड परिपथ प्रोटोकॉल में, हम ओब्लिवियस स्थानांतरण का उपयोग करते हैं। ओब्लिवियस स्थानांतरण में, एक स्ट्रिंग (कंप्यूटर विज्ञान) एक प्रेषक और एक अभिग्राही के बीच निम्नलिखित तरीके से स्थानांतरित किया जाता है: एक प्रेषक के दो स्ट्रिंग $S_{0}$ और $S_{1}$ होते हैं अभिग्राही $b\in \{0,1\}$ चयन करता है और प्रेषक $S_{b}$ को ओब्लिवियस स्थानांतरण प्रोटोकॉल के साथ प्रेषित करता है जैसे कि

1. अभिग्राही को असंतुलित स्ट्रिंग $S_{(1-b)}$ के बारे में कोई जानकारी नहीं मिलती है,
2. $b$ का मान प्रेषक के सामने नहीं आता है।

ध्यान दें कि जबकि अभिग्राही $S_{0},S_{1}$ मानों को नहीं जानता है, व्यवहार में अभिग्राही कुछ जानकारी जानता है कि $S_{b}$ क्या एन्कोड करता है ताकि अभिग्राही बिना विचार किए $b$ चयन करता है। अर्थात यदि $S_{0}$ गलत मान को एनकोड करता है, तो $S_{1}$ सही मान को एनकोड करता है और अभिग्राही एन्कोडेड सही मान प्राप्त करना चाहता है, तब अभिग्राही $b=1$ चयन करता है।

आरएसए गुप्‍त संदेश पद्धति की तरह असममित क्रिप्टोग्राफी का उपयोग करके विस्मृत हस्तांतरण का निर्माण किया जा सकता है।

परिभाषाएं और नोटेशन

ऑपरेटर $\parallel$ स्ट्रिंग संयोजन है। ऑपरेटर $\oplus$ बिट-वार एक्सओआर है। k एक सुरक्षा पैरामीटर और कुंजियों की लंबाई है। यह 80 से अधिक होना चाहिए और सामान्य रूप से 128 पर स्थापित होता है।

गारबल्ड परिपथ प्रोटोकॉल

प्रोटोकॉल में निम्नानुसार 6 चरण होते हैं:

1. अंतर्निहित फ़ंक्शन (उदाहरण के लिए, मिलियनैर की समस्या में, समतुल्यता फ़ंक्शन) को 2-इनपुट गेट्स के साथ बूलियन परिपथ के रूप में वर्णित किया गया है। परिपथ दोनों पक्षों के लिए जाना जाता है। यह चरण किसी तीसरे पक्ष द्वारा पहले ही किया जा सकता है।
2. ऐलिस परिपथ को गारबल्स (एन्क्रिप्ट) करता है। हम ऐलिस द गारब्लर कहते हैं।
3. ऐलिस अपने एन्क्रिप्टेड इनपुट के साथ बॉब को गारबल्ड परिपथ भेजती है।
4. परिपथ की गणना करने के लिए, बॉब को अपने स्वयं के इनपुट को भी गारबल करने की आवश्यकता है। यह अंत करने के लिए, उसे ऐलिस की सहायता की आवश्यकता है, क्योंकि केवल गार्बलर ही एन्क्रिप्ट करना जानता है। अंत में, बॉब ओब्लिवियस स्थानांतरण के जरिए अपने इनपुट को एन्क्रिप्ट कर सकता है। ऊपर से परिभाषा के संदर्भ में, बॉब अभिग्राही है और ऐलिस इस ओब्लिवियस स्थानांतरण पर प्रेषक है।
5. बॉब परिपथ का मूल्यांकन (डिक्रिप्ट) करता है और एन्क्रिप्टेड आउटपुट प्राप्त करता है। हम बॉब को मूल्यांकनकर्ता कहते हैं।
6. एलिस और बॉब आउटपुट जानने के लिए संवाद करते हैं

परिपथ उत्पादन

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

गारबिंग

एएनडी गेट पर स्ट्रिंग और उनके लेबल

एएनडी गेट की सत्यता सारणी का निर्माण

ऐलिस (गार्बलर) इस चरण में बूलियन परिपथ को गारबल्ड परिपथ प्राप्त करने के लिए एन्क्रिप्ट करता है। ऐलिस परिपथ में प्रत्येक स्ट्रिंग के लिए दो यादृच्छिक रूप से उत्पन्न स्ट्रिंग्स को लेबल करता है: एक बूलियन डेटा प्रकार सिमेंटिक 0 के लिए और एक 1 के लिए लेबल k-बिट लंबा है जहां k सुरक्षा पैरामीटर है और सामान्य रूप से 128 पर निर्धारित होता है। अगला, वह परिपथ के सभी गेटों पर जाती है और 0 और 1 को संबंधित लेबल के साथ सत्य सारणी में बदल देती है। नीचे दी गई सारणी दो इनपुट $w^{a},w^{b}$ और आउटपुट $w^{c}$ के साथ एएनडी गेट के लिए सत्य सारणी दिखाती है:

a	b	c
0	0	0
0	1	0
1	0	0
1	1	1

ऐलिस ने 0 और 1 को संबंधित लेबल से बदल दिया:

a	b	c
$X_{0}^{a}$	$X_{0}^{b}$	$X_{0}^{c}$
$X_{0}^{a}$	$X_{1}^{b}$	$X_{0}^{c}$
$X_{1}^{a}$	$X_{0}^{b}$	$X_{0}^{c}$
$X_{1}^{a}$	$X_{1}^{b}$	$X_{1}^{c}$

वह फिर सत्य सारणी के आउटपुट प्रविष्टि को संबंधित दो इनपुट लेबल के साथ एन्क्रिप्ट करती है। एन्क्रिप्टेड सारणी को गारबल्ड सारणी कहा जाता है। यह इस तरह से किया जाता है कि कोई गारबल्ड सारणी को केवल तभी डिक्रिप्ट कर सकता है जब उसके पास सही दो इनपुट लेबल हों। नीचे दी गई सारणी में, $Enc_{k}(X)$ एक डबल-कुंजी सममित एन्क्रिप्शन है जिसमें k गुप्त कुंजी है और X एन्क्रिप्ट (निश्चित-कुंजी ब्लॉकसीफर देखें) किया जाने वाला मान है।

Garbled Table
$Enc_{X_{0}^{a},X_{0}^{b}}(X_{0}^{c})$
$Enc_{X_{0}^{a},X_{1}^{b}}(X_{0}^{c})$
$Enc_{X_{1}^{a},X_{0}^{b}}(X_{0}^{c})$
$Enc_{X_{1}^{a},X_{1}^{b}}(X_{1}^{c})$

इसके बाद, ऐलिस सही तरीके से सारणी को इस तरह से बदल देता है कि आउटपुट मान को पंक्ति से निर्धारित नहीं किया जा सकता है। प्रोटोकॉल का नाम, गारबल्ड, इस यादृच्छिक क्रमचय से लिया गया है।

डेटा स्थानांतरण

एलिस बॉब को परिपथ में सभी गेट्स के लिए गणना की गई गारबल्ड सारणी भेजती है। विकृत सारणी को प्रारंभ करने के लिए बॉब को इनपुट लेबल की आवश्यकता है। इस प्रकार, ऐलिस उसके इनपुट के अनुरूप लेबल चयन करती है और उन्हें बॉब को प्रेषित करती है। उदाहरण के लिए, यदि ऐलिस का इनपुट $\mathbf {a} =a_{4}a_{3}a_{2}a_{1}a_{0}=01101$