क्रिप्टोग्राफ़र संपूर्ण खोज गोपनीयता के लिए एक दृष्टिकोण तैयार करते हैं | क्वांटा पत्रिका

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

ये स्थितियाँ क्रिप्टोग्राफी में एक महत्वपूर्ण प्रश्न को जन्म देती हैं: आपने जो भी एक्सेस किया है उसके बारे में कुछ भी बताए बिना आप सार्वजनिक डेटाबेस से जानकारी कैसे खींच सकते हैं? यह लाइब्रेरियन को यह जाने बिना कि कौन सी किताब है, लाइब्रेरी से जाँचने के बराबर है।

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

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

"[यह] क्रिप्टोग्राफी में कुछ ऐसा है जो मुझे लगता है कि हम सभी चाहते थे लेकिन हमें विश्वास नहीं था कि यह मौजूद है," कहा विनोद वैकुंठनाथन, मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी में एक क्रिप्टोग्राफर जो पेपर में शामिल नहीं था। "यह एक ऐतिहासिक परिणाम है।"

निजी डेटाबेस एक्सेस की समस्या 1990 के दशक में सामने आई। सबसे पहले, शोधकर्ताओं ने माना कि एकमात्र समाधान प्रत्येक खोज के दौरान पूरे डेटाबेस को स्कैन करना था, जो आपकी पुस्तक के साथ लौटने से पहले लाइब्रेरियन को प्रत्येक शेल्फ को स्कैन करने जैसा होगा। आख़िरकार, यदि खोज से कोई अनुभाग छूट जाता है, तो लाइब्रेरियन को पता चल जाएगा कि आपकी पुस्तक लाइब्रेरी के उस हिस्से में नहीं है।

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

2000 के दशक की शुरुआत में, शोधकर्ताओं को संदेह होने लगा कि वे डेटाबेस को "प्रीप्रोसेसिंग" करके पूर्ण-स्कैन बाधा से बच सकते हैं। मोटे तौर पर, इसका मतलब पूरे डेटाबेस को एक विशेष संरचना के रूप में एन्कोड करना होगा, ताकि सर्वर उस संरचना के केवल एक छोटे से हिस्से को पढ़कर एक प्रश्न का उत्तर दे सके। पर्याप्त सावधानी से प्रीप्रोसेसिंग, सैद्धांतिक रूप से, इसका मतलब यह हो सकता है कि जानकारी होस्ट करने वाला एक सर्वर केवल एक बार प्रक्रिया से गुजरता है, जिससे सभी भविष्य के उपयोगकर्ताओं को बिना किसी अधिक प्रयास के निजी तौर पर जानकारी प्राप्त करने की अनुमति मिलती है।

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

लेकिन 2017 में शोधकर्ताओं के दो समूह प्रकाशित परिणाम जिससे उसका मन बदल गया. उन्होंने पहला प्रोग्राम बनाया जो इस प्रकार की निजी जानकारी पुनर्प्राप्ति कर सकता था, लेकिन वे यह दिखाने में सक्षम नहीं थे कि प्रोग्राम सुरक्षित थे। (क्रिप्टोग्राफर किसी सिस्टम की सुरक्षा को यह दिखाकर प्रदर्शित करते हैं कि इसे तोड़ना किसी कठिन समस्या को हल करने जितना ही कठिन है। शोधकर्ता इसकी तुलना किसी विहित कठिन समस्या से करने में सक्षम नहीं थे।)

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

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

उस पद्धति से कोई सुधार नहीं हुआ, और समूह हार मानने के करीब आ गया - जब तक कि उन्हें आश्चर्य नहीं हुआ कि क्या यह उपकरण वास्तव में प्रतिष्ठित एकल-सर्वर मामले में काम कर सकता है। उन्होंने देखा, एक बहुपद को पर्याप्त सावधानी से चुनें, और एक एकल सर्वर 2011 के परिणाम के आधार पर इसे प्रीप्रोसेस कर सकता है - सुरक्षित, कुशल लुकअप योजना की उपज, जिस पर विच ने वर्षों से विचार किया था। आख़िरकार अचानक, उन्होंने कठिन समस्या का समाधान कर लिया।

पहले तो लेखकों को इस पर विश्वास नहीं हुआ। "आइए पता लगाएं कि इसमें क्या गलत है," विच्स को याद आया। "हम यह पता लगाने की कोशिश करते रहे कि यह कहां टूटता है।"

लेकिन समाधान कायम रहा: उन्होंने वास्तव में एकल-सर्वर डेटाबेस को प्रीप्रोसेस करने का एक सुरक्षित तरीका खोज लिया था ताकि कोई भी गुप्त रूप से जानकारी खींच सके। “यह वास्तव में उन सभी चीज़ों से परे है जिनकी हमने आशा की थी,” कहा युवल ईशाई, इज़राइल में टेक्नियन में एक क्रिप्टोग्राफर जो इस काम में शामिल नहीं था। उन्होंने कहा, ''यह परिणाम है कि ''हम मांगने के लिए पर्याप्त साहसी भी नहीं थे।''

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

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

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

अभी के लिए, कोई भी योजना व्यावहारिक रूप से उपयोगी नहीं है: प्रीप्रोसेसिंग वर्तमान में चरम सीमा पर मदद करती है, जब डेटाबेस का आकार अनंत की ओर बढ़ जाता है। लेकिन वास्तव में इसे तैनात करने का मतलब है कि वे बचतें पूरी नहीं हो सकेंगी, और इस प्रक्रिया में बहुत अधिक समय और भंडारण स्थान की खपत होगी।

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

क्वांटा अपने दर्शकों को बेहतर सेवा देने के लिए सर्वेक्षणों की एक श्रृंखला आयोजित कर रहा है। हमारा ले कंप्यूटर विज्ञान पाठक सर्वेक्षण और आपको निःशुल्क जीतने के लिए प्रवेश दिया जाएगा क्वांटा माल।