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

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

गारबल्ड सर्किट का इतिहास जटिल है। गारबल्ड सर्किट के आविष्कार का श्रेय एंड्रयू याओ को दिया गया, क्योंकि याओ ने एक पेपर की मौखिक प्रस्तुति में विचार पेश किया कंप्यूटर साइंस'86 की नींव पर संगोष्ठी में। यह 2003 में ओडेड गोल्ड्रेइच द्वारा प्रलेखित किया गया था। इस तकनीक के बारे में पहला लिखित दस्तावेज़ गोल्ड्रेइच, सिल्वियो मिकाली और द्वारा किया गया था कम्प्यूटिंग के सिद्धांत पर संगोष्ठी में एवी विगडरसन'87। गारबल्ड सर्किट शब्द का पहली बार उपयोग STOC'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$ बिट-वार XOR है। k एक सुरक्षा पैरामीटर और चाबियों की लंबाई है। यह 80 से अधिक होना चाहिए और आमतौर पर 128 पर सेट होता है।

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

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

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

सर्किट जनरेशन

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

गारबिंग

AND गेट पर तार और उनके लेबल

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

ऐलिस (गार्बलर) इस चरण में बूलियन सर्किट को गारबल्ड सर्किट प्राप्त करने के लिए एन्क्रिप्ट करता है। ऐलिस सर्किट में प्रत्येक तार के लिए दो यादृच्छिक रूप से उत्पन्न स्ट्रिंग्स को लेबल करता है: एक बूलियन डेटा प्रकार सिमेंटिक 0 के लिए और एक 1 के लिए। (लेबल k-बिट लंबा है जहां k सुरक्षा पैरामीटर है और आमतौर पर 128 पर सेट होता है।) अगला, वह सर्किट के सभी गेटों पर जाती है और 0 और 1 को संबंधित लेबल के साथ सत्य तालिका में बदल देती है। नीचे दी गई तालिका दो इनपुट वाले AND गेट के लिए सत्य तालिका दिखाती है $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 एन्क्रिप्ट किया जाने वाला मान है (#Fixed-key Blockcipher|Fixed-Key Blockcipher देखें)।

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})$

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

डेटा ट्रांसफर

एलिस बॉब को सर्किट में सभी फाटकों के लिए गणना की गई विकृत तालिकाएँ भेजती है। विकृत तालिकाओं को खोलने के लिए बॉब को इनपुट लेबल की आवश्यकता है। इस प्रकार, ऐलिस अपने इनपुट के अनुरूप लेबल चुनती है $a$ और उन्हें बॉब को भेजता है। उदाहरण के लिए, यदि ऐलिस का इनपुट है $\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)$. इन मानों का उपयोग करते हुए, XOR गेट के आउटपुट वायर का लेबल $w^{c}$ इनपुट तारों के साथ $w^{a}$, $w^{b}$ इसके लिए सेट है $X^{c}=X^{a}\oplus X^{b}$. इस अनुकूलन के लिए यादृच्छिक ओरेकल में सुरक्षा का प्रमाण फ्री-एक्सओआर पेपर में दिया गया है।

निहितार्थ

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

फिक्स्ड-कुंजी अवरोधक

यह विधि SHA-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$ एक अद्वितीय-प्रति-गेट संख्या है (उदाहरण के लिए, गेट पहचानकर्ता) जिसे ट्वीक कहा जाता है।

आधा और

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

सुरक्षा

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

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

यह भी देखें

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

अग्रिम पठन

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