💻 computer science

Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

यह शोध पत्र $L_p$ दूरी मेट्रिक्स के लिए अत्यधिक कुशल फजी प्राइवेट सेट इंटरसेक्शन प्रोटोकॉल प्रस्तावित करता है जो रैखिक जटिलता प्राप्त करने और रनिंग टाइम एवं संचार लागत दोनों में अत्याधुनिक निर्माणों से काफी बेहतर प्रदर्शन करने के लिए सीक्रेट-शेयर्ड ऑब्लिवियस प्रोग्रामेबल PRFs और एक प्रीफिक्स तकनीक का लाभ उठाते हैं।

मूल लेखक: Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, Yonggang Wen, Tianwei Zhang

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

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

CC BY 4.0

मूल लेखक: Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, Yonggang Wen, Tianwei Zhang

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

मुख्य विचार: "फजी" (Fuzzy) मैचमेकिंग की समस्या

कल्पना कीजिए कि आप और आपका दोस्त एक समान आधार (common ground) खोजने की कोशिश कर रहे हैं, लेकिन आप एक-दूसरे को अपनी सूचियाँ नहीं दिखा सकते।

परिदृश्य: आपके पास आपके पसंदीदा गानों की एक सूची है (सेट A)। आपके दोस्त के पास उनके पसंदीदा गानों की एक सूची है (सेट B)।
मानक समस्या (सटीक मिलान - Exact Match): आप जानना चाहते हैं कि कौन से गाने बिल्कुल एक जैसे हैं। यह आसान है। आप बस यह देखते हैं कि आपकी सूची में "गाना X" उनकी सूची में "गाना X" है या नहीं।
"फजी" (Fuzzy) समस्या: अब, कल्पना कीजिए कि आपकी सूचियाँ केवल गाने नहीं हैं, बल्कि फिंगरप्रिंट या चेहरे के स्कैन हैं।
- आज आपका फिंगरप्रिंट थोड़ा धुंधला हो सकता है।
- आपके दोस्त का फेस स्कैन अलग रोशनी में लिया गया हो सकता है।
- वे बिल्कुल एक जैसे नहीं हैं, लेकिन वे "काफी हद तक" एक ही व्यक्ति होने के लिए पर्याप्त हैं।
- लक्ष्य: आप इन "काफी हद तक" समान चीज़ों को खोजना चाहते हैं, बिना अपने वास्तविक फिंगरप्रिंट या चेहरे को एक-दूसरे को दिखाए।

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

लेखकों का समाधान: एक नया, हल्का टूलकिट (Lightweight Toolkit)

शोधकर्ताओं (यांग, हाओ, आदि) ने एक नया सिस्टम बनाया है जो तेज़, सस्ता और सुरक्षित है। उन्होंने भारी "गणितीय कवच" को चालाक, हल्के ट्रिक्स के एक सेट से बदल दिया है।

उन्होंने इसे कैसे किया, इसे तीन मुख्य विचारों में विभाजित किया गया है:

1. "सीक्रेट हैंडशेक" (so-OPPRF)

उपमा (Analogy): कल्पना कीजिए कि आप और आपका दोस्त यह जांचना चाहते हैं कि क्या आप दोनों को एक गुप्त पासवर्ड पता है, लेकिन आप पासवर्ड को ज़ोर से नहीं बोलना चाहते, और आप दूसरे व्यक्ति का पासवर्ड भी नहीं जानना चाहते।

पुराना तरीका: आप दोनों अपना पासवर्ड कागज के एक टुकड़े पर लिखते, उसे एक भारी स्टील की तिजोरी (महंगा एन्क्रिप्शन) में बंद करते और जांच के लिए तीसरे पक्ष को भेज देते। इसमें बहुत समय लगता है।
नया तरीका (so-OPPRF): आप और आपका दोस्त एक विशेष "जादुई नोटबुक" का उपयोग करते हैं।
- आप नोटबुक में अपने "संभावित मिलान" (potential matches) लिखते हैं।
- आपका दोस्त पूछता है, "क्या 'X' आपकी नोटबुक में है?"
- नोटबुक आप दोनों को एक विभाजित रहस्य (split secret) देती है। आपको आधा उत्तर मिलता है, और उन्हें दूसरा आधा हिस्सा मिलता है।
- जादू: आप दोनों में से कोई भी अकेले पूरा उत्तर नहीं जान पाता। आपको उत्तर तभी पता चलता है जब आप अपने हिस्सों को मिलाते हैं। यदि उत्तर है "हाँ, वे मेल खाते हैं," तो आप दोनों को एक विशिष्ट संकेत मिलता है। यदि "नहीं," तो आपको केवल रैंडम शोर (noise) मिलता है।
- यह क्यों महान है: यह जटिल एन्क्रिप्शन के बजाय सरल गणित (जैसे संख्याओं को जोड़ना) का उपयोग करता है, जिससे यह अविश्वसनीय रूप से तेज़ हो जाता है।

2. "दो-चरणीय फ़िल्टर" (Coarse then Fine)

उपमा: कल्पना कीजिए कि आप एक बड़े शहर में खोए हुए कुत्ते को ढूंढ रहे हैं। आप एक-एक करके हर घर की जाँच नहीं करते; अन्यथा इसमें सालों लग जाएंगे।

चरण 1: मोहल्ले की जाँच (Coarse Mapping):
- आप शहर को मोहल्लों में विभाजित करते हैं। यदि कुत्ता "मोहल्ला A" में है, तो आप केवल मोहल्ला A के घरों की जाँच करते हैं।
- शोध पत्र में, वे हर फिंगरप्रिंट को एक "मोहल्ला आईडी" (Neighborhood ID) में बदल देते हैं। यदि दो फिंगरप्रिंट करीब हैं, तो उन्हें एक ही आईडी मिलती है।
- जोखिम: कभी-कभी, दो अलग-अलग कुत्ते एक ही मोहल्ले में रह सकते हैं (False Positive)।
चरण 2: दहलीज की जाँच (Refined Filtering):
- अब, आप केवल उस मोहल्ले के विशिष्ट घरों की जाँच करते हैं। आप बारीकी से देखते हैं कि क्या कुत्ता वास्तव में वही है जिसे आप ढूंढ रहे हैं।
- शोध पत्र में, वे इस अंतिम जाँच को करने के लिए "सीक्रेट हैंडशेक" (चरण 1 से) का उपयोग करते हैं। यदि फिंगरप्रिंट वास्तव में करीब हैं, तो हैंडशेक पुष्टि करता है। यदि वे केवल "मोहल्ले के पड़ोसी" हैं लेकिन मिलान नहीं हैं, तो हैंडशेक विफल हो जाता है।

3. "ज़िप कोड" ट्रिक (Prefix Optimization)

उपमा: कल्पना कीजिए कि आप 100 और 200 के बीच के स्ट्रीट नंबर वाले घर की तलाश कर रहे हैं।

पुराना तरीका: आप हर नंबर की जाँच करते हैं: 100, 101, 102... पूरे 200 तक। यह 100 जाँचें हैं!
नया तरीका (Prefix): आप महसूस करते हैं कि आपको हर नंबर की जाँच करने की आवश्यकता नहीं है। आपको केवल "प्रीफिक्स" (पहले कुछ अंक) की जाँच करनी है।
- 100 नंबरों की जाँच करने के बजाय, आप कुछ "ब्लॉक" की जाँच करते हैं (जैसे "10x", "11x", "12x")।
- यह एक कार्य को जो 100 चरणों में लेता है, उसे केवल 7 या 8 चरणों के कार्य में बदल देता है।
- यह क्यों मायने रखता है: जब "दूरी" (distance) की अनुमति बड़ी होती है (जैसे, एक बहुत ही धुंधला फिंगरप्रिंट), तो यह ट्रिक सिस्टम को घातीय रूप से (exponentially) तेज़ बना देती है।

परिणाम: हमें इसकी परवाह क्यों करनी चाहिए?

शोधकर्ताओं ने अपने नए सिस्टम का वर्तमान "सर्वश्रेष्ठ" तरीकों (जो एक रेस कार को चलाने के लिए स्टीम इंजन का उपयोग करने जैसे हैं) के विरुद्ध परीक्षण किया।

गति (Speed): उनका सिस्टम 12 से 145 गुना तेज़ है।
- उपमा: यदि पुराने सिस्टम को मिलान खोजने में 10 मिनट लगते, तो नया सिस्टम इसे 4 सेकंड में कर देता।
डेटा उपयोग (Data Usage): उनका सिस्टम इंटरनेट पर भेजने के लिए 3 से 8 गुना कम डेटा का उपयोग करता है।
- उपमा: ईंटों का एक ट्रक भेजने के बजाय, वे एक लिफाफा भेजते हैं।
स्केलेबिलिटी (Scalability): यह तब भी बहुत अच्छा काम करता है जब आपके पास लाखों आइटम हों या बहुत उच्च-आयामी डेटा (जैसे जटिल 3D फेस स्कैन) हो।

एक वाक्य में सारांश

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

यह आपके लिए क्यों महत्वपूर्ण है

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

यहाँ शोध पत्र "Efficient Fuzzy Private Set Intersection from Secret-shared OPRF" का विस्तृत तकनीकी सारांश दिया गया है।

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

प्राइवेट सेट इंटरसेक्शन (PSI) दो पक्षों (एक प्रेषक (Sender) जिसके पास सेट $Q$ है और एक प्राप्तकर्ता (Receiver) जिसके पास सेट $W$ है) को बिना गैर-प्रतिच्छेदन (non-intersecting) तत्वों को प्रकट किए $Q \cap W$ की गणना करने की अनुमति देता है। फजी PSI (FPSI) इसे उन परिदृश्यों तक विस्तारित करता है जहाँ सटीक मिलान अपर्याप्त है (जैसे, बायोमेट्रिक प्रमाणीकरण), जिससे प्राप्तकर्ता को उन तत्वों $q \in Q$ को जानने की अनुमति मिलती है यदि कोई $w \in W$ मौजूद हो कि $dist(q, w) \le \delta$ हो, जो कि एक दूरी मीट्रिक (आमतौर पर $L_p$ जहाँ $p \in [1, \infty]$ ) के अंतर्गत हो।

वर्तमान सीमाएँ:

उच्च जटिलता (High Complexity): सामान्य $L_p$ दूरियों के लिए मौजूदा FPSI प्रोटोकॉल अक्सर तत्व आयाम (element dimension) $d$ में घातांकीय (exponential) जटिलता या दूरी थ्रेशोल्ड $\delta$ में सुपर-लीनियर जटिलता से ग्रस्त होते हैं।
अक्षमता (Inefficiency): अत्याधुनिक लीनियर-कॉम्प्लेक्सिटी प्रोटोकॉल (जैसे, Gao et al. [14], Dang et al. [16]) भारी रूप से एडिटिवली होमोमोर्फिक एन्क्रिप्शन (AHE) (जैसे, ElGamal, Paillier) पर निर्भर करते हैं। ये पब्लिक-की ऑपरेशन्स गणनात्मक रूप से महंगे होते हैं, जिससे सिमेट्रिक-की दृष्टिकोणों की तुलना में प्रदर्शन खराब होता है।
स्केलेबिलिटी (Scalability): उच्च-आयामी डेटा और बड़े दूरी थ्रेशोल्ड ( $\delta$ ) मौजूदा समाधानों को अत्यधिक धीमा और संचार-गहन (communication-heavy) बना देते हैं।

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

लेखक FPSI के लिए एक नया ढांचा प्रस्तावित करते हैं जो सेट आकारों ( $m, n$ ), आयाम ( $d$ ), और थ्रेशोल्ड ( $\delta$ ) में लीनियर कॉम्प्लेक्सिटी प्राप्त करता है, जो मुख्य रूप से हल्के सिमेट्रिक-की ऑपरेशन्स का उपयोग करता है। मुख्य कार्यप्रणाली में तीन मुख्य घटक शामिल हैं:

A. नया बिल्डिंग ब्लॉक: शेयर्ड-आउटटपुट OPPRF (so-OPPRF)

यह शोध पत्र ओब्लीवियस प्रोग्रामेबल साइफर्ड-आउटपुट ओपीआरएफएफ (so-OPPRF) को पेश करता है।

कार्यक्षमता: मानक OPPRF के विपरीत जहाँ प्राप्तकर्ता आउटपुट सीखता है, so-OPPRF का आउटपुट दोनों पक्षों को PRF मान के सीक्रेट शेयर्स (secret shares) प्रदान करता है। कोई भी पक्ष व्यक्तिगत रूप से पूर्ण मान नहीं जान पाता है।
निर्माण: यह एक ओब्लीवियस की-वैल्यू स्टोर (OKVS) को शेयर्ड-आउटपुट OPRF (so-OPRF) के साथ जोड़ता है।
- प्रेषक OKVS एनकोडिंग का उपयोग करके विशिष्ट बिंदुओं पर PRF को प्रोग्राम करता है।
- प्राप्तकर्ता इनपुट क्वेरी करता है और परिणाम के सीक्रेट शेयर्स प्राप्त करता है।
- यह आंशिक मिलान जानकारी के रिसाव को रोकता है जो मानक OPPRF में होता है, जिसे पहले मास्क करने के लिए महंगे AHE की आवश्यकता होती थी।

B. मॉड्यूलर फजी मैपिंग (Modular Fuzzy Mapping)

लेखक "कोर्स मैपिंग" चरण (तत्वों को $\delta$ दूरी के भीतर अंतराल के आधार पर पहचानकर्ता सौंपना) के लिए एक मॉड्यूलर प्रोटोकॉल डिजाइन करते हैं:

लोकल मैपिंग: दोनों पक्ष $2\delta$ आकार के अंतरालों के आधार पर स्थानीय पहचानकर्ता उत्पन्न करते हैं। अंतराल ओवरलैप के बारे में सूचना रिसाव को रोकने के लिए, वे इन अंतरालों से जुड़े यादृच्छिक (random) मानों के सीक्रेट शेयर्स प्राप्त करने के लिए so-OPPRF का उपयोग करते हैं।
ग्लोबल मैपिंग: स्थानीय मैपिंग को बिना मूल मान प्रकट किए ग्लोबल ID में संयोजित करने के लिए, वे सीक्रेट-शेयर्ड इनपुट OPRF (si-OPRF) का परिचय देते हैं। दोनों पक्ष की (key) और इनपुट के सीक्रेट शेयर्स रखते हैं। प्राप्तकर्ता अंतिम ID सीखता है, जबकि प्रेषक अपने स्वयं के IDs सीखता है, यह सुनिश्चित करते हुए कि $\delta$ दूरी के भीतर के तत्वों को समान ID प्राप्त हो, बिना मध्यवर्ती मानों को लीक किए।

C. रिफाइंड फिल्टरिंग (Refined Filtering)

कोर्स मैपिंग के बाद, फॉल्स पॉजिटिव्स (वे तत्व जिनका ID समान है लेकिन दूरी $> \delta$ है) को हटाया जाना चाहिए।

पक्ष दूरी (या $L_\infty$ के लिए 0) के सीक्रेट शेयर्स की गणना करने के लिए फिर से so-OPPRF का उपयोग करते हैं।
वे यह सत्यापित करने के लिए कि क्या साझा की गई दूरी थ्रेशोल्ड के भीतर है, एक प्राइवेट इक्वैलिटी टेस्ट (PEQT) या प्राइवेट इंटरवल टेस्ट का उपयोग करते हैं।
अंत में, एक ओब्लीवियस ट्रांसफर (OT) प्रोटोकॉल प्राप्तकर्ता को मिलान करने वाले प्रेषक तत्वों को प्राप्त करने की अनुमति देता है।

D. प्रीफिक्स ऑप्टिमाइजेशन (Prefix Optimization)

बड़े दूरी थ्रेशोल्ड ( $\delta$ ) के लिए, प्रीफिक्स रिप्रेजेंटेशन का उपयोग करके $\delta$ पर लीनियर डिपेंडेंस को लॉगारिदमिक ( $O(\log \delta)$ ) में अनुकूलित किया जाता है।

पूरे अंतराल $[q-\delta, q+\delta]$ (आकार $2\delta+1$ ) को प्रोग्राम करने के बजाय, प्रेषक केवल $O(\log \delta)$ प्रीफिक्स प्रोग्राम करता है जो उस अंतराल को कवर करते हैं।
यह भारी पब्लिक-की ऑपरेशन्स के बिना संचार और गणना लागत को काफी कम कर देता है।

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

so-OPPRF: एक नवीन क्रिप्टोग्राफिक प्रिमिटिव जो सीक्रेट-शेयर्ड आउटपुट के साथ प्रोग्रामेबल PRFs के ओब्लीवियस मूल्यांकन को सक्षम बनाता है, जो कुशल फजी मैचिंग के लिए एक आधारभूत ब्लॉक के रूप में कार्य करता है।
कुशल FPSI प्रोटोकॉल: सामान्य $L_p$ ( $p \in [1, \infty]$ ) दूरियों के लिए पहले FPSI प्रोटोकॉल जो AHE के बजाय सिमेट्रिक-की प्रिमिटिव्स (PRF, OT, OKVS) का उपयोग करके $m, n, d,$ और $\delta$ में लीनियर कॉम्प्लेक्सिटी प्राप्त करते हैं।
प्रीफिक्स ऑप्टिमाइजेशन: बड़े $\delta$ के लिए दक्षता बनाए रखते हुए, भारी पब्लिक-की ऑपरेशन्स के बिना $O(\delta)$ को $O(\log \delta)$ में बदलने के लिए प्रीफिक्स तकनीकों का अनुकूलन।
मॉड्यूलर डिज़ाइन: फजी मैपिंग और फिल्टरिंग चरणों का स्पष्ट पृथक्करण, जो प्रोटोकॉल विश्लेषण और कार्यान्वयन को सरल बनाता है।

4. प्रयोगात्मक परिणाम (Experimental Results)

लेखकों ने C++ में अपने प्रोटोकॉल को लागू किया और अत्याधुनिक कार्यों: Gao et al. (ASIACRYPT'24) और Dang et al. (CCS'25) के विरुद्ध तुलना की।

प्रदर्शन लाभ (Performance Gains):
- रनिंग टाइम: Gao et al. की तुलना में 12 $\times$ से 145 $\times$ और Dang et al. की तुलना में 9 $\times$ से 80 $\times$ की गति वृद्धि प्राप्त की।
- संचार (Communication): Gao की तुलना में 3 $\times$ से 8 $\times$ और Dang की तुलना में 5 $\times$ से 19 $\times$ कम संचार लागत।
स्केलेबिलिटी: बड़े सेट आकार और आयामों के साथ प्रदर्शन का अंतर बढ़ता जाता है। उदाहरण के लिए, $m=n=2^{16}, d=8,$ और $\delta=32$ के साथ, प्रस्तावित प्रोटोकॉल Gao et al. की तुलना में 145 $\times$ तेज़ है।
प्रीफिक्स ऑप्टिमाइजेशन: बड़े $\delta$ (जैसे, $\delta=1024$ ) के लिए, प्रीफिक्स-ऑप्टिमाइज़्ड संस्करण ने गैर-प्रीफिक्स संस्करण की तुलना में संचार को 11 $\times$ कम किया और रनिंग टाइम को ~50% कम किया, जबकि प्रतिस्पर्धियों से बेहतर प्रदर्शन बनाए रखा।

5. महत्व (Significance)

व्यावहारिक व्यवहार्यता (Practical Viability): महंगे होमोमोर्फिक एन्क्रिप्शन को सिमेट्रिक-की ऑपरेशन्स से बदलकर, यह कार्य FPSI को बायोमेट्रिक प्रमाणीकरण (फिंगरप्रिंट/चेहरा पहचान) और जीनोम मिलान जैसे वास्तविक दुनिया के अनुप्रयोगों के लिए व्यावहारिक बनाता है, जहाँ उच्च-आयामी डेटा और शोर सहिष्णुता (noise tolerance) महत्वपूर्ण है।
सैद्धांतिक प्रगति: यह इस खुले प्रश्न को हल करता है कि क्या AHE के बिना लीनियर कॉम्प्लेक्सिटी के साथ ठोस रूप से कुशल FPSI संभव है, जो फजी मैचिंग परिदृश्यों में सुरक्षित मल्टी-पार्टी कंप्यूटेशन के लिए एक नया प्रतिमान प्रदान करता है।
भविष्य का प्रभाव: पेश किए गए so-OPPRF और si-OPRF प्रिमिटिव्स अन्य गोपनीयता-संरक्षण प्रोटोकॉल के लिए उपयोगी बिल्डिंग ब्लॉक्स होने की संभावना है जिनमें सीक्रेट-शेयर्ड मूल्यांकन की आवश्यकता होती है।

सीमाएं और भविष्य का कार्य:
वर्तमान प्रोटोकॉल डिस्जॉइंट प्रोजेक्शन धारणा (disjoint projection assumption) (तत्व कम से कम एक आयाम में पर्याप्त दूर हैं) पर निर्भर करता है। भविष्य के कार्य का लक्ष्य इन धारणाओं को शिथिल करना और बिना किसी महत्वपूर्ण दक्षता हानि के मैलिसियस सुरक्षा (malicious security) प्राप्त करना है।