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

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

गारबल्ड परिपथ (सर्किट) का इतिहास जटिल है। गारबल्ड परिपथ के आविष्कार का श्रेय एंड्रयू याओ को दिया गया, क्योंकि याओ ने कंप्यूटर विज्ञान की नींव'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$, तो वह $X_{0}^{a_{4}}$, $X_{1}^{a_{3}}$, $X_{1}^{a_{2}}$, $X_{0}^{a_{1}}$, और $X_{1}^{a_{0}}$ प्रेषित करती है ऐलिस के इनपुट $\mathbf {a}$ के बारे में बॉब कुछ नहीं सीखेगा चूंकि लेबल ऐलिस द्वारा अच्छे तरीके से उत्पन्न होते हैं और वे बॉब को यादृच्छिक स्ट्रिंग की तरह दिखते हैं।

बॉब को अपने इनपुट के अनुरूप लेबल की भी आवश्यकता होती है। वह अपने इनपुट के प्रत्येक बिट के लिए ओब्लिवियस स्थानान्तरण के माध्यम से अपने लेबल प्राप्त करता है। उदाहरण के लिए, यदि बॉब का इनपुट $\mathbf {b} =b_{4}b_{3}b_{2}b_{1}b_{0}=10100$ है, बॉब पहले $b_{0}=0$ अपेक्षा करता है, कि ऐलिस के लेबल $X_{0}^{b_{0}}$ के बीच $X_{1}^{b_{0}}$ और 2 में से 1 ओब्लिवियस स्थानांतरण के माध्यम से $X_{0}^{b_{0}}$ प्राप्त कर सके। ओब्लिवियस स्थानान्तरण के बाद, ऐलिस बॉब के इनपुट के बारे में कुछ नहीं सीखेगा और बॉब अन्य लेबल के बारे में कुछ नहीं सीखेगा।

मूल्यांकन

डेटा स्थानांतरण के बाद, बॉब के पास गारबल्ड सारणी और इनपुट लेबल हैं। वह एक-एक करके सभी गेट्स से गुजरता है और उनकी गारबल्ड सारणियों में पंक्तियों को डिक्रिप्ट करने का प्रयास करता है। वह प्रत्येक तालिका के लिए एक पंक्ति प्रारंभ करने और संबंधित आउटपुट लेबल : $X^{c}=Dec_{X^{a},X^{b}}(garbled\_table[i])$ को पुनः प्राप्त करने में सक्षम है, जहाँ $0\leq i\leq 3$ है। वह तब तक मूल्यांकन जारी रखता है जब तक वह आउटपुट लेबल तक नहीं पहुंच जाता।

आउटपुट प्रदर्शन

मूल्यांकन के बाद, बॉब आउटपुट लेबल $X^{c}$प्राप्त करता है, और ऐलिस बूलियन मान के लिए इसकी मैपिंग जानती है क्योंकि उसके पास दोनों $X_{0}^{c}$ और $X_{1}^{c}$ लेबल हैं। या तो ऐलिस अपनी जानकारी बॉब को साझा कर सकती है या बॉब ऐलिस को आउटपुट प्रकट कर सकता है जैसे कि उनमें से एक या दोनों आउटपुट सीखते हैं।

अनुकूलन

बिंदु और क्रमपरिवर्तन

इस अनुकूलन में, ऐलिस एक यादृच्छिक बिट $s$ उत्पन्न करता है, प्रत्येक स्ट्रिंग के लिए बिट $w^{a}$ का चयन करें वह फिर लेबल 0 का पहला बिट निर्धारित करती है, और $X_{0}^{a}$ को $s$ और लेबल 1 का पहला बिट $X_{1}^{a}$, को ${\bar {s}}$ ( $s$ का नॉट) निर्धारित करती है। उसके बाद, व्यवस्थित रूप से स्वीकृति देने के अतिरिक्त, इनपुट बिट के अनुसार गारबल्ड सारणी को क्रम मे रखता है। इस तरह, बॉब को सही खोजने के लिए सारणी की सभी चार पंक्तियों का परीक्षण करने की आवश्यकता नहीं है, क्योंकि उसके पास इनपुट लेबल हैं और वह सही पंक्ति पता कर सकता है और इसे एक प्रयास से डिक्रिप्ट कर सकता है। इससे मूल्यांकन भार 4 गुना कम हो जाता है। यह आउटपुट मान के बारे में कुछ भी नहीं बताता है क्योंकि चयनात्मक बिट्स व्यवस्थित रूप से उत्पन्न होते हैं।

रो (कम्प्यूटर) अवनति

यह अनुकूलन गारबल्ड सारणी के आकार को 4 पंक्तियों से 3 पंक्तियों तक कम कर देता है। यहां, गेट के आउटपुट स्ट्रिंग के लिए व्यवस्थित रूप से एक लेबल बनाने के अतिरिक्त, ऐलिस इनपुट लेबल के फ़ंक्शन का उपयोग करके इसे उत्पन्न करता है। वह आउटपुट लेबल उत्पन्न करती है जैसे कि गारबल्ड सारणी की पहली प्रविष्टि 0 हो जाती है और अब उसे प्रेषित करने की आवश्यकता नहीं होती है:

${\begin{aligned}&Enc_{X_{0}^{a},X_{0}^{b}}(X_{0}^{c})=0\\&X_{0}^{c}=Dec_{X_{0}^{a},X_{0}^{b}}(0).\end{aligned}}$

मुक्त एक्सओआर

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

निहितार्थ

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

निश्चित-कुंजी ब्लॉकसीफर

यह विधि एसएचए-2 जैसे उपयुक्त क्रिप्टोग्राफ़िक हैश फ़ंक्शन के अतिरिक्त निश्चित-कुंजी उन्नत एन्क्रिप्शन मानक का उपयोग करके कुशलता से गार्बल और मूल्यांकन और गेट की स्वीकृति देती है। इस गारब्लिंग योजना में जो मुक्त एक्सओआर और रो अवनति तकनीकों के साथ संगत है, आउटपुट कुंजी $X^{c}$ इनपुट टोकन के साथ $X^{a}$ और $X^{b}$ को एन्क्रिप्ट किया गया है, एन्क्रिप्शन फ़ंक्शन $Enc(X^{a},X^{b},T,X^{c})=\pi (K)\oplus K\oplus X^{c}$ का उपयोग किया जाता है, जहाँ $K=2X^{a}\oplus 4X^{b}\oplus T$, $\pi$ एक निश्चित-कुंजी ब्लॉक सिफर है उदाहरण के लिए, उन्नत एन्क्रिप्शन मानक के साथ तत्काल, और $T$ एक अद्वितीय-प्रति-गेट संख्या है उदाहरण के लिए, गेट पहचानकर्ता जिसे ट्वीक कहा जाता है।

आधा और

यह अनुकूलन एएनडी गेट्स के लिए गारबल्ड सारणी के आकार को रो अवनति में 3 पंक्ति से घटाकर 2 पंक्तियाँ कर देता है। यह दिखाया गया है कि यह गारबल्ड सारणी में पंक्तियों की संख्या के लिए, गारबलिंग तकनीकों के एक निश्चित वर्ग के लिए सैद्धांतिक न्यूनतम है।

सुरक्षा

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

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

यह भी देखें

• क्रिप्टोग्राफी
• आरएसए (एल्गोरिदम)
• सुरक्षित बहुपक्षीय संगणना
• याओ के मिलियनैर की समस्या

अग्रिम पठन

• "Yao's Garbled Circuit" (PDF). CS598. illinois.edu. Retrieved 18 October 2016.