Better Privacy Guarantees for Larger Groups

तकनीकी सारांश: बड़े समूहों के लिए बेहतर गोपनीयता गारंटी

समस्या विवरण
यह शोध पत्र पुजोल और डेसफॉन्टेन्स [2023] द्वारा प्रस्तुत एक खुले प्रश्न को संबोधित करता है, जो निश्चित, विलगित (disjoint) समूहों के लिए निजी हिस्टोग्राम के डिज़ाइन से संबंधित है। मानक डिफरेंशियल प्राइवेसी तंत्र आमतौर पर प्रत्येक गणना (count) में एक निश्चित परिमाण का शोर (noise) जोड़ते हैं, जिससे एक समान पूर्ण गोपनीयता (absolute privacy) तो मिलती है, लेकिन इसके परिणामस्वरूप बड़े समूहों की तुलना में छोटे समूहों के लिए सापेक्ष त्रुटि (relative error) काफी अधिक होती है। मुख्य प्रश्न यह है कि क्या कोई इस अतिरिक्त सटीकता का उपयोग अलग तरह से कर सकता है: यानी, एक समूह में त्रुटि को उसकी गणना ($x_i$) के आनुपातिक रूप से बढ़ने की अनुमति देकर: जिससे बड़े समूहों के सदस्यों के लिए मजबूत गोपनीयता गारंटी (एक छोटा प्राइवेसी बजट) प्राप्त हो सके।

यह शोध पत्र "ऐड-ऑर-रिमूव-वन" (add-or-remove-one) आसन्नता मॉडल (adjacency model) के तहत इसकी जांच करता है। लक्ष्य एक ऐसा तंत्र खोजना है जहाँ प्राइवेसी बजट $v(n)$ केवल समूह की संख्या $n$ पर निर्भर करता हो, गैर-बढ़ता (non-increasing) हो, और काउंट-डिपेंडेंट ग्रुप-वाइज जीरो-कन्सेंट्रेटेड डिफरेंशियल प्राइवेसी (zCDP) को संतुष्ट करता हो। इसके लिए प्रत्येक क्रम $\alpha > 1$ के लिए दोनों दिशाओं में रेनी डायवर्जेंस (Rényi divergence) को सीमित करना आवश्यक है।

एक महत्वपूर्ण तकनीकी बाधा शून्य पर सीमा स्थिति (boundary condition at zero) की पहचान की गई है। मूल फॉर्मूलेशन के लिए अपेक्षित पूर्ण त्रुटि (expected absolute error) $r x_i$ से कम होनी चाहिए थी। $x_i = 0$ पर, इसका अर्थ है $E|\hat{x}_i| < 0$, जो असंभव है। इसके अलावा, $0 \leftrightarrow 1$ एज के बीच परिमित दो-तरफा रेनी डायवर्जेंस बनाए रखते हुए असमिका (inequality) को $\leq$ में बदलने से भी विरोधाभास उत्पन्न होता है (जो आउटपुट को नियत/deterministic बना देता है, जिससे त्रुटि सीमा का उल्लंघन होता है)।

कार्यप्रणाली और सुधारा गया फॉर्मूलेशन
इस सीमा समस्या को हल करने के लिए, लेखक एक "सुधारा हुआ" उपयोगिता (utility) आवश्यकता प्रस्तावित करते हैं:
$$E|\hat{x}_i - x_i| < r \max\{x_i, 1\}$$
यह सभी धनात्मक गणनाओं के लिए सापेक्ष त्रुटि लक्ष्य को बनाए रखता है जबकि शून्य पर एक निश्चित पूर्ण सहनशीलता (absolute tolerance) पेश करता है, जिससे समस्या व्यवहार्य हो जाती है।

शोध पत्र दो प्राथमिक कार्यप्रणाली दृष्टिकोणों का उपयोग करता है:

1. व्यवहार्यता (ऊपरी सीमा - Feasibility): लेखक एक मौजूदा "शिफ्टेड-ट्रांसफॉर्मेशन" ढांचे (फिनली एट अल. [2026]) का विशेषीकरण करते हैं। वे एक शिफ्ट $c$ के साथ लघुगणक (logarithm) के माध्यम से गणना स्थान को रूपांतरित करते हैं (अर्थात, $\log(x_i + c)$), स्थिर-विचलन वाला गॉसियन शोर जोड़ते हैं, और घातांक बनाने (exponentiating) और क्लिपिंग करने से पहले एक नियत ड्रिफ्ट (drift) लागू करते हैं।

   • प्रमुख नवाचार: मानक लॉग-नॉर्मल तंत्रों के विपरीत, जो माध्य-निष्पक्षता (mean-unbiasedness) सुनिश्चित करने के लिए $-\sigma^2/2$ के ड्रिफ्ट का उपयोग करते हैं, यह तंत्र $-\sigma^2$ के ड्रिफ्ट का उपयोग करता है। इस विशिष्ट ड्रिफ्ट को अपेक्षित पूर्ण गुणात्मक त्रुटि (expected absolute multiplicative error) को न्यूनतम करने के लिए चुना गया है, जो शोध पत्र के उपयोगिता मीट्रिक के अनुरूप है।
   • प्राइवेसी मैकेनिज्म: लॉग-स्पेस में समान विचरण (equal variance) के साथ काम करके, यह तंत्र सुनिश्चित करता है कि सभी आदेशों $\alpha$ के लिए आसन्न गणनाओं के बीच रेनी डायवर्जेंस परिमित हो, जिससे "टेल ऑब्स्ट्रक्शन" (tail obstruction) से बचा जा सके जहाँ असमान विचरण एक दिशा में अनंत डायवर्जेंस का कारण बनते हैं।

2. असंभवता (निचली सीमा - Impossibility): लेखक सिद्ध करते हैं कि कोई भी तंत्र जो सुधारा हुआ उपयोगिता और काउंट-डिपेंडेंट zCDP आवश्यकताओं को पूरा करता है, वह गणना के व्युत्क्रम-वर्ग (inverse-square) से तेज़ प्राइवेसी बजट क्षय दर (decay rate) प्राप्त नहीं कर सकता है।

   • दो-गणना तर्क (Two-Count Argument): दो विशिष्ट गणनाओं के बीच एक परीक्षण $n^{-2}$ घातांक को स्थापित करता है।
   • कई-गणना तर्क (Many-Count Argument): एक "हिडन ऑफसेट" यादृच्छिक चर (random variable) का उपयोग करते हुए और सूचना-सैद्धांतिक तर्कों (अपेक्षित पूर्ण त्रुटि को म्यूचुअल इंफॉर्मेशन से जोड़ते हुए) का उपयोग करके, लेखक प्राइवेसी बजट के अग्रणी गुणांक (leading coefficient) पर एक कड़ा निचला स्तर (tighter lower bound) प्राप्त करते हैं।

मुख्य परिणाम

• इष्टतम स्पर्शोन्मुख दर (Optimal Asymptotic Rate): किसी भी निश्चित $0 < r < 1$ के लिए, इष्टतम प्राइवेसी बजट $v(n)$, $\Theta_r(n^{-2})$ के रूप में घटता है।

  • ऊपरी सीमा: शिफ्टेड-लॉग गॉसियन तंत्र $v(n) = O_r(n^{-2})$ प्राप्त करता है। विशेष रूप से, जैसे-जैसे $n \to \infty$, $v(n) \approx \frac{1}{2\sigma^2 n^2}$।
  • निचली सीमा: कोई भी तंत्र जो आवश्यकताओं को संतुष्ट करता है, उसका \liminf_{n \to \infty} n^2 v(n) \geq \frac{(1-r)^6}{128r^2(1+r)^2 होगा। यह पुष्टि करता है कि इनवर्स-स्क्वायर दर अंतर्निहित है और निर्माण का कोई कृत्रिम परिणाम नहीं है।

• अग्रणी गुणांक (Leading Coefficients): शोध पत्र छोटे $r$ और बड़े $n$ के सीमा में अग्रणी गुणांक $C^*$ के लिए सर्वोत्तम संभव ऊपरी और निचली सीमाओं के बीच के अंतर को कम करता है:
  $$\frac{\pi}{4e^2} \leq C^* \leq \frac{1}{\pi}$$
  दोनों सीमाओं के बीच का अनुपात लगभग 2.995 है, जो दर्शाता है कि सीमाएँ तीन के कारक के भीतर हैं।

• असमान-विचरण वाले गॉसियन की विफलता: शोध पत्र प्रदर्शित करता है कि एक सहज तंत्र जो $N(n, r^2 n^2)$ (गणना के वर्ग के अनुपात में विचरण वाला गॉसियन शोर) जारी करता है, zCDP परिभाषा को विफल कर देता है। हालांकि इसमें सही त्रुटि पैमाना है, लेकिन आसन्न गणनाओं के बीच असमान विचरण पर्याप्त उच्च आदेशों $\alpha$ के लिए एक दिशा में रेनी डायवर्जेंस को अनंत कर देते हैं, जो zCDP की "सभी-आदेशों" की आवश्यकता का उल्लंघन करता है।

• तुच्छ मामला (Trivial Case): $r=1$ पर, एक डेटा-स्वतंत्र रिलीज (जैसे, हमेशा $0.5$आउटपुट करना) शून्य प्राइवेसी लॉस ($v \equiv 0$) के साथ सुधारा हुआ मानदंड संतुष्ट करता है।

महत्व और दावे
शोध पत्र का दावा है कि यह इस विशिष्ट फॉर्मूलेशन के लिए इस प्रकार की ग्रुप-वाइज प्राइवेसी हेतु इनवर्स-स्क्वायर दर के इष्टतम होने का पहला मैकेनिज्म-स्वतंत्र प्रमाण प्रदान करता है।

• व्यवहार्यता: यह स्थापित करता है कि "सुधारा हुआ" फॉर्मूलेशन समाधान योग्य है और एक ठोस, संयोज्य (composable) तंत्र (शिफ्टेड-लॉग गॉसियन) प्रदान करता है जो इष्टतम दर प्राप्त करता है।
• इष्टतमता: यह सिद्ध करता है कि कोई भी तंत्र, चाहे उसकी जटिलता या सहसंबंध संरचना कुछ भी हो, $n^{-2}$ क्षय दर में सुधार नहीं कर सकता है।
• परिशुद्धता: कई-गणना सूचना तर्कों का उपयोग करके, शोध पत्र पिछले दो-गणना विश्लेषणों की तुलना में अग्रणी स्थिरांक (leading constant) पर निचली सीमाओं को काफी कड़ा करता है, जिससे अनिश्चितता को तीन के कारक से कम कर दिया जाता है।

लेखक स्पष्ट रूप से कहते हैं कि इष्टतम गुणांक $C^*$ के सटीक मान को निर्धारित करना एक खुला प्रश्न बना हुआ है। वे यह भी नोट करते हैं कि उनके परिणाम निश्चित, विलगित समूहों के लिए लागू होते हैं; ओवरलैपिंग या डेटा-डिपेंडेंट समूहों के लिए अलग संवेदनशीलता विश्लेषण की आवश्यकता होगी। तंत्र पक्षपाती (biased) है (क्योंकि $-\sigma^2$ ड्रिफ्ट के कारण), लेकिन इसे विशेष रूप से अपेक्षित पूर्ण त्रुटि को न्यूनतम करने के लिए कैलिब्रेट किया गया है, न कि निष्पक्ष (unbiased) होने के लिए।