Efficient DPF-based Error-Detecting Information-Theoretic Private Information Retrieval Over Rings

यहाँ शोध पत्र "Efficient DPF-based Error-Detecting Information-Theoretic Private Information Retrieval Over Rings" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

प्राइवेट इंफॉर्मेशन रिट्रीवल (PIR) क्लाइंट को सर्वरों को इंडेक्स प्रकट किए बिना एक विशिष्ट डेटाबेस प्रविष्टि (entry) प्राप्त करने की अनुमति देता है। जबकि मल्टी-सर्वर इंफॉर्मेशन-थ्योरेटिक PIR (itPIR) पूर्ण गोपनीयता (unconditional privacy) प्रदान करता है, यह व्यावहारिक तैनाती में दो महत्वपूर्ण चुनौतियों का सामना करता है:

1. दुर्भावनापूर्ण लचीलापन (Malicious Resilience): हमले या विफलताओं के कारण सर्वर गलत डेटा लौटा सकते हैं। मौजूदा एरर-डिटेक्टिंग PIR (ED-PIR) योजनाएं, विशेष रूप से ऑथेंटिकेटेड PIR (APIR), इसे संबोधित करती हैं लेकिन अक्षमताओं से ग्रस्त हैं।
2. स्टेट-ऑफ-द-आर्ट (APIR) में अक्षमताएं:
   • डुअल-की ओवरहेड (Dual-Key Overhead): शुद्धता को सत्यापित करने के लिए APIR को प्रति सर्वर दो डिस्ट्रीब्यूटेड पॉइंट फंक्शन (DPF) कुंजियों की आवश्यकता होती है, जिससे क्वेरी संचार लागत दोगुनी हो जाती है।
   • फाइनाइट फील्ड बाधा (Finite Field Constraint): APIR $\mathbb{F}_p$ (फाइनाइट फील्ड) तक सीमित है, जो इसे केवल प्राइम-ऑर्डर DPF तक सीमित करता है। यह उच्च सुरक्षा प्राप्त करने के लिए बड़े अभाज्य संख्याओं ($p$) का उपयोग करने के लिए मजबूर करता है, जिससे अत्यधिक बड़े की-साइज और संचार जटिलता उत्पन्न होती है। यह अधिक कुशल प्राइम-पावर-ऑर्डर DPFs (जैसे $\mathbb{Z}_{p^\tau}$ पर) का उपयोग नहीं कर सकता है।

इस शोध पत्र का लक्ष्य एक itED-PIR योजना डिजाइन करना है जो रिंग संरचनाओं और सिंगल-की डिजाइनों का लाभ उठाकर उप-बहुपद (subpolynomial) संचार जटिलता और काफी कम ओवरहेड के साथ इन सीमाओं को दूर कर सके।

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

लेखक एक नवीन रिंग-आधारित itED-PIR योजना प्रस्तावित करते हैं जिसे रिंग $R = (\mathbb{Z}_{p^\tau}, +, \cdot)$ पर निर्मित किया गया है, जहाँ $p$ एक अभाज्य संख्या (prime) है और $\tau \geq 1$ है।

मुख्य निर्माण (Core Construction)

यह योजना प्रति सर्वर एक सिंगल DPF की (key) का उपयोग करती है (APIR के डुअल की के विपरीत) और इस प्रकार कार्य करती है:

1. क्वेरी चरण (Query Phase):
   • क्लाइंट एक यादृच्छिक व्युत्क्रमणीय तत्व (random invertible element) $\beta \in R^*$ चुनता है।
   • क्लाइंट पॉइंट फंक्शन $f_{\alpha, \beta}$ के लिए एक एकल DPF कुंजियों का सेट $\{k_j\}$ उत्पन्न करता है, जहाँ $f_{\alpha, \beta}(i) = \beta$ यदि $i=\alpha$ है और अन्यथा $0$ है।
   • क्लाइंट प्रत्येक सर्वर $S_j$ को एक की $k_j$ भेजता है और $\beta$ को सहायक जानकारी (auxiliary information) के रूप में अपने पास रखता है।
2. उत्तर चरण (Answer Phase):
   • प्रत्येक सर्वर $S_j$ डेटाबेस $x = (x_1, \dots, x_n)$ पर DPF का मूल्यांकन करता है और एक भारित योग (weighted sum) की गणना करता है: $a_j = \sum_{i=1}^n x_i \cdot \text{Eval}_j(k_j, i)$।
   • सर्वर $a_j$ को क्लाइंट को वापस भेजता है।
3. पुनर्निर्माण और सत्यापन (Reconstruction & Verification):
   • क्लाइंट प्रतिक्रियाओं को एकत्रित करता है: $R_{agg} = \sum a_j$।
   • क्लाइंट $res = \beta^{-1} \cdot R_{agg}$ की गणना करता है।
   • सत्यापन (Verification): यदि $res \in \{0, 1\}$ (बाइनरी डेटाबेस के लिए), तो क्लाइंट परिणाम को स्वीकार करता है। यदि $res \notin \{0, 1\}$, तो क्लाइंट $\perp$ आउटपुट करता है, जो छेड़छाड़ का संकेत देता है।

त्रुटि पहचान के लिए तकनीकी तंत्र (Technical Mechanism for Error Detection)

इसकी सुरक्षा रिंग $R$ के गुणों पर आधारित है:

• यदि सर्वर ईमानदार हैं, तो $R_{agg} = \beta \cdot x_\alpha$, इसलिए $\beta^{-1} R_{agg} = x_\alpha \in \{0, 1\}$।
• यदि दुर्भावनापूर्ण सर्वर परिणाम में ऑफसेट $\Delta$ जोड़कर हेरफेर करते हैं, तो पुनर्निर्मित मान $\beta^{-1}(R_{agg} + \Delta)$ हो जाता है।
• सत्यापन पास करने के लिए (अर्थात, वापस $\{0, 1\}$ में आने के लिए), $\beta$ को $\Delta$ से प्राप्त एक विशिष्ट रैखिक समीकरण को संतुष्ट करना होगा। चूंकि $\beta$ को $R^*$ से यादृच्छिक रूप से चुना गया है, इसलिए इस "फॉल्स एक्सेप्टेंस" (गलत स्वीकृति) की संभावना $1/|R^*|$ द्वारा सीमित है।
• एक ऐसी रिंग चुनने से जिसमें एक बड़ा मल्टीप्लिकेटिव ग्रुप हो (जैसे, बड़े $\tau$ के साथ $\mathbb{Z}_{2^\tau}$), बिना किसी विशाल प्राइम $p$ की आवश्यकता के, सफल जालसाजी (forgery) की संभावना नगण्य हो जाती है।

3. मुख्य योगदान (Key Contributions)

1. रिंग-आधारित ढांचा (Ring-Based Framework): यह शोध पत्र APIR की फाइनाइट फील्ड बाधा को तोड़ता है और $\mathbb{Z}_{p^\tau}$ पर एक योजना का निर्माण करता है। यह प्राइम-पावर-ऑर्डर DPFs का उपयोग करने में सक्षम बनाता है, जो उच्च सुरक्षा सेटिंग्स के लिए प्राइम-ऑर्डर DPFs की तुलना में काफी अधिक कुशल हैं।
2. सिंगल-की डिज़ाइन (Single-Key Design): यह योजना APIR की अनावश्यक डुअल-की संरचना को समाप्त करती है। प्रति सर्वर एक एकल DPF की का उपयोग करके, यह क्वेरी-साइड संचार ओवरहेड को आधा कर देता है।
3. ठोस इंस्टेंशिएशन (Concrete Instantiations): लेखक विभिन्न ठोस योजनाएं प्रदान करते हैं (जो पेपर की तालिका 1 में संक्षेपित हैं) जिनमें शामिल हैं:
   • सर्वर की संख्या: 3, 4, 8, और सामान्य $d(t+1)$ सर्वर।
   • गोपनीयता स्तर: सांख्यिकीय (Statistical) और पूर्ण (Perfect) दोनों गोपनीयता।
   • मिलीभगत सहिष्णुता (Collusion Tolerance): $t=1$ से लेकर अनिश्चित $t$ तक।
   • जटिलता: सभी इंस्टेंशिएशन उप-बहुपद संचार जटिलता (subpolynomial communication complexity) बनाए रखते हैं।
4. औपचारिक सुरक्षा प्रमाण (Formal Security Proofs): शोध पत्र शुद्धता (correctness), $t$-गोपनीयता (पूर्ण और सांख्यिकीय), और $(t, \epsilon)$-सत्यापनीयता को कड़ाई से सिद्ध करता है, जो यह दर्शाता है कि यह योजना $t$ नोड्स को नियंत्रित करने वाले दुर्भावनापूर्ण सर्वरों के विरुद्ध लचीली है।

4. परिणाम और प्रदर्शन विश्लेषण (Results and Performance Analysis)

यह शोध पत्र प्रस्तावित itED-PIR की तुलना अत्याधुनिक itAPIR से करता है:

• संचार जटिलता (Communication Complexity):
  • itAPIR: उच्च सुरक्षा के साथ पूर्ण गोपनीयता के लिए $O(\log p \cdot 2^{2p} \cdot \sqrt{\log n \log \log n})$ की आवश्यकता होती है। घातांकीय पद $2^{2p}$ तेजी से बढ़ता है जैसे-जैसे सुरक्षा पैरामीटर $\epsilon$ घटता है (जिसके लिए बड़े $p$ की आवश्यकता होती है)।
  • itED-PIR: $O(\tau \log p \cdot 2^{c} \cdot \sqrt{\log n \log \log n})$ प्राप्त करता है। $p=2$ सेट करके और सुरक्षा आवश्यकताओं को पूरा करने के लिए $\tau$ बढ़ाकर, घातांकीय पद स्थिर ($2^6$ या समान) रहता है, जबकि $\tau$ रैखिक रूप से स्केल करता है।
• व्यावहारिक प्रभाव (Practical Impact):
  • उच्च सुरक्षा स्तर (जैसे, $\epsilon = 2^{-128}$) के लिए, itAPIR को $p > 2^{128}$ की आवश्यकता होगी, जिससे घातांकीय पद $2^{2 \cdot 2^{128}}$ गणनात्मक रूप से अव्यवहार्य हो जाएगा।
  • इसके विपरीत, itED-PIR $p=2$ और $\tau=128$ का उपयोग करता है, जिसके परिणामस्वरूप $O(128 \cdot 2^6 \cdot \dots)$ की व्यवहार्य संचार जटिलता प्राप्त होती है।
• की साइज (Key Size): रिंग-आधारित दृष्टिकोण APIR की बड़ी-फील्ड आवश्यकताओं की तुलना में की-साइज को काफी कम कर देता है।

5. महत्व (Significance)

• उच्च सुरक्षा के लिए स्केलेबिलिटी: यह कार्य सूचना-थ्योरेटिक ED-PIR को उन उच्च-सुरक्षा परिदृश्यों (जैसे, पोस्ट-क्वांटम गोपनीयता) के लिए व्यवहार्य बनाता है जहाँ पिछले स्कीम्स की की-साइज के घातांकीय विकास के कारण वे अव्यवहार्य थे।
• दक्षता: सिंगल-की डिज़ाइन और रिंग संरचना क्वेरी संचार को 50% कम करती है और सत्यापन के कम्प्यूटेशनल बोझ को काफी कम करती है।
• दुर्भावनापूर्ण लचीलापन: यह एक हल्का ढांचा प्रदान करता है जिसका उपयोग दुर्भावनापूर्ण-लचीले PIR के निर्माण के लिए किया जा सकता है, जो वितरित भंडारण प्रणालियों (जैसे IPFS या Hadoop) के लिए आवश्यक है जहाँ सर्वर अखंडता की गारंटी नहीं दी जा सकती है।
• भविष्य के लिए सुरक्षित (Future-Proofing): सूचना-थ्योरेटिक होने के नाते, यह योजना क्वांटम कंप्यूटिंग हमलों के प्रति अंतर्निहित प्रतिरोध प्रदान करती है, जो कम्प्यूटेशनल हार्डनेस धारणाओं (जैसे, लैटिस-आधारित क्रिप्टोग्राफी) पर निर्भर योजनाओं के विपरीत है।

निष्कर्षतः, यह शोध पत्र फाइनाइट फील्ड से रिंग की ओर स्थानांतरित होकर PIR में एक मौलिक प्रगति प्रस्तुत करता है, जो बड़े पैमाने पर, उच्च-सुरक्षा तैनाती के लिए व्यावहारिक, सुरक्षित और सत्यापन योग्य निजी डेटा पुनर्प्राप्ति को सक्षम बनाता है।