🔢 mathematics

Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS

यह शोध पत्र यह प्रदर्शित करता है कि रिस्ट्रिक्टेड सिंड्रोम डिकोडिंग, जो क्रॉस (CROSS) सिग्नेचर स्कीम का सुरक्षा आधार है, को कोड-आधारित और लैटिस-आधारित दोनों समस्याओं में घटाया जा सकता है, जिससे संभावित हमले के वेक्टरों का विस्तार होता है और योजना की सुरक्षा में नई अंतर्दृष्टि प्राप्त होती है।

मूल लेखक: Étienne Burle, Aleksei Udovenko

प्रकाशित 2026-04-13

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

CC0 1.0

मूल लेखक: Étienne Burle, Aleksei Udovenko

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

कल्पना कीजिए कि आप एक मास्टर लॉकस्मिथ (ताले खोलने वाले विशेषज्ञ) हैं जो एक हाई-टेक तिजोरी खोलने की कोशिश कर रहे हैं। उस तिजोरी की सुरक्षा एक विशिष्ट प्रकार के पहेली पर टिकी है जिसे रिस्ट्रिक्टेड सिंड्रोम डिकोडिंग (ResSD) कहा जाता है। यह CROSS नामक एक नए डिजिटल सिग्नेचर सिस्टम के पीछे का "दिमाग" है, जिसका परीक्षण हमारे डेटा को भविष्य के क्वांटम कंप्यूटरों से बचाने के लिए किया जा रहा है।

यह पहेली इस प्रकार काम करती है: आपके पास संख्याओं का एक विशाल ग्रिड (एक मैट्रिक्स) और एक लक्ष्य परिणाम (सिंड्रोम) है। आपका काम संख्याओं का एक विशिष्ट पैटर्न (एक एरर वेक्टर) खोजना है, जो उस ग्रिड के साथ गुणा होने पर लक्ष्य परिणाम दे सके। लेकिन इसमें एक पेच है: आपके पैटर्न की प्रत्येक संख्या को बहुत ही छोटे, विशिष्ट "मेन्यू" (अनुमत मानों की सूची) में से चुना जाना चाहिए (जैसे केवल 1, 2, 4, और 8 का उपयोग करना)।

इस शोध पत्र के लेखक एक टीम की तरह हैं जो सुरक्षा ऑडिटर्स (लेखा परीक्षकों) का काम कर रहे हैं। उन्होंने पूछा: "क्या यह सुरक्षित तिजोरी वास्तव में अटूट है, या इसमें कुछ छिपे हुए बैकडोर (पीछे के रास्ते) हैं जिन्हें हमने अभी तक नहीं देखा है?"

यहाँ उन्होंने अपने शोध की व्याख्या सरल उपमाओं (analogies) के माध्यम से की है:

1. "अनुवाद" रणनीति (एक पहेली को दूसरी में बदलना)

टीम ने सबसे पहले यह महसूस किया कि यह विशिष्ट पहेली (ResSD), दो अन्य प्रसिद्ध पहेलियों के बहुत करीब है जिनका क्रिप्टोग्राफर्स दशकों से अध्ययन कर रहे हैं: रेगुलर सिंड्रोम डिकोडिंग और लैटिस प्रॉब्लम्स (Lattice Problems)।

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

2. "लैटिस" उपमा (निकटतम बिंदु खोजना)

उनकी जांच का दूसरा हिस्सा लैटिस (Lattices) से संबंधित था। क्रिप्टोग्राफी में, लैटिस बिंदुओं का एक अनंत, बहु-आयामी ग्रिड है।

उपमा: कल्पना कीजिए कि आपको एक विशाल, धुंधले जंगल (लैटिस) में छोड़ दिया गया है और आपको जमीन के एक विशिष्ट स्थान के सबसे करीब स्थित पेड़ को खोजना है। इसे क्लोजेस्ट वेक्टर प्रॉब्लम (CVP) कहा जाता है।
ट्विस्ट: लेखकों ने दिखाया कि CROSS पहेली गणितीय रूप से उस "निकटतम पेड़" को खोजने के समान है। हालाँकि, क्योंकि जंगल बहुत विशाल और घना है, इसलिए उस पेड़ को खोजना अविश्वसनीय रूप से कठिन है।
"हाइब्रिड" हमला: खोज को आसान बनाने के लिए, उन्होंने "अनुमान और जाँच" (guess and check) की रणनीति आजमाई। उन्होंने जंगल में कुछ पेड़ों के स्थान का अनुमान लगाया ताकि खोज क्षेत्र को छोटा किया जा सके। यह ऐसा है जैसे कहना, "मेरा अनुमान है कि पेड़ इस विशिष्ट खाली जगह में है," जिससे खोज बहुत तेज हो जाती है। उन्होंने "ट्रंकेटिंग" (truncating) का भी प्रयास किया—यानी, यह अनुमान लगाना कि समाधान केवल अनुमत संख्याओं के एक छोटे उपसमूह का उपयोग करता है (जैसे यह अनुमान लगाना कि चाबी केवल 1 और 2 का उपयोग करती है, न कि 4 या 8 का)।

3. "एफाइन डायमीटर" (संख्याओं को सिकोड़ना)

टीम ने गौर किया कि CROSS में अनुमत संख्याओं का "मेन्यू" यादृच्छिक (random) नहीं है; इसमें एक विशिष्ट संरचना (एक मल्टीप्लिकेटिव सबग्रुप) है।

उपमा: कल्पना कीजिए कि अनुमत संख्याएँ एक लंबे गलियारे में बिखरी हुई हैं। "एफाइन डायमीटर" (Affine Diameter) यह मापने का एक तरीका है कि आप उन संख्याओं को खींचकर या खिसकाकर एक छोटे कमरे में कितनी मजबूती से सिकोड़ सकते हैं।
अंतर्दृष्टि: उन्होंने पाया कि CROSS के लिए, इन संख्याओं को काफी मजबूती से सिकोड़ा जा सकता है। यह कसाव उन्हें शक्तिशाली गणितीय उपकरणों (जैसे लिस्ट-CVP) का उपयोग करके समाधान खोजने की अनुमति देता है। यह ऐसा है जैसे यह महसूस करना कि भले ही जंगल विशाल है, लेकिन जिन पेड़ों की आपको तलाश है, वे वास्तव में एक बहुत ही घनी झाड़ी में केंद्रित हैं।

निर्णय: क्या CROSS सुरक्षित है?

इन जटिल सिमुलेशन और गणितीय प्रमाणों को चलाने के बाद, उन्होंने क्या पाया:

कोई तत्काल खतरा नहीं: जो "बैकडोर" उन्हें मिले (पहेली को बदलने के नए तरीके), वे वर्तमान में CROSS को तोड़ने के लिए पर्याप्त मजबूत नहीं हैं। CROSS को तोड़ने का सबसे अच्छा तरीका अभी भी पुराना, मानक तरीका (इंफॉर्मेशन सेट डिकोडिंग) है, जो बहुत धीमा और महंगा है।
नई अंतर्दृष्टि: हालाँकि, उन्हें कुछ दिलचस्प टाइम-मेमोरी ट्रेड-ऑफ्स (Time-Memory Trade-offs) मिले। इसका अर्थ यह है कि यदि किसी हमलावर के पास बहुत अधिक कंप्यूटर मेमोरी (RAM) हो, तो वह पहेली को पहले की तुलना में थोड़ा तेज़ी से हल कर सकता है। लेकिन इस लाभ के बावजूद, पहेली अपने चुने हुए मापदंडों के साथ सुरक्षित रहती है।
भविष्य के लिए तैयारी: सबसे महत्वपूर्ण बात यह है कि उन्होंने इस समस्या के पूरे परिदृश्य का मानचित्र तैयार कर दिया है। उन्होंने दिखाया कि ResSD अन्य प्रकार की गणितीय समस्याओं से कैसे जुड़ता है। यह CROSS के डिजाइनरों (और भविष्य के सिस्टम) को यह समझने में मदद करता है कि कमजोर बिंदु कहाँ हो सकते हैं, जिससे यह सुनिश्चित होता है कि यदि कोई नया सुपर-कंप्यूटर आविष्कार किया जाता है, तो वे सुरक्षित रहने के लिए पहेली में बदलाव कर सकें।

सारांश

इस शोध पत्र को एक नए डिजिटल वॉल्ट (तिजोरी) के विस्तृत वास्तुशिल्प ब्लूप्रिंट (architectural blueprint) के रूप में देखें। लेखकों ने तिजोरी को उड़ाकर नहीं खोला, बल्कि उन्होंने एक नक्शा बनाया है जो हमले के हर संभावित कोण, हर छिपे हुए गलियारे और ताले को दूसरी भाषा में बदलने के हर तरीके को दर्शाता है।

उनका निष्कर्ष? तिजोरी अभी भी सुरक्षित है। लेकिन उनके नक्शे की बदौलत, हम जानते हैं कि यदि कोई नया खतरा पैदा होता है, तो दीवारों को कैसे मजबूत किया जाए। यह हमें विश्वास दिलाता है कि CROSS भविष्य की क्वांटम-प्रतिरोधी सुरक्षा के लिए एक मजबूत उम्मीदवार है।

यहाँ एटीन बर्ले और अलेक्सी उडोवेनको के शोध पत्र "Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या की परिभाषा (Problem Definition)

यह शोध पत्र रिस्ट्रिक्टेड सिंड्रोम डिकोडिंग (ResSD) समस्या पर केंद्रित है, जो क्लासिक सिंड्रोम डिकोडिंग (SD) का एक रूपांतर है, जो कोड-आधारित क्रिप्टोग्राफी का आधार है।

मानक SD: एक पैरिटी-चेक मैट्रिक्स $H$ और एक सिंड्रोम $s$ दिया गया है, तो एक एरर वेक्टर $e$ खोजें ताकि $eH^T = s$ हो, जिसमें एक बाउंडेड हैमिंग वेट (Hamming weight) हो।
ResSD: यहाँ प्रतिबंध अधिक सख्त है: एरर वेक्टर $e$ का प्रत्येक प्रविष्टि (entry) एक निश्चित, छोटे उपसमुच्चय (subset) $E \subset \mathbb{F}_q$ से संबंधित होनी चाहिए।
संदर्भ: यह समस्या CROSS की सुरक्षा का आधार है, जो NIST के एडिशनल सिग्नेचर कॉल के राउंड 2 में शामिल एक पोस्ट-क्वांटम सिग्नेचर स्कीम है। जबकि मानक SD अच्छी तरह से अध्ययन किया गया है, ResSD अपेक्षाकृत नया है, और इसकी सुरक्षा इस धारणा पर टिकी है कि एरर वैल्यू को प्रतिबंधित करने से समस्या महत्वपूर्ण रूप से कमजोर नहीं होती है।

2. कार्यप्रणाली और मुख्य योगदान (Methodology and Key Contributions)

लेखक एक "क्रॉस-पैराडाइम" दृष्टिकोण प्रस्तावित करते हैं, यह प्रदर्शित करते हुए कि ResSD को दो अन्य प्रमुख क्रिप्टोग्राफिक परिवारों: रेगुलर सिंड्रोम डिकोडिंग (RegSD) और लैटिस-आधारित समस्याओं (CVP, SVP, List-CVP, List-SVP) में बदला जा सकता है।

A. रेगुलर सिंड्रोम डिकोडिंग (RegSD) में न्यूनीकरण (Reduction)

लेखक मूल मैट्रिक्स $H$ का विस्तार करके एक नया पैरिटी-चेक मैट्रिक्स $\hat{H}$ निर्मित करते हैं।

निर्माण: $H$ के प्रत्येक कॉलम $H_i$ और प्रत्येक तत्व $r_j \in E$ के लिए, वे $\hat{H}$ में एक ब्लॉक बनाते हैं।
लाइट-रेगुलर वेक्टर्स (Light-Regular Vectors): वे दिखाते हैं कि ResSD का समाधान नए कोड में एक "लाइट-रेगुलर" वेक्टर के अनुरूप होता है। एक लाइट-रेगुलर वेक्टर लंबाई $zn $(जहाँ$ z=|E| $) का एक वेक्टर है जिसे$ z $आकार के$ n$ ब्लॉकों में विभाजित किया गया है, जहाँ प्रत्येक ब्लॉक में ठीक एक गैर-शून्य प्रविष्टि (जो हमेशा 1 होती है) होती है।
परिणाम: यह ResSD को एक विशिष्ट प्रकार के समाधान खोजने के लिए Regular Syndrome Decoding के उदाहरण में बदल देता है।
विश्लेषण: उन्होंने इस नई संरचना के लिए सूचना सेट डिकोडिंग (ISD) एल्गोरिदम (परम्यूटेशन-आधारित और एन्यूमरेशन-आधारित) को अनुकूलित किया। हालाँकि, परिणामी कोड की उच्च दर (high rate) के कारण, ये हमले सीधे मूल ResSD समस्या पर लागू ISD हमलों की तुलना में कम कुशल पाए गए।

B. लैटिस समस्याओं (CVP और SVP) में न्यूनीकरण

शोध पत्र का सबसे महत्वपूर्ण योगदान ResSD को लैटिस समस्याओं, विशेष रूप से क्लोजेस्ट वेक्टर प्रॉब्लम (CVP) और शॉर्टेस्ट वेक्टर प्रॉब्लम (SVP) में मैप करना है।

लैटिस निर्माण: वे लीनियर कोड को $\mathbb{Z}^n$ पर एक लैटिस $\mathcal{L}$ में एम्बेड करते हैं (मानक निर्माण का उपयोग करते हुए जहाँ लैटिस कोड को मॉड्यूल $p$ के रूप में समाहित करता है)।
ज्यामितीय अंतर्दृष्टि (Geometric Insight): वे देखते हैं कि लाइट-रेगुलर वेक्टर्स (ResSD के समाधान) समाधानों के बीच यूक्लिडियन नॉर्म (Euclidean norm) को न्यूनतम करते हैं।
न्यूनीकरण रणनीतियाँ (Reduction Strategies):
1. डिटरमिनिस्टिक न्यूनीकरण (एफाइन डायमीटर): $E$ के सेट पर एक एफाइन ट्रांसफॉर्मेशन लागू करके ताकि उसका "एफाइन डायमीटर" (शिफ्टिंग/स्केलिंग के बाद रेंज) न्यूनतम हो सके, वे ResSD को एक विशिष्ट रेडियस वाले List-CVP समस्या में बदलते हैं।
2. प्रोबेबिलिस्टिक न्यूनीकरण (स्टैंडर्ड डेविएशन): लैटिस को $E$ के माध्य (mean) के चारों ओर केंद्रित करके और स्टैंडर्ड डेविएशन का उपयोग करके, वे ResSD को List-CVP या List-SVP में बदलते हैं। यह सफलता की संभावना और सर्च बॉल के रेडियस के बीच एक ट्रेड-ऑफ की अनुमति देता है।
3. ट्रंकेशन (Truncation): वे "मल्टीप्लिकेटिव ट्रंकेशन" का उपयोग करते हैं (इस तथ्य का लाभ उठाते हुए कि CROSS में $E$ एक मल्टीप्लिकेटिव सबग्रुप है) ताकि $E$ के आकार को कम किया जा सके (जैसे, 7 से 3 तत्वों तक)। यह लैटिस हमले के लिए सर्च स्पेस और आवश्यक रेडियस को नाटकीय रूप से कम कर देता है।

C. हाइब्रिड हमले (Hybrid Attacks)

लेखक इन न्यूनीकरणों को आधुनिक लैटिस-सॉल्विंग तकनीकों के साथ जोड़ते हैं:

Hybrid-BatchCVP: लैटिस डायमेंशन को कम करने के लिए निर्देशांकों के एक उपसमुच्चय का अनुमान लगाना, फिर CVP के एक बैच को हल करना।
Hybrid-ListCVP: ट्रंकेशन, प्रोबेबिलिस्टिक रैंडमाइजेशन और लैटिस एन्यूमरेशन (सीविंग) को मिलाकर List-CVP/List-SVP उदाहरणों को हल करना।

3. परिणाम और सुरक्षा मूल्यांकन (Results and Security Evaluation)

लेखकों ने CROSS पैरामीटर्स ( $n=127, 187, 251$ ; $q=127$ ; $|E|=7$ ) पर अपने हमलों का मूल्यांकन किया।

मौजूदा हमलों के साथ तुलना: ResSD के लिए ISD एल्गोरिदम का सीधा अनुकूलन (जैसा कि CROSS स्पेसिफिकेशन में प्रस्तावित है) सबसे कुशल हमला बना हुआ है।
लैटिस हमले का प्रदर्शन:
- लैटिस-आधारित न्यूनीकरण (CVP/List-CVP) ने CROSS की सुरक्षा को तोड़ा नहीं है। प्रस्तावित लैटिस हमलों की टाइम कॉम्प्लेक्सिटी आमतौर पर ज्ञात सर्वश्रेष्ठ ISD हमलों से अधिक थी।
- टाइम-मेमोरी ट्रेड-ऑफ: लैटिस दृष्टिकोण एक अनूठा लाभ प्रदान करता है: एक बेहतर टाइम/मेमोरी ट्रेड-ऑफ। जबकि ISD हमलों के लिए अक्सर एक्सपोनेंशियल मेमोरी की आवश्यकता होती है, लैटिस-आधारित हमलों (विशेष रूप से Hybrid-ListCVP) को उच्च टाइम कॉम्प्लेक्सिटी की कीमत पर काफी कम मेमोरी (उदाहरण के लिए, 128-बिट सुरक्षा स्तर के लिए $2^{26}$ बिट्स) का उपयोग करने के लिए ट्यून किया जा सकता है।
- CVP/SVP में क्षरण (Degeneration): कुछ मापदंडों के लिए (विशेष रूप से जब $E$ को आकार $z'=3$ में ट्रंकेट किया जाता है), List-CVP समस्या ह्यूरिस्टिक रूप से एक मानक CVP या SVP समस्या में बदल जाती है। हालाँकि, इन मामलों में भी, जटिलता CROSS के सुरक्षा थ्रेशोल्ड से ऊपर बनी रहती है।

मुख्य निष्कर्ष: CROSS की सुरक्षा वर्तमान में इन नए क्रॉस-पैराडाइम न्यूनीकरणों से खतरे में नहीं है। सबसे अच्छा हमला सीधा ISD एन्यूमरेशन ही है।

4. महत्व और निहितार्थ (Significance and Implications)

नया विश्लेषणात्मक परिप्रेक्ष्य: यह शोध पत्र लैटिस क्रिप्टोग्राफी के लेंस के माध्यम से ResSD का पहला व्यापक विश्लेषण प्रदान करता है। यह कोड-आधारित और लैटिस-आधारित क्रिप्टोएनालिसिस के बीच के अंतर को पाटता है।
ResSD की समझ: यह प्रदर्शित करता है कि ResSD केवल SD का एक प्रतिबंधित संस्करण नहीं है, बल्कि इसमें संरचनात्मक गुण (जैसे लाइट-रेगुलरिटी) हैं जो इसे विशिष्ट लैटिस में शॉर्ट वेक्टर्स खोजने के रूप में मॉडल करने की अनुमति देते हैं।
भविष्य के डिज़ाइन मार्गदर्शन: हालांकि CROSS सुरक्षित है, लेखक इस बात पर जोर देते हैं कि प्रतिबंध सेट $E$ का "एफाइन डायमीटर" एक महत्वपूर्ण पैरामीटर है। भविष्य के कोड-आधारित स्कीम्स के डिजाइनरों को यह सुनिश्चित करना चाहिए कि $E$ का एफाइन डायमीटर बड़ा हो ताकि इन लैटिस-आधारित न्यूनीकरणों का प्रतिरोध किया जा सके।
पद्धतिगत नवाचार (Methodological Innovation): मल्टीप्लिकेटिव ट्रंकेशन को लैटिस न्यूनीकरण के साथ जोड़ना अन्य कोड-आधारित स्कीम्स के विश्लेषण के लिए एक शक्तिशाली ढांचा प्रदान करता है जहाँ एरर डिस्ट्रीब्यूशन में बीजगणितीय संरचना होती है।

निष्कर्षतः, जबकि यह शोध पत्र CROSS को तोड़ता नहीं है, यह प्रतिबंधित सिंड्रोम डिकोडिंग के लिए उपलब्ध क्रिप्टोएनालिटिक टूलकिट का महत्वपूर्ण विस्तार करता है, यह सिद्ध करते हुए कि लैटिस-आधारित तकनीकें पोस्ट-क्वांटम कोड-आधारित हस्ताक्षरों के विश्लेषण के लिए एक व्यवहार्य और आवश्यक वेक्टर हैं।