Billion-Scale Nearest-Neighbor Search under Fully Homomorphic Encryption on a Single GPU, Balancing Leakage and Cost
यह शोधपत्र एक पूर्णतः होमोमोर्फिक एन्क्रिप्शन (fully homomorphic encryption) के तहत बिलियन-स्केल निकटतम-पड़ोसी खोज (nearest-neighbor search) के लिए एक GPU-त्वरित प्रणाली प्रस्तुत करता है जो रैंक न्यूनीकरण (rank reduction) और पदानुक्रमित रूटिंग (hierarchical routing) को संयोजित करके व्यावहारिक विलंबता (latency) प्राप्त करता है, साथ ही सीडेड पैडिंग (seeded padding) के माध्यम से संबंधित ज्यामितीय रिसाव (geometric leakage) को परिमाणित और कम करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आपके पास अरबों तस्वीरों वाली एक लाइब्रेरी है, और आप उस एक तस्वीर को खोजना चाहते हैं जो आपकी जेब में रखी तस्वीर से सबसे अधिक मिलती-जुलती हो। सामान्य रूप से, एक कंप्यूटर मिलान खोजने के लिए हर तस्वीर को स्कैन करेगा, लेकिन क्या होगा यदि आप अपनी तस्वीर को कंप्यूटर को दिखा नहीं सकते क्योंकि वह निजी है? क्या होगा यदि लाइब्रेरी किसी ऐसे अजनबी की है जिस पर आप भरोसा नहीं करते? यह वह समस्या है जिसे हल करने के लिए शोधकर्ताओं ने प्रयास किया। वे एक ऐसा तरीका चाहते थे जिससे एक कंप्यूटर एक विशाल, गुप्त डेटाबेस में खोज कर सके, बिना यह जाने कि वास्तव में क्या सवाल पूछा जा रहा है। इसे करने के लिए, वे 'फुली होमोमोर्फिक एन्क्रिप्शन' (fully homomorphic encryption) नामक एक विधि का उपयोग करते हैं, जो एक पारदर्शी बक्से के भीतर आपके सवाल को रखने जैसा है। कंप्यूटर उस बक्से को खोले बिना उस पर गणना कर सकता है, और एक ऐसा परिणाम वापस करता है जो अभी भी लॉक रहता है। केवल आपके पास, जिसके पास चाबी है, उस अंतिम बक्से को खोलने और उत्तर देखने का अधिकार होता है। वर्षों तक, यह विचार बहुत बड़े डेटा संग्रहों के लिए उपयोगी होने के लिए बहुत धीमा था, क्योंकि बक्से को बंद रखने के लिए आवश्यक गणित अविश्वसनीय रूप से भारी था।
शोधकर्ताओं की एक टीम ने अब ऐसा सिस्टम बनाया है जो इसे एक अरब वस्तुओं के लिए संभव बनाता है, जो एक सिंगल ग्राफिक्स कार्ड पर चलता है। वे 1.39 अरब प्रविष्टियों के डेटाबेस में सबसे समान छवियों को खोजने में सफल रहे, बिना सर्वर द्वारा प्रश्न देखे। यह सिस्टम दो मुख्य तरकीबों का उपयोग करके गति बढ़ाने में सफल रहा। पहला, यह छवियों को सरल बनाता है। प्रत्येक फोटो के हर सूक्ष्म विवरण की तुलना करने के बजाय, सिस्टम खोज शुरू होने से पहले प्रत्येक छवि के विवरण को एक छोटे, सरल संस्करण में बदल देता है। इससे गणित बहुत हल्का हो जाता है। दूसरा, यह हर फोटो को नहीं देखता है। इसके बजाय, यह एक पदानुक्रम (hierarchy) का उपयोग करता है, जैसे कि एक मानचित्र जो पहले एक सामान्य पड़ोस की ओर इशारा करता है, फिर एक विशिष्ट सड़क की ओर, और अंत में कुछ घरों की ओर। कंप्यूटर केवल उन चयनित क्षेत्रों में फोटो की जांच करता है, बाकी को छोड़ देता है। यह सिस्टम को सही उत्तर तेजी से खोजने की अनुमति देता है, भले ही डेटा एक बक्से में बंद हो।
परिणाम बताते हैं कि यह दृष्टिकोण उल्लेखनीय रूप से अच्छा काम करता है। 1.39 अरब छवियों के डेटासेट पर, सिस्टम ने 90 प्रतिशत बार शीर्ष दस परिणामों में सही मिलान पाया। जब शोधकर्ताओं ने लगभग-समान (near-duplicates) छवियों की अनुमति दी—क्योंकि इंटरनेट एक ही फोटो की थोड़ी अलग प्रतियों से भरा है—तो सफलता दर बढ़कर 95 प्रतिशत हो गई। पूरी प्रक्रिया में एक सिंगल ग्राफिक्स कार्ड पर प्रति खोज लगभग छह सेकंड का समय लगा। यह एक 'वॉर्म, डिप्लॉयबल स्पीड' (warm, deployable speed) है, जिसका अर्थ है कि यदि डेटा पहले से तैयार हो, तो यह वास्तविक दुनिया के उपयोग के लिए पर्याप्त तेज़ है। शोधकर्ताओं ने सिस्टम का परीक्षण 96-आयामी वेक्टर्स के एक अन्य बिलियन-आइटम संग्रह पर भी किया, जिसमें केवल 2.3 सेकंड में 90 प्रतिशत सफलता दर प्राप्त हुई। ये संख्याएं सिद्ध करती हैं कि अरबों एन्क्रिप्टेड वस्तुओं को एक सिंगल मशीन पर खोजना अब केवल एक सैद्धांतिक सपना नहीं है।
हालाँकि, शोधकर्ता इस बात को मापने में भी सावधान थे कि इस गति की गोपनीयता के रूप में क्या कीमत चुकानी पड़ती है। जबकि सर्वर न तो प्रश्न देखता है और न ही उत्तर, वह यह देख सकता है कि कंप्यूटर किन समूहों के डेटा को देखने के लिए कहता है। एक्सेस (access) का यह पैटर्न डेटाबेस के बारे में सुराग प्रकट कर सकता है। यह देखते हुए कि कौन से समूह एक साथ अनुरोधित किए जाते हैं, एक पर्यवेक्षक उस मानचित्र का लगभग 72 प्रतिशत पुनर्निर्माण कर सकता है जो दिखाता है कि डेटा कैसे व्यवस्थित है। वे यह भी अनुमान लगा सकते थे कि दो अलग-अलग खोजें समान चीजों की तलाश कर रही थीं यदि उन्होंने एक ही समूहों को अनुरोधित किया। इसे ठीक करने के लिए, शोधकर्ताओं ने एक ऐसी विधि आजमाई जहाँ कंप्यूटर वास्तविक समूहों के साथ अतिरिक्त, नकली समूहों के लिए भी अनुरोध करता है ताकि पैटर्न को छिपाया जा सके। यदि नकली समूह हर बार बदलते हैं, तो एक चतुर हमलावर कई खोजों की तुलना करके सच्चाई का पता लगा सकता है। लेकिन यदि नकली समूह स्थिर हैं और हमेशा एक जैसे रहते हैं, तो हमलावर उन्हें हटा नहीं सकता। यह "सीडेड" (seeded) पैडिंग सूचना के रिसाव को लगभग 35 गुना कम कर देती है, जिससे डेटाबेस मैप की रिकवरी 72 प्रतिशत से घटकर केवल 2 प्रतिशत रह जाती है।
टीम ने डेटा को छोटे कोडों में तोड़ने वाली एक तकनीक, जैसे कि 'प्रोडक्ट क्वांटाइजेशन' (product quantization), का उपयोग करके खोज को और तेज़ बनाने के अन्य तरीकों का भी पता लगाया। उन्होंने पाया कि एन्क्रिप्शन के तहत, यह विधि अच्छी तरह से काम नहीं करती है। या तो यह मानक एन्क्रिप्टेड खोज को मात देने में विफल रही या इसने डेटा संरचना के बारे में बहुत अधिक जानकारी लीक कर दी। उन्होंने इसे उपयोग न करने का निर्णय लिया, और डेटा विवरण के आकार को कम करने और पदानुक्रमित मानचित्र का उपयोग करने वाले सरल तरीके पर टिके रहे। यह विकल्प एक प्रमुख निष्कर्ष को उजागर करता है: कभी-कभी, एक सीधा दृष्टिकोण जटिल दृष्टिकोण से बेहतर होता है जब प्राथमिकता गोपनीयता हो।
यह सिस्टम इस तरह काम करता है कि उपयोगकर्ता सर्वर को एक एन्क्रिप्टेड प्रश्न भेजता है। सर्वर, जिसके पास एन्क्रिप्टेड डेटाबेस है, लॉक किए गए डेटा पर गणित करता है। यह पहले कुछ हजार व्यापक श्रेणियों की जांच करता है, फिर कुछ हजार अधिक विशिष्ट समूहों तक सीमित होता है, और अंत में उन समूहों में वास्तविक छवियों को स्कोर करता है। प्रत्येक चरण पर, सर्वर एन्क्रिप्टेड स्कोर वापस करता है। उपयोगकर्ता स्कोर को डिक्रिप्ट करता है, यह तय करता है कि आगे किन समूहों को देखना है, और एक नया अनुरोध भेजता है। सर्वर उपयोगकर्ता के निर्णय या अंतिम उत्तर को कभी नहीं देखता। यह सिलसिला तब तक चलता रहता है जब तक कि शीर्ष दस मिलान नहीं मिल जाते। शोधकर्ताओं ने डेटा लोड करने और स्कोरिंग करने में लगने वाले समय को मापा, जिसमें उपयोगकर्ता द्वारा अंतिम परिणाम को डिक्रिप्ट करने या नेटवर्क पर डेटा के यात्रा करने का समय शामिल नहीं है। उन्होंने पाया कि समय मुख्य रूप से कंप्यूटर की मेमोरी में एन्क्रिप्टेड डेटा लोड करने में लगता है, न कि गणित द्वारा।
गोपनीयता जोखिमों के अपने विश्लेषण में, शोधकर्ताओं ने दिखाया कि लीकेज (leak) इस बात का गुण है कि खोज कैसे रूट की जाती है, न कि उस विशिष्ट डेटा का जिसकी खोज की जा रही है। चाहे डेटाबेस में चेहरे हों या सामान्य चित्र, एक्सेस पैटर्न ने संरचनात्मक जानकारी के समान ही स्तर को प्रकट किया। उन्होंने प्रदर्शित किया कि बिना सुरक्षा के, एक पर्यवेक्षक डेटा के समूहीकरण (grouping) को लगभग पूरी तरह से प्राप्त कर सकता था। फिक्स्ड-ग्रुप पैडिंग के साथ, यह रिकवरी काफी कम हो गई, हालांकि यह पूरी तरह से समाप्त नहीं हुई। ट्रेड-ऑफ स्पष्ट है: एक्सेस पैटर्न को छिपाने के लिए, सिस्टम को आवश्यक से अधिक डेटा प्राप्त करना होगा, जिससे खोज को पूरा करने में लगने वाला समय बढ़ जाएगा। शोधकर्ताओं ने दिखाया कि इस लागत को प्रबंधित किया जा सकता है, लेकिन इसके लिए इस बात के बीच संतुलन बनाना आवश्यक है कि कितनी गोपनीयता चाहिए और सिस्टम को कितनी गति से चलना चाहिए।
यह कार्य बड़े पैमाने पर निजी खोज को व्यावहारिक बनाने की दिशा में एक महत्वपूर्ण कदम है। यह सिद्ध करता है कि आप अपने इरादे को प्रकट किए बिना एक अरब वस्तुओं की खोज कर सकते हैं, बशर्ते आप कुछ सेकंड की देरी और सावधानीपूर्वक प्रबंधित गोपनीयता लागत को स्वीकार करने के लिए तैयार हों। यह सिस्टम किसी जादू या अपुष्ट सिद्धांतों पर निर्भर नहीं है; यह एक वास्तविक समस्या को हल करने के लिए स्थापित गणित और चतुर इंजीनियरिंग का उपयोग करता है। शोधकर्ताओं ने इस प्रणाली को बनाने और चलाने के लिए एक पूर्ण मार्गदर्शिका प्रदान की है, जिसमें गति और सटीकता के लिए सटीक सेटिंग्स भी शामिल हैं। उन्होंने यह भी दिखाया है कि सीमाएँ कहाँ हैं, विशेष रूप से उस जानकारी के संबंध में जो खोज पैटर्न के माध्यम से लीक होती है। जो छिपा हुआ है और जो प्रकट होता है, उसके बारे में पारदर्शी होकर, वे सुरक्षित डेटा खोज के लिए एक यथार्थवादी मार्ग प्रदान करते हैं।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।