Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

यहाँ दक्ष पांडे के शोध पत्र "Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields" का विस्तृत तकनीकी सारांश दिया गया है।

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

लेजेंड्रे स्यूडो-रैंडम फंक्शन (Legendre PRF) एक क्रिप्टोग्राफिक प्रिमिटिव है जो अपने कम मल्टीप्लिकेटिव कॉम्प्लेक्सिटी के कारण अत्यंत मूल्यवान है, जो इसे मल्टी-पार्टी कम्प्यूटेशन (MPC) और ज़ीरो-नॉलेज प्रूफ (ZKP) के लिए अत्यधिक कुशल बनाता है। जबकि प्राइम फील्ड्स ($\mathbb{F}_p$) पर इसकी सुरक्षा अच्छी तरह से अध्ययन की गई है, थ्रूपुट को अनुकूलित करने के लिए हाल के कार्यान्वयनों में एक्सटेंशन फील्ड्स ($\mathbb{F}_{p^r}$) की ओर रुख किया गया है।

मुख्य समस्या एक्सटेंशन फील्ड्स ($\mathbb{F}_{p^r}$) पर सिंगल-डिग्री ($d=1$) लेजेंड्रे PRF की सुरक्षा है।

• संदर्भ: $\mathbb{F}_{p^r}$ में, इनपुट को पॉलिनॉमियल (बहुपदों) के रूप में एनकोड किया जाता है। पूर्णांक अंकगणित (integer arithmetic) के विपरीत, $\mathbb{F}_{p^r}$ में पॉलिनॉमियल जोड़ उच्च डिग्री तक "कैरी-ओवर" (carry-over) के बिना कोएफिशिएंट-वाइज (coefficient-wise) संचालित होता है।
• परिकल्पना (Hypothesis): यह पहले माना जाता था कि "नो-कैरी" (no-carry) गुण शास्त्रीय स्लाइडिंग-विंडो कोलिजन हमलों के लिए आवश्यक निरंतर योगात्मक प्रगति (additive progressions) को बाधित कर देगा, जिससे यह PRF को पैसिव एडवर्सरीज़ (passive adversaries) से सुरक्षित रखेगा।
• उद्देश्य: यह शोध पत्र उस धारणा को चुनौती देता है, जिसका लक्ष्य यह निर्धारित करना है कि क्या कैरी की कमी से उत्पन्न संरचनात्मक विखंडन (structural fracture) का उपयोग करके, पैसिव और एक्टिव दोनों ही मॉडलों में सीक्रेट की (secret key) को रिकवर किया जा सकता है।

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

यह शोध पत्र दो थ्रेट मॉडल्स के तहत बीजगणितीय विश्लेषण (algebraic analysis), सांख्यिकीय बाउंडिंग (statistical bounding), और एल्गोरिथमिक क्रिप्टोएनालिसिस के संयोजन का उपयोग करता है:

A. गणितीय आधार (Mathematical Foundations)

• एनकोडिंग: पूर्णांकों $n$ को बेस-$p$ एक्सपेंशन के माध्यम से $X_n(x)$ पॉलिनॉमियल के रूप में मैप किया जाता है।
• "नो-कैरी फ्रैक्चर" (The No-Carry Fracture): लेखक डिफरेंशियल $\Delta_n = X_{n+1} \oplus X_n$ का विश्लेषण करते हैं। मानक पूर्णांकों में, यह हमेशा 1 होता है। $\mathbb{F}_{p^r}$ में, कैरी प्रोपेगेशन की कमी के कारण, यह स्थिर नहीं होता है बल्कि $\{x^k + 1\}$ के सेट से मान लेता है, जो "फ्रैक्चर्ड" (fractured) अनुक्रमों के अर्थमैटिक सब-ब्लॉक्स बनाता है।
• सांख्यिकीय सीमाएँ (Statistical Bounds): पेपर हासे-वील बाउंड (Hasse-Weil bound) का उपयोग यह सिद्ध करने के लिए करता है कि कीस्ट्रीम यूनिफॉर्म डिस्ट्रीब्यूशन से सांख्यिकीय रूप से अविभेद्य (indistinguishable) है। यह स्थापित करता है कि हमले सांख्यिकीय बायस (bias) पर निर्भर नहीं हो सकते बल्कि उन्हें बीजगणितीय संरचना का शोषण करना चाहिए।

B. पैसिव थ्रेट मॉडल (Sequential Queries)

• दृष्टिकोण: एडवर्सरी एक क्रमबद्ध तरीके से इनपुट काउंटर को बढ़ाते हुए उत्पन्न की गई कीस्ट्रीम का अवलोकन करता है।
• तकनीक: लेखक एक "डिफरेंशियल सिग्नेचर" (Differential Signature) बकेटिंग तकनीक पेश करते हैं।
  • वे एक सिग्नेचर $\delta_n$ को एक शुरुआती बिंदु के सापेक्ष संचयी पॉलिनॉमियल अंतरों के अनुक्रम के रूप में परिभाषित करते हैं।
  • "फ्रैक्चर" के बावजूद, डिफरेंशियल का अनुक्रम निश्चित रूप से आवधिक (deterministically periodic) होता है।
  • हमलावर देखे गए कीस्ट्रीम विंडोज़ को उनके संरचनात्मक "आकार" (सिग्नेचर) के आधार पर इक्वीवैलेंस क्लासेस में समूहित करते हैं।
  • एक प्री-कंप्यूटेड हैश टेबल के विरुद्ध इन आकारों (shapes) का मिलान करके, हमलावर फ्रैक्चर को दरकिनार कर सकता है और की (key) को रिकवर कर सकता है।

C. एक्टिव थ्रेट मॉडल (Chosen-Query)

• दृष्टिकोण: एडवर्सरी PRF को क्वेरी करने के लिए विशिष्ट इनपुट चुन सकता है।
• तकनीक: हमलावर योगात्मक अनुक्रमों (additive sequences) को त्याग देता है और $\mathbb{F}_{p^r}^*$ के एक प्रिमिटिव एलिमेंट $g(x)$ द्वारा उत्पन्न ज्यामितीय अनुक्रम (geometric sequence) के साथ PRF को क्वेरी करता है।
• बीजगणितीय न्यूनीकरण (Algebraic Reduction):
  • लेजेंड्रे सिंबल पूरी तरह से मल्टीप्लिकेटिव है।
  • मूल्यांकन $L(g^i + K)$ को $L(K) \cdot L(g^{i+j} + 1)$ में फैक्टराइज़ किया जा सकता है, जहाँ $j$ एक डिस्क्रीट लॉगरिदम शिफ्ट है।
  • यह समस्या को एक यूनिवर्सल रेफरेंस सीक्वेंस में शिफ्ट $j$ खोजने में बदल देता है, जो प्रभावी रूप से योगात्मक फ्रैक्चर को पूरी तरह से निष्प्रभावी कर देता है।

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

1. प्रथम व्यापक विश्लेषण: यह विस्तार क्षेत्रों ($\mathbb{F}_{p^r}$) पर सिंगल-डिग्री लेजेंड्रे PRF का पूर्ण क्रिप्टोएनालिसिस प्रदान करने वाला पहला शोध पत्र है।
2. पैसिव अटैक (Shape Bucketing): यह प्रदर्शित करता है कि "नो-कैरी फ्रैक्चर" एक रक्षा नहीं बल्कि एक निश्चित आवधिकता (deterministic periodicity) है। लेखक एक नवीन डिफरेंशियल सिग्नेचर विधि प्रस्तावित करते हैं जो फ्रैक्चर्ड अनुक्रमों को क्लस्टर करती है, जिससे पैसिव की रिकवरी संभव होती है।
3. एक्टिव अटैक (Geometric Sequences): यह सिद्ध करता है कि एक एक्टिव एडवर्सरी ज्यामितीय क्वेरीज़ का उपयोग करके योगात्मक सीमाओं को पूरी तरह से दरकिनार कर सकता है। यह सख्त मल्टीप्लिकेटिव होमोमोर्फिज्म को लागू करता है, जिससे समस्या एक सरल शिफ्ट सर्च में बदल जाती है।
4. जटिलता विश्लेषण (Complexity Breakdown):
   • पैसिव कॉम्प्लेक्सिटी: $O(U \cdot p^r / M)$, जहाँ $U$ यूनिसिटी डिस्टेंस है और $M$ देखे गए बिट्स की संख्या है।
   • एक्टिव कॉम्प्लेक्सिटी: $O(p^r / M)$। यह टेबल कोलिजन हमलों के सैद्धांतिक निचले स्तर से मेल खाता है, जो सिद्ध करता है कि सिंगल-डिग्री वेरिएंट टूट चुका है।
5. सुरक्षा सीमाएँ: यह स्थापित करता है कि उच्च-डिग्री वेरिएंट ($d \ge 2$) आवश्यक हैं। पेपर तर्क देता है कि जबकि $d=2$ ज्यामितीय गुणनखंड (geometric factorization) का विरोध करता है, यह अभी भी अनुकूलित मीट-इन-द-मिडल (MITM) हमलों के प्रति संवेदनशील हो सकता है, जिससे सुझाव मिलता है कि मजबूत सुरक्षा के लिए $d \ge 3$ या $4$ की आवश्यकता है।

4. परिणाम (Results)

• $d=1$ को तोड़ना: सिंगल-डिग्री लेजेंड्रे PRF $\mathbb{F}_{p^r}$ पर दोनों पैसिव और एक्टिव मॉडलों के तहत पूरी तरह से असुरक्षित है। "नो-कैरी" गुण संरचनात्मक विश्लेषण के विरुद्ध सुरक्षा प्रदान करने में विफल रहता है।
• दक्षता: एक्टिव ज्यामितीय हमला लेजेंड्रे PRF की सुरक्षा को एक मानक टेबल कोलिजन अटैक की जटिलता तक कम कर देता है, जिसमें केवल $O(p^r/M)$ ऑपरेशन्स की आवश्यकता होती है।
• सांख्यिकीय सुरक्षा: पेपर पुष्टि करता है कि PRF सांख्यिकीय रूप से रैंडम है (कोई बायस नहीं), जिसका अर्थ है कि हमले विशुद्ध रूप से बीजगणितीय और संरचनात्मक हैं, न कि सांख्यिकीय।
• शमन (Mitigation): लेखक पुष्टि करते हैं कि सीक्रेट पॉलिनॉमियल की डिग्री बढ़ाना ($d \ge 2$) मल्टीप्लिकेटिव फैक्टराइजेशन को रोकता है, लेकिन चेतावनी देते हैं कि $d=2$ अभी भी $O(p^r)$ हमलों के प्रति संवेदनशील हो सकता है, इसलिए घातांकीय सुरक्षा मार्जिन के लिए $d \ge 3$ की सिफारिश की जाती है।

5. महत्व (Significance)

• प्रोटोकॉल सुरक्षा: यह कार्य उन MPC और ZKP प्रोटोकॉल के लिए तत्काल प्रभाव रखता है जो दक्षता के लिए लेजेंड्रे PRF को एक्सटेंशन फील्ड्स पर तैनात कर रहे हैं या करने पर विचार कर रहे हैं। यह सिंगल-डिग्री इंस्टेंशिएशन की सुरक्षा को अमान्य करता है।
• डिजाइन दिशानिर्देश: यह पेपर एक महत्वपूर्ण डिजाइन दिशानिर्देश प्रदान करता है: एक्सटेंशन फील्ड्स लीनियर PRF के लिए स्वचालित रूप से सुरक्षा नहीं बढ़ाते हैं; वास्तव में, वे विशिष्ट बीजगणितीय संरचनाएं (जैसे कैरी की कमी) पेश करते हैं जिनका शोषण किया जा सकता है यदि PRF की डिग्री नहीं बढ़ाई जाती है।
• भावी अनुसंधान: यह एक्सटेंशन फील्ड्स में क्रिप्टोएनालिसिस के लिए एक नया आधार रेखा (baseline) सेट करता है, जो उच्च-डिग्री पॉलिनॉमियल ($d \ge 3$) की आवश्यकता पर जोर देता है और उच्च-डिग्री वेरिएंट के लिए ट्शिरनहास ट्रांसफॉर्मेशन (Tschirnhaus transformations) और बीजगणितीय न्यूनीकरण के नए अनुसंधान दिशाओं का सुझाव देता है।
• पुनरुत्पादकता (Reproducibility): लेखकों ने अपने पायथन कार्यान्वयन (ज्यामितीय टेबल कोलिजन और पैसिव बकेटिंग सहित) को ओपन-सोर्स कर दिया है, जिससे तत्काल सत्यापन और आगे के अनुसंधान की सुविधा मिलती है।

निष्कर्ष: यह पेपर प्रभावी ढंग से प्रदर्शित करता है कि लेजेंड्रे PRF के लिए प्राइम फील्ड से एक्सटेंशन फील्ड में संक्रमण सिंगल-डिग्री वेरिएंट के लिए सुरक्षा अपग्रेड नहीं बल्कि एक भेद्यता (vulnerability) है जो कुशल की रिकवरी की अनुमति देती है। यह सुरक्षित रहने के लिए उच्च-डिग्री पॉलिनॉमियल निर्माण की ओर बदलाव को अनिवार्य बनाता है।