💻 computer science

Lower Bounds for PIR with Preprocessing from Blackbox Cryptography

यह शोध पत्र ब्लैकबॉक्स क्रिप्टोग्राफी पर आधारित क्लाइंट प्रीप्रोसेसिंग वाले सिंगल-सर्वर प्राइवेट इंफॉर्मेशन रिट्रीवल के लिए इष्टतम गणना और संचार निचली सीमाओं (lower bounds) को स्थापित करता है, जो यह सिद्ध करता है कि ऐसे स्कीम्स को $\Omega(n/s)$ अमॉर्टाइज्ड ऑनलाइन लागत या सर्वर संचालन का सामना करना ही होगा और इन धारणाओं के तहत डबली एफिशिएंट (doubly efficient) PIR के अस्तित्व को खारिज करता है।

मूल लेखक: Alexander Hoover, Giuseppe Persiano, Kevin Yeo

प्रकाशित 2026-07-08

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Alexander Hoover, Giuseppe Persiano, Kevin Yeo

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आपके पास एक विशाल पुस्तकालय (एक डेटाबेस) है जिसमें $n$ पुस्तकें हैं, और आप बिना लाइब्रेरियन (सर्वर) को यह बताए कि आपने कौन सी पुस्तक चुनी है, केवल एक विशिष्ट पुस्तक उधार लेना चाहते हैं। यह प्राइवेट इंफॉर्मेशन रिट्रीवल (PIR) की समस्या है।

आमतौर पर, अपने रहस्य को सुरक्षित रखने के लिए, आपको लाइब्रेरियन से पूरे पुस्तकालय की सूची पढ़ने के लिए कहना होगा जो धीमा और महंगा होता है। हालिया सफलताओं ने इसे पहले से तेज़ बनाने का एक तरीका खोजा है जिससे आप कुछ "होमवर्क" (प्रीप्रोसेसिंग) पहले से कर सकते हैं (क्लाइंट स्टोरेज)। आप एक छोटा सा 'चीट शीट' (cheat sheet) स्टोर कर सकते हैं जो बाद में एक बहुत छोटा प्रश्न पूछने में आपकी मदद करता है।

यह शोध पत्र एक मौलिक प्रश्न पूछता है: यह चीट शीट वास्तव में चीजों को कितना बेहतर बना सकती है? क्या हम लाइब्रेरियन के काम को इतना आसान बना सकते हैं कि उन्हें बहुत कम सोचना पड़े, जबकि आप केवल एक छोटा सा संदेश भेजें?

लेखक कहते हैं: "नहीं, यहाँ कठोर सीमाएँ हैं।"

यहाँ उनके निष्कर्षों का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है:

1. "चीट शीट" का व्यापार (Trade-off)

कल्पना कीजिए कि आपके पास एक विशाल विश्वकोश ( $n$ पृष्ठ) है। आपको $s$ आकार का एक छोटा चीट शीट याद करने की अनुमति है (आपका क्लाइंट स्टोरेज)।

पुराना नियम: बिना चीट शीट के, लाइब्रेरियन को आपको उत्तर देने के लिए पूरी किताब पढ़नी पड़ती है।
नई उम्मीद: चीट शीट के साथ, शायद लाइब्रेरियन केवल कुछ पन्नों पर नज़र डाल सकता है?
पेपर का निर्णय: लेखक इस सिस्टम के लिए एक सख्त भौतिक नियम (law of physics) सिद्ध करते हैं। यदि आपके चीट शीट का आकार $s$ $s$ है, तो लाइब्रेरियन को कम से कम $n/s$ $n / s$ मात्रा में काम करना ही होगा।
- उपमा: डेटाबेस को $n$ स्लाइस वाले एक विशाल पिज्जा के रूप में सोचें। आपका चीट शीट एक छोटा नैपकिन ( $s$ ) है जहाँ आप कुछ नोट्स लिख सकते हैं। पेपर सिद्ध करता है कि आपका नैपकिन चाहे कितना भी चतुर क्यों न हो, शेफ (लाइब्रेरियन) को आपको परोसने के लिए कम से कम $n/s$ स्लाइस को देखना ही होगा। यदि आपका नैपकिन बहुत छोटा है, तो शेफ को लगभग पूरा पिज्जा देखना होगा। यदि आपका नैपकिन बहुत बड़ा है (पिज्जा के आकार के लगभग), तो शेफ को केवल कुछ स्लाइस देखने होंगे। आप एक छोटा नैपकिन और एक ऐसा शेफ नहीं रख सकते जो लगभग कोई काम न करे।

2. "ड्यूल" पहेली (The Dual Puzzle - जादुई ट्रिक)

इसे सिद्ध करने के लिए, लेखकों ने एक नया, अजीब खेल बनाया जिसे "ड्यूल PIR" कहा जाता है।

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

3. "ब्लैक बॉक्स" का नियम

यह पेपर मानता है कि लाइब्रेरियन "ब्लैक बॉक्स" क्रिप्टोग्राफी का उपयोग करता है।

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

4. "सिमेट्रिक" समस्या (दोनों तरफ गोपनीयता बनाए रखना)

इसका एक सख्त संस्करण है जिसे सिमेट्रिक PIR (SPIR) कहा जाता है।

सामान्य PIR: लाइब्रेरियन को नहीं पता कि आपने कौन सी पुस्तक ली है।
सिमेट्रिक PIR: लाइब्रेरियन को नहीं पता कि आपने कौन सी पुस्तक ली है, और आपको पुस्तकालय की अन्य पुस्तकों को झाँकने की अनुमति नहीं है।
निष्कर्ष: लेखकों ने एक नया सिस्टम बनाया है जो ऑनलाइन भाग के दौरान केवल सरल गणित (One-Way Functions) का उपयोग करके इस सिमेट्रिक PIR को प्राप्त करता है।
कैच (Catch): इस सिस्टम की एक सीमा है कि आप कितनी बार इसका उपयोग कर सकते हैं इससे पहले कि आपको फिर से भारी "होमवर्क" करने की आवश्यकता हो। आप अनंत प्रश्न पूछने के लिए एक ही चीट शीट का उपयोग अनंत काल तक नहीं कर सकते, अन्यथा लाइब्रेरियन को या तो अधिक काम करना होगा या सिस्टम टूट जाएगा।

खोजे गए "नियमों" का सारांश

यह पेपर इन सिस्टमों के लिए तीन मुख्य "नियम" स्थापित करता है:

कार्य का नियम (The Work Law): यदि आप $s$ बिट्स का डेटा स्टोर करते हैं, तो सर्वर को प्रति क्वेरी कम से कम $n/s$ काम करना होगा।
संचार का नियम (The Communication Law): यदि सर्वर बहुत कम काम करता है, तो आपको बहुत अधिक डेटा भेजना होगा।
सिमेट्री का नियम (The Symmetry Law): यदि आप (बिना भारी "पब्लिक-की" जादू के) यूजर से डेटाबेस को सुरक्षित रखना चाहते हैं (सिमेट्रिक PIR), तो आप कितने प्रश्न पूछ सकते हैं इसकी एक सीमा है, इससे पहले कि आपको अपना डेटा रिफ्रेश करने की आवश्यकता हो।

संक्षेप में: यह पेपर एक नया तेज़ तरीका खोजने के बजाय, "असंभव क्षेत्र" का मानचित्र बनाता है। यह हमें बताता है कि वर्तमान सर्वोत्तम तरीके पहले से ही सैद्धांतिक सीमा (theoretical ceiling) से टकरा रहे हैं। आप लाइब्रेरियन के काम को आसान बनाए बिना अपने संदेश को बड़ा नहीं कर सकते, और आप अपने संदेश को छोटा किए बिना लाइब्रेरियन के काम को कठिन नहीं बना सकते।

तकनीकी सारांश: ब्लैकबॉक्स क्रिप्टोग्राफी के साथ प्रीप्रोसेसिंग वाले PIR के लिए लोअर बाउंड्स

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

यह शोध पत्र प्रीप्रोसेसिंग मॉडल में सिंगल-सर्वर प्राइवेट इंफॉर्मेशन रिट्रीवल (PIR) की मौलिक सीमाओं की जांच करता है। इस सेटिंग में, एक क्लाइंट $n$ -बिट डेटाबेस के बारे में एक छोटा सा स्टेट ( $s$ बिट्स) स्टोर करने के लिए एक ऑफलाइन चरण (phase) निष्पादति करता है, जिससे अधिक कुशल ऑनलाइन क्वेरी संभव हो पाती है। जबकि हालिया सफलताओं ने प्रीप्रोसेसिंग का लाभ उठाकर सबलीनियर क्वेरी कंप्यूटेशन और कम्युनिकेशन वाले सिंगल-सर्वर PIR स्कीम्स को प्रदर्शित किया है (जैसे, [CHK22, ZPZS24, LMW23]), इन कंस्ट्रक्शंस की सैद्धांतिक सीमाएं स्पष्ट नहीं हैं।

विशेष रूप से, लेखक यह पता लगाने का प्रयास करते हैं कि क्या ऐसे सिंगल-सर्वर PIR स्कीम्स का निर्माण करना संभव है जो:

सबलीनियर एमोर्टाइज्ड ऑनलाइन कंप्यूटेशन (विशेष रूप से $o(n/s)$ ) प्राप्त करें।
ब्लैकबॉक्स क्रिप्टोग्राफी (क्रिप्टो ओरैकल्स, जिसमें रैंडम ओरैकल्स, वर्चुअल ब्लैकबॉक्स ऑब्फस्केशन और जेनेरिक मल्टीलिनर ग्रुप्स शामिल हैं, के माध्यम से मॉडल किया गया है) पर निर्भर हों।
सिमेट्रिक PIR (SPIR) का समर्थन करें (जहाँ क्लाइंट केवल क्वेरी की गई प्रविष्टि ही सीखता है) और ऑनलाइन चरण के दौरान केवल वन-वे फंक्शन्स (OWFs) का उपयोग करे।

प्रीप्रोसेसिंग वाले PIR के लिए पूर्ववर्ती लोअर बाउंड्स प्रतिबंधित श्रेणियों (जैसे, नॉन-एनकोडिंग सर्वर, डेटाबेस-ऑब्लीवियस क्वेरी, या सिंगल-राउंडट्रिप इंटरैक्शन की आवश्यकता वाले स्कीम्स) तक सीमित थे या अपुष्ट जटिलता धारणाओं (complexity assumptions) पर आधारित थे। यह कार्य ब्लैकबॉक्स क्रिप्टोग्राफी के उपयोग करने वाले स्कीम्स के एक व्यापक वर्ग के लिए अनकंडीशनल (unconditional) लोअर बाउंड्स प्रदान करने का लक्ष्य रखता है।

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

शोध पत्र की कार्यप्रणाली का मुख्य आधार एक नया प्रिमिटिव (primitive) है जिसे डुअल PIR कहा जाता है, और मानक PIR विद प्रीप्रोसेसिंग से इस प्रिमिटिव तक एक रिडक्शन (reduction) प्रस्तुत करना है।

2.1 डुअल प्राइवेट इंफॉर्मेशन रिट्रीवल (Dual PIR)

लेखक डुअल PIR को मानक PIR प्रीप्रोसेसिंग मॉडल के व्युत्क्रम (inversion) के रूप में परिभाषित करते हैं:

एडवाइस फेज (Advice Phase): किसी भी क्वेरी के ज्ञात होने से पहले, क्लाइंट डेटाबेस के आधार पर एक $t$ -बिट एडवाइस स्ट्रिंग (ट्रांसक्रिप्ट) उत्पन्न करता है।
हिंट फेज (Hint Phase): डेटाबेस, $k$ क्वेरी इंडेक्स का एक बैच, और एडवाइस दिए जाने पर, क्लाइंट एक $s$ -बिट हिंट उत्पन्न करता है।
रिकंस्ट्रक्शन (Reconstruction): केवल क्वेरी इंडेक्स, एडवाइस और हिंट का उपयोग करके (लेकिन डेटाबेस तक पहुंच के बिना), क्लाइंट को क्वेरी किए गए डेटाबेस एंट्रीज को पुनर्गठित करना चाहिए।

यह फॉर्मूलेशन PIR दक्षता की समस्या को एक कंप्रेशन समस्या में बदल देता है। यदि कोई PIR स्कीम बहुत अधिक कुशल है (अर्थात, $t = o(n)$ और $s < k$ ), तो यह एक ऐसे डुअल PIR के अस्तित्व का संकेत देता है जो $t$ बिट्स की प्री-शेयर्ड एडवाइस का उपयोग करके $k$ बिट्स की जानकारी को $s$ बिट्स में कंप्रेस कर सकता है, जो कुछ स्थितियों में सूचना-सैद्धांतिक रूप से (information-theoretically) असंभव है।

2.2 PIR से डुअल PIR तक रिडक्शन

लेखक एक रिडक्शन का निर्माण करते हैं जो यह दर्शाता है कि प्रीप्रोसेसिंग के साथ किसी भी सुरक्षित PIR स्कीम को डुअल PIR स्कीम में बदला जा सकता है।

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

2.3 सबकी प्रेडिक्शन (Subkey Prediction) से संबंध

कुशल डुअल PIR की असंभवता को सिद्ध करने के लिए, लेखक इस समस्या को लीकेज-रेज़िलिएंट क्रिप्टोग्राफी ([BKR16]) में सबकी प्रेडिक्शन से जोड़ते हैं। वे दिखाते हैं कि एक सही और कुशल डुअल PIR, $t$ बिट्स के लीकेज के आधार पर, $n$ -बिट की (key) के $k$ रैंडम बिट्स की भविष्यवाणी करने के लिए एक एडवर्सरी को सक्षम करेगा, जिसकी सफलता की संभावना ज्ञात सूचना-सैद्धांतिक सीमाओं से अधिक होगी। विशेष रूप से, यदि $t < n/2$ और $k = \Omega(s)$ है, तो सही रिकंस्ट्रक्शन की संभावना $2^{s - \Omega(k)}$ द्वारा सीमित है।

3. प्रमुख योगदान और परिणाम (Key Contributions and Results)

3.1 कंप्यूटेशन लोअर बाउंड्स

यह शोध पत्र स्थापित करता है कि ब्लैकबॉक्स क्रिप्टोग्राफी के उपयोग करने वाले प्रीप्रोसेसिंग वाले किसी भी सिंगल-सर्वर PIR के लिए:

थ्योरम 1.1: $o(n/s)$ एमोर्टाइज्ड ऑनलाइन कम्युनिकेशन और $o(n/s)$ एमोर्टाइज्ड सर्वर क्रिप्टोग्राफिक ऑपरेशंस को एक साथ प्राप्त करना असंभव है।
निहितार्थ (Implication): ऐसी किसी भी स्कीम को निम्नलिखित में से कम से कम एक को संतुष्ट करना चाहिए:
1. एमोर्टाइज्ड ऑनलाइन कम्युनिकेशन $\Omega(n/s)$ बिट्स है।
2. सर्वर $\Omega(n/s)$ क्रिप्टोग्राफिक बिट ऑपरेशंस करता है।
टाइटनेस (Tightness): यह बाउंड इष्टतम (optimal) है। मौजूदा स्कीम्स (जैसे, [WR25]) बिना सर्वर क्रिप्टो ऑपरेशंस के $O(n/s)$ कम्युनिकेशन प्राप्त करती हैं, जबकि अन्य (जैसे, [ZPZS24]) बिना सर्वर क्रिप्टो ऑपरेशंस के $O(n/s)$ कम्युनिकेशन प्राप्त करती हैं लेकिन क्लाइंट स्टेट को रिफ्रेश करने की आवश्यकता होती है। लोअर बाउंड पुष्टि करता है कि दोनों बाधाओं को एक साथ पार नहीं किया जा सकता है।

3.2 डबली एफिशिएंट PIR (DEPIR)

लेखक ब्लैकबॉक्स क्रिप्टोग्राफी से निर्मित डबली एफिशिएंट PIR (जहाँ क्लाइंट और सर्वर दोनों का समय सबलीनियर है) के अस्तित्व को खारिज करते हैं।

थ्योरम 1.2: ब्लैकबॉक्स क्रिप्टोग्राफी से कोई भी सिंगल-सर्वर DEPIR मौजूद नहीं है जिसमें सिंगल क्वेरी के लिए सबलीनियर क्वेरी कंप्यूटेशन ( $t = o(n)$ ) हो, भले ही सर्वर मनमाना एनकोडिंग करे।
यह परिणाम पब्लिक-की DEPIR पर लागू होता है और पूर्ववर्ती असंभवता परिणामों में सुधार करता है जो निष्क्रिय सर्वरों के साथ सिंगल-राउंडट्रिप क्वेरी तक सीमित थे।

3.3 कम्युनिकेशन लोअर बाउंड्स

यह शोध पत्र PIR की प्रतिबंधित श्रेणियों के लिए विशिष्ट कम्युनिकेशन लोअर बाउंड्स निकालता है:

थ्योरम 1.4: यदि कोई PIR स्कीम निम्नलिखित में से किसी को भी संतुष्ट करती है, तो उसे $\Omega(n/s)$ $Ω (n / s)$ एमोर्टाइज्ड कम्युनिकेशन की आवश्यकता होती है:
1. सर्वर $o(n/s)$ क्रिप्टोग्राफिक ऑपरेशंस करता है।
2. सर्वर क्रिप्टोग्राफिक ऑपरेशंस केवल कम्युनिकेशन ट्रांसक्रिप्ट पर निर्भर हैं (डेटाबेस-ऑब्लीवियस क्रिप्टो उपयोग)।
3. स्कीम एक आइडियलाइज्ड मॉडल में परफेक्ट प्राइवेसी प्रदान करती है।

3.4 सिमेट्रिक PIR (SPIR)

यह शोध पत्र प्रीप्रोसेसिंग के साथ सिमेट्रिक PIR (SPIR) को संबोधित करता है, जहाँ क्लाइंट केवल क्वेरी की गई प्रविष्टि ही सीखता है।

कंस्ट्रक्शन (थ्योरम 1.5): लेखक SPIR के निर्माण को प्रस्तुत करते हैं जो ऑनलाइन क्वेरी चरण के दौरान केवल वन-वे फंक्शन्स (OWFs) पर निर्भर करता है। यह स्कीम $\tilde{O}(n/s)$ कम्युनिकेशन और कंप्यूटेशन प्राप्त करती है, जो ऑफलाइन चरण के प्रति $\tilde{O}(s)$ क्वेरी का समर्थन करती है।
सीमा (थ्योरम 1.6): रैंडम ओरकल मॉडल में, ऐसा कोई भी SPIR स्कीम एक ऑफलाइन चरण के लिए $k > s$ क्वेरी का समर्थन नहीं कर सकता है। यह नॉन-सिमेट्रिक PIR के विपरीत है, जो स्टेट को रिफ्रेश करके अनबाउंडेड (unbounded) क्वेरी का समर्थन कर सकता है। लेखक सिद्ध करते हैं कि $k > s$ क्वेरी का समर्थन करने के लिए पब्लिक-की क्रिप्टोग्राफी या लीनियर कम्युनिकेशन की आवश्यकता होती है।

3.5 वीक PIR (Weak PIR)

लोअर बाउंड्स "वीक" PIR स्कीम्स तक विस्तारित हैं जो केवल पॉलीनोमियल संख्या में क्रिप्टो ओरकल क्वेरी करने वाले एडवर्सरीज के विरुद्ध प्राइवेसी प्रदान करती हैं (मर्कल पजल्स के समान)।

थ्योरम 1.3 & 1.5: वीक एडवर्सरीज के लिए भी, सिंगल-सर्वर प्रीप्रोसेसिंग वाले PIR के लिए सबलीनियर ऑनलाइन क्वेरी टाइम असंभव है यदि ईमानदार पक्ष और एडवर्सरी समान संख्या में ओरकल क्वेरी करते हैं।

4. महत्व और दावे (Significance and Claims)

यह शोध पत्र ब्लैकबॉक्स क्रिप्टोग्राफी धारणाओं के तहत प्रीप्रोसेसिंग के साथ सिंगल-सर्वर PIR के लिए सर्वोत्तम संभव दक्षता के खुले प्रश्न को हल करने का दावा करता है।

अनकंडीशनल परिणाम: पूर्ववर्ती कार्यों (जैसे, [ISW24]) के विपरीत जो जटिलता धारणाओं (जैसे, SZK और BPP के बीच अलगाव) पर निर्भर थे या क्वेरी मॉडल को प्रतिबंधित करते थे (डेटाबेस-ऑब्लीवियस, सिंगल-राउंडट्रिप), ये लोअर बाउंड्स अनकंडीशनल हैं और कई राउंड और डेटाबेस-डिपेंडेंट क्वेरी वाले स्कीम्स सहित एक व्यापक वर्ग पर लागू होते हैं।
वर्तमान कंस्ट्रक्शंस की इष्टतमता: परिणाम यह प्रमाणित करते हैं कि $\tilde{O}(n/s)$ कम्युनिकेशन या कंप्यूटेशन प्राप्त करने वाले हालिया कंस्ट्रक्शंस अनिवार्य रूप से इष्टतम हैं; आप ब्लैकबॉक्स क्रिप्टोग्राफी धारणाओं को तोड़े बिना इस थ्रेशोल्ड से नीचे दोनों को एक साथ कम नहीं कर सकते हैं।
SPIR व्यवहार्यता: यह कार्य दर्शाता है कि सिमेट्रिक PIR, केवल OWFs के साथ ऑनलाइन चरण में प्राप्त किया जा सकता है, बशर्ते कि क्वेरी की संख्या क्लाइंट द्वारा स्टोर किए गए स्टेट ( $s$ ) के आकार तक सीमित हो। यह प्रीप्रोसेसिंग मॉडल में सिमेट्री (डेटा प्राइवेसी) और क्वेरी क्षमता के बीच के ट्रेड-ऑफ को स्पष्ट करता है।
DEPIR असंभवता: यह पेपर पब्लिक-की DEPIR के अस्तित्व को निर्णायक रूप से खारिज करता है जिसमें ब्लैकबॉक्स क्रिप्टोग्राफी से सबलीनियर क्वेरी कंप्यूटेशन हो, जिससे इस क्षेत्र में एक महत्वपूर्ण खुला प्रश्न हल हो जाता है।

संक्षेप में, यह शोध पत्र स्थापित करता है कि हालिया PIR कंस्ट्रक्शंस में पहचाने गए "बॉटलनेक्स" (bottlenecks) (या तो उच्च कम्युनिकेशन या उच्च सर्वर कंप्यूटेशन) ब्लैकबॉक्स क्रिप्टोग्राफी की अंतर्निहित मौलिक सीमाएँ हैं, न कि केवल वर्तमान निर्माण तकनीकों के आर्टिफैक्ट्स।