💻 computer science

Differential Privacy for Symbolic Trajectories via the Permute-and-Flip Mechanism

यह शोध पत्र 'परम्यूट-एंड-फ्लिप' (permute-and-flip) दृष्टिकोण पर आधारित एक नवीन, कुशल डिफरेंशियल प्राइवेसी तंत्र प्रस्तावित करता है जो घातीय रूप से बड़ी शब्द सूचियों को सूचीबद्ध किए बिना गैर-संख्यात्मक प्रणालियों के लिए निजी प्रतीकात्मक प्रक्षेपवक्र (symbolic trajectories) उत्पन्न करता है, जिससे पूर्ववर्ती अत्याधुनिक विधियों की तुलना में काफी कम त्रुटि दर प्राप्त होती है।

मूल लेखक: Alexander Benvenuti, Huaiyuan Rao, Matthew Hale

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

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

CC BY 4.0

मूल लेखक: Alexander Benvenuti, Huaiyuan Rao, Matthew Hale

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

कल्पना कीजिए कि आपके पास एक विशेष कोड में लिखी गई एक गुप्त डायरी है। इस डायरी में संख्याएँ या गणित नहीं है; इसके बजाय यह शब्दों से बनी एक कहानी है, जैसे कि आज आपके द्वारा देखी गई जगहों की एक सूची: "घर → कॉफी शॉप → पार्क → लाइब्रेरी।"

डेटा की दुनिया में, इसे एक सिंबोलिक ट्रेजेक्टरी (symbolic trajectory) कहा जाता है। यह इस बात का तरीका है जिससे कंप्यूटर आपकी दैनिक यात्रा, आपके वेब ब्राउज़िंग इतिहास, या किसी रोबोट द्वारा लिए गए मार्ग को ट्रैक करते हैं। समस्या यह है कि यदि कोई आपका सटीक रास्ता देख लेता है, तो वह आपकी आदतों, आपके घर के पते, या आप किससे मिले, इसका अनुमान लगा सकता है। आप अपने दिन का सामान्य विचार साझा करना चाहते हैं बिना सटीक विवरण बताए।

यहीं पर डिफरेंशियल प्राइवेसी (Differential Privacy) काम आती है। इसे डेटा के लिए एक "प्राइवेसी फ़िल्टर" या "धुंध बनाने वाली मशीन" के रूप में सोचें। यह डेटा में बस इतनी भ्रम की स्थिति पैदा करती है कि एक ऑब्जर्वर यह नहीं बता सके कि क्या आप उस डेटासेट में थे या कोई और था, लेकिन समग्र पैटर्न उपयोगी बना रहता है।

समस्या: आप शब्दों में "शोर (Noise)" नहीं जोड़ सकते

संख्याओं (जैसे आपके बैंक बैलेंस) के लिए, गोपनीयता विशेषज्ञ आमतौर पर बस थोड़ा सा रैंडम "स्टैटिक" या शोर जोड़ देते हैं। यदि आपने $50 खर्च किए, तो सिस्टम$ 52 या $48 रिपोर्ट कर सकता है। यह करीब है, लेकिन सटीक नहीं है।

लेकिन आप किसी शब्द में "स्टैटिक" नहीं जोड़ सकते। यदि आपका रास्ता "घर" है, तो आप इसे "घर-जैसा" या "घरों" में नहीं बदल सकते। यदि आप इसे "काम" में बदलते हैं, तो यह एक बहुत बड़ा अंतर है, मामूली शोर नहीं।

पिछले तरीकों ने इसे हल करने की कोशिश की: उन्होंने हर उस संभावित पथ की सूची बनाई जो आप ले सकते थे, गणना की कि प्रत्येक की संभावना कितनी है, और फिर एक को चुना। लेकिन यदि आपके दिन में 14 स्टॉप हैं और प्रत्येक स्टॉप पर जाने के लिए 40 संभावित स्थान हैं, तो संभावित पथों की संख्या खगोलीय (astronomical) हो जाती है (जैसे समुद्र तट पर रेत के हर कण को गिनने की कोशिश करना)। यह गणना करने में बहुत समय लगता है और कंप्यूटर क्रैश हो जाते हैं।

समाधान: "परम्यूट-एंड-फ्लिप (Permute-and-Flip)" जादू का कमाल

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

इसे समझाने के लिए यहाँ एक सरल उपमा दी गई है:

पुराना तरीका (एक्सहॉस्टिव सर्च - Exhaustive Search):
कल्पना कीजिए कि आप अपनी अलमारी से एक रैंडम आउटफिट चुनना चाहते हैं, लेकिन आपका एक नियम है: "आउटफिट आपकी पसंदीदा लाल शर्ट जैसा दिखना चाहिए, लेकिन बिल्कुल वैसा ही नहीं।"
पुराना तरीका यह होगा कि आप अपने पास मौजूद हर एक शर्ट और पैंट को बाहर निकालें, उन्हें अपने बिस्तर पर बिछाएं, मापें कि प्रत्येक आपके लाल शर्ट से कितना अलग है, और फिर एक भारित पासा (weighted die) फेंककर एक को चुनें। यदि आपके पास 1,000 शर्ट और 1,000 पैंट हैं, तो यह लाखों संयोजनों (combinations) की जांच करने जैसा है। यह धीमा और अस्त-व्यset है।

नया तरीका (स्मार्ट फ़िल्टर):
नया तरीका (मैकेनिज्म 1 और 2) बहुत अधिक स्मार्ट है। हर आउटफिट को देखने के बजाय, यह दो त्वरित चरणों में काम करता है:

पहले "डिफरेंस लेवल (Difference Level)" चुनें: यह पूछता है, "नया आउटफिट कितना अलग होना चाहिए?" शायद यह तय करता है, "आइए एक ऐसा आउटफिट चुनें जो लाल शर्ट से ठीक 2 आइटम अलग हो।" इसे अभी यह परवाह नहीं है कि कौन से आइटम, बस बदलावों की संख्या की परवाह है।
उस स्तर तक पहुँचने के लिए एक "पाथवे (Pathway)" बनाएं: यह एक विशेष मानचित्र (जिसे ऑटोमेटन कहा जाता है) बनाता है जो केवल उन आउटफिट्स तक ले जाता है जिनमें ठीक 2 बदलाव हैं। फिर यह इस मानचित्र पर चलता है, एक रैंडम रास्ता चुनता है। क्योंकि मानचित्र को केवल 2 बदलावों वाले वैध विकल्पों को रखने के लिए बनाया गया था, यह बिना लाखों अन्य विकल्पों को देखे, तुरंत एक परफेक्ट आउटफिट ढूंढ लेता है।

यह एक बड़ी बात क्यों है?

यह शोध पत्र दो मुख्य बातें सिद्ध करता है:

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

ट्रैफिक की उपमा:
कल्पना कीजिए कि आप किसी ड्राइवर के शहर के माध्यम से जाने वाले विशिष्ट मार्ग को छिपाने की कोशिश कर रहे हैं।

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

निचोड़ (The Bottom Line)

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

यहाँ शोध पत्र "Differential Privacy for Symbolic Trajectories via the Permute-and-Flip Mechanism" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र प्रतीकात्मक प्रणालियों (Symbolic Systems) पर डिफरेंशियल प्राइवेसी (DP) लागू करने की चुनौती को संबोधित करता है।

संदर्भ: कई डेटा-संचालित प्रणालियाँ (जैसे ट्रैफ़िक नेटवर्क, स्मार्ट ग्रिड, मार्कोव निर्णय प्रक्रियाएं) ऐसी प्रक्षेपवक्र (trajectories) उत्पन्न करती हैं जो निरंतर संख्यात्मक वेक्टर के बजाय एक परिमित वर्णमाला (finite alphabet) पर गैर-संख्यात्मक डेटा (शब्द या स्ट्रिंग्स) के रूप में प्रतिनिधित्व करती हैं।
मौजूदा विधियों की सीमा: मानक DP तंत्र (जैसे गॉसियन या लैप्लास नॉइज़) संख्यात्मक डेटा में शोर जोड़ने पर निर्भर करते हैं, जो प्रतीकात्मक डेटा के लिए अनुपयुक्त है।
पूर्व अत्याधुनिक स्थिति (Prior State of the Art): प्रतीकात्मक डेटा के लिए पिछले दृष्टिकोणों ने एक्सपोनेंशियल मैकेनिज्म (Exponential Mechanism) का उपयोग किया। हालांकि यह प्रभावी है, लेकिन यह गणनात्मक रूप से महंगा हो सकता है। एक अधिक हालिया प्रगति, परम्यूट-एंड-फ्लिप (P&F) तंत्र, एक्सपोनेंशियल मैकेनिज्म के समान या उससे बेहतर सटीकता प्रदान करता है, लेकिन जब आउटपुट स्पेस (सभी संभावित शब्दों का सेट) घातीय रूप से बड़ा होता है, तो यह अत्यधिक समय जटिलता (time complexity) से ग्रस्त होता है।
मुख्य चुनौती: सभी संभावित आउटपुट शब्दों के घातीय बड़े सेट को स्पष्ट रूप से सूचीबद्ध किए बिना, प्रतीकात्मक प्रक्षेपवक्रों के लिए परम्यूट-एंड-फ्लिप तंत्र को कुशलतापूर्वक कैसे लागू किया जाए।

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

लेखक एक नया ढांचा प्रस्तावित करते हैं जो कुशल और निजी प्रतीकात्मक प्रक्षेपवक्रों को उत्पन्न करने के लिए परम्यूट-एंड-फ्लिप तंत्र को मॉडिफाइड हैमिंग डिस्टेंस ऑटोमेटा (MNFA) के साथ एकीकृत करता है।

A. सैद्धांतिक आधार (Theoretical Foundation)

उपयोगिता फलन (Utility Function): यह तंत्र हैमिंग दूरी ( $d(w, w')$ ) पर आधारित एक उपयोगिता फलन का उपयोग करता है, जो संवेदनशील इनपुट शब्द $w$ और निजी आउटपुट शब्द $w'$ के बीच भिन्न प्रतीकों की संख्या को गिनता है। उपयोगिता को $u(w, w') = -d(w, w')$ के रूप में परिभाषित किया गया है।
परम्यूट-एंड-फ्लिप (P&F): यह तंत्र उपयोगिता स्कोर के आधार पर एक आउटपुट चुनता है। एक सहज (naive) कार्यान्वयन के लिए आउटपुट स्पेस $\Sigma^n$ के प्रत्येक संभावित शब्द के लिए संभाव्यता की गणना करना आवश्यक है, जो कि अव्यवहार्य है ( $m^n$ जटिलता)।

B. प्रस्तावित तंत्र (Mechanism 1)

सूचीबद्ध करने की समस्या से बचने के लिए, लेखक नमूनाकरण (sampling) प्रक्रिया को विघटित करते हैं:

त्रुटि गणना ( $\ell$ ) का नमूना लेना: एक विशिष्ट शब्द का नमूना लेने के बजाय, तंत्र पहले एक लक्षित हैमिंग दूरी $\ell$ (त्रुटियों की संख्या) का नमूना लेता है, जो P&F तंत्र से प्राप्त एक विशिष्ट संभाव्यता वितरण से आता है। यह वितरण गोपनीयता पैरामीटर $\epsilon$ , आसन्नता (adjacency) पैरामीटर $b$ , और $\ell$ दूरी वाले शब्दों का प्रतिनिधित्व करने वाले कॉम्बिनेटोरियल पदों पर निर्भर करता है।
MNFA का निर्माण: एक बार $\ell$ का चयन हो जाने के बाद, लेखक एक मॉडिफाइड हैमिंग डिस्टेंस एनएफए (MNFA) का निर्माण करते हैं। यह ऑटोमेटन इस तरह डिज़ाइन किया गया है कि इसकी भाषा ठीक उन सभी शब्दों से बनी है जिनकी लंबाई $n$ है और जिनका संवेदनशील इनपुट शब्द से हैमिंग दूरी ठीक $\ell$ है।
पॉलिसी सिंथेसिस के माध्यम से समान नमूनाकरण (Uniform Sampling): एल्गोरिदम 1 का उपयोग करके, वे MNFA के लिए एक ट्रांजिशन पॉलिसी $\mu$ $μ$ को संश्लेषित करते हैं। यह पॉलिसी सिस्टम को ऑटोमेटन के माध्यम से आगे बढ़ने और $\ell$ $ℓ$ दूरी वाले सभी शब्दों के सेट में से यादृच्छिक रूप से एक शब्द उत्पन्न करने की अनुमति देती है।
- यह एल्गोरिदम बैकवर्ड इंडक्शन (backward induction) द्वारा कार्य करता है, जो स्वीकार करने वाली अवस्था (accepting state) से प्रत्येक अवस्था से वैध पथों की संख्या निर्धारित करने के लिए ट्रांजिशन संभावनाओं की गणना करता है।

C. मार्कोव चेन में विस्तार (Mechanism 2)

उन प्रणालियों को संभालने के लिए जहाँ सभी शब्द अनुक्रम वैध नहीं हैं (जैसे कि एक मार्कोव चेन जहाँ कुछ अवस्था संक्रमण असंभव हैं), लेखक दृष्टिकोण का विस्तार करते हैं:

प्रोडक्ट MNFA (P-MNFA): वे MNFA (जो हैमिंग दूरी बाधा को लागू करता है) और मार्कोव चेन (जो व्यवहार्यता बाधाओं को लागू करता है) को मिलाने वाला एक उत्पाद ऑटोमेटन (product automaton) बनाते हैं।
व्यवहार्यता (Feasibility): परिणामी तंत्र यह सुनिश्चित करता है कि उत्पन्न निजी शब्द न केवल इनपुट का एक वैध सन्निकटन है, बल्कि उस विशिष्ट मार्कोव चेन के लिए एक व्यवहार्य प्रक्षेपवक्र (feasible trajectory) भी है (अर्थात, यह संक्रमण संभावनाओं और प्रारंभिक अवस्था का सम्मान करता है)।

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

कुशल P&F कार्यान्वयन: यह शोध पत्र बड़े प्रतीकात्मक आउटपुट स्पेस के लिए परम्यूट-एंड-फ्लिप मैकेनिज्म को लागू करने की खुली समस्या को हल करता है। यह त्रुटि गणना के चयन को विशिष्ट शब्द के चयन से अलग करके प्राप्त करता है, जिससे घातीय सूचीकरण (exponential enumeration) से बचा जा सके।
सैद्धांतिक सटीकता सीमाएँ: लेखक निजीकृत प्रक्षेपवक्र के अपेक्षित हैमिंग दूरी (त्रुटि) के लिए ऊपरी और निचली सीमाएँ प्राप्त करते हैं।
- थ्योरम 2 सिद्ध करता है कि उनके तंत्र की अपेक्षित त्रुटि अत्याधुनिक एक्सपोनेंशियल मैकेनिज्म (विशेष रूप से [21] में वर्णित तंत्र) से कभी भी खराब नहीं होती है।
- ऊपरी सीमा एक्सपोनेंशियल मैकेनिज्म की अपेक्षित त्रुटि से सटीक रूप से मेल खाती है।
मार्कोव चेन विशेषज्ञता: ढांचे को मार्कोव चेन के लिए विशेष बनाया गया है (मैकेनिज्म 2), जो यह सुनिश्चित करता है कि गोपनीयता-संरक्षित आउटपुट वैध सिस्टम प्रक्षेपवक्र बने रहें।
अनुभवजन्य सत्यापन (Empirical Validation): दृष्टिकोण का परीक्षण एक वास्तविक दुनिया के ट्रैफ़िक डेटासेट (गेंसविले, फ्लोरिडा AADT) पर किया गया है।

4. परिणाम (Results)

सटीकता में सुधार: $n=14$ $n = 14$ अवस्थाओं और 43 की वर्णमाला आकार वाले ट्रैफ़िक डेटासेट पर अनुभवजन्य मूल्यांकन ने पूर्व अत्याधुनिक तकनीक (चेन एट अल., 2023) की तुलना में महत्वपूर्ण सुधार दिखाया।
- मजबूत गोपनीयता ( $\epsilon = 0.5$ ) के तहत, दोनों तंत्र समान प्रदर्शन करते हैं।
- पारंपरिक गोपनीयता स्तरों (जैसे $\epsilon = 5$ ) के तहत, प्रस्तावित तंत्र ने एक्सपोनेंशियल मैकेनिज्म की तुलना में 55.7% तक कम त्रुटि पेश की।
- सभी $\epsilon > 3$ के लिए, प्रस्तावित तंत्र ने त्रुटि में कम से कम 25% की कमी दिखाई।
स्केलेबिलिटी (Scalability): यह विधि कुशलतापूर्वक स्केल करती है क्योंकि यह घातीय शब्द स्थान के बजाय बहुपद-समय (polynomial-time) ऑटोमेटा निर्माण और पॉलिसी सिंथेसिस पर निर्भर करती है।

5. महत्व (Significance)

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

संक्षेप में, यह शोध पत्र प्रतीकात्मक प्रक्षेपवक्रों को निजीकृत करने के लिए एक गणितीय रूप से कठोर और गणनात्मक रूप से कुशल ढांचा प्रस्तुत करता है, जो यह सिद्ध करता है कि यह मौजूदा विधियों की तुलना में सैद्धांतिक रूप से श्रेष्ठ या समकक्ष है और वास्तविक अनुप्रयोगों के लिए त्रुटि में पर्याप्त कमी का अनुभवजन्य प्रदर्शन करता है।