🔢 mathematics

Cross-Silo De-Anonymization Under Local Differential Privacy: Threat Model, Phase Transition, and Coordination Necessity

यह शोध पत्र एक क्रॉस-साइलो व्यक्ति-स्तरीय डिफरेंशियल प्राइवेसी फ्रेमवर्क स्थापित करता है ताकि यह प्रदर्शित किया जा सके कि डी-एनोनिमाइजेशन (de-anonymization) $k^* = \Theta(\log n / \epsilon^2)$ के एक थ्रेशोल्ड पर एक तीव्र फेज ट्रांजिशन (phase transition) से गुजरता है, जो यह सिद्ध करता है कि भले ही व्यक्तिगत साइलो निजी हों, अनकोऑर्डिनेटेड स्थानीय DP आउटपुट का एकत्रीकरण इस बिंदु के आगे अनिवार्य रूप से गुमनामी से समझौता करता है।

मूल लेखक: Ziniu Liu, Aiping Li

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

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

CC BY 4.0

मूल लेखक: Ziniu Liu, Aiping Li

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

मुख्य चित्र: गोपनीयता का "फुसफुसाहट वाला खेल" (The Whispering Game)

कल्पना कीजिए कि "फुसफुसाहट वाले खेल" (या Telephone) का एक खेल चल रहा है, लेकिन इसमें गोपनीयता से जुड़ा एक ट्विस्ट है।

आपके पास किसी विशिष्ट व्यक्ति (मान लीजिए एलिस) के बारे में एक रहस्य है। यह रहस्य k अलग-अलग अस्पतालों (या डेटा साइलो) में छिपा हुआ है। प्रत्येक अस्पताल का एक सख्त नियम है: उन्हें रोगी की गोपनीयता की रक्षा करनी है। इसे करने के लिए, वे डेटा साझा करने से पहले उसमें थोड़ा सा "शोर" (noise) या स्टैटिक जोड़ देते हैं। इसे लोकल डिफरेंशियल प्रिवेसी (Local Differential Privacy) कहा जाता है।

अपने आप में, अस्पताल A पर शोर इतना पर्याप्त है कि वह एलिस की पहचान छुपा सके। अस्पताल B पर शोर भी उसकी पहचान छिपाने के लिए पर्याप्त है। वास्तव में, हर एक अस्पताल पर शोर इस तरह से डिज़ाइन किया गया है कि यदि आप केवल उस एक अस्पताल के डेटा को देखें, तो आप यह नहीं बता सकते कि एलिस कौन है।

पेपर की खोज:
लेखकों ने एक डरावना सवाल पूछा है: क्या होगा यदि एक जिज्ञासु हैकर सभी k अस्पतालों से उनका शोर वाला (noisy) डेटा मांग ले और उन टुकड़ों को एक साथ जोड़ दे?

उन्होंने पाया कि यहाँ एक टिपिंग पॉइंट (एक निर्णायक मोड़ या चरण परिवर्तन) है।

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

यह पेपर सिद्ध करता है कि यह केवल एक अनुमान नहीं है; यह एक गणितीय निश्चितता है जो इस बात पर आधारित है कि कितने अस्पताल शामिल हैं और वे कितना शोर जोड़ते हैं।

उपमाओं के साथ समझाए गए मुख्य विचार

1. "क्रॉस-साइलो" खतरा (पहेली के टुकड़े)

आमतौर पर, गोपनीयता विशेषज्ञ एक समय में एक ही अस्पताल को देखते हैं। वे कहते हैं, "यह अस्पताल सुरक्षित है।"
लेकिन यह पेपर पूरे नेटवर्क को देखता है।

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

2. "फेज ट्रांजिशन" (लाइट स्विच)

लेखक डी-एनोनिमाइजेशन (पहचान उजागर करने की प्रक्रिया) को एक धीमी गिरावट के रूप में नहीं, बल्कि एक लाइट स्विच के रूप में वर्णित करते हैं।

"ऑफ" अवस्था: जब तक अस्पतालों की संख्या ( $k$ ) एक निश्चित संख्या ( $k^*$ ) से नीचे है, हैकर अंधा है। एलिस का सही अनुमान लगाने की संभावना एक सिक्का उछालने (coin flip) से बेहतर नहीं है।
"ऑन" अवस्था: जैसे ही अस्पतालों की संख्या उस सीमा को पार करती है, सही अनुमान लगाने की संभावना अचानक बढ़कर लगभग 100% हो जाती है।
सूत्र (Formula): यह स्विच इस सूत्र द्वारा दिया गया है: $k^* \approx \frac{\log(\text{Population Size})}{\text{Noise Level}^2}$ $k^{*} \approx \frac{l o g ( Population Size )}{Noise Level ^{2}}$ ।
- यदि जनसंख्या बहुत बड़ी है, तो कोड तोड़ने के लिए आपको अधिक अस्पतालों की आवश्यकता होगी।
- यदि शोर बहुत अधिक है (उच्च गोपनीयता), तो कोड तोड़ने के लिए आपको बहुत अधिक अस्पतालों की आवश्यकता होगी।

3. "सिनर्जी" का आश्चर्य (XOR ट्रिक)

इस पेपर का सबसे दिलचस्प हिस्सा XOR कंस्ट्रक्शन है।

परिदृश्य: कल्पना कीजिए कि दो अस्पताल हैं।
- अस्पताल 1 कहता है: "मेरे पास एक रैंडम कॉइन फ्लिप है।" (यह आपको एलिस के बारे में कुछ नहीं बताता)।
- अस्पताल 2 कहता है: "मेरे पास एक रैंडम कॉइन फ्लिप है।" (यह भी आपको कुछ नहीं बताता)।
जादू: यदि आप दोनों उत्तरों को लेते हैं और उन्हें एक विशिष्ट गणितीय ट्रिक (XOR) का उपयोग करके मिलाते हैं, तो रैंडमनेस (यादृच्छिकता) गायब हो जाती है, और एलिस का रहस्य पूरी तरह से प्रकट हो जाता है।
सबक: यह सिद्ध करता है कि गोपनीयता में 1 + 1 = 3 हो सकता है। दो "बेकार" डेटा टुकड़े मिलकर एक "उपयोगी" (और खतरनाक) जानकारी बना सकते हैं। इसे इन्फॉर्मेशन सिनर्जी (Information Synergy) कहा जाता है।

4. "कोऑर्डिनेशन" की आवश्यकता (टीमवर्क की समस्या)

पेपर संरक्षकों (defenders) के लिए एक कठोर वास्तविकता की चेतावनी के साथ समाप्त होता है।

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

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

मानक गोपनीयता नियम भ्रामक हैं: सिर्फ इसलिए कि कोई सिस्टम कहता है "हम सुरक्षित हैं क्योंकि हम शोर जोड़ते हैं," इसका मतलब यह नहीं है कि आप सुरक्षित हैं यदि कोई आपसे 50 अलग-अलग जगहों से पूछताछ करता है।
टिपिंग पॉइंट मौजूद है: एक विशिष्ट संख्या ( $k^*$ ) है जहाँ सुरक्षा तुरंत गायब हो जाती है।
छोटा डेटा जुड़कर बड़ा हो जाता है: भले ही प्रत्येक अस्पताल लगभग शून्य जानकारी लीक करता हो, कई अस्पतालों का योग सब कुछ लीक कर सकता है।
तालमेल (Coordination) अनिवार्य है: इसे रोकने के लिए, डेटा धारकों को समन्वय करना चाहिए। उन्हें अपने स्वयं के दीवारों के भीतर नहीं, बल्कि पूरे नेटवर्क में कुल प्रश्नों (queries) को ट्रैक करने की आवश्यकता है।

यह पेपर क्या नहीं कहता

यह यह नहीं कहता कि गोपनीयता असंभव है। यह कहता है कि असमन्वित गोपनीयता नाजुक है।
यह अभी तक इसे ठीक करने के लिए कोई विशिष्ट सॉफ़्टवेयर टूल प्रदान नहीं करता है; यह इस बात का गणितीय ब्लूप्रिंट प्रदान करता है कि हमें इसे ठीक करने की आवश्यकता क्यों है।
यह इस बात पर केंद्रित है कि गोपनीयता को तोड़ने के लिए कितने प्रश्नों की आवश्यकता है, न कि विशिष्ट चिकित्सा या नैदानिक परिणामों पर।

संक्षेप में: गोपनीयता एक टीम गेम है। यदि आप अकेले खेलते हैं, तो आप हार जाते हैं। यदि आप समन्वय करते हैं, तो आप जीत सकते हैं।

तकनीकी सारांश: लोकल डिफरेंशियल प्राइवेसी के तहत क्रॉस-साइलो डी-एनोनिमाइजेशन (Cross-Silo De-Anonymization)

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

यह शोध पत्र फेडरेटेड सिस्टम और मल्टी-साइलो डेटा परिवेश में प्राइवेसी विश्लेषण के एक महत्वपूर्ण अंतराल को संबोधित करता है। जबकि मानक डिफरेंशियल प्राइवेसी (DP) कंपोजिशन थ्योरम्स यह गारंटी देते हैं कि $k$ स्वतंत्र $(\varepsilon, \delta)$ -DP मैकेनिज्म मिलकर एक संयुक्त $(k\varepsilon, k\delta)$ -DP गारंटी प्रदान करते हैं, यह 'वर्स्ट-केस' बाउंड इस ठोस प्रतिकूल प्रश्न का उत्तर देने में विफल रहता है: $k$ (साइलो की संख्या) का वह मान क्या है जिस पर एक हमलावर वास्तव में $n$ आकार की जनसंख्या में एक विशिष्ट लक्ष्य व्यक्ति की पहचान करने की क्षमता प्राप्त कर लेता है?

लेखक तर्क देते हैं कि लीनियर कंपोजिशन बाउंड्स उस थ्रेशोल्ड (सीमा) को सटीक रूप से नहीं बताते जहाँ डी-एनोनिमाइजेशन असंभव से संभव में परिवर्तित हो जाता है। वे इस बात की जांच करते हैं कि जब किसी व्यक्ति के रिकॉर्ड $k$ स्वतंत्र डेटा साइलो में मौजूद होते हैं, तो लोकल डिफरेंशियल प्राइवेसी (LDP) द्वारा संरक्षित होने के बावजूद, सूचना-सैद्धांतिक (information-theoretic) सीमाओं के तहत लक्ष्य की पहचान करने की क्या स्थिति होती है।

2. कार्यप्रणाली और ढांचा (Methodology and Framework)

2.1 क्रॉस-साइलो पर्सन-लेवल DP (XSP-DP)

इस खतरे को औपचारिक रूप देने के लिए, शोध पत्र XSP-DP नामक एक Pufferfish-शैली का प्राइवेसी नोटेशन पेश करता है।

एडजसेंसी रिलेशन (Adjacency Relation): दो डेटासेट टुपल्स $D, D'$ को पर्सन-लेवल क्रॉस-साइलो एडजसेंट ( $D \sim_{ps} D'$ ) के रूप में परिभाषित किया गया है यदि एक ही व्यक्ति $p$ के रिकॉर्ड $D$ के सभी $k$ साइलो में मौजूद हैं और $D'$ के सभी $k$ साइलो में अनुपस्थित हैं (या इसके विपरीत)। अन्य सभी रिकॉर्ड समान रहते हैं।
परिभाषा: एक संयुक्त मैकेनिज्म $(\varepsilon, \delta)$ -XSP-DP है यदि वह सभी ऐसे एडजसेंट पेयर्स के लिए मानक DP असमानता को संतुष्ट करता है।
कंपोजिशन: लेखक सिद्ध करते हैं (थ्योरम 4.1) कि यदि प्रत्येक साइलो $i$ पर्सन-लेवल ग्रैनुलैरिटी पर $(\varepsilon_i, \delta_i)$ -DP को संतुष्ट करता है, तो संयुक्त मैकेनिज्म $(\sum \varepsilon_i, \sum \delta_i)$ -XSP-DP को संतुष्ट करता है। यह पुष्टि करता है कि इस विशिष्ट एडजसेंसी मॉडल के भीतर मानक बेसिक कंपोजिशन लागू होता है।

2.2 सूचना-सैद्धांतिक विश्लेषण (Information-Theoretic Analysis)

मुख्य विश्लेषण संचित म्यूचुअल इंफॉर्मेशन (mutual information) को हमलावर की पहचान करने की प्रायिकता ( $P_e$ ) से जोड़ने पर आधारित है।

मान्यताएं: विश्लेषण स्वतंत्र, नॉन-इंटरैक्टिव मैकेनिज्म, लक्ष्य की पहचान के सापेक्ष साइलो आउटपुट्स की कंडीशनल इंडिपेंडेंस, और जनसंख्या पर यूनिफॉर्म प्रायर ( $Z \sim \text{Uniform}([n])$ ) को मानता है।
फेज ट्रांजिशन (Phase Transition): शोध पत्र इस बात की जांच करता है कि क्या $k$ बढ़ने के साथ $P_e$ में एक तीव्र फेज ट्रांजिशन होता है।
सिनर्जी विश्लेषण: पार्शियल इंफॉर्मेशन डिकम्पोजिशन (PID) का उपयोग करते हुए, लेखक "सिनर्जी" का विश्लेषण करते हैं, जहाँ संयुक्त अवलोकन व्यक्तिगत योगदानों के योग से अधिक जानकारी प्रकट करता है। वे एक स्पष्ट XOR + रैंडमाइज्ड रिस्पांस (RR) उदाहरण का निर्माण करते हैं जहाँ व्यक्तिगत साइलो शून्य जानकारी प्रकट करते हैं ( $I(Z; Y_i) = 0$ ), फिर भी संयुक्त आउटपुट सकारात्मक म्यूचुअल इंफॉर्मेशन के साथ लक्ष्य को प्रकट कर देता है।

2.3 बाउंड्स और थ्रेशोल्ड (Bounds and Thresholds)

लेखक एरर प्रोबेबिलिटी पर मिलान करने वाले लोअर और अपर बाउंड्स निकालते हैं:

लोअर बाउंड (Fano): फानो की असमानता (Fano's inequality) का उपयोग करते हुए, वे सिद्ध करते हैं कि $k \ll k^*$ के लिए, कोई भी एस्टीमेटर गैर-नगण्य प्रायिकता के साथ विफल रहता है।
अपर बाउंड (Maximum Likelihood): वे एक मैक्सिमम लाइकलीहुड (ML) अटैक का निर्माण करते हैं और दिखाते हैं कि $k \gg k^*$ के लिए, हमलावर उच्च प्रायिकता के साथ सफल होता है।
थ्रेशोल्ड: क्रिटिकल थ्रेशोल्ड को $k^* = \Theta(\log n / I_1)$ के रूप में पहचाना गया है, जहाँ $I_1$ सिंगल-साइलो म्यूचुअल इंफॉर्मेशन है। बाइनरी रैंडमाइज्ड रिस्पॉन्स पैरामीटर $\varepsilon$ के लिए, यह $k^* = \Theta(\log n / \varepsilon^2)$ के रूप में स्केल करता है।

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

XSP-DP परिभाषा: एक क्रॉस-साइलो एडजसेंसी रिलेशन का औपचारिकीकरण जो व्यक्ति की उपस्थिति/अनुपस्थिति को सभी साइलो में एक संरक्षित इकाई के रूप में मानता है, और सत्यापित करता है कि मानक कंपोजिशन बाउंड्स इस मॉडल पर लागू होते हैं।
फेज ट्रांजिशन थ्योरम: इस बात का प्रमाण कि डी-एनोनिमाइजेशन एरर प्रोबेबिलिटी $k^* = \Theta(\log n / I_1)$ पर एक तीव्र फेज ट्रांजिशन से गुजरती है। इस थ्रेशोल्ड से नीचे, पहचान सूचना-सैद्धांतिक रूप से असंभव है; इसके ऊपर, यह संभव है।
सूचना सिनर्जी प्रदर्शन: एक XOR + RR मैकेनिज्म का निर्माण जो दिखाता है कि व्यक्तिगत साइलो पूरी तरह से प्राइवेट ( $I=0$ ) हो सकते हैं जबकि संयुक्त आउटपुट जानकारी लीक करता है ( $I>0$ ), जो यह सिद्ध करता है कि सिनर्जी के नजरिए से देखे जाने पर प्राइवेसी सूचना रिसाव के मामले में "अनुकूल" रूप से कंपोज़ नहीं होती है।
गैर-समन्वित रक्षा की असंभवता (Impossibility of Non-Coordinated Defense): एक प्रमाण (थ्योरम 7.3) कि बाइनरी रैंडमाइज्ड-रिस्पॉन्स मैकेनिज्म के लिए, कोई भी गैर-समन्वित, स्वतंत्र DP मैकेनिज्म तब तक डी-एनोनिमाइजेशन को नहीं रोक सकता जब तक कि $k$ थ्रेशोल्ड से अधिक न हो जाए। यह स्थापित करता है कि क्रॉस-साइलो समन्वय (coordination) इस बिंदु के आगे गोपनीयता बनाए रखने के लिए आवश्यक है।

4. परिणाम (Results)

थ्रेशोल्ड स्केलिंग: सफल डी-एनोनिमाइजेशन के लिए आवश्यक क्रिटिकल साइलो की संख्या $k^* \propto \frac{\log n}{\varepsilon^2}$ के रूप में स्केल करती है।
अनुभवजन्य सत्यापन (Empirical Validation): सिंथेटिक प्रयोग सैद्धांतिक भविष्यवाणियों की पुष्टि करते हैं। जैसे ही $k$ नॉर्मलाइज्ड थ्रेशोल्ड $k/k^*$ को पार करता है, एरर प्रोबेबिलिटी $P_e$ लगभग 1 से गिरकर लगभग 0 हो जाती है। अनुभवजन्य क्रॉसिंग पॉइंट लगभग $1.5 k^*$ पर होता है, जो ML अपर बाउंड से प्राप्त कांस्टेंट फैक्टर्स के अनुरूप है।
स्केलिंग लॉज़: प्रयोग सत्यापित करते हैं कि $k^*$ रैखिक रूप से $\log n$ के साथ और $\varepsilon^2$ के व्युत्क्रमानुपाती (inversely) रूप से स्केल करता है।
गौसियन मैकेनिज्म विस्तार (Gaussian Mechanism Extension): शोध पत्र विश्लेषणात्मक रूप से गौसियन मैकेनिज्म (जो DP-SGD में उपयोग किए जाते हैं) के परिणामों का विस्तार करता है, यह दिखाते हुए कि हालांकि कांस्टेंट फैक्टर बदल जाता है (जिससे गौसियन मैकेनिज्म $\delta$ पर निर्भर कारक के आधार पर अधिक मजबूत बनते हैं), गुणात्मक $\Theta(\log n / \varepsilon^2)$ फेज ट्रांजिशन संरचना बनी रहती है।

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

शोध पत्र दावा करता है कि यह लोकल डिफरेंशियल प्राइवेसी के तहत क्रॉस-साइलो इन्फरेंस हमलों के लिए बेसलाइन थ्रेट मॉडल और $\Theta$ -लेवल थ्रेशोल्ड प्रदान करता है।

कंपोजिशन की सीमाएं: यह रेखांकित करता है कि वास्तविक दुनिया के डी-एनोनिमाइजेशन जोखिमों का आकलन करने के लिए मानक कंपोजिशन बाउंड्स अपर्याप्त हैं, क्योंकि वे सूचना-सैद्धांतिक फेज ट्रांजिशन को कैप्चर नहीं करते हैं।
समन्वय की आवश्यकता: एक प्राथमिक निष्कर्ष यह है कि गैर-समन्वित सेटिंग्स में (जहाँ साइलो बिना स्टेट साझा किए स्वतंत्र रूप से काम करते हैं), गोपनीयता अनिवार्य रूप से खो जाती है जब क्वेरी किए गए साइलो की संख्या प्राप्त थ्रेशोल्ड से अधिक हो जाती है। इसका तात्पर्य यह है कि फेडरेटेड सिस्टम में दीर्घकालिक गोपनीयता के लिए कोऑर्डिनेशन मैकेनिज्म (जैसे क्वेरी काउंट पर वितरित सर्वसम्मति) केवल फायदेमंद ही नहीं बल्कि आवश्यक भी हैं।
दायरा (Scope): लेखक स्पष्ट रूप से कहते हैं कि उनके परिणाम $\Theta$ -लेवल पर हैं। वे सही स्केलिंग और फेज ट्रांजिशन के अस्तित्व की पहचान करते हैं, लेकिन सटीक क्रिटिकल कांस्टेंट्स या सेकंड-ऑर्डर करेक्शन को निर्धारित नहीं करते हैं (जो एक साथी शोध पत्र के लिए सुरक्षित हैं)। असंभवता का परिणाम बाइनरी रैंडमाइज्ड रिस्पॉन्स के लिए कठोरता से सिद्ध है, जबकि फानो लोअर बाउंड सार्वभौमिक है।

शोध पत्र निष्कर्ष निकालता है कि हालांकि सैद्धांतिक ढांचा स्थापित किया गया है, लेकिन विशिष्ट समन्वित रक्षा प्रोटोकॉल (जैसे "CoDef" या "Theory-of-Mind" फ़िल्टरिंग) के डिजाइन और सुरक्षा विश्लेषण को भविष्य के कार्य के लिए छोड़ दिया गया है।