Post-Quantum Cryptography from Quantum Stabilizer Decoding

यहाँ लु, पोरेम्बा, क्वेक और रामकुमार के शोध पत्र "Post-Quantum Cryptography from Quantum Stabilizer Decoding" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण और प्रेरणा

समस्या:
वर्तमान पोस्ट-क्वांटम क्रिप्टोग्राफी (PQC) मुख्य रूप से हार्डनेस असाइनमेंट के एक संकीर्ण सेट पर निर्भर करती है, विशेष रूप से लैटिस-आधारित (Learning with Errors - LWE) और कोड-आधारित (Learning Parity with Noise - LPN) समस्याओं पर। हालांकि ये क्वांटम-प्रतिरोधी माने जाते हैं, लेकिन समुदाय के सामने महत्वपूर्ण जोखिम हैं:

1. विविधता का अभाव: यदि LWE या LPN के विरुद्ध कोई बड़ी सफलता मिलती है, तो यह अधिकांश क्रिप्टोग्राफिक इंफ्रास्ट्रक्चर को खतरे में डाल देगा।
2. शास्त्रीय जड़ें (Classical Roots): मौजूदा धारणाएं शास्त्रीय गणित पर आधारित हैं। इन धारणाओं की विफलता का प्रभाव मौलिक क्वांटम सूचना विज्ञान कार्यों पर नहीं पड़ सकता है।
3. भेद्यता (Vulnerability): अन्य PQC उम्मीदवारों (जैसे कि आइसोजीनी) पर हालिया शास्त्रीय हमलों ने एकल प्रकार की हार्डनेस पर निर्भर रहने की नाजुकता को उजागर किया है।

प्रस्तावित समाधान:
लेखक शास्त्रीय क्रिप्टोग्राफी को एक नेटिव क्वांटम हार्डनेस असाइनमेंट पर आधारित करने का प्रस्ताव देते हैं: यादृच्छिक (random) क्वांटम स्टेबलाइजर कोड्स को डिकोड करने की कठिनाई। विशेष रूप से, वे Learning Stabilizers with Noise (LSN) समस्या पर ध्यान केंद्रित करते हैं, जो LPN का क्वांटम एनालॉग है।

• LSN चुनौती: एक यादृच्छिक क्लिफोर्ड एनकोडिंग $C$ और एक शोरयुक्त (noisy) क्वांटम कोडवर्ड $E C |0^{n-k}\rangle \otimes |\psi\rangle$ दिया गया है, जिसमें से लॉजिकल स्टेट $|\psi\rangle$ को पुनः प्राप्त करना है।
• मुख्य अंतर्दृष्टि: हाल के कार्यों ने स्थापित किया है कि औसत-मामले (average-case) वाला LSN, शुद्ध रूप से शास्त्रीय समस्या के समान है जिसके इनपुट/आउटपुट शास्त्रीय हैं, जिससे यह शास्त्रीय क्रिप्टोग्राफी के लिए व्यवहार्य बन जाता है।

2. कार्यप्रणाली और तकनीकी दृष्टिकोण

लेखकों का दृष्टिकोण तीन मुख्य तकनीकी स्तंभों पर आधारित है:

A. सिम्पलेक्टिक LPN (sympLPN) में न्यूनीकरण (Reduction)

प्राथमिक चुनौती यह है कि LSN में क्वांटम अवस्थाएँ शामिल हैं, जबकि क्रिप्टोग्राफी के लिए शास्त्रीय इनपुट की आवश्यकता होती है। लेखक LSN को Symplectic LPN (sympLPN) नामक एक शास्त्रीय समस्या में बदलकर इस अंतर को पाटते हैं।

• LSN फॉर्मूलेशन: LSN का शास्त्रीय समकक्ष इसमें शामिल है जहाँ $([A|B], Ax + By + e)$दिया गया है और$x, y$को पुनः प्राप्त करना है, जहाँ$A$और$B$ के कॉलम सिम्पलेक्टिकली ऑर्थोगोनल हैं।
• sympLPN में न्यूनीकरण: लेखक सिद्ध करते हैं कि LSN (जहाँ $k = O(\log n)$ लॉजिकल क्यूबिट्स हैं) sympLPN में न्यूनीकृत होता है, जो एक निर्णय समस्या (decision problem) है जहाँ व्यक्ति को $(A, Ax+e)$और$(A, u)$के बीच अंतर करना होता है, जहाँ$A$एक यादृच्छिक **आइसोट्रोपिक** (सिम्पलेक्टिकली ऑर्थोगोनल) मैट्रिक्स है और$e$ डिपोलराइजिंग नॉइज़ है।
• महत्व: यह न्यूनीकरण क्वांटम कोड्स को डिकोड करने की कठिनाई पर आधारित शास्त्रीय क्रिप्टोग्राफिक प्रिमिटिव्स के निर्माण की अनुमति देता है।

B. सुरक्षा प्रमाणों में संरचनात्मक बाधाओं को दूर करना

मानक LPN-आधारित क्रिप्टोग्राफी (जैसे एलेखोविच-शैली की PKE) इस तथ्य पर निर्भर करती है कि एनकोडिंग मैट्रिक्स में समान रूप से यादृच्छिक, स्वतंत्र प्रविष्टियाँ होती हैं। sympLPN में, मैट्रिक्स $A$ के पास सिम्पलेक्टिकली ऑर्थोगोनल कॉलम होने चाहिए, जो एक मजबूत बीजगणितीय निर्भरता पैदा करता है।

• बाधा: मानक सेल्फ-रिडक्शन (जैसे $k$ लॉजिकल बिट्स वाली समस्या को $k-1$ बिट्स में बदलना) sympLPN के लिए विफल हो जाता है क्योंकि एक कॉलम को हटाने से शेष इंस्टेंस यादृच्छिक से भिन्न दिखने लगता है, जिससे सिम्पलेक्टिक संरचना नष्ट हो जाती है।
• समाधान (सिम्पलेक्टिक स्कैम्बलिंग): लेखक सिम्पलेक्टिक सबस्पेस को "स्कैम्बल" करने के लिए नवीन तकनीकों का विकास करते हैं:
  1. हाइपरप्लेन रोटेशन: वे एक स्पार्स रैंडम क्लिफोर्ड ऑपरेटर पेश करते हैं जो सिम्पलेक्टिक हाइपरप्लेन को घुमाता है, जिससे प्रभावी रूप से सबस्पेस का आधार (basis) रैंडमाइज हो जाता है।
  2. नॉइज़ सिमेट्राइजेशन: वे रोटेशन के बाद एरर डिस्ट्रीब्यूशन को डिपोलराइजिंग रूप में बहाल करने के लिए नॉइज़ फ्लडिंग और परम्यूटेशन का उपयोग करते हैं।
  3. इंटरपोलेशन ट्रिक: वे सिद्ध करते हैं कि यदि एक न्यूनीकरण विशिष्ट शोर की स्थितियों के तहत विफल होता है, तो अतिरिक्त शोर के साथ एक वैकल्पिक न्यूनीकरण सफल होगा, जो $\text{sympLPN}(n, n, p)$ से $\text{sympLPN}(n-1, n, p')$ तक एक वैध न्यूनीकरण सुनिश्चित करता है।

C. क्रिप्टोग्राफिक प्रिमिटिव्स का निर्माण

sympLPN की कठिनाई का उपयोग करते हुए, लेखक निम्नलिखित का निर्माण करते हैं:

1. पब्लिक-की एन्क्रिप्शन (PKE): लो-नॉइज़ रिजीम ($p = O(1/\sqrt{n})$) पर आधारित।
2. ओब्लिवियस ट्रांसफर (OT): PKE को Strongly Uniform PKE (SU-PKE) में अपग्रेड करके प्राप्त किया गया है, जहाँ पब्लिक की एक यूनिफॉर्म रैंडम स्ट्रिंग के समान कम्प्यूटेशनल रूप से अविभेद्य है।
3. वन-वे फंक्शन्स (OWF): कॉन्स्टेंट-नॉइज़ रिजीम ($p = \Omega(1)$) पर आधारित।

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

1. नई हार्डनेस धारणा: यह शोध पत्र sympLPN (और विस्तार से, क्वांटम स्टेबलाइजर डिकोडिंग) को पोस्ट-क्वांटम क्रिप्टोग्राफी के एक व्यवहार्य, स्वतंत्र आधार के रूप में स्थापित करता है।
2. कुशल निर्माण:
   • PKE: प्रस्तावित योजना $O(n^2)$ एन्क्रिप्शन और $O(n)$ डिक्रिप्शन प्राप्त करती है, जो अत्याधुनिक LPN-आधारित योजनाओं (एलेखोविच-शैली) की दक्षता से मेल खाती है।
   • OT: निर्माण एक राउंड-ऑप्टिमल (4-राउंड) मैलिसियसली सिक्योर ओब्लिवियस ट्रांसफर प्रोटोकॉल प्रदान करता है।
   • MPCT: चूंकि OT सामान्य सिक्योर मल्टी-पार्टी कंप्यूटेशन (MPC) को सक्षम बनाता है, इसलिए यह कार्य यह स्थापित करता है कि क्वांटम स्टेबलाइजर डिकोडिंग "क्रिप्टोमेनिया" की पूर्ण शक्ति का समर्थन करती है।
3. सुरक्षा प्रमाण:
   • लेखक कठोर सुरक्षा न्यूनीकरण (security reductions) प्रदान करते हैं जो यह दर्शाते हैं कि उनके स्कीम्स को तोड़ना अंतर्निहित sympLPN समस्या को हल करने के समान है।
   • वे सिद्ध करते हैं कि $\text{sympLPN}(n, n, p)$ कम से कम $\text{sympLPN}(n-1, n, p)$ के समान कठिन है, जो बीजगणितीय बाधाओं को देखते हुए एक गैर-तुच्छ परिणाम है।
4. तुलनात्मक हार्डनेस विश्लेषण:
   • शोध पत्र साक्ष्य प्रदान करता है कि sympLPN को लीनियर न्यूनीकरण के माध्यम से मानक LPN में न्यूनीकृत नहीं किया जा सकता है। वे सिद्ध करते हैं कि sympLPN से LPN तक कोई भी लीनियर न्यूनीकरण या तो मैट्रिक्स को रैंडमाइज करने में विफल रहेगा या एरर रेट को डिकोड करने योग्य स्तर (शैनन की सीमा से ऊपर) तक बढ़ा देगा।
   • यह सुझाव देता है कि sympLएफ (sympLPN) एक वास्तव में नई हार्डनेस धारणा है, जो मौजूदा लैटिस या कोड-आधारित समस्याओं से भिन्न है।

4. महत्व और प्रभाव

• PQC का विविधीकरण: यह कार्य LWE/LPN के लिए एक महत्वपूर्ण विकल्प प्रदान करता है। यदि LWE या LPN टूट जाते हैं, तो हमारे पास एक मजबूत, क्वांटम-नेटिव बैकअप होगा।
• क्लासिक और क्वांटम के बीच सेतु: यह प्रदर्शित करता है कि क्वांटम सूचना विज्ञान के मौलिक कार्य (क्वांटम एरर-करेक्टिंग कोड को डिकोड करना) सीधे शास्त्रीय क्रिप्टोग्राफी का आधार बन सकते हैं।
• "विन-विन-विन" (Win-Win-Win) परिदृश्य:
  • यदि LSN सुरक्षित है, तो हमें एक नया PQC आधार प्राप्त होता है।
  • यदि LSN टूट जाता है, तो यह क्वांटम एरर करेक्शन की समझ में एक बड़ी सफलता का संकेत देता है।
  • यदि LSN, LPN के समान है, तो यह शास्त्रीय और क्वांटम कोडिंग थ्योरी के बीच गहरे, अप्रत्याशित संबंधों को प्रकट करता है।
• व्यावहारिकता: निर्माण केवल सैद्धांतिक नहीं हैं; वे वर्तमान PQC उम्मीदवारों के साथ प्रतिस्पर्धा करने के लिए पर्याप्त कुशल हैं, जहाँ लो-नॉइज़ रिजीम में सुरक्षा $2^{\Theta(\sqrt{n})}$ के रूप में स्केल होती है।

निष्कर्ष

यह शोध पत्र सफलतापूर्वक तर्क देता है कि यादृच्छिक क्वांटम स्टेबलाइजर कोड्स को डिकोड करना पोस्ट-क्वांटम क्रिप्टोग्राफी के लिए एक सम्मोहक उम्मीदवार है। नवीन सिम्पलेक्टिक स्कैम्बलिंग तकनीकों के माध्यम से महत्वपूर्ण बीजगणितीय बाधाओं को पार करके, लेखक प्रदर्शित करते हैं कि यह क्वांटम-नेटिव समस्या मौजूदा सर्वोत्तम LPN-आधारित स्कीम्स के समान दक्षता के साथ पूर्ण स्पेक्ट्रम के शास्त्रीय क्रिप्टोग्राफिक प्रिमिटिव्स (PKE, OT, MPC) का समर्थन कर सकती है। यह कार्य पोस्ट-क्वांटम सुरक्षा धारणाओं के परिदृश्य को महत्वपूर्ण रूप से व्यापक बनाता है।