Weak Private Information Retrieval for Graph-based Storage

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

हालाँकि, एक पेंच है। अपने सवाल को छिपाने के लिए, आपको आमतौर पर बहुत सारी अतिरिक्त, बेकार जानकारी मांगनी पड़ती है (जैसे कि यह दिखाने के लिए कि आप कोई भी किताब मांग सकते हैं, पूरी लाइब्रेरी की हर किताब मांग लेना)। यह धीमा और बर्बादी भरा है। लंबे समय तक, वैज्ञानिकों ने सोचा कि आपको या तो 100% अदृश्य (पूर्ण गोपनीयता) या तेज़ (उच्च गति) में से किसी एक को चुनना होगा। आप दोनों नहीं रख सकते थे। लेकिन क्या होगा यदि आप लाइब्रेरियन को अपने अनुरोध पर थोड़ा सा झांकने की अनुमति देने के लिए तैयार हों? क्या होगा यदि आप थोड़ी सी गोपनीयता के बदले गति में भारी उछाल पाने के लिए तैयार हों? यह प्रश्न यह शोध पत्र संबोधित करता है। यह "वीक प्राइवेट इंफॉर्मेशन रिट्रीवल" (कमजोर निजी सूचना पुनर्प्राप्ति) नामक एक मध्य मार्ग की खोज करता है: यदि हम थोड़ी सी, नियंत्रित जानकारी लीक होने की अनुमति देते हैं, तो हम कितनी तेज़ गति से जा सकते हैं?

ग्राफ लाइब्रेरी की कहानी

इस शोध पत्र के लेखक, शोदासाक्षरी विद्या, चंदन आनंद और प्रसाद कृष्णिशर ने एक बहुत ही विशिष्ट प्रकार के पुस्तकालय को देखने का निर्णय लिया: जो एक ग्राफ (graph) की तरह व्यवस्थित है। कल्पना कीजिए कि सर्वर (लाइब्रेरियन) कागज पर बिंदुओं की तरह हैं, और फाइलें (किताबें) उन्हें जोड़ने वाली रेखाओं की तरह हैं। यदि एक फाइल सर्वर A और सर्वर B पर संग्रहीत है, तो उनके बीच एक रेखा खींची जाती है। यह "ग्राफ-आधारित स्टोरेज" आधुनिक वितरित प्रणालियों (distributed systems) में डेटा को व्यवस्थित करने का एक सामान्य तरीका है।

अतीत में, शोधकर्ताओं ने बिना किसी लीकेज के इन ग्राफ-लाइब्रेरी से फाइलें प्राप्त करने का तरीका खोजा था। लेकिन लेखकों ने सोचा: क्या हम नियमों को थोड़ा ढीला करके बेहतर कर सकते हैं? उन्होंने एक नया प्रोटोकॉल प्रस्तावित किया जिसे वे G-WPIR (ग्राफ-आधारित वीक प्राइवेट इंफॉर्मेशन रिट्रीवल) कहते हैं।

यहाँ मूल विचार को एक सरल उपमा के साथ समझाया गया है:

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

लेखकों की नई तरकीब एक बायस्ड कॉइन (पक्षपाती सिक्का) का उपयोग करना है। एक निष्पक्ष सिक्के (50/50) के बजाय, वे एक ऐसे सिक्के का उपयोग करते हैं जो 'टेल्स' (मौन) पर अधिक आने के लिए थोड़ा झुका हुआ है।

• ट्रेड-ऑफ (समझौता): क्योंकि आप अधिक बार चुप रहते हैं, आप कम दोस्तों से बात करते हैं, और आपको अपना उत्तर बहुत तेज़ी से मिल जाता है। यह "रेट" (गति) है।
• लागत: हालाँकि, क्योंकि आप अधिक बार चुप रहते हैं, वे दोस्त जो वास्तव में आपको सवाल पूछते हुए सुनते हैं, वे आपके रहस्य के बारे में थोड़ा बेहतर अनुमान लगा सकते हैं। यह "लीकेज" (रिसाव) है।

यह शोध पत्र सिद्ध करता है कि "हेवीनेस" (सिक्के के झुकाव) को समायोजित करके (एक पैरामीटर जिसे वे $p$ कहते हैं), आप एक वक्र (curve) पर सुचारू रूप से फिसल सकते हैं। आप लगभग पूरी तरह से निजी (सिक्का निष्पक्ष है, गति धीमी है) या लगभग पूरी तरह से तेज़ (सिक्का बहुत भारी है, गति उच्च है, लेकिन गोपनीयता कम है) होने का विकल्प चुन सकते हैं। उनकी समाधान की सुंदरता यह है कि यह किसी भी आकार के ग्राफ के लिए काम करता है, चाहे वह कनेक्शनों का एक उलझा हुआ जाल हो या एक व्यवस्थित संरचना।

"लीकिंग" को मापने के दो तरीके

यह सुनिश्चित करने के लिए कि वे अपने "लीकेज" को सही ढंग से माप रहे हैं, लेखकों ने दो अलग-अलग पैमाने (रूलर) का उपयोग किया:

1. म्युचुअल इंफॉर्मेशन (Mutual Information): यह मापता है कि औसतन आपके रहस्य के बारे में दोस्त का ज्ञान कितना बढ़ जाता है। यह पूछने जैसा है, "औसतन, वे अब मेरे रहस्य के बारे में कितना अधिक जानते हैं?"
2. मैक्सिमल लीकेज (Maximal Leakage): यह एक सख्त पैमाना है। यह पूछता है, "मेरे द्वारा सवाल पूछे जाने के बाद एक दोस्त अपने रहस्य के बारे में सबसे अच्छा अनुमान क्या लगा सकता है?" यह सबसे खराब स्थिति (worst-case scenario) को देखता है।

शोध पत्र दोनों पैमानों के लिए सटीक गणितीय सूत्र प्रदान करता है, जो दिखाता है कि आप प्रत्येक थोड़े से खोए हुए गोपनीयता के लिए कितनी गति प्राप्त करते हैं।

विशेष मामले: पूर्ण वृत्त और दो टीमें

लेखकों ने केवल अव्यवधर, यादृच्छिक ग्राफों पर ही नहीं रुके। उन्होंने यह देखने के लिए कि चरम मामलों में गणित कैसे काम करता है, दो बहुत ही विशिष्ट, अत्यधिक संगठित प्रकार के ग्राफों पर अपने विचार का परीक्षण किया:

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

   • एक मोड़: उनके खेल के मानक संस्करण में, लाइन में मौजूद "पहला" दोस्त कुछ भी लीक नहीं करता है, जबकि "आखिरी" दोस्त सबसे अधिक लीक करता है। यह अनुचित लगा। इसलिए, उन्होंने एक साइक्लिक-शिफ्ट प्रोटोकॉल (Cyclic-Shift Protocol) का आविष्कार किया। कल्पना कीजिए कि दोस्त एक घेरे में बैठे हैं, और खेल शुरू होने से पहले, आप गुप्त रूप से घेरे को घुमाते हैं ताकि हर किसी के पास किसी भी सीट में होने का समान अवसर हो। यह लीकेज को सभी के लिए समान बनाता है। किसी को भी "लीकी" (रिसाव करने वाला) व्यक्ति के रूप में अलग नहीं किया गया है; जोखिम पूरे समूह में समान रूप से साझा किया गया है।

2. द कम्पलीट बाइटाइट ग्राफ (दो टीमों वाला खेल): कल्पना कीजिए कि सर्वर दो टीमों में विभाजित हैं, टीम A और टीम B। फाइलें केवल टीम A के एक सदस्य और टीम B के एक सदस्य के बीच संग्रहीत की जाती हैं (टीम A के भीतर कोई भी आपस में फाइल साझा नहीं करता है)।

   • यहाँ, परिणाम दिलचस्प थे। लेखकों ने पाया कि पूरी टीम A पूरी तरह से निजी (शून्य लीकेज) रह सकती है, जबकि टीम B लीकेज का भार उठाती है। यह एक ऐसी कुशल प्रणाली की तरह है जहाँ कुछ सर्वर पूरी तरह से सुरक्षित रहते हैं, जबकि अन्य टीम गति बढ़ाने के लिए गोपनीयता के समझौते को संभालती है। यह एक बहुत ही कुशल सिस्टम की अनुमति देता है जहाँ कुछ सर्वर पूरी तरह से सुरक्षित रहते हैं जबकि अन्य जोखिम को संभालते हैं।

उन्होंने क्या पाया (और क्या नहीं)

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

शोध पत्र यह दावा नहीं करता है कि उसने "परफेक्ट" गोपनीयता के साथ "परफेक्ट" गति की समस्या को हल कर दिया है। वास्तव में, यह स्पष्ट रूप से तर्क देता है कि यदि आप पुराने तरीकों से तेज़ होना चाहते हैं, तो आप दोनों को एक साथ नहीं रख सकते। यह सिद्ध करता है कि उच्च गति प्राप्त करने के लिए, आपको कुछ लीकेज स्वीकार करना ही होगा।

लेखक अपने गणित को लेकर बहुत आश्वस्त हैं। उन्होंने इसे केवल कंप्यूटर पर सिम्युलेट नहीं किया; उन्होंने गणितीय प्रमाण (Theorems 1, 2, 3, 4, और 5) प्रदान किए जो दिखाते हैं कि किसी भी ग्राफ के लिए दर (rate) और लीकेज कैसे संबंधित हैं, और विशेष रूप से कम्पलीट और बाइटाइट ग्राफ के लिए। उन्होंने दिखाया कि उनका प्रोटोकॉल "सही" है (आप हमेशा सही फाइल प्राप्त करते हैं) और उन्होंने सटीक "लीकेज" संख्या की गणना की।

यह क्यों महत्वपूर्ण है

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

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