🔢 mathematics

Linear Code Equivalence via Plücker Coordinates

यह शोध पत्र प्लकर्स निर्देशांक (Plücker coordinates) और अपरिवर्तनीय परिमेय फलनों (invariant rational functions) का उपयोग करके अंतर्निहित क्रमपरिवर्तन आव्यूह (permutation matrix) को एक मूल (root) के रूप में निर्मित करने वाले बहुपदों के माध्यम से लीनियर कोड इक्विवेलेंस समस्या के लिए एक सैद्धांतिक बीजगणितीय ढांचे को प्रस्तुत करता है, जो यह प्रदर्शित करता है कि परिणामी बहुपद व्यावहारिक हमलों के लिए गणनात्मक रूप से अव्यवहार्य होने के बावजूद भी क्रिप्टैनालिसिस में बीजगणितीय ज्यामिति की क्षमता कितनी है।

मूल लेखक: Gessica Alecci, Giuseppe D'Alconzo

प्रकाशित 2026-03-11

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

CC BY 4.0

मूल लेखक: Gessica Alecci, Giuseppe D'Alconzo

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

मुख्य चित्र: डिजिटल "ताला और चाबी"

कल्पना कीजिए कि आपके पास एक जटिल, बहु-रंगीन बॉक्स के अंदर छिपा हुआ एक गुप्त संदेश है। यह बॉक्स एक लीनियर कोड (डेटा को सुरक्षित रूप से स्टोर करने का एक तरीका) का प्रतिनिधित्व करता है।

क्रिप्टोग्राफी की दुनिया में (विशेष रूप से पेपर में उल्लेखित "LESS" सिग्नेचर स्कीम में), सुरक्षा एक विशिष्ट पहेली पर टिकी है: लीनियर कोड इक्विवेलेंस (LCE) समस्या।

पहेली:
आपको दो बॉक्स दिए गए हैं, बॉक्स A और बॉक्स B। आपको बताया गया है कि वे वास्तव में एक ही बॉक्स हैं, बस उन्हें अलग-अलग कोणों से देखा गया है या उनके रंग थोड़े बदले हुए हैं। आपका काम उन सटीक निर्देशों ("चाबी") को खोजना है जो बॉक्स A को बॉक्स B में बदल दें।

इन निर्देशों में दो प्रकार के मूव्स शामिल हैं:

शफलिंग (Shuffling): रंगीन टाइल्स की स्थितियों को बदलना (परम्यूटेशन)।
स्केलिंग (Scaling): रंगों की चमक या तीव्रता को बदलना (डायगोनल स्केलिंग)।

पेपर पूछता है: *क्या हम ब्रूट फोर्स (brute force) से तेज़ तरीके से "शफलिंग" निर्देशों का पता लगाने के लिए उन्नत गणित का उपयोग कर सकते हैं?

समस्या: बहुत अधिक वेरिएबल्स

आमतौर पर, इस पहेली को हल करने के लिए, आपको शफलिंग (परम्यूटेशन) और स्केलिंग (डायगोनल) दोनों को एक साथ अनुमान लगाना पड़ता है। यह एक रूबिक क्यूब को हल करने जैसा है जबकि कोई व्यक्ति साथ-साथ स्टिकर के रंगों को भी बदल रहा हो। यह वेरिएबल्स का एक बड़ा झमेला है।

लेखकों की अंतर्दृष्टि (Insight):
लेखकों ने महसूस किया कि "स्केलिंग" वाला हिस्सा वास्तव में एक भटकाव है। यदि आप बॉक्स को एक विशिष्ट गणितीय परिप्रेक्ष्य से देखते हैं, तो स्केलिंग बॉक्स के आकार को नहीं बदलती, केवल उसके "आकार" या "लेबल" को बदलती है।

उन्होंने पूरी तरह से स्केलिंग को अनदेखा करने और केवल शफलिंग पर ध्यान केंद्रित करने का निर्णय लिया। उन्होंने पूछा: "यदि हम रंग परिवर्तनों को हटा दें, तो क्या हम शुद्ध ज्यामिति (geometry) का उपयोग करके शफलिंग पैटर्न को खोज सकते हैं?"

उपकरण: "प्लकर मैप" (जादुई दर्पण)

यह करने के लिए, लेखकों ने बीजगणितीय ज्यामिति (Algebraic Geometry) नामक गणित की एक शाखा से एक उपकरण का उपयोग किया। उन्होंने प्लकर कोऑर्डिनेट्स (Plücker Coordinates) का उपयोग किया।

उपमा (Analogy):
कल्पना कीजिए कि आपके पास एक 3D वस्तु (कोड) है। केवल कच्चे डेटा को देखकर उसके आकार का वर्णन करना कठिन है।
प्लकर एम्बेडिंग (Plücker Embedding) एक जादुई दर्पण की तरह है। जब आप इस वस्तु को इस दर्पण के सामने रखते हैं, तो यह वस्तु को स्वयं नहीं दिखाता है; यह एक जटिल, बहु-आयामी छाया (निर्देशांकों का एक सेट जिन्हें कोऑर्डिनेट्स कहा जाता है) प्रोजेक्ट करता है जो वस्तु के आकार और अभिविन्यास (orientation) का सटीक वर्णन करता है।

इस दर्पण की सुंदरता यह है कि यह अव्यवस्थित "शफलिंग और स्केलिंग" की समस्या को एक स्वच्छ "शफलिंग" समस्या में बदल देता है।

रणनीति: "इनवेरिएंट" फिंगरप्रिंट्स खोजना

लेखक यह पता लगाने का एक तरीका चाहते थे कि दो कोड समान हैं या नहीं, बिना तुरंत शफलिंग की चाबी को हल किए। उन्होंने इनवेरिएंट्स (Invariants) की तलाश की।

उपमा:
कल्पना कीजिए कि आपके पास एक उंगली का निशान (फिंगरप्रिंट) है। चाहे आप अपने हाथ को कैसे भी घुमाएं या अपनी त्वचा को खींचें (स्केलिंग), रेखाओं का अनूठा पैटर्न (इनवेरिएंट) अपरिवर्तित रहता है।

लक्ष्य: कोड के लिए एक गणितीय "फिंगरप्रिंट" खोजना जो स्केलिंग (डायगोनल) मूव्स लागू करने पर कभी न बदले।
खोज: लेखकों ने इन फिंगरप्रिंट्स को खोजने के लिए एक नया तरीका विकसित किया (एक मैट्रिक्स का उपयोग करके जिसे वे $W_{k,n}$ $W_{k, n}$ कहते हैं)। वे इन्हें इनवेरिएंट रैशनल फंक्शन्स (Invariant Rational Functions) कहते हैं।
- पुराना तरीका: इन फिंगरप्रिंट्स को खोजने के लिए भारी, धीमे कंप्यूटर एल्गोरिदम (ग्रोबनर बेसिस) का उपयोग करना।
- नया तरीका: लेखकों ने इन फिंगरप्रिंट्स को सीधे बनाने के लिए एक "रेसिपी" (एक एल्गोरिदम) बनाई, जैसे पहले से बने आटे से कुकीज़ बनाना, बिना भारी मशीनरी की आवश्यकता के।

"अहा!" मोमेंट: सुरागों को दोगुना करना

एक बार जब उन्होंने ये फिंगरप्रिंट्स (इनवेरिएंट्स) खोज लिए, तो उन्होंने उन्हें पहेली पर लागू किया।

यहाँ चालाकी भरी ट्रिक है:

यदि आप जानते हैं कि कैसे एक शफल $P$ का उपयोग करके बॉक्स A को बॉक्स B में बदला जाए, तो आप यह भी जानते हैं कि बॉक्स B को वापस बॉक्स A में बदलने के लिए रिवर्स (उल्टा) शफल ( $P^{-1}$ ) का उपयोग किया जाएगा।
परम्यूटेशन (शफलिंग) की दुनिया में, रिवर्स शफल केवल ट्रांसपोज़ (transpose) (विकर्ण के ऊपर से मैट्रिक्स को पलटना) है।
जादू: रिवर्स शफल के लिए गणित लीनियर और सरल है।

अपने नए फिंगरप्रिंट्स का उपयोग करके, लेखक दो प्रकार के समीकरण लिख सके:

एक सेट जो कहता है: "यदि आप A पर शफल $P$ लागू करते हैं, तो आपको B प्राप्त होता है।"
दूसरा सेट जो कहता है: "यदि आप B पर रिवर्स शफल लागू करते हैं, तो आपको A प्राप्त होता है।"

यह प्रभावी रूप से उन समीकरणों की संख्या को दोगुना कर देता है जिन्हें उन्हें अज्ञातों (unknowns) के लिए हल करना है। यह एक ही खजाने के दो अलग-अलग मानचित्र होने जैसा है; यदि एक मानचित्र धुंधला है, तो दूसरा स्पष्ट हो सकता है।

पकड़: "बहुत बड़ा" होने की समस्या

तो, क्या यह उस एन्क्रिप्शन को तोड़ने वाला कोई जादुई समाधान है? अभी नहीं।

लेखक स्वीकार करते हैं कि हालांकि उनका गणित सुंदर और सैद्धांतिक रूप से सुदृढ़ है, लेकिन परिणामी समीकरण विशाल हैं।

डिग्री (Degree): समीकरण अविश्वसनीय रूप से जटिल (डिग्री 4 या उससे अधिक) हैं।
आकार (Size): इन समीकरणों में पदों (terms) की संख्या तेजी से (exponentially) बढ़ती है। यह एक ऐसी किताब पढ़ने जैसा है जहाँ हर बार पन्ना पलटने पर शब्दों की संख्या दोगुनी हो जाती है।

वास्तविक दुनिया की क्रिप्टोग्राफी (जैसे कि LESS सिग्नेचर स्कीम) में उपयोग किए जाने वाले विशिष्ट मापदंडों के लिए, समीकरण इतने बड़े हैं कि वर्तमान कंप्यूटर उचित समय में उन्हें हल नहीं कर सकते।

निष्कर्ष: यह क्यों मायने रखता है?

भले ही वे आज कोड को तोड़ नहीं सकते, यह पेपर तीन कारणों से एक बड़ा कदम है:

नया दृष्टिकोण: यह पहली बार है जब इन विशिष्ट ज्यामितीय उपकरणों (प्लकर कोऑर्डिनेट्स) का उपयोग इस विशिष्ट क्रिप्टोग्राफिक समस्या पर हमला करने के लिए किया गया है। यह भविष्य के शोधकर्ताओं के लिए एक नया दरवाजा खोलता है।
बेहतर समझ: यह साबित करता है कि हम "स्केलिंग" के शोर को अनदेखा करते हुए, समस्या के "शफलिंग" हिस्से को विशुद्ध रूप से बीजगणितीय रूप से मॉडल कर सकते हैं।
भविष्य की तैयारी (Future Proofing): क्रिप्टोग्राफी एक हथियारों की दौड़ है। आज का "असंभव" गणित कल की "आसान" गणना बन सकता है क्योंकि कंप्यूटर तेज़ हो रहे हैं या नए एल्गोरिदम आविष्कार किए जा रहे हैं। यह पेपर उस भविष्य के हमले के लिए ब्लूप्रिंट प्रदान करता है।

सारांश में:
लेखकों ने गुप्त कोड के "आकार" को देखने के लिए एक परिष्कृत गणितीय सूक्ष्मदर्शी (microscope) बनाया है। उन्होंने "रंग परिवर्तन" को अनदेखा करने और शुद्ध रूप से "शफलिंग" पर ध्यान केंद्रित करने का तरीका खोजा। उन्होंने पहेली को हल करने के लिए उपलब्ध सुरागों की संख्या को दोगुना करने का तरीका बनाया। हालांकि पहेली अभी हल करने के लिए बहुत बड़ी है, लेकिन उन्होंने अगली पीढ़ी के क्रिप्टोग्राफरों को प्रयास करने के लिए उपकरणों का एक बहुत अधिक सटीक सेट थमा दिया है।

यहाँ गेसिका अलेची और ज्यूसेपे डी'अल्कोनो द्वारा लिखित शोध पत्र "Linear Code Equivalence via Plücker Coordinates" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र लीनियर कोड इक्विवेलेंस (LCE) समस्या को संबोधित करता है, जो पोस्ट-क्वांटम क्रिप्टोग्राफी (विशेष रूप से LESS सिग्नेचर स्कीम) के लिए एक मौलिक धारणा है।

परिभाषा: यदि $\mathbb{F}_q$ पर $k$ आयाम और $n$ लंबाई वाले दो लीनियर कोड $C_1$ और $C_2$ दिए गए हैं, तो समस्या एक लीनियर आइसोमेट्री (एक मोनोमियल मैट्रिक्स $Q = DP $, जहाँ$ D$ विकर्ण (diagonal) है और $P$ एक परम्यूटेशन मैट्रिक्स है) खोजने की है ताकि $C_2 = C_1 \cdot Q$ हो सके।
संदर्भ: हालिया क्रिप्टएनालिटिक प्रगति (जैसे Chou, Persichetti, Santini) ने आइसोमेट्री समूह $M_{n,q} \cong D_{n,q} \rtimes S_n$ को फैक्टर करके खोज स्थान (search space) को कम कर दिया है। यह समस्या को विकर्ण स्केलिंग के सापेक्ष कोड के कोटिएंट स्पेस (quotient space) पर एक परम्यूटेशन मैट्रिक्स $P$ खोजने के रूप में देखने की अनुमति देता है: $S_n \times \text{Gr}_q(k, n)/D_{n,q} \to \text{Gr}_q(k, n)/D_{n,q}$ ।
लक्ष्य: लेखक इस कम किए गए समस्या के लिए एक एल्जेब्रिक मॉडल बनाने का लक्ष्य रखते हैं। विशेष रूप से, वे बहुपदों (polynomials) की एक प्रणाली चाहते हैं जहाँ अज्ञात चर (unknowns) परम्यूटेशन मैट्रिक्स $P$ के प्रविष्टियाँ (entries) हैं, जो डायगोनल ग्रुप एक्शन के इनवेरियंट्स (invariants) से व्युत्पन्न हैं।

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

लेखक एल्जेब्रिक ज्योमेट्री और इनवेरिएंट थ्योरी के उपकरणों का उपयोग करते हैं, विशेष रूप से प्लकर कोऑर्डिनेट्स (Plücker coordinates) और ग्रासमैनियन (Grassmannians) की ज्यामिति का।

A. गणितीय ढांचा (Mathematical Framework)

ग्रासमैनियन एम्बेडिंग: लीनियर कोड को ग्रासमैनियन $\text{Gr}_q(k, n)$ में बिंदुओं के रूप में माना जाता है। लेखक प्लकर एम्बेडिंग $\iota: \text{Gr}_q(k, n) \hookrightarrow \mathbb{P}^{\binom{n}{k}-1}$ का उपयोग करते हैं, जो एक कोड को उसके प्लकर कोऑर्डिनेट्स (जेनेरेटर मैट्रिक्स के माइनर्स) में मैप करता है।
डायगोनल एक्शन: डायगोनल ग्रुप $D_{n,q}$ का कोड पर प्रभाव प्लकर कोऑर्डिनेट्स पर एक स्केलिंग एक्शन में बदल जाता है। यदि $\lambda = (\lambda_1, \dots, \lambda_n) \in D_{n,q}$ , तो एक प्लकर कोऑर्डिनेट $p_I$ (जहाँ $I \subset \{1, \dots, n\}$ ) इस प्रकार परिवर्तित होता है:
$p_I \mapsto \left(\prod_{i \in I} \lambda_i\right) p_I$
इनवेरिएंट फंक्शन्स: मुख्य रणनीति प्लकर कोऑर्डिनेट्स में इनवेरिएंट रैशनल फंक्शन्स $\mu$ को खोजना है जो इस डायगोनल स्केलिंग के तहत इनवेरिएंट हों। यदि $C_1$ और $C_2$ एक ही $P$ के माध्यम से समान (equivalent) हैं, तो किसी भी इनवेरिएंट $\mu$ के लिए, स्थिति $\mu(P \cdot C_1) = \mu(C_2)$ सत्य होनी चाहिए।

B. इनवेरिएंट जनरेशन के लिए एल्गोरिदम (Algorithm for Invariant Generation)

शोध पत्र एक नया एल्गोरिदम, InvGen, प्रस्तावित करता है, जो कंप्यूटेशनल रूप से महंगे ग्रोबनर बेसिस (Gröbner bases) या रेनॉल्ड्स ऑपरेटर्स (Reynolds operators) पर निर्भर किए बिना इनवेरिएंट रैशनल फंक्शन्स के क्षेत्र $\mathbb{F}_q(\text{Gr}_q(k, n))^{D_{n,q}}$ के जनरेटर्स की गणना करता है।

कॉम्बिनेटोरियल मैट्रिक्स निर्माण: एक मैट्रिक्स $W_{k,n}$ का निर्माण करें जिसका आकार $\binom{n}{k} \times n$ है, जहाँ पंक्तियाँ (rows) उपसमुच्चय $I \in \binom{[n]}{k}$ के अनुरूप हैं और प्रविष्टियाँ इंडिकेटर वेक्टर्स हैं।
कर्नेल विश्लेषण: $\mathbb{Z}$ पर $W_{k,n}$ का लेफ्ट कर्नेल (left kernel) मोनोमियल इनवेरियंट्स के एक्सपोनेंट्स (exponents) के अनुरूप होता है। कर्नेल में एक वेक्टर $v$ इस प्रकार के इनवेरिएंट को जनरेट करता है:
$f_v = \prod_{I} p_I^{v_I}$
स्वतंत्र जनरेटर्स का चयन: जैकबियन क्राइटेरियन (Proposition 1) के एक वेरिएंट का उपयोग करते हुए, एल्गोरिदम इन फंक्शन्स के एक उपसमुच्चय का चयन करता है जो बीजगणितीय रूप से स्वतंत्र हैं, जो इनवेरिएंट्स के क्षेत्र के लिए एक ट्रांसेंडेंटल बेस (transcendental basis) बनाते हैं।

C. एल्जेब्रिक मॉडल का निर्माण (Constructing the Algebraic Model)

एक बार जब एक इनवेरिएंट $\mu = g/f$ की पहचान हो जाती है:

अज्ञात परम्यूटेशन मैट्रिक्स $X$ (जहाँ $X$ $P$ का प्रतिनिधित्व करता है) द्वारा गुणा किए गए जेनेरेटर मैट्रिक्स $G_1$ को प्लकर कोऑर्डिनेट्स में प्रतिस्थापित करें।
बहुपद समीकरण बनाएँ:
$h(X) = g(G_1 X) - f(G_1 X) \cdot \mu(G_2) = 0$
डबल इक्वेशन्स (Double Equations): चूंकि $P^{-1} = P^T$ , लेखक इस तथ्य का लाभ उठाते हैं कि यदि $C_2 = P \cdot C_1$ , तो $C_1 = P^T \cdot C_2$ । यह $X^T$ का उपयोग करके समीकरणों का एक दूसरा सेट बनाने की अनुमति देता है, जिससे समान अज्ञात चरों के लिए बाधाओं (constraints) की संख्या दोगुनी हो जाती है।

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

कोटिएंट LCE के लिए पहला एल्जेब्रिक मॉडल: शोध पत्र कोटिएंट स्पेस $\text{Gr}_q(k, n)/D_{n,q}$ पर संचालित होने वाले LCE समस्या का पहला स्पष्ट एल्जेब्रिक निरूपण प्रदान करता है, जहाँ अज्ञात केवल परम्यूटेशन मैट्रिक्स $P$ की प्रविष्टियाँ हैं।
कुशल इनवेरिएंट कंप्यूटेशन: लेखक इंडेंस मैट्रिक्स $W_{k,n}$ के कर्नेल और जैकबियन क्राइटेरियन का उपयोग करके इनवेरिएंट फील्ड के जनरेटर्स की गणना करने की एक विधि पेश करते हैं। यह बड़े समूहों के लिए असंभव होने वाले ग्रोबनर बेसिस की गणना से बचता है।
Multi-Sample LCE में सैद्धांतिक अंतर्दृष्टि: यह कार्य ग्रुप एक्शन इन्वर्जन प्रॉब्लम के "Multi-Sample" वेरिएंट को संबोधित करता है। कोटिएंट पर $S_n$ के एक्शन को मॉडल करके, लेखक LCE की "मल्टीपल वन-वेनेस" (multiple one-wayness) का विश्लेषण करने के लिए एक ढांचा प्रदान करते हैं, जो एक ऐसा गुण है जिसे कोटिएंट एक्शन के लिए अभी तक पूरी तरह से समझा नहीं गया है।
स्पष्ट निर्माण: शोध पत्र विस्तार से बताता है कि कैसे ज्यामितीय इनवेरियंट्स को $P$ को रूट (root) के रूप में लेकर बहुपद प्रणालियों में अनुवादित किया जाए।

4. परिणाम और सीमाएँ (Results and Limitations)

सैद्धांतिक सफलता: लेखकों ने सफलतापूर्वक इनवेरियंट्स की एल्जेब्रिक संरचना को प्राप्त किया और छोटे मापदंडों (जैसे $k=2, n=4$ ) के लिए बहुपद समीकरणों के निर्माण का प्रदर्शन किया।
व्यावहारिक सीमाएँ:
- डिग्री (Degree): परिणामी बहुपदों की डिग्री $2k$ है। क्रिप्टोग्राफिक मापदंडों (जैसे $k=126$ ) के लिए, यह डिग्री अत्यधिक उच्च ($252$) हो जाती है।
- मोनोमियल विस्फोट (Monomial Explosion): इन बहुपदों में मोनोमियल्स की संख्या $n$ और $k$ के साथ तेजी से (exponentially) बढ़ती है।
- व्यवहार्यता (Feasibility): लेखक स्पष्ट रूप से कहते हैं कि हालांकि यह मॉडल सैद्धांतिक रूप से सुदृढ़ है, लेकिन अपने आकार और जटिलता के कारण परिणामी प्रणालियाँ वर्तमान क्रिप्टएनालिसिस के लिए व्यावहारिक उपयोग में नहीं हैं। उन्हें हल करना वर्तमान में असंभव है।

5. महत्व (Significance)

क्रिप्टोग्राफिक विश्लेषण: तत्काल व्यावहारिक क्रिप्टएनालिसिस की कमी के बावजूद, यह कार्य महत्वपूर्ण है क्योंकि यह LCE समस्या के लिए प्लकर कोऑर्डिनेट्स और इनवेरिएंट थ्योरी का पहला अनुप्रयोग है। यह सैद्धांतिक क्रिप्टएनालिसिस के लिए एक नया मार्ग खोलता है।
सुरक्षा निहितार्थ: शोध पत्र इस बात पर प्रकाश डालता है कि कोटिएंट एक्शन (जो कुछ उन्नत सिग्नेचर स्कीम्स में उपयोग किया जाता है) के संबंध में "मल्टीपल वन-वेनेस" की सुरक्षा अभी भी एक खुला प्रश्न है। एल्जेब्रिक मॉडल इस सुरक्षा गुण का मूल्यांकन करने के लिए आवश्यक उपकरण प्रदान करता है।
मेथोडोलॉजिकल ब्रिज: यह एल्जेब्रिक ज्योमेट्री (Grassmannians, invariant theory) और पोस्ट-क्वांटम क्रिप्टोग्राफी के बीच के अंतर को पाटता है, यह सुझाव देता है कि कोड-आधारित स्कीम्स पर भविष्य के हमलों के लिए केवल कॉम्बिनेटोरियल सर्च के बजाय परिष्कृत ज्यामितीय दृष्टिकोणों की आवश्यकता हो सकती है।

संक्षेप में, यह शोध पत्र प्लकर कोऑर्डिनेट्स का उपयोग करके लीनियर कोड इक्विवेलेंस समस्या के लिए एक कठोर एल्जेब्रिक ढांचा स्थापित करता है। हालांकि परिणामी बहुपद प्रणालियाँ वर्तमान में क्रिप्टोग्राफिक मापदंडों को तोड़ने के लिए बहुत जटिल हैं, फिर भी यह कार्य समस्या की संरचना और इसके इनवेरियंट्स की प्रकृति की सैद्धांतिक समझ को मौलिक रूप से आगे बढ़ाता है।