2025-11-17T12:40:13.303016

Over-Threshold Multiparty Private Set Intersection for Collaborative Network Intrusion Detection

Arpaci, Boutaba, Kerschbaum
An important function of collaborative network intrusion detection is to analyze the network logs of the collaborators for joint IP addresses. However, sharing IP addresses in plain is sensitive and may be even subject to privacy legislation as it is personally identifiable information. In this paper, we present the privacy-preserving collection of IP addresses. We propose a single collector, over-threshold private set intersection protocol. In this protocol $N$ participants identify the IP addresses that appear in at least $t$ participant's sets without revealing any information about other IP addresses. Using a novel hashing scheme, we reduce the computational complexity of the previous state-of-the-art solution from $O(M(N \log{M}/t)^{2t})$ to $O(t^2M\binom{N}{t})$, where $M$ denotes the dataset size. This reduction makes it practically feasible to apply our protocol to real network logs. We test our protocol using joint networks logs of multiple institutions. Additionally, we present two deployment options: a collusion-safe deployment, which provides stronger security guarantees at the cost of increased communication overhead, and a non-interactive deployment, which assumes a non-colluding collector but offers significantly lower communication costs and applicable to many use cases of collaborative network intrusion detection similar to ours.
academic

सहयोगी नेटवर्क घुसपैठ पहचान के लिए ओवर-थ्रेशोल्ड मल्टीपार्टी प्राइवेट सेट इंटरसेक्शन

मूल जानकारी

  • पेपर ID: 2510.12045
  • शीर्षक: सहयोगी नेटवर्क घुसपैठ पहचान के लिए ओवर-थ्रेशोल्ड मल्टीपार्टी प्राइवेट सेट इंटरसेक्शन
  • लेखक: Onur Eren Arpaci, Raouf Boutaba, Florian Kerschbaum (वाटरलू विश्वविद्यालय)
  • वर्गीकरण: cs.CR (क्रिप्टोग्राफी और सुरक्षा), cs.NI (नेटवर्किंग और इंटरनेट आर्किटेक्चर)
  • प्रकाशन समय: 14 अक्टूबर 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2510.12045

सारांश

सहयोगी नेटवर्क घुसपैठ पहचान की एक महत्वपूर्ण कार्यक्षमता सहयोगियों के नेटवर्क लॉग का विश्लेषण करके सामान्य IP पते की पहचान करना है। हालांकि, IP पते को सादे पाठ में साझा करना संवेदनशील है, और यह व्यक्तिगत पहचान योग्य जानकारी होने के कारण गोपनीयता कानूनों द्वारा प्रतिबंधित भी हो सकता है। यह पेपर IP पते के गोपनीयता-संरक्षित संग्रह के लिए एक विधि प्रस्तावित करता है, जिसमें एक एकल संग्राहक, ओवर-थ्रेशोल्ड प्राइवेट सेट इंटरसेक्शन प्रोटोकॉल शामिल है। इस प्रोटोकॉल में, N प्रतिभागी उन IP पते की पहचान करते हैं जो कम से कम t प्रतिभागियों के सेट में दिखाई देते हैं, अन्य IP पते के बारे में कोई जानकारी प्रकट किए बिना। एक नई हैशिंग योजना के माध्यम से, पिछले अत्याधुनिक समाधान की कम्प्यूटेशनल जटिलता को O(M(Nlog⁡M/t)2t)O(M(N \log{M}/t)^{2t}) से घटाकर O(t2M(Nt))O(t^2M\binom{N}{t}) कर दिया गया है, जहां M डेटासेट आकार को दर्शाता है। यह कमी प्रोटोकॉल को वास्तविक नेटवर्क लॉग पर लागू करना व्यावहारिक रूप से संभव बनाती है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

सहयोगी नेटवर्क घुसपैठ पहचान का मूल समस्या यह है कि गोपनीयता की रक्षा करते हुए बहु-संस्थागत हमलों की पहचान कैसे की जाए। अनुसंधान से पता चलता है कि 75% संस्थागत हमले एक दिन के भीतर दूसरी संस्था में फैल जाते हैं, और 40% से अधिक एक घंटे के भीतर फैल जाते हैं। हमलावर आमतौर पर कुछ बाहरी IP पते का उपयोग करके एक साथ कई संस्थाओं पर हमला करते हैं। यदि कोई बाहरी IP एक विशिष्ट समय विंडो के भीतर कम से कम t संस्थाओं से जुड़ता है, तो इसे 95% रिकॉल दर के साथ दुर्भावनापूर्ण के रूप में वर्गीकृत किया जा सकता है।

गोपनीयता चुनौतियां

पारंपरिक विधियों के लिए संस्थाओं को नेटवर्क लॉग को सादे पाठ में साझा करने की आवश्यकता होती है, जो गंभीर गोपनीयता जोखिम लाती है:

  1. कानूनी अनुपालन: IP पते को GDPR, PIPEDA, CCPA आदि कानूनों द्वारा व्यक्तिगत पहचान योग्य जानकारी के रूप में मान्यता दी जाती है
  2. डेटा संवेदनशीलता: कच्चा नेटवर्क डेटा सुरक्षा सतर्कताओं की तुलना में अधिक संवेदनशील है, जिसमें बहुत सारी अप्रासंगिक संवेदनशील जानकारी होती है
  3. डेटा स्केल: कच्चा डेटा सुरक्षा सतर्कताओं की तुलना में कई परिमाण बड़ा है, जो मौजूदा समाधानों को कम्प्यूटेशनल रूप से अव्यावहारिक बनाता है

मौजूदा विधियों की सीमाएं

  • Kissner और Song 26: O(N) संचार दौर की आवश्यकता है, कम्प्यूटेशनल जटिलता O(N³M³)
  • Mahdavi et al. 34: हालांकि संचार जटिलता में सुधार हुआ है, लेकिन कम्प्यूटेशनल लागत अभी भी बहुत अधिक है, जटिलता O(M(N logM/t)²ᵗ) है

मुख्य योगदान

  1. नई हैशिंग योजना: एक नवीन हैशिंग एल्गोरिदम प्रस्तावित किया गया है जो कम्प्यूटेशनल जटिलता को O(M(N logM/t)²ᵗ) से घटाकर O(t²M(N choose t)) करता है, M के लिए रैखिक जटिलता प्राप्त करता है
  2. व्यावहारिकता में वृद्धि: प्रोटोकॉल को वास्तविक पैमाने के नेटवर्क लॉग को संभालने में सक्षम बनाता है, 33 भाग लेने वाली संस्थाओं और अधिकतम 144,045 IP के सेटअप में 170 सेकंड में पहचान पूरी करता है
  3. दोहरी तैनाती विकल्प:
    • कोलूजन-प्रतिरोधी तैनाती: मजबूत सुरक्षा गारंटी प्रदान करता है, लेकिन संचार ओवरहेड अधिक है
    • गैर-इंटरैक्टिव तैनाती: गैर-कोलूजन संग्राहक मान लेता है, संचार लागत में काफी कमी करता है
  4. सुरक्षा प्रमाण: अर्ध-ईमानदार बहु-पक्षीय कम्प्यूटेशन मॉडल के तहत प्रोटोकॉल की सुरक्षा साबित की गई है
  5. व्यावहारिक सत्यापन: CANARIE IDS परियोजना के वास्तविक नेटवर्क लॉग का उपयोग करके मूल्यांकन किया गया

विधि विवरण

कार्य परिभाषा

ओवर-थ्रेशोल्ड मल्टीपार्टी प्राइवेट सेट इंटरसेक्शन (OT-MP-PSI):

  • इनपुट: N प्रतिभागी, प्रत्येक के पास अधिकतम M तत्वों का सेट Si
  • आउटपुट: कम से कम t सेट में दिखाई देने वाले तत्वों की पहचान, थ्रेशोल्ड से नीचे के तत्वों के बारे में कोई जानकारी प्रकट न करना
  • बाधा: अर्ध-ईमानदार सुरक्षा मॉडल, प्रतिभागी प्रोटोकॉल का पालन करते हैं लेकिन अतिरिक्त जानकारी सीखने का प्रयास कर सकते हैं

मुख्य तकनीकी घटक

1. Shamir गुप्त साझाकरण

(t,n) थ्रेशोल्ड योजना का उपयोग करते हुए, कोई भी t पक्ष गुप्त V को पुनर्निर्माण कर सकता है, t से कम पक्ष कोई जानकारी प्राप्त नहीं कर सकते:

P(x) = c_{t-1}x^{t-1} + c_{t-2}x^{t-2} + ... + c_1x + V

2. विस्मृत छद्म-यादृच्छिक फ़ंक्शन (OPRF)

प्रतिभागी H_K(x) सीखते हैं लेकिन कुंजी K को नहीं समझते, कुंजी धारक इनपुट x या आउटपुट मान को नहीं समझते।

3. विस्मृत छद्म-यादृच्छिक गुप्त साझाकरण (OPR-SS)

गुप्त साझाकरण और OPRF की सुरक्षा गुणों को जोड़ता है, प्रतिभागियों को कुंजी धारक से अद्वितीय गुप्त शेयर प्राप्त करने की अनुमति देता है।

प्रोटोकॉल आर्किटेक्चर

गैर-इंटरैक्टिव तैनाती

  1. शेयर निर्माण: प्रत्येक प्रतिभागी अपने सेट में प्रत्येक तत्व के लिए गुप्त शेयर बनाता है
  2. हैशिंग मैपिंग: नई हैशिंग योजना का उपयोग करके शेयर को आकार 1 के बाल्टी में मैप करता है
  3. पुनर्निर्माण: संग्राहक Lagrange इंटरपोलेशन के लिए सभी t प्रतिभागियों के संयोजन का प्रयास करता है
  4. परिणाम सूचना: संग्राहक प्रतिभागियों को सफल पुनर्निर्माण किए गए सूचकांकों के बारे में सूचित करता है

कोलूजन-प्रतिरोधी तैनाती

साझा कुंजी के बजाय OPR-SS प्रोटोकॉल का उपयोग करता है, बहु-कुंजी OPRF प्रोटोकॉल के माध्यम से हैशिंग फ़ंक्शन की गणना करता है, मजबूत कोलूजन प्रतिरोध प्रदान करता है।

तकनीकी नवाचार बिंदु

नई हैशिंग योजना

मुख्य विचार: टकराव को समायोजित करने के बजाय टकराव से बचने के लिए आकार 1 की बाल्टी का उपयोग करना:

  1. टकराव हैंडलिंग: जब कई तत्व एक ही बाल्टी में मैप होते हैं, तो छद्म-यादृच्छिक सॉर्टिंग का उपयोग करके सबसे छोटा चुनना
  2. बहु-तालिका रणनीति: प्रत्येक प्रतिभागी कई तालिकाएं बनाता है, यह सुनिश्चित करता है कि खोए हुए मान अन्य तालिकाओं में दिखाई देते हैं
  3. विफलता संभावना नियंत्रण: 20 तालिकाओं के माध्यम से विफलता संभावना को 2⁻⁴⁰ से नीचे नियंत्रित करना

मुख्य लाभ:

  • संग्राहक को शेयर संयोजनों के बजाय केवल प्रतिभागी संयोजनों का प्रयास करना होता है
  • जटिलता घातांकीय से रैखिक (M के संबंध में) तक कम हो जाती है
  • पारंपरिक बकेटिंग विधि के बड़े स्थिर कारकों से बचा जाता है

अनुकूलन तकनीकें

  1. सॉर्टिंग उलटा करना: लगातार दो तालिकाएं एक ही सॉर्टिंग फ़ंक्शन का उपयोग करती हैं, सम तालिकाएं सॉर्टिंग को उलट देती हैं
  2. खाली बाल्टी उपयोग: दूसरा सम्मिलन पहले सम्मिलन के बाद खाली बाल्टी का उपयोग करता है

प्रायोगिक सेटअप

डेटासेट

  • वास्तविक डेटा: CANARIE IDS परियोजना के 54 संस्थाओं के नेटवर्क कनेक्शन लॉग
  • समय सीमा: 1-8 नवंबर 2023, प्रतिदिन लगभग 80 बिलियन लॉग प्रविष्टियां
  • डेटा स्केल: प्रतिदिन लगभग 700GB (gzip संपीड़न)
  • प्रसंस्करण विधि: प्रति घंटा बैच में प्रसंस्करण, बाहरी IP से आंतरिक IP तक कनेक्शन निकालना

मूल्यांकन मेट्रिक्स

  • पुनर्निर्माण समय: संग्राहक द्वारा पुनर्निर्माण पूरा करने का समय
  • शेयर जनरेशन समय: एकल प्रतिभागी द्वारा शेयर बनाने का समय
  • संचार जटिलता: प्रोटोकॉल का कुल संचार ओवरहेड
  • सही होना: विफलता संभावना सत्यापन

तुलना विधियां

  • Mahdavi et al. 34: वर्तमान अत्याधुनिक OT-MP-PSI समाधान
  • सैद्धांतिक सीमा: गणना की गई विफलता संभावना की ऊपरी सीमा के साथ तुलना

कार्यान्वयन विवरण

  • प्रोग्रामिंग भाषा: Julia, 430 पंक्तियों का कोड
  • क्रिप्टोग्राफी लाइब्रेरी: SHA.jl, Nettle.jl
  • परिमित क्षेत्र: 61-बिट Mersenne अभाज्य
  • हार्डवेयर वातावरण: 8×Intel Xeon E7-8870 प्रोसेसर, 80 भौतिक कोर, 1TB मेमोरी

प्रायोगिक परिणाम

मुख्य परिणाम

प्रदर्शन तुलना

Mahdavi et al. 34 की तुलना में:

  • गति में सुधार: कम से कम दो परिमाण, अधिकतम 23,066 गुना
  • स्केलेबिलिटी: M=10⁵ पर, यह विधि सैकड़ों सेकंड की आवश्यकता है, तुलना विधि को दिन लगते हैं

वास्तविक डेटा प्रदर्शन

CANARIE डेटा पर प्रदर्शन:

  • औसत पुनर्निर्माण समय: 170 सेकंड
  • अधिकतम पुनर्निर्माण समय: 438 सेकंड (40 संस्थाएं, 220,011 IP)
  • औसत भाग लेने वाली संस्थाएं: 33
  • औसत अधिकतम सेट आकार: 144,045 IP

जटिलता विश्लेषण

कम्प्यूटेशनल जटिलता

  • संग्राहक: O(t²M(N choose t))
  • प्रतिभागी (गैर-इंटरैक्टिव): O(tM)
  • विशेष मामले: N=t=2 पर O(M), N=t पर O(N²M)

संचार जटिलता

  • गैर-इंटरैक्टिव तैनाती: O(tMN)
  • कोलूजन-प्रतिरोधी तैनाती: O(tkMN), 5 दौर संचार

सही होने का सत्यापन

  • सैद्धांतिक विफलता संभावना: 2⁻⁴⁰
  • प्रायोगिक सत्यापन: 10⁷ परीक्षणों में, वास्तविक विफलताएं सैद्धांतिक ऊपरी सीमा से बहुत कम हैं
  • तालिका संख्या अनुकूलन: सैद्धांतिक 28 तालिकाओं से व्यावहारिक 20 तालिकाओं तक अनुकूलित

संबंधित कार्य

OT-MP-PSI समाधान

  1. Kissner और Song 26: पहला समाधान, बहुपद वलय प्रतिनिधित्व का उपयोग, O(N³M³) जटिलता
  2. Mahdavi et al. 34: स्थिर दौर, O(M(N logM/t)²ᵗ) जटिलता
  3. Ma et al. 33: छोटे इनपुट सेट और छोटे डोमेन के लिए उपयुक्त, O(N|S|) जटिलता

संबंधित समस्याएं

  • थ्रेशोल्ड प्राइवेट सेट इंटरसेक्शन (TPSI): इंटरसेक्शन सीखना यदि और केवल यदि इंटरसेक्शन आकार थ्रेशोल्ड से अधिक हो
  • Quorum-PSI: OT-MP-PSI का विशेष मामला, केवल विशिष्ट प्रतिभागियों के पास आउटपुट है

हैशिंग तकनीकें

  • कोकू हैशिंग: हैशिंग टकराव से बचने के लिए, PSI प्रोटोकॉल में व्यापक रूप से लागू
  • 2D कोकू हैशिंग: दो-पक्षीय PSI के लिए डिज़ाइन किया गया, O(M) जटिलता प्राप्त करता है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. व्यावहारिकता में सफलता: पहली बार OT-MP-PSI को वास्तविक नेटवर्क लॉग पैमाने पर व्यावहारिक रूप से संभव बनाया
  2. दक्षता में सुधार: नई हैशिंग योजना के माध्यम से परिमाण स्तर का प्रदर्शन सुधार प्राप्त किया
  3. लचीली तैनाती: विभिन्न सुरक्षा आवश्यकताओं के अनुकूल दो तैनाती विकल्प प्रदान करता है
  4. व्यावहारिक सत्यापन: वास्तविक बहु-संस्थागत नेटवर्क वातावरण में प्रोटोकॉल की व्यावहारिकता सत्यापित की

सीमाएं

  1. अर्ध-ईमानदार मॉडल: हालांकि दुर्भावनापूर्ण मॉडल तक विस्तारित किया जा सकता है, फिर भी इनपुट प्रतिस्थापन हमलों के लिए असुरक्षित है
  2. सेट आकार प्रकटीकरण: मुख्य प्रोटोकॉल प्रतिभागी सेट आकार को निजी नहीं मानता है
  3. संग्राहक विश्वास: गैर-इंटरैक्टिव तैनाती को संग्राहक पर विश्वास की आवश्यकता है कि वह प्रतिभागियों के साथ कोलूजन न करे
  4. थ्रेशोल्ड सीमा: जब t N/2 के करीब हो और N बहुत बड़ा हो, तो जटिलता लाभ स्पष्ट नहीं हो सकता है

भविष्य की दिशाएं

  1. दुर्भावनापूर्ण सुरक्षा: सक्रिय हमलावरों का विरोध करने के लिए प्रोटोकॉल का विस्तार
  2. गतिशील थ्रेशोल्ड: अतिरिक्त क्लाइंट लागत के बिना बहु-थ्रेशोल्ड कम्प्यूटेशन का समर्थन
  3. बड़े पैमाने पर अनुकूलन: प्रतिभागी संयोजनों के प्रसंस्करण दक्षता में आगे सुधार
  4. गोपनीयता वृद्धि: सेट आकार जानकारी की रक्षा के लिए अंतर गोपनीयता तकनीकों की खोज

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक योगदान महत्वपूर्ण: नई हैशिंग योजना मौजूदा तकनीक में एक महत्वपूर्ण सफलता है, घातांकीय जटिलता को रैखिक तक कम करती है
  2. व्यावहारिक मूल्य अधिक: वास्तविक दुनिया के सहयोगी घुसपैठ पहचान की मुख्य गोपनीयता समस्या को हल करता है
  3. प्रयोग पर्याप्त: सैद्धांतिक विश्लेषण और वास्तविक डेटा सत्यापन दोनों, उचित प्रायोगिक सेटअप
  4. इंजीनियरिंग कार्यान्वयन पूर्ण: खुला स्रोत कार्यान्वयन प्रदान करता है, पुनरुत्पादनशीलता बढ़ाता है
  5. सुरक्षा कठोर: औपचारिक सुरक्षा प्रमाण और दो तैनाती विकल्प प्रदान करता है

कमियां

  1. सुरक्षा मॉडल सीमा: अर्ध-ईमानदार मॉडल कुछ व्यावहारिक परिदृश्यों में पर्याप्त मजबूत नहीं हो सकता है
  2. पैरामीटर चयन: 20 तालिकाओं का चयन अनुभवजन्य अनुकूलन पर आधारित है, सैद्धांतिक मार्गदर्शन अपर्याप्त है
  3. स्केलेबिलिटी सीमा: अत्यंत बड़े पैमाने (जैसे वैश्विक इंटरनेट स्तर) के लिए प्रयोज्यता पर्याप्त रूप से अन्वेषित नहीं है
  4. तुलना आधार सीमित: मुख्य रूप से एक बेंचमार्क विधि के साथ तुलना, अधिक व्यापक प्रदर्शन तुलना की कमी

प्रभाव

  1. शैक्षणिक मूल्य: बहु-पक्षीय सुरक्षित कम्प्यूटेशन क्षेत्र के लिए नया तकनीकी पथ प्रदान करता है
  2. व्यावहारिक महत्व: नेटवर्क सुरक्षा क्षेत्र की वास्तविक आवश्यकताओं को सीधे संबोधित करता है
  3. तकनीक प्रचार: हैशिंग योजना अन्य बहु-पक्षीय कम्प्यूटेशन समस्याओं पर लागू हो सकती है
  4. मानकीकरण क्षमता: सहयोगी घुसपैठ पहचान के लिए मानक प्रोटोकॉल बनने की संभावना

लागू परिदृश्य

  1. बहु-संस्थागत नेटवर्क सुरक्षा: विश्वविद्यालयों, अस्पतालों आदि जैसी समान संस्थाओं का सहयोगी सुरक्षा
  2. क्लाउड सुरक्षा सेवाएं: सुरक्षा संचालन केंद्र की गोपनीयता-संरक्षित लॉग विश्लेषण
  3. खतरा बुद्धिमत्ता साझाकरण: गोपनीयता बाधाओं के तहत खतरा संकेतक विनिमय
  4. अनुपालन आवश्यकताएं: GDPR जैसे गोपनीयता नियमों को संतुष्ट करने वाला डेटा सहयोग

संदर्भ

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

समग्र मूल्यांकन: यह एक उच्च-गुणवत्ता वाला अनुप्रयुक्त क्रिप्टोग्राफी पेपर है जो सैद्धांतिक नवाचार और व्यावहारिक अनुप्रयोग के बीच अच्छा संतुलन प्राप्त करता है। प्रस्तावित नई हैशिंग योजना न केवल सैद्धांतिक रूप से महत्वपूर्ण सफलता है, बल्कि व्यावहारिक अनुप्रयोग में भी उल्लेखनीय मूल्य प्रदर्शित करती है। पेपर का प्रायोगिक सत्यापन पर्याप्त है, सुरक्षा विश्लेषण कठोर है, और यह सहयोगी नेटवर्क सुरक्षा क्षेत्र के लिए महत्वपूर्ण तकनीकी योगदान प्रदान करता है।