Property-Preserving Hashing for $\ell_1$-Distance Predicates: Applications to Countering Adversarial Input Attacks

यहाँ असगर, झांग और काफ़र के शोध पत्र "Property-Preserving Hashing for $\ell_1$-Distance Predicates: Applications to Countering Adversarial Input Attacks" का विस्तृत तकनीकी सारांश दिया गया है।

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

संदर्भ: परसेप्चुअल हैशिंग (Perceptual hashing) का उपयोग छवियों की समानता का पता लगाने के लिए व्यापक रूप से किया जाता है (जैसे कॉपीराइट सुरक्षा, चेहरा पहचान, या सामग्री मॉडरेशन के लिए), जो संकुचित हैश डाइजेस्ट (compact hash digests) उत्पन्न करता है जो दृश्य समानता को बनाए रखते हैं।
भेद्यता (The Vulnerability): हाल के अध्ययन दर्शाते हैं कि परसेप्चुअल हैशिंग एडवर्सरियल इवेजन अटैक्स (adversarial evasion attacks) के प्रति संवेदनशील है। हमलावर एक छवि में छोटे, अदृश्य परिवर्तन (perturbations) पेश कर सकते हैं (अक्सर $\ell_2$-दूरी के लिए अनुकूलित), जिससे परिणामी छवि मानव को समान दिखती है लेकिन एक पूरी तरह से अलग हैश डाइजेस्ट उत्पन्न करती है, जिससे वह पहचान से बच जाती है।
अंतराल (The Gap): मानक परसेप्चुअल हैशिंग संभावabilistic समानता गारंटी पर निर्भर करती है, जिसका अर्थ है कि समान छवियों द्वारा अलग हैश उत्पन्न करने की एक गैर-नगण्य संभावना होती है। यह "करेक्टनेस एरर" (correctness error) हमलावर को एडवर्सरियल उदाहरण तैयार करने के लिए आवश्यक स्थान (slack) प्रदान करता है।
लक्ष्य: लेखक $\ell_1$-दूरी प्रेडिकेट्स ( $\ell_1$-distance predicates) के लिए विशेष रूप से एक प्रॉपर्टी-प्रिजर्विंग हैशिंग (PPH) योजना का निर्माण करने का लक्ष्य रखते हैं। मानक हैशिंग के विपरीत, PPH गारंटी देता है कि यदि दो इनपुट एक विशिष्ट गुण (जैसे, दूरी $\le t$) को संतुष्ट करते हैं, तो उनके हैश डाइजेस्ट हमेशा "सत्य" (true) का मूल्यांकन करेंगे, भले ही हमलावर को हैश फ़ंक्शन के पैरामीटर ज्ञात हों।

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

प्रस्तावित समाधान एसिमेट्रिक $\ell_1$-दूरी (asymmetric $\ell_1$-distance) और एरर-करेक्टिंग कोड्स (error-correcting codes) पर आधारित एक नवीन PPH निर्माण है जो बहुपद बीजगणित (polynomial algebra) से व्युत्पन्न है।

A. प्रेडिकेट (The Predicate)

यह योजना दो छवियों (वेक्टरों) $x, y \in \mathbb{Z}_q^n$ के लिए एक एसिमेट्रिक $\ell_1$-दूरी प्रेडिकेट $P_{as}(x, y)$ को परिभाषित करती है:
$$P_{as}(x, y) = 1 \iff \|y \dot{-} x\|_1 < t_+ \text{ और } \|x \dot{-} y\|_1 \le t_- - \delta$$
जहाँ:

• $x \dot{-} y$ एलिमेंट-वाइज ऑपरेशन है $\max\{x_i - y_i, 0\}$।
• $\| \cdot \|_1$ मानक $\ell_1$ नॉर्म है।
• $t_+ + t_- = t$ कुल थ्रेशोल्ड है।
• $\delta$ एक छोटा पूर्णांक पैरामीटर है जो नॉन-रोबस्ट सेटिंग में फाल्स पॉजिटिव्स को कम करता है।
• यह एसिमेट्रिक परिभाषा महत्वपूर्ण है क्योंकि यह सीधे $\ell_2$-नॉर्म (यूक्लिडियन दूरी) से संबंधित है जिसका उपयोग अधिकांश एडवर्सरियल हमलों में किया जाता है, जैसा कि $\|x-y\|_2 \le \|x-y\|_1 \le \sqrt{n}\|x-y\|_2$ असमानता से स्पष्ट है।

B. निर्माण (Polynomial Mapping)

मुख्य योजना एक इमेज वेक्टर $x$ को एक परिमित क्षेत्र (finite field) $\mathbb{Z}_p$ (जहाँ $p > n$ एक अभाज्य संख्या है) पर एक बहुपद $\sigma_x(z)$ में मैप करती है:
$$\sigma_x(z) = \prod_{i=1}^n (1 - a_i z)^{x_i} \pmod{z^{t+1}}$$
यहाँ, $a = (a_1, \dots, a_n)$ $\mathbb{Z}_p$ के विशिष्ट गैर-शून्य तत्वों का एक वेक्टर है।

प्रमुख गणितीय गुण:

1. मुख्य समीकरण (Key Equation): टालिनी और रोज़ के कार्य पर आधारित, यह योजना पहचान का उपयोग करती है:
   $$\sigma_x(z) \cdot \sigma_{y \dot{-} x}(z) = \sigma_y(z) \cdot \sigma_{x \dot{-} y}(z)$$
2. इवैल्यूएशन एल्गोरिदम (evalh): यह जाँचने के लिए कि क्या $P_{as}(x, y) = 1$:
   • $\tilde{\sigma}_{x,y}(z) = \sigma_x^{-1}(z) \cdot \sigma_y(z) \pmod{z^{t+1}}$ की गणना करें।
   • इनपुट $z^{t+1}$ और $\tilde{\sigma}_{x,y}(z)$ पर एक्सटेंडेड यूक्लिडियन एल्गोरिदम (EEA) चलाएं।
   • तब तक रुकें जब तक कि शेषफल $r_k(z)$ की डिग्री $\le t_+$ न हो जाए।
   • एल्गोरिदम 1 आउटपुट देता है यदि संगत कोफैक्टर $u_k(z)$ की डिग्री $\le t_- - \delta$ है।
   • यह प्रभावी रूप से जाँचता है कि क्या "एरर" बहुपदों $\sigma_{y \dot{-} x}$ और $\sigma_{x \dot{-} y}$ की डिग्री थ्रेशोल्ड के भीतर है, जो $\ell_1$-दूरी की स्थिति के अनुरूप है।

C. सुरक्षा मॉडल (Security Model)

• मजबूती (Robustness): यह योजना 1-साइडेड एरर्स (फाल्स नेगेटिव: $P(x,y)=1$ लेकिन evalh 0 लौटाता है) के विरुद्ध मजबूत है। यह इवेजन हमलों को रोकने के लिए महत्वपूर्ण है।
• कोलिजन रेजिस्टेंस (Collision Resistance): हालांकि 0-साइडेड एरर्स (फाल्स पॉजिटिव्स) सैद्धांतिक रूप से संभव हैं, लेखक दिखाते हैं कि व्यावहारिक मापदंडों के लिए इसकी संभावना नगण्य ($p^{-\delta}$) है।
• इनवर्जन रेजिस्टेंस (Inversion Resistance): हैश डाइजेस्ट (बहुपद गुणांक) से मूल छवि $x$ को पुनः प्राप्त करना, बिना गुप्त वेक्टर $a$ के, एक कम्प्यूटेशनल रूप से कठिन कार्य है ($O(q^n)$)।

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

1. $\ell_1$-दूरी के लिए प्रथम PPH: यह $\ell_1$-दूरी प्रेडिकेट के लिए प्रॉपर्टी-प्रिज़र्विंग हैश का पहला निर्माण है। पिछले कार्य हैमिंग दूरी तक सीमित थे।
2. सैद्धांतिक सीमाएँ (Theoretical Bounds): लेखक कंप्रेशन रेश्यो (हैश डाइजेस्ट आकार $m$) पर निचली सीमाएँ प्राप्त करते हैं। वे दिखाते हैं कि छोटे थ्रेशोल्ड $t$ के लिए, उनका तंत्र सैद्धांतिक निचली सीमा ($m \approx t \log_2 n$) के करीब कंप्रेशन प्राप्त करता है, जो इमेज साइज ($n \log_2 q$) से काफी छोटा है।
3. व्यवहार्यता विश्लेषण (Feasibility Analysis): वे सिद्ध करते हैं कि सिंड्रोम लिस्ट डिकोडिंग (हैमिंग दूरी वाले PPH के लिए एक सामान्य तकनीक) $\ell_1$-दूरी के लिए व्यवहार्य नहीं है क्योंकि $\ell_1$-बॉल का आकार तेजी से बढ़ता है, जिससे संभावित उम्मीदवारों की सूची बहुत बड़ी हो जाती है। उनका बहुपद-आधारित दृष्टिकोण इस समस्या को दूर करता है।
4. एडवर्सरियल डिफेंस मैकेनिज्म: $\ell_1$-दूरी थ्रेशोल्ड को सख्ती से लागू करके, यह योजना हमलावरों को डिटेक्शन से बचने के लिए शोर (noise) को इतना बढ़ाने के लिए मजबूर करती है कि वह थ्रेशोल्ड का उल्लंघन करे। यह शोर अनिवार्य रूप से छवि की गुणवत्ता को कम कर देता है (LPIPS और पिक्सेल चेंज रेश्यो को बढ़ाकर), जिससे हमला प्रभावी रूप से विफल हो जाता है।

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

लेखकों ने galois पायथन लाइब्रेरी का उपयोग करके अपने तंत्र को लागू किया और इसे Imagenette डेटासेट (9,459 RGB छवियां, $224 \times 224$) पर टेस्ट किया।

• दक्षता (Efficiency):
  • छोटी छवियां (28x28): मूल्यांकन समय ~0.078 सेकंड है।
  • बड़ी छवियां (224x224): छवियों को 1,000 ब्लॉक्स में विभाजित करके, मूल्यांकन समय प्रति ब्लॉक ~0.0128 सेकंड है (जो अत्यधिक समानांतर योग्य/parallelizable है)।
  • जटिलता (Complexity): हैश जनरेशन $O(nt^2)$ है, और इवैल्यूएशन $O(t^2)$ है।
• एडवर्सरियल अटैक रेजिस्टेंस:
  • FGSM और PGD हमलों के खिलाफ परीक्षण किया गया।
  • डिटेक्शन से बचने के लिए (अर्थात, $\ell_1$-दूरी को $t$ थ्रेशोल्ड से अधिक करने के लिए), हमलावर को शोर पैरामीटर $\epsilon$ को बढ़ाना होगा।
  • परिणाम: उस थ्रेशोल्ड पर जहाँ हमला डिटेक्शन से बचने में सफल होता है, LPIPS स्कोर काफी बढ़ जाता है (जैसे, > 0.5), और पिक्सेल परिवर्तन अनुपात भी पर्याप्त हो जाता है। इसका मतलब है कि "इवेसिव" छवि मूल छवि के साथ धारणात्मक रूप से (perceptually) समान नहीं रह जाती है, जो हमले के उद्देश्य को विफल कर देती है।
• रूपांतरणों के प्रति मजबूती (Robustness to Transformations): यह योजना सरल रूपांतरणों (ब्राइटनेस, कंट्रास्ट) का विरोध करती है, जब तक कि वे $\ell_1$-दूरी को महत्वपूर्ण रूप से बदलने वाले परिवर्तन न हों।

5. महत्व और निष्कर्ष (Significance and Conclusion)

• प्रतिमान परिवर्तन (Paradigm Shift): यह पेपर संभावabilistic परसेप्चुअल हैशिंग से आगे बढ़कर डिटरमिनिस्टिक प्रॉपर्टी प्रिजर्वेशन की ओर बढ़ता है, जिसमें नगण्य त्रुटि दर होती है, जो उस अंतराल को बंद करता है जिसका उपयोग एडवर्सरियल हमले करते हैं।
• व्यावहारिक उपयोगिता: यह वास्तविक दुनिया में तैनाती के लिए पर्याप्त कुशल है (सब-सेकंड इवैल्यूएशन) और इसे आसानी से समानांतर (parallelize) किया जा सकता है।
• सुरक्षा निहितार्थ: यह प्रदर्शित करता है कि ऐसी इमेज वेरिफिकेशन सिस्टम बनाना संभव है जहाँ सुरक्षा (एवेजन रेजिस्टेंस) और उपयोगिता (इमेज क्वालिटी) सीधे तौर पर जुड़ी हुई हैं। एक हमलावर दृश्य रूप से स्पष्ट बदलाव किए बिना दुर्भावनापूर्ण संशोधन को छिपा नहीं सकता है।
• भविष्य का कार्य: लेखक नोट करते हैं कि जबकि उनका तंत्र एसिमेट्रिक $\ell_1$-दूरी को मजबूती से संभालता है, इसे पूर्ण मजबूती के साथ सटीक $\ell_1$-दूरी या यूक्लिडियन ($\ell_2$) दूरी तक विस्तारित करना एक खुला प्रश्न है। इसके अतिरिक्त, यह सिद्ध करना कि यह तंत्र "प्रूवेबली हाइडिंग" (indistinguishable from random) है, एक भविष्य का लक्ष्य है।

संक्षेप में, यह कार्य पारंपरिक परसेप्चुअल हैशिंग के लिए एक क्रिप्टोग्राफिक रूप से सुदृढ़, कुशल और मजबूत विकल्प प्रदान करता है, जो विशेष रूप से एडवर्सरियल इनपुट हमलों के बढ़ते खतरे का मुकाबला करने के लिए डिज़ाइन किया गया है।