Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval with Adversarial Servers

तकनीकी सारांश: प्रतिकूल सर्वरों के साथ क्षमता-प्राप्त निजी सूचना पुनर्प्राप्ति (PIR) के लिए आवश्यक और पर्याप्त स्थितियाँ

समस्या विवरण

प्राइवेट इंफॉर्मेशन रिट्रीवल (PIR) एक उपयोगकर्ता को $M$ संदेशों के डेटाबेस से एक विशिष्ट संदेश प्राप्त करने में सक्षम बनाता है जो $S$ सर्वरों पर संग्रहीत हैं, बिना सर्वरों को वांछित इंडेक्स का पता चले। जबकि विभिन्न प्रतिकूल (adversarial) PIR परिदृश्यों के लिए सूचना-सैद्धांतिक क्षमता (अधिकतम डाउनलोड दक्षता) को पूर्व साहित्य में स्थापित किया गया है, क्वेरी स्कीमें बनाने के लिए व्यवस्थित विधियों का अभाव है जो इस क्षमता को प्राप्त कर सकें। विशेष रूप से, मौजूदा साहित्य ने स्पष्ट रूप से यह परिभाषित नहीं किया है कि प्रतिकूल व्यवहारों की उपस्थिति में गोपनीयता, शुद्धता और क्षमता प्राप्ति की गारंटी देने के लिए क्वेरी मैट्रिसेस (query matrices) को किन स्थितियों को संतुष्ट करना चाहिए।

यह शोध पत्र तीन प्राथमिक प्रतिकूल परिदृश्यों को संबोधित करता है:

1. कोल्यूडिंग (Colluding) PIR: $T$ सर्वरों का एक समूह मिलीभगत करता है ताकि वे अपनी क्वेरी साझा कर सकें और उपयोगकर्ता के वांछित इंडेक्स का अनुमान लगाने का प्रयास कर सकें।
2. रोबस्ट (Robust) PIR: $U$ सर्वर अनुत्तरदायी (erasure) हैं, और उपयोगकर्ता को कुल $S+U$ सर्वरों में से शेष $S$ सर्वरों के उपयोग से संदेश प्राप्त करना चाहिए।
3. बायज़ेंटाइन (Byzantine) PIR: $B$ सर्वर गलत (noisy) प्रतिक्रियाएँ देते हैं, और उपयोगकर्ता इन त्रुटियों को सुधारने के लिए $S+2B$ सर्वरों का उपयोग करता है।

मुख्य समस्या क्वेरी जनरेशन प्रक्रिया पर उन गणितीय स्थितियों को व्युत्पन्न करने की है जो यह सुनिश्चित करती हैं कि एक PIR योजना न केवल निजी और सही हो, बल्कि डाउनलोड दर (क्षमता) के सैद्धांतिक ऊपरी स्तर को भी प्राप्त करे।

कार्यप्रणाली (Methodology)

लेखक एक सूचना-सैद्धांतिक दृष्टिकोण अपनाते हैं, जो रैखिक PIR योजनाओं पर ध्यान केंद्रित करता है जहाँ सर्वर प्रतिक्रियाओं का निर्माण संदेशों और क्वेरीज़ के मैट्रिक्स उत्पादों के रूप में किया जाता है। कार्यप्रणाली में निम्नलिखित चरण शामिल हैं:

1. औपचारिकीकरण (Formalization): शोध पत्र सिस्टम मॉडल को परिभाषित करता है, जिसमें संदेश एंट्रॉपी, एक रैंडम फैक्टर $F$ के माध्यम से क्वेरी जनरेशन, और कोल्यूडिंग, रोबस्ट और बायज़ेंटाइन सेटिंग्स के लिए विशिष्ट गोपनीयता और शुद्धता बाधाएं शामिल हैं।
2. शर्तों का व्युत्पत्ति (Derivation of Conditions):
   • शुद्धता (Correctness): लेखक स्थापित करते हैं कि एक डिकोडिंग मैट्रिक्स $D_m$ का अस्तित्व होना चाहिए ताकि सर्वर प्रतिक्रियाओं का रैखिक संयोजन वांछित संदेश $W_m$ प्रदान करे और अन्य सभी संदेशों को रद्द कर दे।
   • गोपनीयता (Privacy): कोल्यूडिंग और गैर-कोल्यूडिंग (रोबस्ट/बायज़ेंटाइन) दोनों परिदृश्यों के लिए, लेखक क्वेरी सेट की एंट्रॉपी का विश्लेषण करते हैं। वे सिद्ध करते हैं कि गोपनीयता तब संतुष्ट होती है जब एक विशिष्ट क्वेरी रियलाइजेशन उत्पन्न करने वाले संभावित रैंडम फैक्टर्स $f$ की संख्या, वांछित संदेश इंडेक्स के संबंध में स्वतंत्र रूप से स्थिर रहती है। यह सुनिश्चित करता है कि सर्वरों के किसी भी उपसमुच्चय द्वारा देखी गई क्वेरीज़ का वितरण उपयोगकर्ता के चुनाव से स्वतंत्र है।
   • क्षमता प्राप्ति (Capacity Achievability): पिछले क्षमता व्युत्पत्तियों (विशेष रूप से म्यूचुअल इंफॉर्मेशन और कंडीशनल एंट्रॉपी से संबंधित असमानताओं) का विश्लेषण करके, लेखक निर्धारित करते हैं कि क्षमता प्राप्त करने के लिए इन असमानताओं को समीकरणों के रूप में संतुष्ट करना आवश्यक है। इससे क्वेरी मैट्रिसेस पर विशिष्ट रैंक स्थितियाँ प्राप्त होती हैं।
3. सत्यापन (Verification): व्युत्पन्न शर्तों को दो प्रतिनिधि मौजूदा विधियों पर लागू किया जाता है: सन (Sun) की विधि (जो ज्ञात रूप से क्षमता-प्राप्त है) और वांग (Wang) की विधि (जो कुछ संदर्भों में उप-इष्टतम है)। लेखक सत्यापित करते हैं कि क्या ये विधियाँ उनके द्वारा नए परिभाषित आवश्यक और पर्याप्त शर्तों को पूरा करती हैं।

मुख्य योगदान

इस कार्य का प्राथमिक योगदान प्रतिकूल सेटिंग्स में क्षमता-प्राप्त PIR योजनाओं के लिए आवश्यक और पर्याप्त स्थितियों का व्युत्पत्ति है, जिसे क्वेरी मैट्रिसेस के गुणों के रूप में स्पष्ट रूप से व्यक्त किया गया है।

1. शुद्धता के लिए स्थितियाँ

किसी भी वांछित संदेश $m$ के लिए, एक डिकोडिंग मैट्रिक्स $D_m$ का अस्तित्व होना चाहिए ताकि:
$$D_m \begin{pmatrix} Q^{(m)}_1 \\ \vdots \\ Q^{(m)}_S \end{pmatrix} = \begin{pmatrix} O \\ E \\ O \end{pmatrix}^\top$$
जहाँ $E$ एक आइडेंटिटी मैट्रिक्स है और $O$ गैर-वांछित संदेशों के अनुरूप शून्य मैट्रिसेस को दर्शाता है।

2. गोपनीयता के लिए स्थितियाँ

• रोबस्ट/बायज़ेंटाइन गोपनीयता: किसी भी सर्वर $j$ और किन्हीं दो संदेश इंडेक्स $m, m'$ के लिए, रैंडम फैक्टर्स $f$ की संख्या जो एक ही क्वेरी रियलाइजेशन $q_j$ उत्पन्न करती है, समान होनी चाहिए: $|\{f | Q^{(m)}_j = q_j\}| = |\{f | Q^{(m')}_j = q_j\}|$।
• कोल्यूडिंग गोपनीयता: यही स्थिति $T$ कोल्यूडिंग सर्वरों के किसी भी सेट के लिए लागू होती है: $|\{f | Q^{(m)}_T = q_T\}| = |\{f | Q^{(m')}_T = q_T\}|$।

3. क्षमता प्राप्ति के लिए स्थितियाँ

शोध पत्र क्वेरी मैट्रिसेस पर रैंक-आधारित स्थितियाँ स्थापित करता है:

• रोबस्ट/बायज़ेंटाइन PIR के लिए:
  • सभी सर्वरों में गैर-वांछित संदेशों के लिए क्वेरी मैट्रिक्स का रैंक, किसी एकल सर्वर के क्वेरी मैट्रिक्स के अधिकतम रैंक के बराबर होना चाहिए: $\text{rank } Q^{(m)}_{1:S+\mu}[\bar{m}] = \max_{j} \text{rank } Q^{(m)}_j[\bar{m}]$।
  • $S$ सर्वरों के किसी भी उपसमुच्चय $\kappa$ के लिए, वांछित संदेश घटकों का क्वेरी मैट्रिक्स का रैंक, व्यक्तिगत रैंकों के योग के बराबर होना चाहिए: $\text{rank } Q^{(m)}_\kappa[I] = \sum_{j \in \kappa} \text{rank } Q^{(m)}_j[I]$।
• कोल्यूडिंग PIR के लिए:
  • सभी सर्वरों में वांछित संदेश घटकों के लिए समान रैंक योगात्मकता (rank additivity) स्थितियाँ लागू होती हैं।
  • गैर-वांछित संदेशों के लिए सभी सर्वरों में क्वेरी मैट्रिक्स का रैंक, $T$ कोल्यूडिंग सर्वरों के किसी भी उपसमुच्चय द्वारा प्राप्त अधिकतम रैंक के बराबर होना चाहिए: $\text{rank } Q^{(m)}_{1:S}[\bar{m}] = \max_{T} \text{rank } Q^{(m)}_T[\bar{m}]$।

परिणाम

लेखकों ने इन व्युत्पन्न शर्तों को मौजूदा PIR योजनाओं को सत्यापित करने के लिए लागू किया:

1. सन (Sun) की विधि: विश्लेषण पुष्टि करता है कि सन की कोल्यूडिंग, रोबस्ट और बायज़ेंटाइन PIR योजनाएं सभी व्युत्पन्न आवश्यक और पर्याप्त शर्तों को संतुष्ट करती हैं। विशेष रूप से, मैक्सिमम डिस्टेंस सेपरेबल (MDS) कोड्स और फुल-रैंक रैंडम मैट्रिसेस का उपयोग यह सुनिश्चित करता है कि क्षमता के लिए रैंक स्थितियाँ और गोपनीयता के लिए काउंटिंग स्थितियाँ पूरी होती हैं।
2. वांग (Wang) की विधि: विश्लेषण से पता चलता है कि जबकि वांग की कोल्यूडिंग PIR योजना शुद्धता और गोपनीयता को संतुष्ट करती है, यह क्षमता की शर्त में विफल रहती है। विशेष रूप से, वांछित संदेश घटकों के लिए संयुक्त क्वेरी मैट्रिक्स का रैंक ($\text{rank } Q^{(m)}_{1:S}[m]$), व्यक्तिगत सर्वर रैंकों के योग ($\sum \text{rank } Q^{(m)}_j[m]$) के बराबर नहीं है। यह विसंगति स्पष्ट करती है कि वांग की विधि सैद्धांतिक क्षमता की तुलना में कम डाउनलोड दर क्यों प्राप्त करती है। शोध पत्र प्रदर्शित करता है कि वांग की योजना में, कुछ क्वेरी वेक्टर गैर-शून्य प्रायिकता के साथ शून्य वेक्टर बन सकते हैं, जिससे उप-इष्टतम डाउनलोड दर होती है।

महत्व

शोध पत्र का दावा है कि इसका प्राथमिक महत्व क्षमता-प्राप्त PIR योजनाओं के निर्माण और सत्यापन के लिए एक व्यवस्थित ढांचा (systematic framework) प्रदान करना है। इस कार्य से पहले, ऐसी योजनाओं का निर्माण 'एड-हॉक' विधियों पर निर्भर था, और क्षमता प्राप्ति को सत्यापित करना कठिन था। क्वेरी मैट्रिक्स के गुणों (विशेष रूप से रैंक गुणों और रैंडम फैक्टर्स के वितरण) के रूप में शर्तों को व्यक्त करके, लेखक एक स्पष्ट चेकलिस्ट प्रदान करते हैं:

• यह सत्यापित करने के लिए कि क्या बनाया गया PIR स्कीम क्षमता प्राप्त करता है।
• नई क्षमता-प्राप्त योजनाओं के व्यवस्थित निर्माण के लिए मार्गदर्शन करने हेतु।

यह कार्य PIR क्षमता के सैद्धांतिक ऊपरी स्तरों और प्रतिकूल वातावरण में इन सीमाओं तक पहुँचने वाली व्यावहारिक योजनाओं के बीच के अंतर को पाटता है। यह पुष्टि करता है कि ज्ञात क्षमता-प्राप्त विधियाँ (जैसे सन की विधि) वास्तव में इन कठोर गणितीय शर्तों को संतुष्ट करती हैं, जबकि उप-इष्टतम विधियों (जैसे वांग की विधि) में मौजूद विशिष्ट संरचनात्मक कमियों की पहचान करती है जो उन्हें क्षमता तक पहुँचने से रोकती हैं।