💻 computer science

Exponentially Fewer-Server PIR from Sparser $S$ -Decoding Polynomials

तर्कसंगत संख्या-सिद्धांत संबंधी अनुमानों को मानते हुए, यह शोध पत्र समान संचार जटिलता (communication complexity) के लिए पिछले अत्याधुनिक निर्माणों की तुलना में घातांकीय रूप से कम सर्वरों के साथ एक $s$ -सर्वर निजी सूचना पुनर्प्राप्ति (private information retrieval) प्रोटोकॉल प्रस्तुत करता है, जिसे मिलान वेक्टर ढांचे (matching vector framework) के भीतर न्यूनतम विरल $S$ -डिकोडिंग बहुपदों का निर्माण करके प्राप्त किया गया है।

मूल लेखक: Aparna Gupte, Seyoon Ragavan

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

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

CC BY 4.0

मूल लेखक: Aparna Gupte, Seyoon Ragavan

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

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

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

अपर्णा गुप्ते और सियोन राघवन द्वारा लिखित यह शोध पत्र उस दीवार को पूरी तरह से तोड़ देता है। उन्होंने "रूट-ऑफ-यूनिटी ग्रिड्स" (root-of-unity grids) का उपयोग करने वाले एक चतुर नए तरीके के माध्यम से इन गणितीय रेसिपीज़ को बनाने का एक तरीका खोजा जो जितनी संभव हो उतनी सरल हैं। इन ग्रिड्स को घड़ी के चेहरे पर संख्याओं की एक विशेष व्यवस्था के रूप में सोचें जो रेसिपी को अविश्वसनीय रूप से छोटा बनाने की अनुमति देती है। यह सिद्ध करके कि ऐसे अति-लघु रेसिपी मौजूद हैं (यह मानते हुए कि अभाज्य संख्याओं के व्यवहार के बारे में कुछ तर्कसंगत अनुमान सही हैं), उन्होंने दिखाया कि आप अपने गुप्त डेटा को पहले की तुलना में काफी कम संचार (communication) के साथ प्राप्त कर सकते हैं। उदाहरण के लिए, यदि आपके पास 3 लाइब्रेरियन हैं, तो पिछले तरीकों में एक निश्चित मात्रा में डेटा की आवश्यकता थी; उनकी नई विधि इसे नाटकीय रूप से कम कर देती है। उन्होंने छोटे नंबरों के लाइब्रेरियन के लिए कंप्यूटर पर अपने विचारों का परीक्षण भी किया और पाया कि गणित बिना किसी अनुमान के 15 लाइब्रेरियनों तक पूरी तरह से काम करता है।

इस शोध पत्र का मुख्य निष्कर्ष यह है कि किसी भी निश्चित संख्या में सर्वरों (मान लीजिए $s$ ) के लिए, यह डिजाइन करना संभव है कि आपको डेटा की लगभग $exp(O((\log n)^{1/s}(\log \log n)^{1-1/s}))$ मात्रा भेजने की आवश्यकता है। यह पिछले सर्वोत्तम तरीकों की तुलना में एक बहुत बड़ा सुधार है, जिनमें समान गति प्राप्त करने के लिए बहुत अधिक सर्वरों की आवश्यकता थी। लेखक दिखाते हैं कि इस समस्या के लिए सबसे "स्पार्स" (sparsest) संभव गणितीय रेसिपी ठीक $k+1$ घटकों का उपयोग करती है (जहाँ $k$ सर्वरों की संख्या से संबंधित है), जिससे वह अंतर समाप्त हो जाता जो वर्षों से खुला था। वे स्पष्ट रूप से इस विचार का खंडन करते हैं कि इसे काम करने के लिए आपको अधिक जटिल, "भारी" रेसिपीज़ की आवश्यकता है; उनका काम सिद्ध करता है कि सबसे सरल संरचना वास्तव में प्राप्त की जा सकती है।

हालाँकि, लेखक इस बारे में सावधान हैं कि वे कितने आश्वस्त हैं। उनकी मुख्य सफलता एक "नंबर-थ्योरेटिक कंजेक्चर" (number-theoretic conjecture) पर निर्भर करती—जो एक फैंसी तरीका है यह कहने का कि वे अभाज्य संख्याओं में एक विशिष्ट पैटर्न के सच होने पर दांव लगा रहे हैं। उनके पास इसका कठोर गणितीय प्रमाण नहीं है कि यह पैटर्न हर मामले में सत्य है, लेकिन वे मजबूत साक्ष्य और ह्यूरिस्टिक तर्क (जैसे कि रैंडम नंबर आमतौर पर कैसे व्यवहार करते हैं इसके आधार पर सांख्यिकीय अनुमान) प्रदान करते हैं कि यह लगभग निश्चित रूप से सच है। छोटे, ठोस मामलों के लिए (15 सर्वरों तक), उन्होंने कंप्यूटर सिमुलेशन चलाए और वास्तविक उदाहरण पाए जो काम करते हैं, जिससे उन विशिष्ट परिणामों को 100% प्रमाणित और बिना किसी शर्त के सिद्ध किया जा सके। बड़ी संख्या में सर्वरों के लिए, वे दिखाते हैं कि उनकी विधि अभी भी पुराने रिकॉर्ड्स को पीछे छोड़ देती है, लेकिन वे स्वीकार करते हैं कि "मेनी-सर्वर" (many-server) शासन में (जहाँ लाइब्रेरियनों की संख्या बहुत बढ़ जाती है), उनकी विधि पुराने तरीकों की तुलना में कोई सुधार नहीं देती है, जो सुझाव देता है कि वहां एक पूरी तरह से अलग दृष्टिकोण की आवश्यकता हो सकती है।

संक्षेप में, यह शोध पत्र गोपनीयता की खोज में एक बड़ा कदम है। यह दिखाता है कि सही गणितीय युक्तियों के साथ, हम अपने डेटा की निजी प्राप्ति को बहुत अधिक कुशल बना सकते हैं, बशर्ते अभाज्य संख्याओं के बारे में हमारे सर्वोत्तम अनुमान सही हों। यह एक पहाड़ के माध्यम से एक गुप्त सुरंग खोजने जैसा है जिसे सभी ने ठोस चट्टान समझा था; सुरंग मौजूद है, और यह सबसे छोटा रास्ता है, भले ही हमने अभी तक चट्टान के हर इंच का मानचित्रण नहीं किया है।

तकनीकी सारांश: स्पार्सर $S$ -डिकोडिंग पॉलिनॉमियल्स से एक्सपोनेंशियल रूप से कम सर्वर वाले PIR

समस्या विवरण
प्राइवेट इंफॉर्मेशन रिट्रीवल (PIR) एक उपयोगकर्ता को $n$ आकार के डेटाबेस से कोई आइटम प्राप्त करने की अनुमति देता है, जो $s$ गैर-सहयोगी सर्वरों के पास होता है, बिना किसी व्यक्तिगत सर्वर को इंडेक्स का खुलासा किए। प्राथमिक लक्ष्य कुल संचार जटिलता (communication complexity) को कम करना है। जबकि ट्रिवियल प्रोटोकॉल के लिए $O(n)$ संचार की आवश्यकता होती है, पूर्ववर्ती कार्यों ने स्थापित किया कि $s$ सर्वरों की एक स्थिर संख्या के लिए, संचार को उप-पॉलीनोमियल स्तरों तक कम किया जा सकता है, विशेष रूप से $s=3$ के लिए $\exp(\tilde{O}(\sqrt{\log n}))$ (एफ्रेमेनको, 2009) और विशिष्ट संख्या-सिद्धांत संबंधी मान्यताओं के तहत सामान्य $s$ के लिए $\exp(\tilde{O}((\log n)^{1/s})$ ।

हालाँकि, सर्वरों की संख्या $s$ और संचार जटिलता के बीच के ट्रेड-ऑफ में एक महत्वपूर्ण अंतर बना हुआ था। विशेष रूप से, "मैचिंग वेक्टर + $S$ -डिकोडिंग पॉलिनोमिय" फ्रेमवर्क (जिसे एफ्रेमेनको द्वारा शुरू किया गया था और घासेमी, कोप्पर्टी और सुदान द्वारा परिष्कृत किया गया था) के भीतर, ज्ञात सर्वोत्तम निर्माणों के लिए संचार $\exp(\tilde{O}((\log n)^{1/k}))$ प्राप्त करने के लिए $s = 2^k$ या $s = 3k/2$ सर्वरों की आवश्यकता थी। घासेमी और कोप्पर्टी (2026) द्वारा स्थापित सैद्धांतिक निचली सीमाओं (lower bounds) ने सुझाव दिया था कि आवश्यक डिकोडिंग पॉलिनॉमिय की स्पर्सिटी (sparsity) $k+1$ जितनी कम हो सकती है, जिसका अर्थ है कि समान संचार लागत के लिए एक्सपोनेंशियल रूप से कम सर्वरों की क्षमता है। खुला प्रश्न यह था कि क्या ऐसे इष्टतम स्पार्स पॉलिनॉमिय का निर्माण किया जा सकता है।

कार्यप्रणाली
लेखक $S$ -डिकोडिंग पॉलिनॉमिय के निर्माण पर ध्यान केंद्रित करके इस समस्या का समाधान करते हैं। मान लीजिए $m = p_1 \dots p_k$ $k$ अलग-अलग अभाज्य संख्याओं (primes) का गुणनफल है, और $S^*_m \subseteq \mathbb{Z}_m$ प्रत्येक $p_i$ के मॉड्यूल $0 $या$ 1$ के अनुरूप अवशेषों (residues) का कैनोनिकल सेट है। एक परिमित क्षेत्र (finite field) $\mathbb{F}$ पर $S^*_m$ -डिकोडिंग पॉलिनोमिय $P$ को $P(1)=1$ और सभी $j \in S^*_m \setminus \{0\}$ के लिए $P(\gamma^j)=0$ को संतुष्ट करना चाहिए, जहाँ $\gamma$ एक प्रिमिटिव $m$ -वें रूट ऑफ यूनिटी है। $P$ की स्पर्सिटी (गैर-शून्य गुणांकों की संख्या) सीधे तौर पर आवश्यक सर्वरों $s$ की संख्या को निर्धारित करती है।

इन ग्रिड्स का निर्माण करने के लिए, लेखक एक "रूट-ऑफ-यूनिटी ग्रिड" के अस्तित्व और एक $S^*_m$ -डिकोडिंग पॉलिनोमिय की स्पर्सिटी $k+1$ के बीच समानता स्थापित करते हैं। एक रूट-ऑफ-यूनिटी ग्रिड तत्वों $a_1, \dots, a_k \in \mathbb{F} \setminus \{0\}$ और विशिष्ट $t_1, \dots, t_{k+1} \in \mathbb{F}$ का एक विन्यास है ताकि सभी $i, j$ के लिए $1 + a_i t_j$ एक $p_i$ -थ रूट ऑफ यूनिटी हो।

इन ग्रिड्स के निर्माण के लिए, लेखक दो दृष्टिकोण प्रस्तावित करते हैं:

प्रोबेबिलिस्टिक मेथड (रफ रेपुनिट्स): यह मुख्य परिणामों के लिए उपयोग किया जाने वाला प्राथमिक दृष्टिकोण है। यह एक अभाज्य $q$ और पूर्णांक $d_1, \dots, d_k$ खोजने पर निर्भर करता है ताकि $q^{d_i}-1$ का एक बड़ा अभाज्य गुणनखंड हो (विशेष रूप से एक "रफ" संख्या जहाँ सबसे बड़ा अभाज्य गुणनखंड कम से कम $(q^{d_i}-1)^{1-1/(3k)}$ हो)। ऐसी संख्याओं का अस्तित्व एक संभावित संख्या-सिद्धांत संबंधी अनुमान (conjecture) के तहत गारंटीकृत है।
एल्जेब्रिक मेथड (नॉर्म कर्नेल्स): गैलवा थ्योरी और नॉर्म मैप का उपयोग करने वाला एक माध्यमिक दृष्टिकोण जो ग्रिड्स का निर्माण करता है, जो सफलतापूर्वक एफ्रेमेनको के मूल $m=7 \times 73$ उदाहरण को पुनः प्राप्त करता है, लेकिन लेखकों के मुख्य प्रमेयों के लिए व्यापक रूप से सामान्यीकरण नहीं कर पाता है जैसा कि प्रोबेबिलिस्टिक मेथड करता है।

उन स्थितियों के लिए जहाँ सर्वरों की संख्या $s$ , $n$ के साथ बढ़ती है (सुपरकॉन्स्टेंट), लेखक एक ही विशेषता (characteristic) पर कई रूट-ऑफ-यूनिटी ग्रिड्स को एक एकल डिकोडिंग पॉलिनोमिय में संयोजित करने के लिए एक "स्टिचिंग" तकनीक (इतो और सुजुकी, 2010 पर आधारित) का उपयोग करते हैं।

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

स्पर्सिटी गैप का समाधान: एक संख्या-सिद्धांत संबंधी अनुमान (कन्जेक्चर 1.1) के तहत, लेखक सिद्ध करते हैं कि किसी भी स्थिरांक $k$ के लिए, $k+1$ की स्पर्सिटी वाला एक $S^*_m$ -डिकोडिंग पॉलिनोमिय मौजूद है, जहाँ $m$ $k$ अलग-अलग अभाज्य संख्याओं का गुणनफल है। यह घासेमी और कोप्पर्टी द्वारा स्थापित स्पर्सिटी की निचली सीमा से मेल खाता है, जिससे स्पर्सिटी पर ऊपरी और निचली सीमाओं के बीच का एक्सपोनेंशियल अंतर पूरी तरह समाप्त हो जाता है।
- कन्जेक्चर 1.1: प्रत्येक $k>1$ के लिए, एक अभाज्य $q \ge k+1$ और विशिष्ट पूर्णांक $d_i \ge 6$ मौजूद हैं ताकि $q^{d_i}-1$ का एक अभाज्य विभाजक $\ge (q^{d_i}-1)^{1-1/(3k)}$ हो। यह 'जनरलाइज्ड रेपुनिट कन्जेक्चर' या 'शिनज़ेल हाइपोथेसिस H' द्वारा समर्थित है।
बेहतर PIR प्रोटोकॉल: घासेमी, कोप्पर्टी और सुदान (2025) के फ्रेमवर्क में इन नए स्पार्स पॉलिनॉमिय को डालकर, लेखक एक $s$ -सर्वर PIR प्रोटोकॉल प्राप्त करते हैं जिसकी संचार जटिलता है:
$\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$
यह किसी भी $s \ge 4$ के लिए पिछले अत्याधुनिक (state-of-the-art) परिणामों की तुलना में स्पष्ट रूप से बेहतर है। उदाहरण के लिए, जबकि पिछले कार्यों को $\exp(\tilde{O}((\log n)^{1/k}))$ संचार प्राप्त करने के लिए $2^k$ या $3k/2$ सर्वरों की आवश्यकता थी, यह कार्य केवल $k+1$ सर्वरों के साथ (जहाँ $s=k+1$ ) वही संचार प्राप्त करता है।
छोटे $s$ के लिए अनकंडीशनल परिणाम: अनुभवजन्य सत्यापन (empirical validation) के माध्यम से, लेखक प्रदर्शित करते हैं कि आवश्यक संख्या-सिद्धांत संबंधी स्थितियाँ छोटे $k$ के लिए सत्य हैं। यदि संभाव्य अभाज्य (probable primes) वास्तव में अभाज्य हैं, तो हम $s \in [2, 15]$ के लिए सभी अनकंडीशनल $s$ -सर्वर PIR प्रोटोकॉल का निर्माण करते हैं, जो $s \in [2, 24]$ तक विस्तृत होता है।
सुपरकॉन्स्टेंट सर्वर रिजीम: पेपर उस रिजीम का विश्लेषण करता है जहाँ $s$ , $n$ के साथ बढ़ता है। उनके एक मजबूत संस्करण के तहत, वे दिखाते हैं कि संचार जटिलता को $s \le \exp(o(\sqrt{\log \log n} / \log \log \log n))$ के लिए पिछले मैचिंग-वेक्टर PIR निर्माणों की तुलना में सुपरपॉलीनोमियल रूप से कम किया जा सकता है। हालाँकि, बहुत बड़े $s$ के लिए, उनकी तकनीकें वर्तमान में मौजूदा निर्माणों की तुलना में सुधार प्रदान नहीं करती हैं।
AI-असिस्टेड डिस्कवरी: लेखक स्पष्ट रूप से बताते हैं कि मुख्य परिणाम (थ्योरम 1.2) और इसका प्रमाण OpenAI के GPT-5.5 Pro मॉडल के साथ एक बातचीत के माध्यम से खोजा गया था। मॉडल ने आवश्यक पॉलिनॉमिय बनाने के लिए एक सामान्य ढांचे की पहचान की और इसे एक औपचारिक प्रमाण में सामान्यीकृत किया।

महत्व
पेपर दावा करता है कि यह $S$ -डिकोडिंग पॉलिनॉमिय की न्यूनतम स्पर्सिटी से संबंधित एक लंबे समय से चले आ रहे खुले प्रश्न को हल करता है, जिससे मैचिंग-वेक्टर PIR फ्रेमवर्क में संचार-सर्वर ट्रेड-ऑफ को अनुकूलित किया जा सके। संचार-सर्वर ट्रेड-ऑफ को अनुकूलित करने के लिए, आवश्यक सर्वरों की संख्या को एक्सपोनेंट में एक्सपोनेंशियल (जैसे, $2^k$ ) से घटाकर एक्सपोनेंट में लीनियर ( $k+1$ ) करके, यह कार्य PIR प्रोटोकॉल की दक्षता में महत्वपूर्ण सुधार करता है। लेखक इसे वर्तमान "मैचिंग वेक्टर + डिकोडिंग पॉलिनोमिय" प्रतिमान के भीतर एक निर्णायक कदम के रूप में देखते हैं, और स्वीकार करते हैं कि आगे के सुधारों के लिए नए फ्रेमवर्क या रूट-ऑफ-यूनिटी ग्रिड्स के निर्माण के लिए अलग तंत्र की आवश्यकता हो सकती है। यह कार्य नवीन गणितीय निर्माणों और प्रमाणों की खोज में AI मॉडलों की क्षमता को भी उजागर करता है।

इसी तरह के और पेपर