Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

तकनीकी सारांश: 2-पावर साइक्लोटोमिक्स पर मॉड्यूल-LWE पर संभाव्य बहुपद क्वांटम हमला

समस्या विवरण
यह शोध पत्र मॉड्यूल लर्निंग विद एरर्स (Module-LWE) आधारित क्रिप्टोग्राफिक स्कीम्स की सुरक्षा पर केंद्रित है, विशेष रूप से NIST-मानकीकृत ML-KEM (पूर्व में CRYSTALS-Kyber) और संबंधित लैटिस-आधारित स्कीम्स (Falcon, Hawk, NTRU) पर, जो 2-पावर साइक्लोटोमिक रिंग्स ($R = \mathbb{Z}[\zeta_{2^k}]$) पर निर्मित हैं। केंद्रीय समस्या 2-पावर साइक्लोटोमिक रिंग्स पर शॉर्टेस्ट वेक्टर प्रॉब्लम (SVP) के माध्यम से मॉड्यूल लैटिस पर गुप्त कुंजियों (secret keys) की रिकवरी है। जबकि शास्त्रीय हमले लैटिस रिडक्शन एल्गोरिदम (जैसे BKZ) पर निर्भर करते हैं जिनकी जटिलता घातांकीय (exponential) होती है, यह शोध पत्र जांच करता है कि क्या एक क्वांटम विरोधी साइक्लोटोमिक रिंग्स की बीजगणितीय संरचना का लाभ उठाकर प्रिंसिपल आइडियल प्रॉब्लम (PIP) और शॉर्ट जनरेटर प्रॉब्लम (SGP) को कुशलतापूर्वक हल कर सकता है।

लेखक पूर्व कार्य (विशेष रूप से CDPR हमले) में दो महत्वपूर्ण अनसुलझे प्रश्नों की पहचान करते हैं:

1. क्या CDPR हमले द्वारा प्राप्त एप्रोक्सिमेशन फैक्टर पर्याप्त छोटा है ताकि पूर्ण ML-KEM गुप्त कुंजियों को तोड़ा जा सके (अर्थात, क्या $\gamma < q/2$ है)?
2. क्या अंतर्निहित क्वांटम PIP सबरूटीन छिपे हुए घातांकीय ओवरहेड्स या जनरलइज्ड रीमैन हाइपोथेसिसिस (GRH) पर निर्भरता के बिना वास्तविक बहुपद-समय (polynomial-time) जटिलता प्राप्त करता है?

कार्यप्रणाली (Methodology)
यह शोध पत्र एक एकीकृत, चार-चरणों वाले हमले के पाइपलाइन (एल्गोरिदम 1) को प्रस्तुत करता है जो सीरीज़ के भाग I–III के परिणामों को एक नए बहुपद-समय क्वांटम PIP एल्गोरिदम (भाग IV) के साथ एकीकृत करता है।

1. मॉड्यूल-टू-आइडियल रिडक्शन: हमला एक मॉड्यूल-LWE इंस्टेंस को प्रिंसिपल आइडियल प्रॉब्लम में बदलने से शुरू होता है। ग्राम-श्मिट अपघटन (Gram-Schmidt decomposition) का उपयोग करके, मॉड्यूल बेसिस को प्रिंसिपल आइडियल्स के उत्पाद में रूपांतरित किया जाता है। लेखक सिद्ध करते हैं कि यह रिडक्शन केवल एक स्थिरांक कारक $\alpha_d = O(1)$ पेश करता है, जो मॉड्यूल रैंक $d$ से स्वतंत्र है।
2. क्वांटम टॉवर PIP: पूर्ण क्षेत्र $\mathbb{Q}(\zeta_{2^k})$ में सीधे PIP को हल करने के बजाय, लेखक एक "टॉवर डीकंपोजिशन" रणनीति प्रस्तावित करते हैं। वे क्षेत्र को द्विघातीय विस्तार (quadratic extensions) की एक श्रृंखला में विभाजित करते हैं: $\mathbb{Q} \subset \mathbb{Q}(\zeta_8) \subset \dots \subset \mathbb{Q}(\zeta_{2^k})$।
   • प्रत्येक स्तर $L$ पर, एल्गोरिदम एबेलियन हिडन सबग्रुप प्रॉब्लम (HSP) का उपयोग करके सापेक्ष विस्तार (relative extension) के लिए PIP को हल करता है।
   • महत्वपूर्ण रूप से, प्रत्येक स्तर पर नए यूनिट जनरेटर्स की संख्या रैखिक रूप से बढ़ती है ($\Delta r_L = 2^{L-3}$), जिससे HSP इंस्टेंस का आकार बहुपद (polynomial) बना रहता है।
   • यह दृष्टिकोण मानक पावर-बेसिस प्रतिनिधित्व में निहित गुणांक विस्फोट (coefficient explosion) से बचता है और GRH की आवश्यकता को समाप्त करता है, क्योंकि $k \le 12$ के लिए मैक्सिमल रियल सबफील्ड का क्लास नंबर 1 सिद्ध किया गया है।
3. लॉग-यूनिट CVP: एक बार जब किसी आइडियल का जनरेटर $g$ मिल जाता है (जो घातांकीय रूप से लंबा हो सकता है), तो एल्गोरिदम इसके लॉग-एम्बेडिंग की गणना करता है। इसके बाद, यह यूनिट विसंगति (unit discrepancy) $\epsilon$ को खोजने के लिए लॉग-यूनिट लैटिस पर क्लोजेस्ट वेक्टर प्रॉब्लम (CVP) को हल करता है ताकि $g = g_0 \epsilon$ हो सके, जहाँ $g_0$ शॉर्ट जनरेटर है।
   • लेखक बाबाई के नियरएस्ट-प्लेन एल्गोरिदम (Babai's nearest-plane algorithm) का उपयोग करते हैं। वे सिद्ध करते हैं कि शॉर्ट रिंग जनरेटर्स के लिए, टारगेट वेक्टर लैटिस के "कैप्चर रेडियस" के भीतर होता है, जिससे बाबाई का एल्गोरिदम यूनिट विसंगति को सटीक रूप से रिकवर कर पाता है।
4. शॉर्ट जनरेटर रिकवरी: CVP समाधान से यूनिट $\epsilon$ को पुनर्गठित किया जाता है, और शॉर्ट जनरेटर $g_0 = g \cdot \epsilon^{-1}$ के रूप में प्राप्त किया जाता है।

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

• बहुपद-समय क्वांटम PIP: यह शोध पत्र 2-पावर साइक्लोटोमिक रिंग्स पर PIP के लिए पहले बहुपद-समय क्वांटम एल्गोरिदम का निर्माण प्रदान करता है। इसकी जटिलता $O(n^3 \log^2 n)$ क्वांटम गेट्स और $O(n^2 \log n)$ क्यूबिट्स है, जहाँ $n$ रिंग डिग्री है। यह Biasse-Song एल्गोरिदम से जुड़े घातांकीय ओवरहेड को हटा देता है।
• टाइट एप्रोक्सिमेशन फैक्टर विश्लेषण: लेखक एक सटीक एप्रोक्सिमेशन फैक्टर $\gamma = \alpha_d \cdot \exp(\sigma_d \sqrt{2 \ln n})$ प्राप्त करते हैं। वे सिद्ध करते हैं कि लॉग-एम्बेडिंग का वेरिएंस $\sigma_d$ $O(1)$ है और मॉडुलस $q$ से स्वतंत्र है।
• क्लास नंबर का सत्यापन: यह कार्य इस प्रमाण (भाग I से) पर निर्भर करता है कि $k \le 12$ के लिए सभी मैक्सिमल रियल सबफील्ड का क्लास नंबर ट्रिवियल ($h^+_k = 1$) है, जो यह सुनिश्चित करता है कि प्रत्येक आइडियल प्रिंसिपल है।
• एकाधिक स्कीम्स तक विस्तार: इस फ्रेमवर्क को ML-KEM के अलावा Falcon, Hawk, और NTRU वेरिएंट्स का विश्लेषण करने के लिए विस्तारित किया गया है, यह प्रदर्शित करते हुए कि समान बीजगणितीय कमजोरियां लागू होती हैं।

परिणाम
लेखक मानकीकृत पैरामीटर सेट्स के लिए ठोस सुरक्षा अनुमान प्रदान करते हैं:

• ML-KEM-1024: हमला एक मीडियन एप्रोक्सिमेशन फैक्टर $\gamma_{med} \approx 21$ और 99वें पर्सेंटाइल फैक्टर $\gamma_{99\%} \approx 103$ प्राप्त करता है। दोनों मान सुरक्षा थ्रेशोल्ड $q/2 = 1665$ से काफी नीचे हैं। सफलता की संभावना $d \le 3$ के लिए $\ge 0.99$ और $d=4$ के लिए $\ge 0.90$ अनुमानित है, जिसे पुनरावृत्ति (repetition) के माध्यम से विफलता की संभावना $< 10^{-6}$ तक कम किया जा सकता है।
• संसाधन अनुमान: ML-KEM-1024 ($n=256$) के लिए, हमले को लगभग $2^{27}$ लॉजिकल गेट्स और $1.4 \times 10^6$ फिजिकल क्यूबिट्स की आवश्यकता होगी (डिस्टेंस 30 के साथ सरफेस कोड मानते हुए)।
• अन्य स्कीम्स:
  • Falcon: हमला Falcon-512 और Falcon-1024 को क्रमशः $72\times$ और $63\times$ के मार्जिन से तोड़ देता है।
  • Hawk: हमला Hawk-512 और Hawk-1024 को तोड़ देता है। Hawk-256 सशर्त रूप से टूटा हुआ है; हालांकि औपचारिक 99% बाउंड थ्रेशोल्ड से अधिक है, अनुभवजन्य सिमुलेशन 99.99% की सफलता दर दिखाते हैं।
  • NTRU: हमला 2-पावर साइक्लोटोमिक रिंग्स पर NTRU-HPS और NTRU-HRSS वेरिएंट्स पर लागू होता है, जो $11\times$ से $45\times$ तक के मार्जिन प्राप्त करता है।

महत्व और दावे
शोध पत्र यह दावा करता है कि वह CDPR हमले के खुले प्रश्नों को हल करता है, यह प्रदर्शित करते हुए कि:

1. एप्रोक्सिमेशन फैक्टर इतना छोटा है कि वह 2-पावर साइक्लोटोमिक रिंग्स पर सभी मानकीकृत ML-KEM, Falcon, Hawk, और NTRU पैरामीटर सेट्स को क्वांटम हमले के तहत तोड़ सकता है।
2. PIP को बिना किसी छिपे हुए घातांकीय कारकों या GRH जैसे अप्रमाणित संख्या-सिद्धांत संबंधी अनुमानों पर निर्भर किए, वास्तविक बहुपद समय ($O(n^3 \log^2 n)$) में हल किया जा सकता है।
3. 2-पावर साइक्लोटोमिक रिंग्स की बीजगणितीय संरचना एक क्वांटम विरोधी को एप्रोक्सिमेशन फैक्टर को सुपर-पॉलिनोमियल ($\approx 2^{54}$ पिछले अनुमानों में) से घटाकर सब-पॉलिनोमियल ($\approx 2^{21}$) करने की अनुमति देती है, जो प्रभावी रूप से इन पोस्ट-क्वांटम उम्मीदवारों की सुरक्षा धारणाओं को तोड़ देती है।

लेखक नोट करते हैं कि हालांकि हमला संभाव्य (probabilistic) है, विफलता की संभावना कम है और इसे स्वतंत्र पुनरावृत्तियों के माध्यम से कम किया जा सकता है। वे इस बात पर जोर देते हैं कि परिणाम 2-पावर साइक्लोटोमिक रिंग्स के विशिष्ट बीजगणितीय गुणों और $k \le 12$ के लिए क्लास नंबर की ट्रिवियलिटी पर निर्भर करते हैं।