Private Information Retrieval from Joint Systematic MDS-Coded with Non-Colluding Servers: Bounds and Constructions

तकनीकी सारांश: गैर-मिलीभगत वाले सर्वरों के साथ संयुक्त व्यवस्थित MDS-कोडेड (Joint Systematic MDS-Coded) से निजी सूचना पुनर्प्राप्ति (Private Information Retrieval)

समस्या विवरण
यह शोध पत्र वितरित भंडारण प्रणालियों (distributed storage systems) में 'प्राइवेट इंफॉर्मेशन रिट्रीवल' (PIR) की समस्या को संबोधित करता है जहाँ $M$ फ़ाइलें $N$ गैर-मिलीभगत वाले (non-colluding) सर्वरों में एक $[N, K]$ मैक्सिमम डिस्टेंस सेपरेबल (MDS) कोड का उपयोग करके संग्रहीत की जाती हैं। पारंपरिक "पृथक" (separate) MDS-कोडेड PIR योजनाओं के विपरीत, जहाँ प्रत्येक फ़ाइल को स्वतंत्र रूप से एनकोड किया जाता है, यह कार्य संयुक्त MDS-कोडेड PIR पर केंद्रित है। इस मॉडल में, सभी $M$ फ़ाइलों को एक एकल कोडवर्ड में एक व्यवस्थित MDS ऐरे कोड का उपयोग करके एक साथ एनकोड किया जाता है। उपयोगकर्ता किसी व्यक्तिगत सर्वर को अपनी पहचान $\theta$ प्रकट किए बिना एक विशिष्ट फ़ाइल $W_\theta$ को प्राप्त करना चाहता है।

मुख्य प्रेरणा सन और टियान [28] के उस अवलोकन से आती है जहाँ उन्होंने बताया था कि विशिष्ट पैरामीटर व्यवस्थाओं में संयुक्त एनकोडिंग, पृथक MDS-कोडेड PIR (बनावन और उलुकस [9] द्वारा स्थापित) की क्षमता सीमाओं को तोड़ सकती है। हालाँकि, संयुक्त MDS-कोडेड PIR की सैद्धांतिक क्षमता, विशेष रूप से यह कि स्टोरेज पैटर्न और व्यवस्थित बाधाएँ (systematic constraints) पुनर्प्राप्ति दरों को कैसे प्रभावित करती हैं, काफी हद तक अनछुए रह गए थे।

कार्यप्रणाली और सिस्टम मॉडल
लेखक दो महत्वपूर्ण घटकों को पेश करके सिस्टम मॉडल को परिष्कृत करते हैं:

1. स्टोरेज पैटर्न ($P$): एक मैट्रिक्स जो यह वर्णन करता है कि $M$ फ़ाइलों को स्टोरेज कोड के $K$ व्यवस्थित इनपुट ब्लॉक्स में कैसे व्यवस्थित किया गया है।
2. व्यवस्थित MDS ऐरे कोड ($C$): एक कोड जो इन ब्लॉक्स को $N$ सर्वरों में एनकोड करता है।

पेपर एक निश्चित स्टोरेज पैटर्न $P$ के लिए सभी संगत व्यवस्थित MDS ऐरे कोड्स के लिए पुनर्प्राप्ति दरों के सुप्रीमम (supremum) के रूप में क्षमता $C^{(s)}_{JMDS-PIR}(M, N, K, P)$ को परिभाषित करता है। अध्ययन दो विशिष्ट स्टोरेज पैटर्न पर केंद्रित है:

• मामला 1: $K = Mt$विद पैटर्न$P = \ell I_M \otimes \mathbf{1}_t$।
• मामला 2: $K = Mt + 1$विद पैटर्न$P = \frac{\ell}{M} (M I_M \otimes \mathbf{1}_t \mid \mathbf{1}_M^\top)$।

सैद्धांतिक सीमाओं को प्राप्त करने के लिए, लेखक सूचना-सैद्धांतिक उपकरणों (information-theoretic tools) का उपयोग करते हैं, विशेष रूप से सर्वर उत्तरों की सशर्त स्वतंत्रता संरचना (conditional independence structure) को स्पष्ट करते हुए (लेम्मा 3) और हान के अनोपात (Han's inequality) पर आधारित पुनरावर्ती असमानताओं को व्युत्पन्न करते हुए (लेम्मा 5 और 8)। निर्माण (construction) के लिए, वे गोपनीयता सुनिश्चित करने और उपयोगी जानकारी के डाउनलोड को अधिकतम करने के लिए रैंडम परम्यूटेशन और संग्रहीत प्रतीकों (symbols) के रैखिक संयोजन का उपयोग करते हैं।

प्रमुख योगदान और परिणाम

1. क्षमता पर ऊपरी सीमाएँ (Upper Bounds on Capacity):

   • **$K = Mt$** और पैटर्न$P = \ell I_M \otimes \mathbf{1}_t$के लिए, लेखक$1 - (1 - \frac{1}{M})\frac{K}{N}$ की एक ऊपरी सीमा व्युत्पन्न करते हैं।
   • **$K = Mt + 1$** और पैटर्न$P = \frac{\ell}{M} (M I_M \otimes \mathbf{1}_t \mid \mathbf{1}_M^\top)$के लिए, वे$\frac{K(N-K+t)}{(K-1)(N-1)}$ की ऊपरी सीमा व्युत्पन्न करते हैं।
   • महत्वपूर्ण रूप से, $K = Mt$और$N \le K + t$ के मामले के लिए, व्युत्पन्न ऊपरी सीमा सन और टियान [28] द्वारा प्रस्तावित योजनाओं के प्रदर्शन से मेल खाती है, जो इन विशिष्ट स्टोरेज पैटर्न के तहत उनकी इष्टतमता (optimality) का पहला प्रमाण प्रदान करती है।

2. योजना निर्माण (Scheme Constructions):
   यह पेपर तीन संयुक्त व्यवस्थित MDS-कोडेड PIR योजनाएं निर्मित करता है:

   • निर्माण 1 ($N \le K + t, K = Mt$): यह योजना ऊपरी सीमा $1 - (1 - \frac{1}{M})\frac{K}{N}$ प्राप्त करती है, जिससे इस शासन (regime) के लिए सटीक क्षमता स्थापित होती है।
   • **निर्माण 2 ($N > K + t, K = Mt$):** यह योजना$\frac{N+K-t}{NM}$ की पुनर्प्राप्ति दर प्राप्त करती है।
   • निर्माण 3 ($N \le K + t, K = Mt + 1$): यह योजना $\frac{K(N-K+t)}{M((t+1)N-K)}$ की पुनर्प्राप्ति दर प्राप्त करती है।

3. प्रदर्शन सुधार:
   प्रस्तावित योजनाओं की तुलना क्षमता-प्राप्त करने वाली पृथक MDS-कोडेड PIR योजनाओं (जैसे, [9], [17], [18]) से की जाती है। विश्लेषण दिखाता है कि संयुक्त योजनाएं विशिष्ट पैरामीटर श्रेणियों में उच्च पुनर्प्राप्ति दर प्राप्त करती हैं:

   • $K = Mt$के लिए, जब स्टोरेज रेट$r = K/N$ उच्च होता है, तो सुधार महत्वपूर्ण होता है।
   • $K = Mt + 1$के लिए, संयुक्त योजना हमेशा पृथक योजना से बेहतर प्रदर्शन करती है जब$K < N \le K + t$ हो।
   • मात्रात्मक लाभ: सापेक्ष पुनर्प्राप्ति-दर सुधार $M \ge 4$ होने पर 15% से अधिक, $M \ge 9$ होने पर 20% से अधिक हो सकता है, और जैसे-जैसे $M$ बढ़ता है, यह $1 - 2/e \approx 26.42\%$ के करीब पहुंच जाता है।
   • इसके अतिरिक्त, प्रस्तावित निर्माणों के लिए छोटे फ़ाइल आकार की आवश्यकता होती है और कुछ मामलों में (जैसे, $M=2, N=3t$), पिछले संयुक्त स्कीम्स [28] की तुलना में आवश्यक फाइनाइट फील्ड साइज को काफी कम कर देते हैं।

महत्व
इस शोध पत्र का प्राथमिक महत्व निर्धारित स्टोरेज पैटर्न के तहत निर्धारित 'जॉइंट सिस्टेमैटिक MDS-कोडेड PIR' की क्षमता को सैद्धांतिक रूप से स्पष्ट करने में निहित है, जो कि पहले एक खुला प्रश्न था। विशिष्ट मापदंडों के लिए सन और टियान [28] की योजनाओं की इष्टतमता को सिद्ध करके और व्यापक पैरामीटर सेटों के लिए नई रचनाएँ प्रदान करके, यह कार्य प्रदर्शित करता है कि संयुक्त एनकोडिंग केवल एक ह्यूरिस्टिक नहीं है बल्कि एक प्रमाणित रूप से श्रेष्ठ रणनीति है। परिणाम पुष्टि करते हैं कि संयुक्त MDS-कोडेड PIR, पृथक कोडिंग की क्षमता सीमाओं को तोड़ सकता है, जो गोपनीयता से समझौता किए बिना पुनर्प्राप्ति दक्षता में पर्याप्त लाभ प्रदान करता है, विशेष रूप से जैसे-जैसे फ़ाइलों की संख्या ($M$) बढ़ती है। लेखक नोट करते हैं कि जबकि उनके परिणाम विशिष्ट पैरामीटर श्रेणियों को कवर करते हैं, अधिक सामान्य संयुक्त MDS-कोडेड PIR सेटिंग्स तक इन निष्कर्षों का विस्तार करना भविष्य के अनुसंधान के लिए एक चुनौतीपूर्ण दिशा बनी हुई है।