The Star Product of Uniformly Random Codes

तकनीकी सारांश: समान रूप से यादृच्छिक कोड का स्टार उत्पाद (The Star Product of Uniformly Random Codes)

समस्या विवरण
यह शोध पत्र एक परिमित क्षेत्र $\mathbb{F}_q$ पर दो स्वतंत्र, समान रूप से यादृच्छिक रैखिक कोडों, $C_1$ और $C_2$, के स्टार उत्पाद (जिसे शूर या हेडामार्ड उत्पाद भी कहा जाता है) के अपेक्षित आयाम (expected dimension) की जांच करता है। इन कोडों के निर्धारित आयाम $k_1$ और $k_2$ तथा लंबाई $n$ है। स्टार उत्पाद को कोडिंग थ्योरी में एक मौलिक ऑपरेशन माना जाता है जिसका उपयोग क्वांटम एरर करेक्शन, प्राइवेट इंफॉर्मेशन रिट्रीवल (PIR), और सुरक्षित डिस्ट्रिब्यूटेड मैट्रिक्स मल्टीप्लिकेशन (SDMM) में किया जाता है, लेकिन दो यादृच्छिक कोडों के स्टार उत्पाद का आयाम निर्धारित करना सरल नहीं है। पूर्ववर्ती कार्य, जैसे कि [19], ने रैंक-1 मैट्रिसेस की रैखिक स्वतंत्रता का विश्लेषण करके इस आयाम का अनुमान लगाया था, जिससे यह स्थापित हुआ कि प्रतिबंधित पैरामीटर व्यवस्थाओं के तहत अपेक्षित आयाम $\min\{n, k_1k_2\}$ के बराबर होता है। इस शोध पत्र का लक्ष्य अधिक सामान्य और स्पष्ट विश्लेषण प्रदान करना है, जो इन प्रतिबंधित व्यवस्थाओं से आगे बढ़कर अपेक्षित आयाम और इसके प्रसरण (variance) का विस्तार करता है।

कार्यप्रणाली (Methodology)
लेखक दो कोडों के स्टार उत्पाद और द्विसम (bilinear forms) के मूल्यांकन के बीच एक संबंध स्थापित करते हैं। विशेष रूप से, यदि $C_1$ और $C_2$ के जनरेटर मैट्रिसेस $G_1$ और $G_2$ हैं, तो $C_1 \star C_2$ को द्विसम $B = \text{Bil}(\mathbb{F}_q^{k_1}, \mathbb{F}_q^{k_2})$ पर कार्य करने वाले एक रैखिक मानचित्र $\psi_{G_1, G_2}$ के इमेज (image) के रूप में पहचाना जाता है। स्टार उत्पाद का आयाम $k_1k_2 - \dim(\ker \psi_{G_1, G_2})$ द्वारा दिया जाता है।

अपेक्षित आयाम का विश्लेषण करने के लिए, लेखक कर्नेल (kernel) के अपेक्षित आकार, $\mathbb{E}[|\ker \psi_{C_1, C_2}|]$, की गणना करने पर ध्यान केंद्रित करते हैं। वे एक संभावabilistic मॉडल का उपयोग करते हैं जहाँ कोड्स को एक व्यवस्थित जनरेटर मैट्रिक्स के अंतिम $n-k$ कॉलम को यादृच्छिक रूप से चुनकर बनाया जाता है। विश्लेषण में शामिल हैं:

1. गणनात्मक संयोजन विज्ञान (Enumerative Combinatorics): उन विशिष्ट रैंक $r$ के द्विसमों (मैट्रिसेस के रूप में प्रतिनिधित्व) की गिनती करना जो जनरेटर मैट्रिसेस के कॉलमों पर शून्य होते हैं। इसके लिए शून्य विकर्ण (zero diagonals) और विशिष्ट शून्य पैटर्न वाले मैट्रिसेस की गिनती की आवश्यकता होती है।
2. स्पष्ट सूत्र (Explicit Formulas): $q$-बाइनोमियल गुणांकों और समावेशन-अपवर्जन (inclusion-exclusion) सिद्धांतों का उपयोग करके अपेक्षित कर्नेल आकार के लिए एक स्पष्ट सूत्र व्युत्पन्न करना (लेम्मा 3.5 और प्रमेय 3.9)।
3. अनंतस्पर्शी विश्लेषण (Asymptotic Analysis): क्षेत्र के आकार $q \to \infty$ और कोड आयामों $k_1, k_2 \to \infty$ के रूप में विशिष्ट विकास स्थितियों के तहत इन सूत्रों के व्यवहार की जांच करना।
4. प्रसरण विश्लेषण (Variance Analysis): अपेक्षित कर्नेल आकार पर प्राप्त बाउंड्स का उपयोग करके स्टार उत्पाद आयाम के प्रसरण को ऊपरी सीमा (upper bound) प्रदान करना।

मुख्य योगदान और परिणाम

1. स्पष्ट निचली सीमा (Explicit Lower Bound): शोध पत्र मूल्यांकन मानचित्र के अपेक्षित कर्नेल आकार के लिए एक स्पष्ट सूत्र प्रदान करता है, जो सभी पैरामीटर विकल्पों के लिए स्टार उत्पाद के अपेक्षित आयाम पर एक स्पष्ट निचली सीमा प्रदान करता है (कोरोलरी 3.11)। यह दृष्टिकोण रैंक-1 मैट्रिक्स विश्लेषण से भिन्न है क्योंकि यह कर्नेल की सीधी कॉम्बिनेटोरियल गिनती प्रदान करता है।

2. क्षेत्र के आकार में अनंतस्पर्शी व्यवहार ($q \to \infty$):

   • लेखक सिद्ध करते हैं कि जैसे-जैसे क्षेत्र का आकार $q$ अनंत की ओर बढ़ता है, स्टार उत्पाद का अपेक्षित आयाम अपने अधिकतम संभव मान, $\min\{n, k_1k_2\}$, तक पहुँच जाता है, चाहे $k_1$ और $k_2$ के बीच का संबंध कुछ भी हो (कोरोलरी 4.2)।
   • विशेष रूप से, यदि $k_1k_2 < n$ है, तो अपेक्षित कर्नेल आकार 1 के करीब पहुँच जाता है; यदि $k_1k_2 = n$ है, तो यह 2 के करीब पहुँच जाता है; और यदि $k_1k_2 > n$ है, तो यह अपसारी (diverges) हो जाता है।
   • आयाम का प्रसरण (variance) 0 की ओर घटता हुआ दिखाया गया है, जिसकी दर इस बात पर निर्भर करती है कि $k_1k_2 < n$ है या $k_1k_2 \ge n$ (प्रपोजिशन 4.3)।

3. कोड आयामों में अनंतस्पर्शी व्यवहार ($k_1, k_2 \to \infty$):

   • "सक्षम" (admissible) विकास स्थितियों के तहत (जहाँ $k_1$ और $k_2$ सख्ती से मोनोटोनिक रूप से बढ़ते हैं और $k_1k_2$, $q^{k_1}$ के सापेक्ष बहुत तेजी से नहीं बढ़ता है), शोध पत्र सिद्ध करता है कि अपेक्षित कर्नेल आकार स्थिर हो जाता है (थ्योरम 5.7)।
   • फलस्वरूप, जैसे-जैसे आयाम बढ़ते हैं, स्टार उत्पाद का अपेक्षित आयाम उच्च प्रायिकता (high probability) के साथ $\min\{n, k_1k_2\}$ प्राप्त कर लेता है (कोरोलरी 5.12)।
   • प्रसरण को इन स्थितियों के तहत शून्य होता हुआ दिखाया गया है, जो या तो $n < k_1k_2$ होने पर या यदि अंतर $n - k_1k_2$ रैखिक रूप से बढ़ता है, तो कम से कम घातीय (exponentially) रूप से घटता है (प्रपोजिशन 5.14)।

4. पूर्ववर्ती कार्य के साथ तुलना: परिणामों की तुलना [19] के रैंक-1 मैट्रिक्स दृष्टिकोण से की गई है। लेखक नोट करते हैं कि उनके परिणाम व्यापक रेंज के पैरामीटरों को कवर करते हैं, विशेष रूप से बड़े क्षेत्र आकार $q \ge 3$ के लिए, जहाँ उनके आयाम वृद्धि के बाउंड्स [19] की तुलना में अधिक मजबूत हैं (रिमार्क 5.13)।

महत्व और निहितार्थ
शोध पत्र का दावा है कि इन परिणामों के कई क्षेत्रों में सीधे निहितार्थ हैं:

• प्राइवेट इंफॉर्मेशन रिट्रीवल (PIR): स्टार उत्पादों पर आधारित PIR स्कीम्स में, रिट्रीवल रेट स्टार उत्पाद के आयाम द्वारा सीमित होता है। परिणाम बताते हैं कि जबकि यादृच्छिक कोड (random codes) अनंतस्पर्शी रूप से अधिकतम स्टार उत्पाद आयाम प्रदान करते हैं (जो GRS जैसे संरचित कोड की तुलना में कम रिट्रीवल रेट की ओर ले जाता है), छोटे क्षेत्रों (जैसे $\mathbb{F}_2$) पर उप-अधिकतम (sub-maximal) आयाम वाले कोड जोड़े प्राप्त करने की गैर-नगण्य संभावना बनी रहती है। इसका तात्पर्य है कि त्रुटि-मुक्त सेटिंग्स में PIR के लिए अनुकूल यादृच्छिक कोड जोड़ों की प्रयोगात्मक खोज व्यावहारिक है।
• सुरक्षित डिस्ट्रिब्यूटेड मैट्रिक्स मल्टीप्लिकेशन (SDMM): PIR के समान, SDMM में रिकवरी थ्रेशोल्ड और स्ट्रैगलर टॉलरेंस स्टार उत्पाद के आयाम पर निर्भर करते। निष्कर्ष संकेत देते हैं कि यादृच्छिक निर्माण आमतौर पर निम्न रिकवरी थ्रेशोल्ड प्राप्त नहीं करते हैं, लेकिन छोटे क्षेत्रों में अनुकूल पैरामीटर्स वाले व्यावहारिक उदाहरण अभी भी मिल सकते हैं।
• क्वांटम एरर करेक्शन: शोध पत्र बाइनरी CSS-T कोड्स पर चर्चा करता है, जिन्हें $C_2 \subseteq C_1 \cap (C_1 \star C_1)^\perp$ की आवश्यकता होती है। परिणाम बताते हैं कि पर्याप्त बड़े आयाम वाले पर्याप्त रूप से यादृच्छिक कोड्स के लिए, स्टार उत्पाद $C_1 \star C_1$ के बड़े होने की संभावना होती है, जिससे ऑर्थोगोनल कॉम्प्लीमेंट छोटा हो जाता है। यह सुझाव देता है कि यादृच्छिक $C_1$ का उपयोग करके उच्च-दूरी वाले CSS-T कोड बनाना कठिन है, क्योंकि परिणामी क्वांटम कोड का न्यूनतम दूरी पर कमजोर निचली सीमा होगी।
• क्रिप्टोएनालिसिस: स्टार उत्पाद आयाम का उपयोग कोड-आधारित क्रिप्टोग्राफी (जैसे गोपा कोड्स के विरुद्ध) में एक डिस्टिंग्विशर (distinguisher) के रूप में किया जाता है। शोध पत्र नोट करता है कि जबकि उनके परिणाम पुष्टि करते हैं कि यादृच्छिक कोड आम तौर पर अधिकतम स्टार उत्पाद आयाम रखते हैं (जो उन्हें गोपा कोड्स जैसे संरचित कोड्स से अलग बनाता है जिनका वर्ग छोटा होता है), विश्लेषण किए गए विशिष्ट पैरामीटर रेंज वर्तमान में मानक मैसीली (McEliece) सिस्टम की सुरक्षा के लिए खतरा पैदा नहीं करते हैं। हालांकि, कार्यप्रणाली विभिन्न कोड जोड़ों के स्टार उत्पादों के विश्लेषण के लिए नए पैरामीटर रेंज तलाशने का मार्ग प्रशस्त करती है।

निष्कर्ष
शोध पत्र निष्कर्ष निकालता है कि दो समान रूप से यादृच्छिक कोडों के स्टार उत्पाद का अपेक्षित आयाम, जैसे-जैसे क्षेत्र का आकार बढ़ता है, अपने सैद्धांतिक अधिकतम तक पहुँच जाता है, और विशिष्ट विकास स्थितियों के तहत, जैसे-जैसे कोड के आयाम बढ़ते हैं। प्रसरण (variance) लुप्त हो जाता है, जो मापन के संकेंद्रण (concentration of measure) को दर्शाता है। लेखक प्रसरण के लिए सटीक निचली सीमा प्राप्त करने और गैर-अनंतस्पर्शी (non-asymptotic) मामलों के विश्लेषण को भविष्य के कार्य के लिए खुले प्रश्न के रूप में पहचानते हैं।