💻 computer science

Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold

यह शोध पत्र सामान्य $L_p$ दूरियों के लिए नए फजी प्राइवेट सेट इंटरसेक्शन (FPSI) प्रोटोकॉल प्रस्तुत करता है जो केवल ओब्लिवियस ट्रांसफर और सिमेट्रिक-की प्रिमिटिव्स का उपयोग करके दूरी थ्रेशोल्ड $\delta$ पर इष्टतम लॉगरिदमिक निर्भरता प्राप्त करते हैं, जिससे महंगी होमोमोर्फिक एन्क्रिप्शन की आवश्यकता समाप्त हो जाती है और रनटाइम एवं संचार में अत्याधुनिक समाधानों की तुलना में काफी बेहतर प्रदर्शन होता है।

मूल लेखक: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

प्रकाशित 2026-06-16

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

CC BY 4.0

मूल लेखक: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

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

कल्पना कीजिए कि दो लोग, एलिस (Alice) और बॉब (Bob), यह पता लगाना चाहते हैं कि क्या उनके पास अपने संबंधित संग्रहों में कोई "समान" वस्तुएं हैं, बिना एक-दूसरे को अपनी पूरी सूचियाँ दिखाए।

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

चुनौती इसे सुरक्षित रूप से करने की है। एलिस को बॉब की पूरी सूची के बारे में पता नहीं चलना चाहिए, और बॉब को एलिस की पूरी सूची के बारे में पता नहीं चलना चाहिए। वे केवल यह जानना चाहते हैं कि कौन सी वस्तुएं पर्याप्त रूप से करीब हैं।

पुराना तरीका: धीमा और महंगा खोज (The Old Way: The Slow, Expensive Search)

पिछले तरीकों में इस "फजी मैचिंग" खेल के साथ दो बड़ी समस्याएं थीं:

"लीनियर" का जाल (The "Linear" Trap): यदि "निकटता" का थ्रेशोल्ड बड़ा था (मान लीजिए 100 यूनिट), तो कंप्यूटरों को प्रत्येक आइटम के लिए 100 अलग-अलग संभावनाओं की जांच करनी पड़ती थी। यह एक घास के ढेर में सुई खोजने जैसा था, जहाँ हर एक तिनके को एक-एक करके चेक किया जा रहा हो। थ्रेशोल्ड जितना बड़ा होता, यह उतना ही धीमा होता जाता।
"भारी मशीनरी" की समस्या (The "Heavy Machinery" Problem): इसे सुरक्षित रूप से काम करने के लिए, पुराने तरीकों ने बहुत भारी, धीमे क्रिप्टोग्राफिक उपकरणों (जैसे एडिटिव होमोमोर्फिक एन्क्रिप्शन) का उपयोग किया। इसे ऐसे समझें जैसे आप एक विशाल, ईंधन की खपत करने वाले ट्रक का उपयोग करके एक गुप्त संदेश भेजने की कोशिश कर रहे हों, जबकि एक साइकिल भी काम कर सकती थी।

नया ब्रेकथ्रू: "प्रिफिक्स" शॉर्टकट (The New Breakthrough: The "Prefix" Shortcut)

यह शोध पत्र इस खेल को खेलने का एक नया तरीका पेश करता है जो तेज़, हल्का और स्मार्ट है।

1. "ज़िप कोड" सादृश्य (Prefixes)

संख्याओं की एक रेंज (जैसे 10, 11, 12... से 100 तक की जांच करना) को चेक करने के बजाय, लेखक "प्रिफिक्स" (Prefixes) नामक एक ट्रिक का उपयोग करते हैं।

कल्पना कीजिए कि आप एक शहर में एक घर की तलाश कर रहे हैं।

पुराना तरीका: आप अपने दोस्त को खोजने के लिए पड़ोस के हर दरवाजे पर दस्तक देते हैं।
नया तरीका: आप ज़िप कोड देखते हैं। यदि आपका दोस्त "10001" प्रिफिक्स वाले क्षेत्र में रहता है, तो आपको केवल उसी प्रिफिक्स वाले घरों की जांच करने की आवश्यकता है। आपको पूरे शहर को चेक करने की आवश्यकता नहीं है।

लेखकों ने महसूस किया कि संख्याओं की किसी भी "रेंज" (थ्रेशोल्ड) को कुछ ही "ज़िप कोड" (प्रिफिक्स) में तोड़ा जा सकता है।

जादू: इन प्रिफिक्स को चेक करने में लगने वाला समय थ्रेशोल्ड के आकार के साथ नहीं बढ़ता, बल्कि यह लॉगारिदमिक (logarithmic) रूप से बढ़ता है।
- यदि थ्रेशोल्ड दोगुना हो जाता है, तो काम केवल थोड़ा सा बढ़ता है।
- यदि थ्रेशोल्ड 100 गुना बड़ा हो जाता है, तो काम केवल दोगुना होता है।
- सादृश्य: यह लाइब्रेरी में किताब खोजने जैसा है। हर किताब को चेक करने में सदियां लग जाएंगी। शेल्फ लेबल (प्रिफिक्स) को चेक करने में सेकंड लगते हैं, चाहे शेल्फ पर कितनी भी किताबें क्यों न हों।

2. "हल्के" उपकरण (Symmetric Primitives)

लेखकों ने भारी "ट्रकों" (महंगे एन्क्रिप्शन) को "साइकिल" (सिमेट्रिक-की प्रिमिटिव्स और ऑब्लिवियस ट्रांसफर) से बदल दिया।

ऑब्लिवियस ट्रांसफर (OT): कल्पना कीजिए कि एक वेटर आपको दो गुप्त मेनू आइटमों में से एक दे सकता है बिना यह जाने कि आपने कौन सा चुना, और बिना यह जाने कि वेटर को क्या चाहिए था। लेखक जानकारी को सुरक्षित रूप से बदलने के लिए इनका उपयोग करते हैं ताकि पूरी सूची प्रकट न हो।
परिणाम: उनका सिस्टम पूरी तरह से इन हल्के और तेज़ उपकरणों से बना है।

दो परिदृश्य: छोटे कमरे बनाम विशाल हॉल (The Two Scenarios: Small Rooms vs. Giant Halls)

पेपर डेटा कितना "भीड़भाड़ वाला" है (डायमेंशनलिटी/आयाम), इसके आधार पर दो अलग-अलग रणनीतियां प्रदान करता है:

परिदृश्य A: कम आयाम (The "Apart" Assumption)

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

परिदृश्य B: उच्च आयाम (The "Separate" Assumption)

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

"सीक्रेट सॉस": इक्वैलिटी कंडिशनल सम (The "Secret Sauce": Equality Conditional Sum)

उनका मुख्य आविष्कार एक नया गणितीय उपकरण है जिसे इक्वैलिटी कंडिशनल सम (ECSS) कहा जाता है।

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

परिणाम: एक बड़ी बढ़त (The Results: A Massive Speedup)

लेखकों ने अपने सिस्टम का एक वर्किंग वर्जन बनाया और मौजूदा सर्वोत्तम तरीकों के विरुद्ध इसका परीक्षण किया।

गति (Speed): उनका सिस्टम पिछले सर्वश्रेष्ठ तरीकों की तुलना में 43.7 गुना तक तेज़ है।
डेटा उपयोग (Data Usage): यह नेटवर्क पर भेजने के लिए 31.3 गुना तक कम डेटा का उपयोग करता है।
स्केलेबिलिटी (Scalability): जबकि अन्य सिस्टम बड़े डेटा सेट आने पर क्रैश हो गए (मेमोरी खत्म होने के कारण), उनका सिस्टम सुचारू रूप से चलता रहा।

सारांश

संक्षेप में, यह शोध पत्र "फजी मैचिंग" की समस्या को हल करता है:

धीमे, भारी एन्क्रिप्शन को तेज़, हल्के उपकरणों से बदलकर।
"प्रिफिक्स" (ज़िप कोड की तरह) का उपयोग करके एक धीमी, लीनियर खोज को एक तेज़, लॉगरिदमिक खोज में बदलकर।
नए "सीक्रेट सम" टूल्स बनाकर जो दो पक्षों को उनके रहस्य प्रकट किए बिना निकटता की जांच करने की अनुमति देते हैं।

परिणामस्वरूप, यह प्रणाली विशाल, निजी डेटासेट्स में "समान" वस्तुओं को लगभग तुरंत ढूंढ सकती है, जिससे बड़े पैमाने पर गोपनीयता-संरक्षित डेटा मिलान व्यावहारिक हो जाता है।

तकनीकी सारांश: सममित प्रिमिटिव्स (Symmetric Primitives) से फजी पीएसआई (Fuzzy PSI) - दूरी थ्रेशोल्ड पर सटीक लघुगणकीय निर्भरता के साथ

समस्या विवरण
फजी प्राइवेट सेट इंटरसेक्शन (FPSI), एक प्रेषक (sender) जिसके पास $d$ -आयामी वेक्टर्स का एक सेट $Q$ है और एक प्राप्तकर्ता (receiver) जिसके पास $W$ का एक सेट है, को उन आइटम्स $q \in Q$ की पहचान करने में सक्षम बनाता है जिनके लिए ऐसा $w \in W$ मौजूद है कि $\text{dist}(q, w) \le \delta$ , बिना अतिरिक्त जानकारी प्रकट किए। जबकि मानक PSI ने उच्च दक्षता प्राप्त कर ली है, मौजूदा FPSI प्रोटोकॉल महत्वपूर्ण सैद्धांतिक और व्यावहारिक बाधाओं का सामना करते हैं। पूर्ववर्ती कार्य आमतौर पर दूरी थ्रेशोल्ड $\delta$ के साथ रैखिक स्केलिंग (अर्थात, $O(\delta)$ ) प्रदर्शित करते हैं, या केवल $L_\infty$ दूरियों के लिए पॉली-लॉगारिदमिक निर्भरता प्राप्त करते हैं। सामान्य मिंकोव्स्की दूरियों ( $L_p$ जहाँ $p \in [1, \infty]$ ) का समर्थन करने वाले प्रोटोकॉल या तो महंगी एडिटिव होमोमॉर्फिक एन्क्रिप्शन (AHE) पर निर्भर रहे हैं या सुरक्षा खामियों और आयाम $d$ में घातीय जटिलता (exponential complexity) से ग्रस्त रहे हैं। लक्ष्य सामान्य $L_p$ दूरियों के लिए $\delta$ पर सटीक लघुगणकीय (logarithmic) निर्भरता प्राप्त करना है, जो केवल कुशल सममित-कुंजी प्रिमिटिव्स (symmetric-key primitives) का उपयोग करता है।

कार्यप्रणाली और मुख्य तकनीकें
लेखक पूरी तरह से ऑब्लिवियस ट्रांसफर (OT) और सममित-कुंजी प्रिमिटिव्स से निर्मित नए FPSI प्रोटोकॉल प्रस्तावित करते हैं, जो AHE जैसे पब्लिक-की ऑपरेशन्स से बचते हैं। यह निर्माण दो प्राथमिक धारणाओं पर आधारित है: अपार्ट (apart) धारणा (जो कम-आयामी परिवेश के लिए उपयुक्त है) और सेपरेट (separate) धारणा (जो उच्च-आयामी परिवेश के लिए उपयुक्त है)।

प्रिफिक्स प्रतिनिधित्व और इंटरवल टेस्टिंग:
मुख्य नवाचार $[q_k - \delta, q_k + \delta]$ अंतराल में सभी पूर्णांकों के एन्यूमरेशन (enumeration) को $O(\log \delta)$ प्रिफिक्स के उपयोग वाले प्रिफिक्स प्रतिनिधित्व से बदलना है (जिसकी लागत $O(\delta)$ होती है)। यह प्रति आयाम इंटरवल टेस्टिंग लागत को $O(\log \delta)$ तक कम कर देता है।
इक्वैलिटी कंडिशनल सम/इनर-प्रोडक्ट शेयर (ECSS/ECIPS):
प्रिफिक्स मिलान द्वारा आवश्यक इंटरैक्शन को संभालने के लिए, जो प्रेषक के इनपुट को प्रकट किए बिना या घातीय ओवरहेड के बिना काम करता है, लेखक दो नए क्रिप्टोग्राफिक प्रिमिटिव्स पेश करते हैं:

इक्वैलिटी कंडिशनल सम शेयर (ECSS): $L_\infty$ दूरी के लिए उपयोग किया जाता है। यह पक्षों को इनपुट वेक्टर्स के बीच समानता मिलान (equality match) की स्थिति में मानों का योग कंप्यूट करने की अनुमति देता है, जिससे परिणाम के गुप्त शेयर्स (secret shares) प्राप्त होते हैं।
इक्वैलिटी कंडिशनल इनर-प्रोडक्ट शेयर (ECIPS): सामान्य $L_p$ दूरियों के लिए उपयोग किया जाता है। यह समानता की स्थिति में एक इनर प्रोडक्ट को कंप्यूट करता है, जिससे द्विपद विस्तार (binomial expansion) के माध्यम से विशिष्ट पदों को प्रकट किए बिना $|w_k - q_k|^p$ की गणना संभव होती है।
इन दोनों प्रिमिटिव्स को OT, ऑब्लिवियस प्रोग्रामेबल PRF (OPPRF), और पर्म्यूट+शेयर (PS) प्रोटोकॉल का उपयोग करके कुशलतापूर्वक लागू किया गया है।

एकाधिक तत्वों को संभालना:

कम-आयामी ( $L_\infty$ और $L_p$ ): प्रोटोकॉल युग्म-वार तुलनाओं की संख्या को कम करने के लिए स्थानिक हैशिंग (ग्रिड सेल्स) को कूकू हैशिंग (Cuckoo hashing) के साथ जोड़ते हैं। लेखक साझा OPRF (sOPRF) का उपयोग करके अनुकूलन पेश करते हैं ताकि खाली बिनों के लिए डमी मानों की आवश्यकता को समाप्त किया जा सके, जिससे प्रेषक की हैशिंग स्थितियों को छिपाना और कुछ कॉन्फ़िगरेशन में ग्लोबल परम्यूटेशन स्टेप्स की आवश्यकता को हटाना संभव होता है।
उच्च-आयामी ( $L_\infty$ और $L_p$ ): $O(2^d)$ की स्थानिक हैशिंग लागत से बचने के लिए, लेखक एक डिस्ट्रिब्यूटेड आईडी जनरेशन (dIDG) प्रोटोकल का उपयोग करते हैं। यह प्रोटोकल तत्वों के लिए अद्वितीय आईडी उत्पन्न करता है ताकि निकट तत्वों के बीच समान आईडी साझा हो सके। लेखक हालिया dIDG कंस्ट्रक्शन्स (विशेष रूप से [DZL25]) में कोलिजन लीकेज (collision leakage) से संबंधित सुरक्षा खामियों की पहचान करते हैं और sOPRF और ECSS का उपयोग करके एक सुरक्षित, सममित-कुंजी-आधारित dIDG प्रस्तावित करते हैं।

मुख्य योगदान

नए प्रिमिटिव्स: ECSS और ECIPS का परिचय, जो केवल सममित प्रिमिटिव्स का उपयोग करके $\delta$ पर सटीक लघुगणकीय निर्भरता के साथ कुशल फजी मैचिंग को सक्षम करते हैं।
इष्टतम जटिलता: सामान्य $L_p \in [1, \infty]$ दूरियों के लिए पहले FPSI प्रोटोकॉल जो $\delta$ में सख्ती से लघुगणकीय जटिलता $O(d \log \delta)$ प्राप्त करते हैं। यह सैद्धांतिक रूप से इष्टतम है, क्योंकि $O(\delta)$ लंबाई के अंतराल में मानों को अलग करने के लिए $\Omega(\log \delta)$ बिट्स की जानकारी की आवश्यकता होती है।
सुरक्षा और दक्षता: ये प्रोटोकॉल AHE पर निर्भरता को समाप्त करते हैं, और इसे OT और सममित-कुंजी ऑपरेशन्स से बदलते हैं। लेखक प्रिफिक्स-आधारित प्रोटोकॉल (जैसे [DZL25]) में मास्क पुन: उपयोग (mask reuse) और कोलिजन लीकेज से जुड़ी सुरक्षा कमजोरियों की पहचान करते हैं और उन्हें ठीक करते हैं।
स्केलेबल कंस्ट्रक्शन्स: कम-आयामी (स्थानिक हैशिंग का उपयोग करके) और उच्च-आयामी (dIDG का उपयोग करके) परिवेशों के लिए अलग-अलग निर्माण, जो दोनों इष्टतम एसिम्प्टोटिक जटिलता प्राप्त करते हैं।

प्रायोगिक परिणाम
लेखकों ने अपने प्रोटोकॉल को लागू किया और उनकी तुलना अत्याधुनिक कार्यों ([GQL+24], [DZL25], [BGMP25]) से की।

प्रदर्शन: नए प्रोटोकॉल पूर्ववर्ती कार्यों की तुलना में काफी बेहतर प्रदर्शन करते हैं। कम-आयामी परिवेश में, वे 43.7 गुना तेज़ रनटाइम और 31.3 गुना कम संचार (communication) ओवरहेड प्राप्त करते हैं।
स्केलेबिलिटी: जबकि पूर्ववर्ती कार्य जैसे [GQL+24] और [DZL25] उच्च-आयामी परिवेश में $2^{16}$ के सेट आकार पर मेमोरी ओवरफ्लो का सामना करते थे, प्रस्तावित प्रोटोकॉल समान कॉन्फ़िगरेशन के तहत सफलतापूर्वक निष्पादित हुए।
थ्रेशोल्ड निर्भरता: प्रयोग पुष्टि करते हैं कि रनटाइम और संचार लागत $\delta$ के साथ लघुगणकीय रूप से स्केल करती है, जो पिछले रैखिक-निर्भरता वाले प्रोटोकॉल में देखे गए रैखिक स्केलिंग के विपरीत है।

महत्व
यह शोध पत्र FPSI के लिए इष्टतम थ्रेशोल्ड स्केलिंग में एक सैद्धांतिक सफलता का दावा करता है, यह प्रदर्शित करते हुए कि महंगी पब्लिक-की क्रिप्टोग्राफी के बिना सामान्य $L_p$ दूरियों के लिए सटीक लघुगणकीय निर्भरता प्राप्त की जा सकती है। व्यावहारिक रूप से, यह फजी मैचिंग की आवश्यकता वाले डोमेन में, जैसे कि जीनोमिक सीक्वेंस मैचिंग, समान इमेज रिट्रीवल और समझौता किए गए क्रेडेंशियल डिटेक्शन में, दूरी थ्रेशोल्ड और डाइमेंशनलिटीिटी से जुड़ी दक्षता संबंधी बाधाओं को हटाकर स्केलेबल FPSI अनुप्रयोगों की व्यवहार्यता को बढ़ाता है।