QUBO Modeling of Module Learning With Errors: Stability and Scaling in Post-Quantum Cryptography

तकनीकी सारांश: मॉड्यूल लर्निंग विद एरर्स (MLWE) का QUBO मॉडलिंग

समस्या विवरण
लैटिस-आधारित पोस्ट-क्वांटम क्रिप्टोग्राफी (PQC), विशेष रूप से MLWE समस्या पर आधारित स्कीमें, क्वांटम हमलों के विरुद्ध प्रणालियों को सुरक्षित करने के लिए एक प्रमुख दावेदार हैं। MLWE की मुख्य कठिनाई शोर वाले रैखिक संबंधों $b = As + e \pmod q$ से एक छिपे हुए सीक्रेट वेक्टर $s$ को पुनः प्राप्त करने में निहित है, जहाँ $A$ एक सार्वजनिक मैट्रिक्स है और $e$ एक छोटा एरर (त्रुटि) वेक्टर है। जबकि क्लासिकल लैटिस रिडक्शन एल्गोरिदम (जैसे BKZ) और क्वांटम-एन्हांस्ड सर्च मेथड्स का व्यापक अध्ययन किया गया है, इस बात की समझ में एक अंतराल है कि कैसे क्वांटम एनीलिंग के अनुकूल एक एकीकृत अनुकूलन ढांचे (optimization framework) में सीक्रेट और एरर दोनों चरों (variables) को स्पष्ट रूप से एनकोड किया जाए। मौजूदा फॉर्मूलेशन अक्सर निर्णय आउटपुट पर ध्यान केंद्रित करते हैं या शोर चरों को हटा देते हैं, जिसमें विक्षोभ (perturbations) के तहत समाधान परिदृश्य (solution landscape) की स्थिरता का विश्लेषण करने के लिए पारदर्शी प्रतिनिधित्व का अभाव होता है।

कार्यप्रणाली (Methodology)
लेखक छोटे MLWE इंस्टेंस को क्वाड्रेटिक अनकन्स्ट्रेंड बाइनरी ऑप्टिमाइजेशन (QUBO) मॉडल में एनकोड करने के लिए एक रचनात्मक ढांचे का प्रस्ताव करते हैं। कार्यप्रणाली में निम्नलिखित चरण शामिल हैं:

1. संयुक्त एनकोडिंग (Joint Encoding): शोर को हाशिए पर रखने (marginalize) वाले दृष्टिकोणों के विपरीत, यह कार्य सीक्रेट गुणांकों ($s$) और एरर घटकों ($e$) दोनों को एक एकल बाइनरी वेक्टर $z$ में स्पष्ट रूप से एनकोड करता है। पूर्णांक मानों को सीमित-बिट बाइनरी एक्सपेंशन के माध्यम से दर्शाया जाता है (जैसे, $s_i = \sum 2^k x_{ik}$)।
2. ऑब्जेक्टिव फंक्शन फॉर्मुलेशन: MLWE रिकवरी समस्या को एक रेसिडुअल मिनिमाइजेशन समस्या में परिवर्तित किया जाता है। शोर वाले मामले के लिए, ऑब्जेक्टिव फंक्शन को इस प्रकार परिभाषित किया गया है:
   $$\min_{s,e} \|As + e - b\|^2_2 + \lambda\|e\|^2_2$$
   जहाँ $\lambda$ एक रेगुलराइजेशन पैरामीटर है। बाइनरी एनकोडिंग को प्रतिस्थापित करने से यह एक मानक QUBO रूप में परिवर्तित हो जाता है:
   $$\min_{z \in \{0,1\}^{N_{logical}}} z^\top Q z + c^\top z$$
3. मैट्रिक्स संरचना: परिणामी इंटरेक्शन मैट्रिक्स $Q$ एक ब्लॉक संरचना प्रदर्शित करता है:
   $$Q = \begin{bmatrix} Q_{ss} & Q_{se} \\ Q_{es} & Q_{ee} \end{bmatrix}$$
   जहाँ $Q_{ss}$ सीक्रेट चरों के बीच की अंतःक्रियाओं को दर्शाता है, $Q_{ee}$ शोर रेगुलराइजेशन को एनकोड करता है, और $Q_{se}$ सीक्रेट्स और शोर के बीच के कपलिंग (coupling) को कैप्चर करता है।
4. स्थिरता विश्लेषण (Stability Analysis): शोध पत्र एक अनुकूलन परिदृश्य (optimization landscape) के स्थिरता विश्लेषण को विकसित करता है। यह शोर के क्षेत्र में स्वीकार्य विक्षोभों (admissible perturbations) के क्षेत्र को शोर स्पेस में एक कॉन्वेक्स पॉलीटोप (convex polytope) के रूप में वर्णित करता है, जो प्रतिस्पर्धी कैंडिडेट सीक्रेट्स के अनुरूप हाफ-स्पेस के इंटरसेक्शन द्वारा परिभाषित होता है। यह ज्यामितीय दृष्टिकोण एनर्जी गैप ($\Delta E = E_2 - E_1$) के साथ जुड़ा हुआ है, जो ग्राउंड स्टेट और पहले एक्साइटेड स्टेट के बीच का अंतर है।

मुख्य परिणाम
लेखकों ने सटीक सिमुलेशन (एग्जॉस्टिव एन्यूमरेशन) का उपयोग करके लो-डायमेंशनल बेंचमार्क इंस्टेंस (विशेष रूप से $q=4$ के साथ $3 \times 3$ सिस्टम) पर संख्यात्मक प्रयोग किए:

• सटीक रिकवरी: शोर रहित ($e=0$) और शोर युक्त ($e \neq 0$) दोनों सेटिंग्स में, QUBO फॉर्मुलेशन ने प्लांटेड सीक्रेट वेक्टर और डिस्क्रीटाइज्ड एरर वेक्टर को अद्वितीय ग्लोबल मिनिमम के रूप में सफलतापूर्वक पहचाना।
• स्थिरता सत्यापन: संख्यात्मक परिणामों ने ज्यामितीय स्थिरता और ऊर्जा व्यवहार के बीच सैद्धांतिक संबंध की पुष्टि की। वह क्षेत्र जहाँ ऊर्जा गैप सकारात्मक बना रहा, वह ज्यामितीय रूप से व्युत्पन्न स्वीकार्य विक्षोभों के कॉन्वेक्स पॉलीटोप के साथ मेल खाता था।
• स्केलिंग विश्लेषण: अध्ययन ने लॉजिकल वेरिएबल्स ($N_{logical} = n\lceil \log_2 q \rceil + m\lceil \log_2 q_e \rceil$) के स्केलिंग को मापा। एक क्रिप्टोग्राफिक रूप से प्रासंगिक इंस्टेंस (जैसे $n=256, m=512$ के साथ Kyber-जैसे पैरामीटर्स) के लिए, लॉजिकल वेरिएबल की संख्या लगभग 5,120 तक पहुँच जाती है।
• हार्डवेयर बाधाएं: विश्लेषण इस बात पर प्रकाश डालता है कि हालांकि लॉजिकल वेरिएबल्स की संख्या आयाम के साथ रैखिक रूप से बढ़ती है, लेकिन परिणामी QUBO की सघन कनेक्टिविटी (A की संरचना के कारण) एक महत्वपूर्ण एम्बेडिंग ओवरहेड पैदा करती है। यह क्रिप्टोग्राफिक रूप से प्रासंगिक इंस्टेंस को वर्तमान क्वांटम एनीलिंग हार्डवेयर की क्षमता से बहुत दूर ले जाता है।

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

इस कार्य का प्राथमिक महत्व निम्नलिखित में निहित है:

1. एकीकृत प्रतिनिधित्व: एक पारदर्शी ढांचा प्रदान करना जो सीक्रेट और एरर को संयुक्त रूप से मॉडल करता है, जिससे उनके बीच की अंतःक्रिया का एक ही अनुकूलन परिदृश्य के भीतर अध्ययन करना संभव होता है।
2. रोबस्टनेस फ्रेमवर्क: लैटिस-आधारित समस्याओं और क्वांटम अनुकूलन के बीच एक व्यवस्थित संबंध स्थापित करना, जो ज्यामितीय (पॉलीटोप) और ऊर्जा (गैप) दोनों दृष्टिकोणों के माध्यम से QUBO फॉर्मुलेशन की मजबूती का विश्लेषण करने के उपकरण प्रदान करता है।
3. बेंचमार्किंग: क्वांटम ऑप्टिमाइजेशन सेटिंग्स में लैटिस-आधारित समस्याओं के अध्ययन के लिए एक संरचित आधार बनाना, जो भविष्य के हाइब्रिड क्वांटम-क्लासिकल ह्यूरिस्टिक्स या स्पार्स QUBO वेरिएंट के लिए एक संदर्भ के रूप में कार्य करेगा।

निष्कर्षतः, यह कार्य लैटिस-आधारित क्रिप्टोग्राफिक मॉडलिंग और हार्डवेयर-अवेयर बाइनरी ऑप्टिमाइजेशन के बीच के सेतु को जोड़ता है, जो QUBO में MLWE को एनकोड करने की सैद्धांतिक व्यवहार्यता को स्पष्ट करता है और वर्तमान क्वांटम एनीलिंग आर्किटेक्चर द्वारा लगाई गई व्यावहारिक सीमाओं को रेखांकित करता है।