🔢 गणित

Constructing Complete Permutations via the D-Class of Locally Crooked Permutations

यह शोध पत्र स्थानीय संयुग्मन (local conjugations) के माध्यम से पूर्ण क्रमपरिवर्तनों (complete permutations) को अभिलक्षणित और निर्मित करने के लिए $\mathbb{F}_{2^{n+1}}$ पर $D$ -वर्ग के क्रमपरिवर्तनों को प्रस्तुत करता है, जो उनके बीजगणितीय गुणों, क्रिप्टोग्राफिक सीमाओं और CCZ-असमतुल्यता (CCZ-inequivalence) को स्थापित करते हुए ऐसे एल्गोरिदम प्रस्तुत करता है जो नए $\delta=4$ पूर्ण क्रमपरिवर्तनों को सफलतापूर्वक गणन (enumerate) करते हैं।

मूल लेखक: Li Shuai

प्रकाशित 2026-10-16

📖 7 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Li Shuai

मूल पेपर CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

आधुनिक डिजिटल सुरक्षा की छिपी हुई वास्तुकला में, पूर्ण क्रमपरिवर्तनों (complete permutations) के रूप में ज्ञात गणितीय वस्तुओं का एक वर्ग मौजूद है। ये केवल संख्याओं के यादृच्छिक फेरबदल नहीं हैं; ये अत्यधिक संरचित पुनर्व्यवस्थाएँ हैं जहाँ किसी वस्तु को उसके पुराने स्थान से नए स्थान पर ले जाने की क्रिया और उसे उसके पुराने और नए स्थानों के योग वाले स्थान पर ले जाने की क्रिया, दोनों ही एक पूर्ण, गैर-अतिव्यापी (non-overlapping) व्यवस्था का परिणाम देती हैं। यह दोहरी आवश्यकता प्रतिस्थापन बक्सों (substitution boxes), या S-बॉक्सों के डिजाइन के लिए महत्वपूर्ण है, जो एन्क्रिप्शन प्रणालियों के प्राथमिक घटक हैं जो अर्थ को छिपाने के लिए डेटा को अस्त-व्यस्त करते हैं। यदि ये घटक बहुत अधिक अनुमानित (predictable) हैं, तो एन्क्रिप्शन को तोड़ा जा सकता है; यदि वे बहुत अधिक अराजक हैं, तो वे अक्षम हो जाते हैं। क्रिप्टोग्राफरों के लिए चुनौती लंबे समय से एक 'स्वीट स्पॉट' खोजने की रही है: ऐसे क्रमपरिवर्तन जो परिष्कृत हमलों का प्रतिरोध करने के लिए पर्याप्त जटिल हों और फिर भी तेजी से लागू करने के लिए पर्याप्त संरचित हों।

निंग्ज़िया विश्वविद्यालय के ली शुआई द्वारा एक हालिया अध्ययन ज्यामितीय समरूपता (geometric symmetry) के लेंस के माध्यम से इन क्रमपरिवर्तनों के एक विशिष्ट परिवार की खोज करके इस चुनौती का समाधान करता है। यह शोध "स्थानीय टेढ़ेपन" (local crookedness) नामक एक गुण पर केंद्रित है, जो यह बताता है कि एक क्रमपरिवर्तन कैसा व्यवहार करता है जब उसके इनपुट को एक विशिष्ट मात्रा से स्थानांतरित किया जाता है। लेखक इन कार्यों की एक नई श्रेणी पेश करता है, जिसे उनके आउटपुट में परिवर्तन के पैटर्न द्वारा परिभाषित किया गया है। इन कार्यों को एक बड़े समूह के तत्वों के रूप में मानकर, जिन्हें डेटा के विशिष्ट हिस्सों को स्थानांतरित करने, घुमाने या बदलने से रूपांतरित किया जा सकता है, अध्ययन संभावनाओं के एक परिदृश्य का मानचित्र तैयार करता है। लक्ष्य यह देखना था कि क्या इस परिदृश्य के भीतर घूमना नए, बेहतर क्रमपरिवर्तन उत्पन्न कर सकता है जो डिफरेंशियल क्रिप्टोएनालिसिस (differential cryptanalysis) के विरुद्ध बेहतर सुरक्षा प्रदान करते हैं, जो एक ऐसी विधि है जहाँ हमलावर गुप्त कुंजी का पता लगाने के लिए यह अध्ययन करते हैं कि इनपुट में छोटे बदलाव आउटपुट को कैसे प्रभावित करते हैं।

इस कार्य का मुख्य भाग एक निर्माण श्रृंखला (construction chain) है जो एक ज्ञात, सुव्यवस्थित क्रमपरिवर्तन से शुरू होती है और नए क्रमपरिवर्तनों को बनाने के लिए सटीक बीजगणितीय ऑपरेशनों की एक श्रृंखला लागू करती है। लेखक नियमों का एक विशिष्ट सेट, या "D-क्लास" परिभाषित करता है जिसका पालन इन क्रमपरिवर्तनों को वैध रहने के लिए करना चाहिए। इस सेट के भीतर, शोधकर्ता यह सिद्ध करता है कि "लिफ्टेड" (lifted) क्रमपरिवर्तनों का संग्रह—वे जो एक छोटे स्थान से एक बड़े स्थान तक विस्तारित किए गए हैं—एक अद्वितीय कठोरता (rigidity) रखता है। यदि कोई केवल एक प्रकार के ऑपरेशन का उपयोग करके, जैसे कि एक साधारण शिफ्ट या एक रैखिक रोटेशन का उपयोग करके, एक एकल क्रमपरिवर्तन को बदलने का प्रयास करता है, तो परिणाम आमतौर पर एक वैध पूर्ण क्रमपरिवर्तन बने रहने में विफल रहता है। हालाँकि, अध्ययन यह प्रदर्शित करता है कि दो अलग-अलग ऑपरेशनों को एक विशिष्ट अनुक्रम में संयोजित करने से यह कठोरता टूट जाती है। यह संयोजन शोधकर्ता को संभावनाओं के स्थान में नेविगेट करने की अनुमति देता है, जिससे वह आवश्यक सुरक्षा गुणों को खोए बिना एक वैध क्रमपरिवर्तन से दूसरे तक पहुँच सकता है।

इस सैद्धांतिक ढांचे को व्यावहारिक बनाने के लिए, पेपर दो अलग-अलग एल्गोरिदम विकसित करता है। पहला एक बैकट्रैकिंग सर्च है जो शून्य से एक पूर्ण क्रमपरिवर्तन का निर्माण करता है, यह सुनिश्चित करते हुए कि प्रत्येक चरण पर दोहरी व्यवस्था संबंधी आवश्यकताओं को पूरा किया जाए। दूसरा एक ग्रीडी लोकल सर्च (greedy local search) है जो एक मौजूदा क्रमपरिवर्तन से शुरू होता है और पहले वर्णित संयुक्त ऑपरेशनों को लागू करके इसे बेहतर बनाने का प्रयास करता है। यह दूसरा एल्गोरिदम एक ऊंचे शिखर की तलाश में रहने वाले पर्वतारोही की तरह कार्य करता है: यह विभिन्न छोटे संशोधनों का परीक्षण करता है, लेकिन केवल तभी एक परिवर्तन को स्वीकार करता है जब वह क्रमपरिवर्तन की क्रिप्टोग्राफिक गुणवत्ता में स्पष्ट रूप से सुधार करता है। गुणवत्ता को दो मुख्य संकेतकों द्वारा मापा जाता है: डिफरेंशियल यूनिफॉर्मिटी (differential uniformity), जो आउटपुट पैटर्न की सबसे खराब स्थिति की आवृत्ति को गिनता है, और नॉन-लिनियरिटी (nonlinearity), जो यह मापता है कि फंक्शन एक सरल रैखिक समीकरण से कितना दूर है। कम डिफरेंशियल यूनिफॉर्मिटी और उच्च नॉन-लिनियरिटी आम तौर पर सुरक्षा के लिए बेहतर होते हैं।

शोधकर्ताओं ने 32 के आकार के एक विशिष्ट गणितीय स्थान पर इन विधियों का परीक्षण किया, जो 5-बिट सिस्टम के अनुरूप है। एक सरल, रैखिक क्रमपरिवर्तन से शुरू होकर, जो कि कमजोर माना जाता था, ग्रीडी सर्च एल्गोरिदम को सौ बार चलाया गया। प्रयोगों ने 4 की डिफरेंशियल यूनिफॉर्मिटी वाले कई क्रमपरिवर्तन दिए, जो शुरुआती मान 32 की तुलना में एक महत्वपूर्ण सुधार है। अध्ययन ने एक सौ यादृच्छिक रूप से उत्पन्न क्रमपरिवर्तनों के साथ भी शुरुआत की और उसी सर्च प्रक्रिया को लागू किया। यहाँ भी, एल्गोरिदम ने लगातार 4 की डिफरेंशियल यूनफॉर्मिटी वाले क्रमपरिवर्तन खोजे। परिणाम केवल बेहतर संख्याएं खोजने के बारे में नहीं थे; नए क्रमपरिवर्तनों के पास विशिष्ट "स्पेक्ट्रा" (spectra), या आउटपुट आवृत्तियों के पैटर्न थे जो एक-दूसरे से और शुरुआती बिंदु से भिन्न थे। यह सिद्ध करता है कि यह विधि केवल एक ही वस्तु के विविध संस्करण नहीं बनाती है, बल्कि वास्तव में सुरक्षित क्रमपरिवर्तनों के नए, विशिष्ट वर्गों की खोज करती है।

सबसे उल्लेखनीय निष्कर्षों में से एक इन नए क्रमपरिवर्तनों और APN (Almost Perfect Nonlinear) कार्यों के रूप में ज्ञात कार्यों के एक प्रसिद्ध वर्ग के बीच संबंध है। ऐतिहासिक रूप से, सुरक्षित क्रमपरिवर्तनों के निर्माण के कई निर्माण इन APN कार्यों से शुरू होने पर निर्भर रहे हैं। हालाँकि, अध्ययन ने पाया कि इस नए लोकल-कंजुगेशन (local-conjugation) विधि द्वारा उत्पन्न क्रमपरिवर्तन, जबकि उनमें 4 की समान उत्कृष्ट डिफरेंशियल यूनिफॉर्मिटी है, क्लासिक APN दृष्टिकोणों से प्राप्त क्रमपरिवर्तनों के CCZ-इनइक्विवेलेंट (CCZ-inequivalent) हैं। वास्तव में, एक प्रसिद्ध APN फंक्शन पर आधारित संदर्भ क्रमपरिवर्तन ने इस विशिष्ट परीक्षण में खराब प्रदर्शन किया, जिसकी डिफरेंशियल यूनिफॉर्मिटी 8 थी। यह सुझाव देता है कि नई विधि गणितीय परिदृश्य के एक अलग क्षेत्र की खोज करती है, उन उच्च-गुणवत्ता वाले क्रमपरिवर्तनों को उजागर करती है जो मानक निर्माण तकनीकों के लिए पहले अप्राप्य थे।

पेपर एक अनुमान (conjecture) प्रस्तावित करके समाप्त होता है जो प्रयोगात्मक साक्ष्य पर आधारित है: कि इन लिफ्टेड क्रमपरिवर्तनों का संपूर्ण स्थान जुड़ा हुआ (connected) है। दूसरे शब्दों में, ऐसा प्रतीत होता है कि इन विशिष्ट स्थानीय संशोधनों का अनुसरण करके इन क्रमपरिवर्तनों के परिवार में किसी भी वैध क्रमपरिवर्तन तक पहुँचा जा सकता है। हालाँकि इस कनेक्टिविटी को गणितीय रूप से सिद्ध नहीं किया गया है, लेकिन तथ्य यह है कि सर्च एल्गोरिदम ने विविध शुरुआती बिंदुओं से लगातार उच्च-गुणवत्ता वाले समाधान खोजे, इस विचार के लिए एक मजबूत प्रारंभिक समर्थन प्रदान करता है। अध्ययन यह प्रश्न भी खुला छोड़ देता है कि क्या इस विशिष्ट क्रमपरिवर्तन परिवार में इससे भी अधिक शक्तिशाली फंक्शन मौजूद हैं, जो संभवतः APN के रूप में ज्ञात सुरक्षा के सैद्धांतिक स्तर तक पहुँच सकते हैं। फिलहाल के लिए, यह कार्य सुरक्षित क्रमपरिवर्तन उत्पन्न करने के लिए एक मजबूत नया टूलकिट प्रदान करता है, जो यह प्रदर्शित करता है कि इन गणितीय वस्तुओं की स्थानीय समरूपता को समझकर, हम डिजिटल दुनिया के लिए बेहतर रक्षा का निर्माण कर सकते हैं।

तकनीकी सारांश: स्थानीय क्रूक्ड परम्यूटेशन के D-वर्ग के माध्यम से पूर्ण क्रमचय (Complete Permutations) का निर्माण

समस्या विवरण

यह शोध पत्र परिमित क्षेत्रों $\mathbb{F}_{2^n}$ पर पूर्ण क्रमचय (Complete Permutations - CPs) के निर्माण को संबोधित करता है। एक क्रमचय $f$ एक CP है यदि $f$ और मानचित्र $x \mapsto f(x) + x$ दोनों ही क्रमचय हैं। CPs क्रिप्टोग्राफी में अत्यंत महत्वपूर्ण हैं, विशेष रूप से लाइ-मासी (Lai–Massey) ढांचे में S-बॉक्स के निर्माण खंडों के रूप में और ऑर्थोगोनल लैटिन वर्गों को उत्पन्न करने के लिए।

यद्यपि CPs को शुआई-ली (Shuai–Li) पत्राचार के माध्यम से $\mathbb{F}_{2^{n+1}}$ पर स्थानीय क्रूक्ड क्रमचयों (Locally Crooked Permutations - LCPs) से जोड़ा गया है, पिछले तरीके एक "क्रूक्ड फलन $\to$ LCP $\to$ CP" पथ पर निर्भर थे। यह दृष्टिकोण प्रतिबंधात्मक था, क्योंकि यह स्वयं LCP वर्ग के भीतर नए LCPs की स्वतंत्र गति या पीढ़ी की अनुमति नहीं देता था। यह शोध पत्र स्वयं LCP वर्ग के भीतर आंतरिक समूह क्रियाओं (group actions) के माध्यम से नए CPs उत्पन्न करने के लिए सीधे LCP वर्ग के भीतर कार्य करके इस बाधा को दूर करने का प्रयास करता है।

कार्यप्रणाली

1. D-वर्ग और अपरिवर्तनीयता (Invariance)

लेखक D-वर्ग को परिभाषित करता है, जो $\mathbb{F}_{2^{n+1}}$ पर क्रमचयों का वह सेट है जहाँ एक निश्चित दिशा $q_1 = 2^n$ में अवकलज (derivative) का प्रतिबिंब एक निश्चित हाइपरप्लेन $H = \{x : x_n = 0\}$ का पूरक होता है।
$D = \{f \in S_q : \text{Im } \Delta_{q_1}f = K\}$
जहाँ $K = \mathbb{F}_{2^{n+1}} \setminus H$ ।

यह शोध पत्र सिद्ध करता है कि $D$ तीन विशिष्ट समूह क्रियाओं के तहत बंद (closed) है:

बायां अनुवाद (Left Translation): किसी भी $a \in \mathbb{F}_q$ के लिए $t_a \circ f$ ।
बायां गुणन (Left Multiplication): $H$ को संरक्षित करने वाले सामान्य रैखिक समूह ( $GL_H$ ) के किसी भी $g$ के लिए $g \circ f$ ।
दायां गुणन (Right Multiplication): $H$ और $K$ को बदलने वाले इनवोल्यूशन (involution) के सेंट्रलाइज़र $C$ के किसी भी $h$ के लिए $f \circ h$ ।

इसके अतिरिक्त, यह वर्ग विशिष्ट स्थानीय अनुवादों $t_{a,X}$ (एक उपसमुच्चय $X$ पर प्रतिबंधित अनुवाद) के तहत भी बंद है, बशर्ते $X$ एक विशिष्ट डायहेड्रल समूह (dihedral group) के ऑर्बिट्स का संघ हो, जो अनुवाद और संयुग्मी इनवोल्यूशन द्वारा उत्पन्न होता है।

2. कठोरता (Rigidity) और निर्माण श्रृंखला

लेखक एक लिफ्टेड CP उपवर्ग $D^\uparrow \subset D$ को परिभाषित करता है, जिसमें $D$ के वे क्रमचय शामिल हैं जो $K$ के पूरक पर पहचान (identity) के रूप में कार्य करते हैं।

कठोरता (Rigidity): शोध पत्र सिद्ध करता है कि $D^\uparrow$ ऊपर वर्णित क्लोजर गुणों में से किसी भी एकल ऑपरेशन के तहत "कठोर" (rigid) है (अनुवाद, रैखिक गुणन, या सेंट्रलाइज़र गुणन)। एक एकल ऑपरेशन किसी लिफ्टेड CP को दूसरे लिफ्टेड CP में तब तक नहीं बदल सकता जब तक कि वह पहचान (identity) न हो।
निर्माण श्रृंखला (Construction Chain): नए CPs उत्पन्न करने के लिए, लेखक एक ऑपरेशनों के उत्पाद वाली श्रृंखला का निर्माण करता है:
$CP \xrightarrow{\text{lift}} LCP \xrightarrow{\text{local translation}} LCP' \xrightarrow{\text{centralizer correction}} LCP'' \xrightarrow{\text{restriction}} \text{New } CP$
यह श्रृंखला स्थानीय अनुवादों से उत्पन्न दोष को "मरम्मत" करने के लिए स्थानीयकृत सेंट्रलाइज़र तत्वों ( $g_{a,X_1}$ और $g_{a,X_2}$ ) का उपयोग करती है, जिससे यह सुनिश्चित होता है कि परिणाम $D^\uparrow$ में बना रहे।

3. स्थानीय संयुग्मन (Local Conjugations)

निर्माण से दो विशिष्ट स्थानीय संयुग्मन प्राप्त होते हैं, $f_1$ और $f_2$ , जो आधार क्षेत्र $\mathbb{F}_{2^n}$ पर परिभाषित हैं:

$f_1$ : $H \subset X_1$ पर $f$ का एक संशोधन, जहाँ $X_1$ एक डायहेड्रल समूह के तहत अपरिवर्तनीय है।
$f_2$ : $X_2$ पर $f$ के व्युत्क्रम (inverse) को शामिल करने वाला एक संशोधन, जहाँ $X_2$ एक चक्रीय समूह (cyclic group) के तहत अपरिवर्तनीय है।
शोध पत्र आवश्यक और पर्याप्त शर्तें प्रदान करता है कि ये संशोधित मानचित्र CPs बने रहें।

4. एल्गोरिदम

सिद्धांत को लागू करने के लिए दो एल्गोरिदम प्रस्तुत किए गए हैं:

रैंडम बैकट्रैकिंग सर्च (Random Backtracking Search): $f(x)$ और $f(x)+x$ पर बाधाओं को बनाए रखते हुए शून्य से रैंडम CPs उत्पन्न करता है।
ग्रीडी लोकल सर्च (Greedy Local Search): एक बीज (seed) CP पर स्थानीय संयुग्मन ( $f_1, f_2$ ) को पुनरावृत्ति से लागू करता है। यह केवल तभी चाल स्वीकार करता है जब वह पूर्ण विभेदक स्पेक्ट्रम (DDT) और वाल्श स्पेक्ट्रम (Walsh spectrum) पर आधारित एक गुणवत्ता फलन में सुधार करता है।

मुख्य परिणाम

सैद्धांतिक योगदान

अपरिवर्तनीयता प्रमाण: स्थापित किया कि $D$ -वर्ग निर्दिष्ट समूह क्रियाओं और स्थानीय अनुवादों के तहत अपरिवर्तनीय है।
कठोरता प्रमेय (Rigidity Theorem): सिद्ध किया कि $D^\uparrow$ एकल ऑपरेशनों द्वारा उत्पन्न नहीं किया जा सकता, जिससे संयुक्त निर्माण श्रृंखला की आवश्यकता सिद्ध होती है।
CCZ-असमतुल्यता मानदंड (CCZ-Inequivalence Criteria): यह निर्धारित करने के लिए मानदंड निकाले कि कब नव-निर्मित CPs बीज (seed) के CCZ-असमतुल्य नहीं हैं। यह यह जाँचने पर निर्भर करता है कि क्या विभेदक वितरण तालिका (DDT) या निरपेक्ष वाल्श गुणांकों का मल्टीसेट बदल जाता है।
क्रिप्टोग्राफिक सीमाएँ: स्थानीय संशोधनों के तहत विभेदक एकरूपता ( $\delta$ ), गैर-रैखिकता ($nl $), और बीजगणितीय घात ($ \deg $) के लिए सीमाएँ प्राप्त की गईं।$ \delta $अधिकतम$ 2m $से बदलता है, जहाँ$ m$ संशोधित उपसमुच्चय का आकार है।

प्रयोगात्मक निष्कर्ष

प्रयोग $H \cong \mathbb{F}_{2^5}$ (32 तत्व) पर किए गए:

$\delta=4$ CPs का निर्माण: एक रैखिक बीज ( $\delta=32$ ) और रैंडम बीजों से शुरू होकर, ग्रीडी सर्च ने सफलतापूर्वक कई पूर्ण क्रमचय $\delta=4$ के साथ खोजे।
विशिष्ट स्पेक्ट्रा: निर्मित CPs ने एक-दूसरे के और एक संदर्भ डिलन-आधारित (Dillon-based) CP (जिसका $\delta=8$ था) के विशिष्ट विभेदक स्पेक्ट्रा प्रदर्शित किए।
CCZ-असमतुल्यता: विशिष्ट विभेदक स्पेक्ट्रा पुष्टि करते हैं कि निर्माण नए CCZ-असमतुल्य वर्गों का उत्पादन करता है, न कि केवल बीज के अफ़ाइन वेरिएंट का।
कनेक्टिविटी का साक्ष्य: विभिन्न रैंडम बीजों से समान संकेतक वितरणों (indicator distributions) की ओर बार-बार अभिसरण (convergence) प्रारंभिक साक्ष्य प्रदान करता है कि $D^\uparrow$ का सेट स्थानीय-संयुग्मन चालों के तहत जुड़ा हुआ (connected) हो सकता है।

महत्व और दावे

शोध पत्र का दावा है कि यह क्रूक्ड फलनों पर निर्भरता के बिना, LCP वर्ग की आंतरिक संरचना का लाभ उठाकर नए पूर्ण क्रमचयों को उत्पन्न करने के लिए एक व्यवस्थित बीजगणितीय ढांचा प्रदान करता है।

क्रूक्ड फलनों से परे: क्रूक्ड फंक्शन से शुरू होने वाले पिछले तरीकों के विपरीत, यह दृष्टिकोण CPs खोजने के लिए LCP स्थान का अन्वेषण करने की अनुमति देता है।
क्रिप्टोग्राफिक उपयोगिता: यह विधि सफलतापूर्वक कम विभेदक एकरूपता ( $\delta=4$ ) वाले CPs बनाती है, जो S-बॉक्स के लिए एक वांछनीय गुण है, जिन्हें मानक क्रूक्ड-फंक्शन पत्राचार के माध्यम से बनाना पहले कठिन था।
संरचनात्मक अंतर्दृष्टि: $D^\uparrow$ की "कठोरता" और स्थानीय अनुवादों को "मरम्मत" करने में सेंट्रलाइज़र की विशिष्ट भूमिका की पहचान, LCPs और CPs के बीच के संबंध की गहरी सैद्धांतिक समझ प्रदान करती है।
खुले प्रश्न: लेखक $D^\uparrow$ की कनेक्टिविटी और इस वर्ग के भीतर APN फलनों के अस्तित्व को खुले प्रश्नों के रूप में प्रस्तुत करते हैं, यह सुझाव देते हुए कि जबकि प्रयोग कनेक्टिविटी का समर्थन करते हैं, एक औपचारिक प्रमाण की आवश्यकता है। उन्होंने यह भी नोट किया कि हालांकि परिणाम APN क्रमचयों के साथ एक संभावित लिंक का सुझाव देते हैं, लेकिन इस कार्य में स्पष्ट रूप से कोई APN क्रमचय स्थापित नहीं किए गए हैं।