The Closure of LCD-to-GI Reductions via Generalized Inner Products

तकनीकी सारांश: सामान्यीकृत आंतरिक गुणन (Generalized Inner Products) के माध्यम से LCD-से-GI न्यूनीकरण का समापन

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

रैखिक कोड (linear codes) के लिए क्रमपरिवर्तन तुल्यता समस्या (Permutation Equivalence Problem - PEP) यह पूछती है कि क्या दो दिए गए रैखिक कोड एक समन्वय क्रमपरिवर्तन (coordinate permutation) तक समान हैं। यह समस्या रैखिक कोडों के वर्गीकरण और कोड-आधारित क्रिप्टोग्राफी (जैसे, LESS सिग्नेचर स्कीम और SPECK स्कीम) के सुरक्षा विश्लेषण दोनों के लिए मौलिक है।

PEP की जटिलता ग्राफ आइसोमोर्फिज्म (Graph Isomorphism - GI) समस्या से निकटता से जुड़ी हुई है। जबकि PEP आम तौर पर कठिन माना जाता है, बार्डेट एट अल. [3] द्वारा एक महत्वपूर्ण उपलब्धि ने प्रदर्शित किया कि लीनियर कॉम्प्लीमेंट्री डुअल (LCD) कोड (वे कोड जिनका हल (hull) तुच्छ है, अर्थात $C \cap C^\perp = \{0\}$) के लिए PEP को बहुपद समय (polynomial time) में GI में न्यूनीकृत (reduce) किया जा सकता है। यह न्यूनीकरण उनके ऑर्थोगोनल प्रोजेक्टर $\Pi_C = G^T(GG^T)^{-1}G$ के माध्यम से एक भारित ग्राफ (weighted graph) को मैप करता है।

हालाँकि, यह विधि इस बात पर निर्भर करती है कि ग्राम मैट्रिक्स $GG^T$ गैर-विलक्षण (nonsingular) हो, जो इसकी प्रयोज्यता को LCD कोडों तक ही सीमित कर देती है। गैर-तुच्छ हल वाले कोड (जहाँ $\dim(\text{Hull}(C)) \ge 1$) इस विशिष्ट निर्माण द्वारा संसाधित नहीं किए जा सकते। इस शोध पत्र द्वारा संबोधित केंद्रीय प्रश्न यह है: ऑर्थोगोनल प्रोजेक्टर पद्धति का विस्तार कितना किया जा सकता है? विशेष रूप से, क्या एक भिन्न द्विपद रूप (bilinear form) का उपयोग करके गैर-तुच्छ हल वाले कोडों के लिए इसे सामान्यीकृत किया जा सकता है, और यदि हाँ, तो ऐसे न्यूनीकरण के सटीक संरचनात्मक सीमाएँ क्या हैं?

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

लेखक मानक आंतरिक गुणन को एक संरचना मैट्रिक्स $M$ द्वारा प्रतिनिधित्व किए गए किसी भी गैर-अपभ्रष्ट सममित द्विपद रूप (nondegenerate symmetric bilinear forms) में सामान्यीकृत करते हैं।

• सामान्यीकृत प्रोजेक्टर (Generalized Projectors): वे एक $M$-ड्यूल कोड $C^{\perp_M}$ और एक $M$-हल (hull) $\text{Hull}_M(C)$ को परिभाषित करते हैं। एक $M$-LCD कोड के लिए (जहाँ $\text{Hull}_M(C) = \{0\}$), वे एक सामान्यीकृत ऑर्थोगोनल प्रोजेक्टर का निर्माण करते हैं:
  $$\Pi_{C,M} = M G^T (G M G^T)^{-1} G$$
• न्यूनीकरण की स्थिति (Reduction Condition): न्यूनीकरण का मुख्य आधार पहचान $\Pi_{CP, M} = P^T \Pi_{C,M} P$ है, जहाँ $P$ एक क्रमपरिवर्तन मैट्रिक्स है। यह पहचान सुनिश्चित करती है कि यदि दो कोड क्रमपरिवर्तन-तुल्य (permutation-equivalent) हैं, तो उनके प्रोजेक्टर भारित ग्राफ के रूप में आइसोमॉर्फिक होंगे।
• $M$ का अभिलक्षण (Characterization of $M$): लेखक उन संरचना मैट्रिसेस की जांच करते हैं जो इस स्थिति को संतुष्ट करते हैं कि सभी क्रमपरिवर्तन $P$ के लिए $P M P^T = M$ (या उसका एक अदिश गुणक) हो। यह सुनिश्चित करने के लिए आवश्यक है कि प्रोजेक्टर क्रमपरिवर्तन के तहत सही ढंग से व्यवहार करे।
• गणना और एल्गोरिदम (Enumeration and Algorithms): द्विघात रूपों (विशेष रूप से वेइल के प्रमेय) पर विशेषता योगों (character sums) का उपयोग करते हुए, लेखक न्यूनीकरण योग्य कोडों की संख्या के लिए सटीक गणना सूत्र प्राप्त करते हैं। वे एक बहुपद-समय एल्गोरिदम भी निर्मित करते हैं जो दिए गए कोड युग्म को GI में न्यूनीकृत करने के लिए एक उपयुक्त $M$ खोजने का प्रयास करता है।

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

A. वैध संरचना मैट्रिसेस का अभिलक्षण (Theorem 3.5)
यह शोध पत्र सिद्ध करता है कि ऑर्थोगनल प्रोजेक्टर विधि एक वैध न्यूनीकरण ($C_1 \cong C_2 \iff \Pi_{C_1, M} \cong \Pi_{C_2, M}$) प्रदान करती है यदि और केवल यदि संरचना मैट्रिक्स $M$ का रूप निम्नलिखित हो:
$$M = aI + bJ$$
जहाँ $I$ आइडेंटिटी मैट्रिक्स है, $J$ ऑल-वन्स मैट्रिक्स है, और $a, b \in \mathbb{F}_q$ गैर-अपभ्रष्ट शर्तों ($a \neq 0$ और $a + nb \neq 0$) को संतुष्ट करते हैं। इसके अलावा कोई अन्य गैर-अपभ्रष्ट सममित द्विपद रूप इस न्यूनीकरण की अनुमति नहीं देता है। यह ऑर्थोगोनल प्रोजेक्टर दृष्टिकोण के समापन (closure) को स्थापित करता है: आप मनमाने द्विपद रूपों को चुनकर इस विधि का विस्तार नहीं कर सकते; रूप $I$ और $J$ का एक रैखिक संयोजन होना चाहिए।

B. न्यूनीकरण योग्य कोडों का पूर्ण अभिलक्षण (Theorem 4.5)
लेखक निर्धारित करते हैं कि कौन से कोड ऐसा न्यूनीकरण स्वीकार करते हैं:

• एक कोड $C$ इस विधि के माध्यम से GI-न्यूनीकरणीय (GI-reducible) है यदि और केवल यदि:
  1. $C$ एक LCD कोड है (मानक मामला, $M=I$), या
  2. $\dim(\text{Hull}(C)) = 1$ है और अद्वितीय हल वेक्टर $x$ इस प्रकार है कि $(x, \mathbf{1}) \neq 0$ (जहाँ $\mathbf{1}$ ऑल-वन्स वेक्टर है)।
• विशेषता 2 (Characteristic 2): विशेषता 2 वाले क्षेत्रों में, $(x, \mathbf{1}) \neq 0$ की स्थिति हल के किसी भी वेक्टर के लिए असंभव है (चूंकि $(x, x) = (x, \mathbf{1})^2 = 0$ का अर्थ है $(x, \mathbf{1}) = 0$)। फलस्वरूप, केवल LCD कोड ही न्यूनीकरणीय हैं।
• उच्च हल (Higher Hulls) के लिए असंभवता: $\dim(\text{Hull}(C)) \ge 2$ वाले कोड प्रमाणित रूप से इस विधि के माध्यम से न्यूनीकरणीय नहीं हैं, चाहे $M = aI + bJ$ का चुनाव कुछ भी हो।

C. गणना सूत्र (Theorem 5.3)
यह शोध पत्र $[n, k]_q$ कोडों (विषम $q$ के लिए) की गणना करने के लिए सटीक सूत्र प्रदान करता है। गणना निम्नलिखित का योग है:

1. मानक LCD कोडों की संख्या, $L(n, k, q)$।
2. समन्वय योग की स्थिति को संतुष्ट करने वाले हल-आयाम 1 वाले कोडों की संख्या, जिसे गैर-शून्य समन्वय योग वाले आइसोट्रोपिक वेक्टर्स की गणना और विशिष्ट डिस्क्रिमिनेन्ट्स वाले विशिष्ट कोटिएंट स्पेस पर LCD कोड के मास फॉर्मूला का उपयोग करके निकाला गया है।

D. न्यूनीकरण एल्गोरिदम (Section 6)
एक बहुपद-समय एल्गोरिदम प्रस्तुत किया गया है:

1. हल आयामों की जाँच करें। यदि $\ge 2$ है, तो "not GI-reducible" आउटपुट दें।
2. यदि LCD है, तो $M=I$ का उपयोग करें।
3. यदि हल आयाम 1 है, तो एक अदिश $b$ के लिए खोजें ताकि $M = I + bJ$दोनों कोडों को$M$-LCD बना दे।
4. सामान्यीकृत प्रोजेक्टर का निर्माण करें और परिणामी ग्राफ आइसोमोर्फिज्म समस्या को हल करें।

4. महत्व और दावे (Significance and Claims)

यह शोध पत्र दावा करता है कि यह ऑर्थोगोनल प्रोजेक्टर पद्धति की क्षमताओं का पूर्ण अभिलक्षण प्रदान करता है।

• समापन (Closure): यह स्पष्ट रूप से बड़े हल ($\ge 2$) वाले कोडों के लिए बार्डेट एट अल. के न्यूनीकरण को विस्तारित करने के द्वार बंद कर देता है। यह सिद्ध करता है कि यह विधि स्वाभाविक रूप से हल आयाम अधिकतम 1 (और विशेषता 2 में केवल LCD कोड) तक ही सीमित है।
• संरचनात्मक सीमाएँ: यह उस विशिष्ट बीजगणितीय संरचना ($M = aI + bJ$) की पहचान करता है जो इस न्यूनीकरण को काम करने के लिए आवश्यक है, यह दिखाते हुए कि कोई अन्य सममित द्विपद रूप इस मैपिंग को सुगम नहीं बना सकता।
• क्रिप्टोग्राफिक निहितार्थ: ये परिणाम कोड-आधारित क्रिप्टोग्राफिक स्कीम्स (जैसे SPECK) के लिए पैरामीटर चुनने हेतु एक मानदंड प्रदान करते हैं ताकि यह सुनिश्चित किया जा सके कि उनमें हल आयाम $\ge 2$ है, जिससे उन्हें इस विशिष्ट GI-न्यूनीकरण हमले के दायरे से बाहर रखा जा सके।

लेखक एक खुला प्रश्न छोड़ते हैं: क्या अन्य न्यूनीकरण रणनीतियाँ (जो ऑर्थोगनल प्रोजेक्टर पर आधारित नहीं हैं) मौजूद हैं जो $\dim(\text{Hull}(C)) \ge 2$ वाले कोडों के लिए PEP को GI में मैप कर सकती हैं, या क्या ऐसे न्यूनीकरण प्रमाणित रूप से असंभव हैं?