तकनीकी सारांश: K-निकटतम पड़ोसी (k-Nearest Neighbor) प्रश्नों को स्थान अनुमान हमलों (Location Inference Attacks) से बचाना

1. समस्या विवरण

यह शोध पत्र एक महत्वपूर्ण, पहले अनदेखी की गई गोपनीयता भेद्यता (vulnerability) को संबोधित करता है जो उन लोकेशन-आधारित सेवाओं (LBS) में मौजूद है जो k-निकटतम पड़ोसी प्रश्नों (kNNQ) का उपयोग करती हैं। जबकि LBS की विशेषताएं जैसे "आस-पास के लोग" (जैसे टिंडर जैसे सोशल ऐप्स में) सटीक निर्देशांकों (coordinates) के बजाय उपयोगकर्ताओं की एक रैंक की गई सूची लौटाती हैं, लेखक तर्क देते हैं कि यह रैंकिंग स्वयं एक शक्तिशाली साइड-चैनल (side-channel) के रूप में कार्य करती है।

मौजूदा स्थान अनुमान हमले (LIAs) आम तौर पर अस्पष्ट निर्देशांकों या प्रक्षेपवक्र डेटा (trajectory data) तक पहुंच पर निर्भर करते हैं। हालाँकि, यह कार्य एक सख्त थ्रेट मॉडल (threat model) की जांच करता है जहाँ एक हमलावर, एक वैध उपयोगकर्ता के रूप में कार्य करते हुए, केवल API द्वारा लौटाए गए $k$ निकटतम पड़ोसियों की गुमनाम, रैंक की गई सूची तक ही पहुँच सकता है। मुख्य समस्या यह है कि विभिन्न स्थानों से अनुकूल रूप से (adaptively) क्वेरी करके (संभावित रूप से मिलीभगत करने वाले उपयोगकर्ताओं के साथ), एक हमलावर लक्षित उपयोगकर्ता के सटीक भौगोलिक निर्देशांकों का अनुमान लगा सकता है, भले ही सर्वर सटीक दूरी और स्थानों को छिपाने का दावा करता हो।

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

शोध पत्र एक दो-चरणीय कार्यप्रणाली प्रस्तावित करता है: पहले, नवीन हमलों के माध्यम से खतरे की गंभीरता को प्रदर्शित करना, और दूसरा, डिफरेंशियल प्राइवेसी (DP) पर आधारित एक रक्षा तंत्र पेश करना।

A. हमले के तरीके (Attack Methods)

लेखक kNNQ सेवाओं के विरुद्ध दो स्थान अनुमान हमलों को डिजाइन और मूल्यांकन करते हैं:

1. ज्यामितीय प्रतिच्छेदन स्थान अनुमान हमला (Geometric Intersection Location Inference Attack - GI-LIA):

   • तंत्र: यह आधारभूत हमला ज्यामितीय त्रिकोणीकरण (triangulation) का उपयोग करता है। एक हमलावर एक प्रोब स्थान (probe location) पर केंद्रित एक वृत्त की पहचान करता है जहाँ एक सहकर्मी (colluder) क्वेरी परिणामों में रैंक $k$ पर दिखाई देता है। चूंकि लक्ष्य भी रैंक $k$ पर है, इसलिए लक्ष्य इस वृत्त की परिधि पर होना चाहिए। दूसरे प्रोब स्थान के साथ इस प्रक्रिया को दोहराकर, हमलावर दूसरे वृत्त को उत्पन्न करता है। इन दो वृत्तों का प्रतिच्छेदन (intersection) दो संभावित स्थानों को देता है, जिन्हें लक्ष्य को सटीक रूप से खोजने के लिए सत्यापित किया जाता है।
   • सीमा: अत्यधिक सटीक होने के बावजूद, GI-LIA को संचार ओवरहेड (communication overhead) का सामना करना पड़ता है क्योंकि इसमें वृत्त की त्रिज्या खोजने और दूसरे प्रोब बिंदु को खोजने के लिए बाइनरी सर्च की आवश्यकता होती है।

2. जीरो-ऑर्डर ऑप्टिमाइज़ेशन स्थान अनुमान हमला (Zero-order Optimization Location Inference Attack - ZO-LIA):

   • तंत्र: दक्षता में सुधार के लिए, ZO-LIA दूसरे ज्यामितीय प्रतिबंध बनाने से बचता है। इसके बजाय, यह पहले प्रतिबंध वृत्त द्वारा परिभाषित व्यवहार्य क्षेत्र के भीतर एक रैंक-निर्देशित स्थानीय खोज (rank-guided local search) करता है।
   • प्रक्रिया:
     1. त्रिज्या खोज (Radius Search): GI-LIA की तरह प्रारंभिक प्रतिबंध वृत्त $C(A_1, R_1)$ स्थापित करता है।
     2. प्रोब जनरेशन (Probe Generation): वृत्त केंद्र के चारों ओर प्रोब बिंदु नमूना (sample) लेता है और प्रत्येक पर लक्ष्य की रैंक रिकॉर्ड करता है।
     3. रैंक ऑप्टिमाइज़ेशन (Rank Optimization): रैंक फीडबैक के आधार पर एक स्यूडो-ग्रेडिएंट (pseudo-gradient) का अनुमान लगाने के लिए ज़ीरो-ऑर्डर ऑप्टिमाइज़ेशन का उपयोग करता है, और उत्तरोत्तर (iteratively) उस बिंदु की ओर बढ़ता है जो लक्ष्य की रैंक को कम करता है।
     4. प्रतिबंधित प्रोजेक्शन (Constrained Projection): अंतिम स्थान का अनुमान लगाने के लिए अनुकूलित आंतरिक बिंदु को वृत्त की सीमा पर लंबवत रूप से प्रोजेक्ट करता है।
   • लाभ: ZO-LIA, GI-LIA की तुलना में लगभग आधे संचार ओवरहेड (क्वेरी संख्या और समय) के साथ उच्च सफलता दर प्राप्त करता है।

B. रक्षा तंत्र: DPRS

इन जोखिमों को कम करने के लिए, लेखक DPRS (kNNQ सुरक्षा के लिए डिफरेंशियल प्राइवेसी फ्रेमवर्क) प्रस्तावित करते हैं। DPRS का लक्ष्य उपयोगकर्ता के स्थानों को बाधित (perturb) करना है जबकि kNNQ रैंकिंग की उपयोगिता (utility) को बनाए रखना है।

• मुख्य घटक:

  1. निजी अंतराल निर्माण (Private Interval Construction - PIC): व्यक्तिगत बिंदुओं को सीधे बाधित करने के बजाय (जिससे अत्यधिक दूरी विरूपण होता है), DPRS पहले एक डिफरेंशियल प्राइवेट k-means एल्गोरिदम का उपयोग करके डेटासेट को क्लस्टर करता है। यह प्रत्येक क्लस्टर के लिए एक "निजी अंतराल" (एक यूक्लिडियन बॉल) बनाता है, जो एक निजी सेंट्रॉइड और एक निजी त्रिज्या द्वारा परिभाषित होता है। त्रिज्या को निकटतम पड़ोसी सेंट्रॉइड की दूरी द्वारा निर्धारित किया जाता है, जिससे अतिरिक्त प्राइवेसी बजट की आवश्यकता नहीं होती है।
  2. रिजेक्शन सैंपलिंग तंत्र (Rejection Sampling Mechanism - RSM): यह मॉड्यूल मूल डेटा बिंदुओं को निर्मित निजी अंतरालों में बाधित करता है। यह एक रिजेक्शन सैंपलिंग रणनीति का उपयोग करता है जहाँ उम्मीदवार स्थानों को एक शोर वितरण (जैसे लैप्लास) से खींचा जाता है और केवल तभी स्वीकार किया जाता है जब वे विशिष्ट अंतराल के भीतर हों और एक संभाव्यता थ्रेशोल्ड को पूरा करते हों। यह सुनिश्चित करता है कि बाधित डेटा लक्षित वितरण का पालन करता है जबकि अंतराल बाधाओं का सख्ती से पालन करता है, जिससे दूरी विरूपण सीमित होता है।

• गोपनीयता गारंटी: फ्रेमवर्क PIC और RSM दोनों मॉड्यूल के गोपनीयता नुकसान का विश्लेषण करने के लिए रेनी डिफरेंशियल प्राइवेसी (Rényi Differential Privacy - RDP) का उपयोग करता है, जो संपूर्ण प्रणाली के लिए एक कठोर $(\epsilon, \delta)$-DP गारंटी प्रदान करता है।

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

शोध पत्र निम्नलिखित प्राथमिक योगदानों का दावा करता है:

• kNNQ पर पहले हमले: यह विशेष रूप से kNNQ सेवाओं को लक्षित करने वाले पहले व्यवस्थित अध्ययन को प्रस्तुत करता है, जिसमें GI-LIA और ZO-LIA शामिल हैं।
• रक्षा फ्रेमवर्क (DPRS): यह DPRS प्रस्तावित करता है, जो एक गोपनीयता-संरक्षित फ्रेमवर्क है जो बाधित अंतराल और रिजेक्शन सैंपलिंग को मिलाकर एक बेहतर गोपनीयता-उपयोगिता ट्रेड-ऑफ प्राप्त करता है।
• सैद्धांतिक विश्लेषण: यह रिजेक्शन सैंपलिंग तंत्र के लिए एक RDP-आधारित गोपनीयता गारंटी स्थापित करता है और डिफ़ॉल्ट अंतराल के लिए उपयोगिता सीमाओं को व्युत्पन्न करता है।
• अनुभवजन्य सत्यापन (Empirical Validation): वास्तविक दुनिया (Brightkite, Gowalla) और सिंथेटिक डेटासेट पर व्यापक प्रयोग प्रस्तावित विधियों की प्रभावशीलता को प्रदर्शित करते हैं।

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

लेखकों ने चार डेटासेट पर तीन अत्याधुनिक बेसलाइनों (L-SRR, Square, और Laplace मैकेनिज्म) के विरुद्ध DPRS का मूल्यांकन किया।

• हमले की प्रभावशीलता: GI-LIA और ZO-LIA दोनों अत्यधिक प्रभावी साबित हुए। ZO-LIA ने 40 मीटर से कम औसत दूरी त्रुटि के साथ 90% से ऊपर की सफलता दर (Acc) प्राप्त की (उदाहरण के लिए, Brightkite पर $k=10$ के साथ 0.948), जबकि GI-LIA ने 99.6% तक सफलता दर प्राप्त की।
• रक्षा प्रदर्शन:
  • गोपनीयता सुरक्षा: कम प्राइवेसी बजट ($\epsilon = 0.5$) के तहत, DPRS ने दोनों हमलों की सफलता दर को 3% से नीचे (उदाहरण के लिए, Brightkite पर Acc = 0.012) कम कर दिया, जो बेसलाइनों से काफी बेहतर है।
  • क्वेरी उपयोगिता (Query Utility): DPRS निरंतर उपयोगिता मेट्रिक्स (Recall और Ratio) में मौजूदा तरीकों से बेहतर प्रदर्शन करता है। उदाहरण के लिए, Brightkite डेटासेट पर $\epsilon=1$ के साथ, DPRS ने रिकॉल को 0.423 (SRR) से बढ़ाकर 0.464 और रेशियो को 0.832 से बढ़ाकर 0.881 कर दिया।
  • ट्रेड-ऑफ: परिणाम संकेत देते हैं कि DPRS अन्य DP-kNNQ विधियों में देखी गई गंभीर उपयोगिता गिरावट के बिना गोपनीयता रिसाव को सफलतापूर्वक कम करता है।

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

शोध पत्र अपने कार्य को व्यापक रूप से उपयोग की जाने वाली LBS सुविधाओं में निहित एक "गंभीर गोपनीयता जोखिम" के आवश्यक उत्तर के रूप में प्रस्तुत करता है। लेखक दावा करते हैं कि वर्तमान kNNQ सेवाएँ तब भी असुरक्षित हैं जब सटीक निर्देशांक छिपे होते हैं, क्योंकि केवल रैंकिंग जानकारी ही सटीक स्थान अनुमान के लिए पर्याप्त है।

DPRS का महत्व गोपनीयता संरक्षण को उपयोगिता हानि से अलग करने की इसकी क्षमता में निहित है। सावधानीपूर्वक निर्मित अंतराल के भीतर बाधाओं और रिजेक्शन सैंपलिंग का उपयोग करके, फ्रेमवर्क उस "अत्यधिक शोर इंजेक्शन" को रोकता है जो आमतौर पर kNNQ डेटा को एकत्रीकरण या रैंकिंग के लिए बेकार बना देता है। लेखक निष्कर्ष निकालते हैं कि DPRS एक मजबूत, स्केलेबल रक्षा प्रदान करता है जो वास्तविक दुनिया में तैनाती के लिए व्यावहारिक है, जैसा कि इसके निम्न ऑनलाइन ओवरहेड (40ms से कम) और विविध डेटासेट में बेहतर प्रदर्शन से सिद्ध होता है।