💻 computer science

Information-Theoretic Distributed Point Functions with Shorter Keys

यह शोध पत्र $\mathbb{Z}_p$ समूह पर एक नवीन, पूर्णतः सुरक्षित 1-निजी सूचना-सैद्धांतिक वितरित बिंदु फलन (ITDPF) प्रस्तुत करता है जो हालिया निजी सूचना पुनर्प्राप्ति तकनीकों पर आधारित शेयर रूपांतरण का लाभ उठाकर मौजूदा योजनाओं की तुलना में साहचर्य रूप से छोटे गुप्त कुंजियों (secret keys) को प्राप्त करता है।

मूल लेखक: Hang Deng, Liang Feng Zhang

प्रकाशित 2026-04-28

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

CC BY 4.0

मूल लेखक: Hang Deng, Liang Feng Zhang

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

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

यह एक डिस्ट्रीब्यूटेड पॉइंट फंक्शन (DPF) का मूल आधार है। यह एक "पॉइंट फंक्शन" (एक ऐसा फंक्शन जो हर जगह शून्य होता है सिवाय एक विशेष बिंदु के) को कई "शेयर्स" (कुंजियों/कीज़) में विभाजित करने का एक क्रिप्टोग्राफिक टूल है।

पुराना तरीका बनाम नया तरीका

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

नया तरीका (हल्के सैचल्स/थैले):
यह पेपर एक नया तरीका पेश करता है जो बहुत हल्के सैचल्स बनाता है। लेखक, हंग डेंग और लियांग फेंग झांग ने एक ऐसी प्रणाली बनाई है जहाँ कुंजियाँ किसी भी पिछली पूर्णतः सुरक्षित विधि की तुलना में काफी छोटी हैं, विशेष रूप से जब डेटा बहुत विशाल हो जाता है।

उन्होंने यह कैसे किया: "गुप्त रेसिपी"

लेखकों ने शून्य से कोई नई जादुвई विधि नहीं बनाई; उन्होंने एक प्रकार के गुप्त-साझाकरण उपकरण को दूसरे में बदलने के लिए एक चतुर रेसिपी (जिसे LKZ फ्रेमवर्क कहा जाता है) का उपयोग किया।

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

परिणाम: एक पूर्णतः सुरक्षित, छोटी कुंजी

यह पेपर दावा करता है कि उन्होंने एक ऐसी प्रणाली बनाई है जो है:

पूर्णतः सुरक्षित (Perfectly Secure): यदि कोई हैकर कुछ कुंजियाँ चुरा लेता है, तो भी वह अनंत कंप्यूटिंग शक्ति होने पर भी गुप्त स्थान के बारे में कुछ भी नहीं जान सकता।
कुशल (Efficient): इसकी "कुंजियाँ" (वह डेटा जो प्रत्येक सर्वर के पास होता है) एसिम्प्टोटिक रूप से छोटी (asymptotically shorter) हैं। सरल शब्दों में: जैसे-जैसे डेटा की मात्रा बढ़ती है, कुंजियों का आकार पहले की तुलना में बहुत धीमी गति से बढ़ता है।
लचीली (Flexible): यह किसी भी अभाज्य संख्या के आकार (एक विशिष्ट प्रकार के गणितीय समूह) के लिए काम करती है, जो व्यावहारिक आवश्यकताओं की एक विस्तृत श्रृंखला को कवर करती है।

कमी (सीमाएं)

लेखक अपने समझौतों (trade-offs) के बारे में ईमानदार हैं:

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

सारांश

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

यहाँ हेंग डेंग और लियांग फेंग झांग के शोध पत्र "Information-Theoretic Distributed Point Functions with Shorter Keys" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र इन्फॉर्मेशन-थ्योरेटिक डिस्ट्रीब्यूटेड पॉइंट फंक्शन्स (ITDPFs) के निर्माण को संबोधित करता है।

परिभाषा: एक $(t, n)$ -ITDPF एक पॉइंट फंक्शन $f_{\alpha, \beta}(x)$ (जो इनपुट $\alpha$ पर $\beta$ आउटपुट देता है और अन्यथा $0 $देता है) को$ n$ गुप्त कुंजियों (secret keys) में विभाजित करने की अनुमति देता है। $\le t$ सर्वरों का कोई भी उपसमूह (subset) फंक्शन के बारे में बिल्कुल कुछ नहीं जान पाता (परफेक्ट सुरक्षा), जबकि सभी $n$ सर्वरों के मूल्यांकन (evaluations) का योग फंक्शन के मान को पुनर्गठित (reconstruct) करता है।
चुनौती: DPFs के लिए प्राथमिक दक्षता मीट्रिक कुंजी का आकार (key size) (गुप्त कुंजियों का अधिकतम आकार) है। आउटपुट ग्रुप $G = \mathbb{Z}_p$ $G = Z_{p}$ (जहाँ $p$ $p$ कोई अभाज्य संख्या है) के लिए मौजूदा पूर्णतः सुरक्षित (perfectly secure) ITDPFs उप-इष्टतम कुंजी आकार से ग्रस्त हैं।
- पिछले कार्यों (जैसे, बॉयल एट अल., ली एट अल.) ने ऐसे कुंजी आकार प्राप्त किए जिनमें $\nu_r(N) = (\log N)^{1/r}(\log \log N)^{1-1/r}$ जैसे फलन शामिल थे।
- लक्ष्य यह है कि पूर्ण सुरक्षा बनाए रखते हुए और किसी भी अभाज्य $p$ का समर्थन करते हुए, एसिम्प्टोटिक (asymptotic) कुंजी आकार को कम किया जाए।

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

लेखक LKZ फ्रेमवर्क (ली, कोपार्टी, और झांग) को अत्याधुनिक प्राइवेट इंफॉर्मेशन रिट्रीवल (PIR) तकनीकों के साथ जोड़कर एक नया निर्माण प्रस्तावित करते हैं।

A. LKZ फ्रेमवर्क

यह फ्रेमवर्क 'शेयर कन्वर्जन' (Share Conversion) के माध्यम से एक सीक्रेट शेयरिंग स्कीम (SSS) को ITDPF में परिवर्तित करता है।

शेयर कन्वर्जन: इसके लिए एक $(t, n)$ -थ्रेशोल्ड SSS ( $L_1$ ) के शेयरों को एक एडिटिव SSS ( $L_2$ ) के शेयरों में बदलने की आवश्यकता होती है, ताकि परिवर्तित शेयरों का योग मूल सीक्रेट के साथ एक विशिष्ट संबंध प्रकट करे।
द्विरेखीय प्रतिनिधित्व (Bilinear Representation): पॉइंट फंक्शन को परिवर्तित शेयरों के एक द्विरेखीय फलन के रूप में दर्शाया जाता है।
मुख्य अंतर्दृष्टि (Key Insight): परिणामी ITDPF का कुंजी आकार उस अंतर्निहित PIR योजना के संचार जटिलता (communication complexity) के समानुपाती होता है जिसका उपयोग शेयर कन्वर्जन उत्पन्न करने के लिए किया जाता है।

B. GKS डेरिवेटिव-आधारित PIR का लाभ उठाना

मुख्य तकनीकी नवाचार घसामी, कोपार्टी, और सुदान (GKS, STOC 2025) द्वारा विकसित हालिया 1-प्राइवेट $n_r$ -सर्वर PIR योजना का उपयोग करना है।

GKS तंत्र: पिछले PIR स्कीमा के विपरीत, जो केवल एक बहुपद (polynomial) के मूल्यांकन (evaluations) को क्वेरी करते हैं, GKS बहुपद के मूल्यांकन और हासे डेरिवेटिव (Hasse derivatives) दोनों को क्वेरी करता है।
गणितीय आधार:
- यह परिमित क्षेत्रों (finite fields) पर $S$ -मैचिंग फैमिली और $S$ -डिकोडिंग बहुपदों का उपयोग करता है।
- यह मल्टीप्लिसिटी के साथ 0-इंटरपोलेशन प्रॉपर्टी पेश करता है। डेरिवेटिव्स की मांग करके, यह योजना कम सर्वरों या छोटे मापदंडों का उपयोग करके एक स्पार्स (sparse) बहुपद के स्थिरांक पद (constant term) को इंटरपोलेट कर सकती है।
- विशेष रूप से, GKS $n_r$ सर्वरों के लिए $2^{O(\nu_{r+1}(N))}$ की संचार जटिलता प्राप्त करता है, जहाँ $n_r$ मॉडुलस के अभाज्य गुणनखंडों की संख्या पर निर्भर करता है।

C. प्रस्तावित निर्माण के चरण

सेटअप (Setup):
- एक मॉडुलस $M = m \cdot p$ (विभिन्न अभाज्य संख्याओं का गुणनफल) चुनें।
- एक $S_M$ -मैचिंग फैमिली और मल्टीप्लिसिटी 2 के साथ एक $S_M$ -डिकोडिंग बहुपद का निर्माण करें (जो डेरिवेटिव क्वेरीज़ द्वारा सक्षम है)।
शेयर कन्वर्जन ($Conv$):
- सर्वर एक रैंडम वेक्टर $w$ और लक्षित इंडेक्स $\alpha$ से प्राप्त शेयर $c_\ell$ रखता है।
- एक इनपुट $x$ के लिए, सर्वर एक मल्टीप्लिकेटिव लाइन पर प्रतिबंधित "कोर बहुपद" $D_x(Z)$ की गणना करता है।
- चेन रूल (chain rule) का उपयोग करते हुए, सर्वर विशिष्ट बिंदुओं $b_\ell$ पर $D_x(Z)$ का प्रथम-क्रम हासे डेरिवेटिव (first-order Hasse derivative) की गणना करता है।
- सर्वर एक परिवर्तित शेयर आउटपुट करता है जिसमें मूल्यांकन $D_x(b_\ell)$ और डेरिवेटिव टर्म शामिल है, जिसे इंटरपोलेशन गुणांकों $a_{\ell, k}$ द्वारा भारित (weighted) किया गया है।
DPF जनरेशन:
- जनरेटर $2n_r$ कुंजियाँ बनाता है। प्रत्येक कुंजी में एक जोड़ा होता है: आउटपुट मान का एक एडिटिव शेयर और अंतर्निहित PIR-आधारित SSS से एक शेयर।
- मूल्यांकन एल्गोरिथ्म $f_{\alpha, \beta}(x)$ के एडिटिव शेयर को पुनः प्राप्त करने के लिए कुंजी घटकों के आंतरिक उत्पाद (inner product) की गणना करता है।

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

नया शेयर कन्वर्जन: लेखक सीधे GKS डेरिवेटिव-आधारित PIR से एक नया शेयर कन्वर्जन फलन व्युत्पन्न करते हैं। यह ITDPF के निर्माण के लिए डेरिवेटिव-आधारित PIR का पहला अनुप्रयोग है।
बेहतर कुंजी आकार: वे एक पूर्णतः सुरक्षित $(1, 2n_r)$ $(1, 2 n_{r})$ -ITDPF का निर्माण करते हैं जिसका आउटपुट ग्रुप $\mathbb{Z}_p$ $Z_{p}$ है।
- कुंजी का आकार: $O(2^{c_2(r) \cdot \nu_{r+1}(N)} \cdot \log p)$ ।
- सुधार: यह पिछले सर्वोत्तम पूर्णतः सुरक्षित ITDPFs (जैसे, ली एट अल. का $2^{O(\nu_r(N))}$ ) की तुलना में एसिम्प्टोटिक रूप से छोटा है, जो प्रभावी रूप से घातांक को $\nu_r(N)$ से घटाकर $\nu_{r+1}(N)$ कर देता है।
पूर्ण सुरक्षा (Perfect Security): यह निर्माण पूर्ण सुरक्षा बनाए रखता है (कंप्यूटेशनल रूप से असीमित विरोधियों के विरुद्ध सूचना-सैद्धांतिक सुरक्षा), जबकि कुछ सांख्यिकीय विकल्प दक्षता के लिए सुरक्षा से समझौता करते हैं।
सामान्यता (Generality): यह योजना आउटपुट ग्रुप के रूप में किसी भी अभाज्य $p$ के लिए काम करती है, जो कि कुछ पूर्ववर्ती निर्माणों का एक महत्वपूर्ण सामान्यीकरण है।

4. परिणाम (Results)

सैद्धांतिक सीमाएँ (Theoretical Bounds): यह शोध पत्र सिद्ध करता है कि प्रस्तावित योजना LKZ फ्रेमवर्क की शुद्धता (correctness) और पूर्ण सुरक्षा आवश्यकताओं को पूरा करती है।
तुलना (तालिका I):
- [10] (ली एट अल.) के थ्योरम 10 की तुलना में, जिसका कुंजी आकार $O(2^{c_1(r) \cdot \nu_r(N)})$ है, नया स्कीम $O(2^{c_2(r) \cdot \nu_{r+1}(N)})$ प्राप्त करता है। चूंकि $\nu_{r+1}(N) < \nu_r(N)$ , इसलिए नई कुंजियाँ एसिम्प्टोटिक रूप से स्पष्ट रूप से छोटी हैं।
- [2] (बॉयल एट अल.) के थ्योरम 1 की तुलना में, नया स्कीम कमतर नहीं है और बड़े $N$ के लिए बेहतर एसिम्प्टोटिक स्केलिंग प्रदान करता है।
पैरामीटर्स: आवश्यक सर्वरों की संख्या $2n_r$ है, जहाँ $n_r$ को PIR निर्माण में अभाज्य गुणनखंडों की संख्या द्वारा परिभाषित किया गया है (जैसे, $n_1=2, n_2=3, \dots$ )।

5. महत्व (Significance)

MPC और PIR में दक्षता: DPFs, सुरक्षित मल्टी-पार्टी कंप्यूटेशन (MPC) और प्राइवेट इंफॉर्मेशन रिट्रीवल (PIR) के मौलिक बिल्डिंग ब्लॉक्स हैं। कुंजी के आकार को कम करने से इन प्रोटोकॉल में संचार ओवरहेड और स्टोरेज आवश्यकताओं में सीधे कमी आती है।
PIR और DPF को जोड़ना: यह कार्य हालिया PIR (विशेष रूप से डेरिवेटिव-आधारित दृष्टिकोण) और DPF निर्माण के बीच एक शक्तिशाली तालमेल को प्रदर्शित करता है। यह सुझाव देता है कि PIR संचार जटिलता में सुधार को सीधे अधिक कुशल DPFs में परिवर्तित किया जा सकता है।
भविष्य की दिशाएँ:
- वर्तमान निर्माण 1-प्राइवेट DPFs तक सीमित है (1 मिलीभगत करने वाले सर्वर के विरुद्ध सुरक्षा) क्योंकि अंतर्निहित GKS PIR 1-प्राइवेट है। सर्वर की संख्या में घातीय वृद्धि (exponential blowup) के बिना $t > 1$ के लिए $t$ -प्राइवेट DPFs तक विस्तार करना एक खुला प्रश्न है।
- आउटपुट ग्रुप को अभाज्य-क्रम $\mathbb{Z}_p$ से किसी भी एबेलियन (Abelian) समूह तक विस्तारित करना भविष्य के कार्य के रूप में पहचाना गया है।

संक्षेप में, यह शोध पत्र डेरिवेटिव-आधारित PIR तकनीकों का लाभ उठाकर पूर्णतः सुरक्षित ITDPFs की दक्षता में एक बड़ी सफलता प्रस्तुत करता है, जिससे अभाज्य-क्रम आउटपुट समूहों के लिए अब तक की सबसे छोटी ज्ञात गुप्त कुंजियाँ प्राप्त होती हैं।