Permutation Polynomials Under Multiplicative-Additive Perturbations: Characterization via Difference Distribution Tables

यहाँ दत्ता, स्टैनिचा और मंडल के शोध पत्र "Permutation Polynomials Under Multiplicative-Additive Perturbations: Characterization via Difference Distribution Tables" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र परिमित क्षेत्रों (finite fields) $\mathbb{F}_{p^n}$ पर c-डिफरेंशियल क्रिप्टैनालिसिस (c-differential cryptanalysis) के विरुद्ध क्रमचय बहुपदों (permutation polynomials) की सुरक्षा को संबोधित करता है, जो कि शास्त्रीय डिफरेंशियल क्रिप्टैनालिसिस का एक सामान्यीकरण है।

• संदर्भ: हालिया क्रिप्टैनालिसिस (विशेष रूप से कुज़नेचिक (Kuznyechik) सिफर के विरुद्ध) ने इस बात पर प्रकाश डाला है कि मानक डिफरेंशियल यूनिफॉर्मिटी अपर्याप्त है; हमलावर $D_{c,a}F(x) = F(x+a) - cF(x)$ के रूप में c-डिफरेंशियल का लाभ उठाते हैं।
• मुख्य प्रश्न: एक फलन को परफेक्ट c-नॉनलीन (PcN) कहा जाता है यदि, एक निश्चित $c \neq 0, 1$ के लिए, मानचित्र $x \mapsto F(x+a) - cF(x)$ सभी गैर-शून्य शिफ्ट $a$ के लिए एक क्रमचय (permutation) है। यह शोध पत्र निम्नलिखित उद्देश्यों को पूरा करने का प्रयास करता है:
  1. PcN गुण को कुशलतापूर्वक अभिलक्षणित (characterize) और सत्यापित करना।
  2. PcN फलनों के संरचनात्मक व्यवहार को समझना (जैसे: मोनोमियल्स बनाम सामान्य बहुपदों का व्यवहार)।
  3. PCN और अन्य क्रिप्टोग्राफिक गुणों जैसे 'ऑलमोस्ट परफेक्ट नॉनलीनियर' (APN) के बीच संबंध निर्धारित करना।
  4. एफाइन रूपांतरणों (affine transformations) और नॉन-लिनियैरिटी बाधाओं के तहत अपरिवर्तनीयता का विश्लेषण करना।

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

लेखक बीजगणितीय संयोजन (algebraic combinatorics), परिमित क्षेत्र सिद्धांत (finite field theory), और स्पेक्ट्रल विश्लेषण (spectral analysis) के संयोजन का उपयोग करते हैं।

• डिफरेंस डिस्ट्रीब्यूशन टेबल (DDT) लिंकेज: प्राथमिक कार्यप्रणाली संबंधी सफलता शास्त्रीय DDT ($\Delta_F(a, b)$) के साथ c-डिफरेंशियल गुण को जोड़ना है, जो $F(x+a) - F(x) = b$ के समाधानों की गणना करता है। यह प्रत्येक $c$ के लिए गणनात्मक रूप से महंगे c-DDT की गणना करने की आवश्यकता को समाप्त करता है।
• बीजगणितीय अपघटन (Algebraic Decomposition): लेखक $F(x+a) - cF(x) = b$ की स्थिति को शास्त्रीय अवकलज (classical derivative) $D_a F$ से जुड़ी स्थितियों में विघटित करते हैं।
• स्पेक्ट्रल विश्लेषण: वे Walsh-Hadamard ट्रांसफॉर्म का उपयोग करके नॉन-लिनियैरिटी पर सीमाएँ (bounds) स्थापित करने और c-DDT तथा लीनियर एप्रोक्सिमेशन टेबल (LAT) के बीच संबंध स्थापित करने के लिए करते हैं।
• ज्यामितीय व्याख्या: "बुरे शिफ्ट्स" (bad shifts) के सेट का (जहाँ c-डेरिवेटिव एक क्रमचय विफल हो जाता है) एक उपसमष्टि (subspace) संरचना के रूप में विश्लेषण किया गया है।

3. प्रमुख योगदान और परिणाम (Key Contributions and Results)

A. शास्त्रीय DDT के माध्यम से कुशल अभिलक्षणन

सबसे महत्वपूर्ण योगदान प्रमेय 3.2 (Theorem 3.2) है, जो केवल शास्त्रीय DDT का उपयोग करके एक क्रमचय बहुपद $F$ के PcN होने के लिए एक आवश्यक और पर्याप्त शर्त प्रदान करता है:

• प्रमेय: $F$ PcN है यदि और केवल यदि सभी गैर-शून्य $a, b \in \mathbb{F}_{p^n}$ के लिए:
  $$\Delta_F(a, b) \cdot \Delta_F(a, c^{-1}b) = 0$$
• निहितार्थ: यह सत्यापन जटिलता को $O(p^{3n})$ (सभी ट्रिपल्स के लिए नैटिव चेकिंग) से घटाकर $O(p^{2n})$ (पूर्व-निर्धारित DDT के आधार पर) कर देता है। यह दिए गए फलन के लिए सभी वैध $c$ मानों को $O(p^{3n})$ में कुशलतापूर्वक सूचीबद्ध करने की अनुमति भी देता है।

B. संरचनात्मक द्वैत और उपसमष्टि (Structural Dichotomies and Subspaces)

• मोनोमियल द्वैत (Monomial Dichotomy - Theorem 3.8): $\mathbb{F}_{2^n}$ पर मोनोमियल क्रमचय $F(x) = ax^d$ के लिए, PcN गुण एक सख्त "सब-या-कुछ-नहीं" (all-or-nothing) व्यवहार प्रदर्शित करता है। या तो $F(x+\alpha) + cF(x)$ सभी गैर-शून्य $\alpha$ के लिए एक क्रमचय है, या किसी के लिए भी नहीं। यह मोनोमियल्स की समरूपता (homogeneity) का सीधा परिणाम है।
• सामान्य बहुपदों के लिए प्रति-उदाहरण: लेखक एक प्रति-उदाहरण ($\mathbb{F}_{2^5}$ पर $F(x) = x^3 + x^5$) प्रदान करते हैं जो दर्शाता है कि सामान्य बहुपदों के लिए यह द्वैत विफल हो जाता है।
• बुरे शिफ्ट्स की उपसमष्टि (Subspace of Bad Shifts - Proposition 3.11 & Theorem 3.12): उन शिफ्ट $a$ का सेट जिनके लिए $F(x+a) - cF(x)$एक क्रमचय नहीं है (0 के साथ),$\mathbb{F}_{p^n}$ की एक उपसमष्टि (subspace) बनाता है। इसका तात्पर्य यह है कि यदि कोई फलन शिफ्ट के आधार (basis) के लिए PcN होने में विफल रहता है, तो वह सभी गैर-शून्य शिफ्ट के लिए विफल हो जाता है।

C. APN गुणों के साथ असंगति (Incompatibility with APN Properties)

• प्रमेय 3.29: यह शोध पत्र कई $c$ मानों के लिए APN (Almost Perfect Nonlinear, $\delta=2$) और PcN के बीच एक मौलिक असंगति को सिद्ध करता है।
  • एक APN क्रमचय अधिकतम दो $c$ मानों के लिए (विशेष रूप से एक युग्म $\{c, c^{-1}\}$) PcN हो सकता है।
  • आमतौर पर, APN क्रमचय किसी भी $c \neq 0, 1$ के लिए PCN नहीं होते हैं।
  • यह एक ट्रेड-ऑफ को प्रकट करता है: c-डिफरेंशियल हमलों के विरुद्ध प्रतिरोध को अनुकूलित करने से अक्सर शास्त्रीय डिफरेंशियल हमलों के विरुद्ध प्रतिरोध से समझौता होता है।

D. एफाइन तुल्यता और अपरिवर्तनीयता (Affine Equivalence and Invariance)

• अपरिवर्तनीयता की शर्तें: लेखक उन विशिष्ट एफाइन रूपांतरणों की पहचान करते हैं जो c-डिफरेंशियल यूनिफॉर्मिटी को संरक्षित करते हैं।
  • यदि $G = A_1 \circ F \circ A_2$ है, और $A_1$ में फ्रोबेनियस ऑटोमोर्फिज्म ($x \mapsto x^p$) शामिल है, तो c-पैरामीटर $c \mapsto c^{1/p}$ में बदल जाता है।
  • वे अभिलक्षणित करते हैं कि कब एक PcN फलन को एक लीनियर क्रमचय $L$ के साथ संयोजित करने से दूसरा PcN फलन प्राप्त होता है (Theorem 4.4, 4.6)।
• असममिति (Asymmetry): शास्त्रीय डिफरेंशियल यूनिफॉर्मिटी के विपरीत, PcN गुण कार्यात्मक व्युत्क्रम (functional inversion) के तहत सामान्यतः संरक्षित नहीं होता है (अर्थात, यदि $F$ PcN है, तो $F^{-1}$ आवश्यक रूप से PcN नहीं है)।

E. नॉन-लिनियैरिटी सीमाएँ (Nonlinearity Bounds)

• स्पेक्ट्रल स्पर्सिटी (Spectral Sparsity - Corollary 5.2): एक PCN फलन के लिए, किसी भी गैर-शून्य इनपुट $a$ पर Walsh-Hadamard ट्रांसफॉर्म का सपोर्ट $b$ और $cb$ दोनों को एक साथ नहीं रख सकता है।
• सख्त सीमाएँ (Tight Bounds - Theorem 5.4): लेखक अधिकतम Walsh गुणांक पर निचली सीमाएं (lower bounds) प्राप्त करते हैं, यह सिद्ध करते हुए कि PCN फलन Sidelnikov–Chabaud–Vaudenay बाउंड (Almost Bent फलनों के लिए सीमा) प्राप्त नहीं कर सकते जब $c$ प्रिमिटिव (primitive) हो और $n$ विषम (odd) हो। यह इंगित करता है कि PcN फलनों में आमतौर पर इष्टतम APN फलनों की तुलना में कम नॉन-लिनियैरिटी होती है।

F. विशिष्ट वर्ग अभिलक्षणन (Specific Class Characterizations)

• क्वाड्रेटिक क्रमचय: ऑर्थोगोनल कॉम्प्लीमेंट्स (orthogonal complements) का उपयोग करके द्विघातीय Dembowski-Ostrom (DO) बहुपदों के लिए स्पष्ट बीजगणितीय अभिलक्षण प्रदान किए गए हैं (Theorem 3.26)।
• Gold-जैसे फलन: ट्रेस फंक्शन (trace functions) को शामिल करते हुए $x^{(2^k+1)/2}$ के रूप में फलनों के लिए स्थितियाँ प्राप्त की गई हैं (Theorem 3.5)।

4. महत्व (Significance)

• व्यावहारिक क्रिप्टैनालिसिस: यह कार्य सीधे कुज़नेचिक सिफर हमले का उत्तर देता है। $O(p^{2n})$ अभिलक्षणन क्रिप्टोग्राफरों को तेजी से यह सत्यापित करने की अनुमति देता है कि मौजूदा या प्रस्तावित सिफर्स के S-बॉक्सेस c-डिफरेंशियल हमलों के प्रति संवेदनशील हैं या नहीं।
• सैद्धांतिक आधार: यह PcN को क्रमचय बहुपद सिद्धांत के भीतर एक अलग संरचनात्मक क्षेत्र के रूप में स्थापित करता है, जो शास्त्रीय PN और APN सिद्धांतों से अलग है।
• डिज़ाइन दिशानिर्देश: यह शोध परिणाम डिज़ाइनरों को यह बताते हैं कि कई $c$ मानों के लिए PcN प्राप्त करना संरचनात्मक रूप से कठिन है (अक्सर APN फलनों के लिए असंभव) और यह नॉन-लिनियैरिटी में कमी की कीमत पर आता है।
• खुले प्रश्न: शोध पत्र यह पहचानता है कि गैर-मोनोमियल बहुपदों के लिए "सब-या-कुछ-नहीं" द्वैत को बनाए रखने के लिए किन बीजगणितीय शर्तों की आवश्यकता है, जो एक प्रमुख खुला प्रश्न है।

संक्षेप में, यह शोध पत्र c-डिफरेंशियल यूनिफॉर्मिटी के विश्लेषण के लिए पहला कुशल कम्प्यूटेशनल ढांचा प्रदान करता है, PcN फलनों के गहरे संरचनात्मक प्रतिबंधों को प्रकट करता है, और c-डिफरेंशियल प्रतिरोध और अन्य क्रिप्टोग्राफिक मेट्रिक्स के बीच अंतर्निहित ट्रेड-ऑफ को स्पष्ट करता है।