An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

तकनीकी सारांश: 3-टुपल लैटिस सीविंग के लिए एक बेहतर क्वांटम एल्गोरिदम

समस्या विवरण
उच्च-आयामी लैटिस (lattice) में शॉर्टेस्ट वेक्टर प्रॉब्लम (SVP) एक मौलिक समस्या है, जो लैटिस-आधारित क्रिप्टोग्राफी की सुरक्षा का आधार है। जबकि SVP के लिए सबसे तेज़ प्रमाणित एल्गोरिदम का रनटाइम घातांकीय (exponential) होता है, सबसे तेज़ ज्ञात ह्यूरिस्टिक हमले "सीविंग" (sieving) विधियों का उपयोग करते हैं। ये विधियाँ लैटिस वेक्टर्स को संयोजित करके छोटे वेक्टर्स उत्पन्न करने के लिए उन्हें बार-बार मिलाती हैं। इन हमलों की दक्षता को अक्सर समय जटिलता (time complexity) और मेमोरी उपयोग के बीच के ट्रेड-ऑफ द्वारा मापा जाता है।

विशेष रूप से, $k$-टुपल सीविंग बुनियादी 2-टुपल दृष्टिकोण का सामान्यीकरण करती है, जहाँ $k$ ऐसे वेक्टर्स की खोज की जाती है जिनका हस्ताक्षरित योग (signed sum) एक छोटा नॉर्म प्राप्त करता है। $k$ को बढ़ाने से आवश्यक मेमोरी (लिस्ट का आकार) कम हो जाती है, लेकिन वैध $k$-टुपल्स खोजने की समय जटिलता बढ़ जाती है। $k=3$ के लिए, न्यूनतम मेमोरी आवश्यकता लगभग $2^{0.1887d}$ है, लेकिन इस कार्य से पहले सबसे अच्छी ज्ञात क्वांटम समय जटिलता $2^{0.3098d}$ थी। लक्ष्य इस क्वांटम समय जटिलता को कम करना है जबकि न्यूनतम मेमोरी फुटप्रिंट को बनाए रखना है।

कार्यप्रणाली (Methodology)
लेखक "3-लिस्ट समस्या" (एक लिस्ट $L$ के आकार $m \approx 2^{0.1887d}$ से $m$ विशिष्ट 3-टुपल्स $(x, y, z)$ खोजना ताकि $\|x - y - z\| \le 1$ हो) के लिए एक नया क्वांटम एल्गोरिदम प्रस्तावित करते हैं। यह एल्गोरिदम, जिसे 3List नाम दिया गया है, दो प्रमुख तकनीकों को जोड़कर पिछले दृष्टिकोणों में सुधार करता है:

1. नेस्टेड एम्प्लीट्यूड एम्प्लीफिकेशन (दो-ओरेकल खोज):
   सभी संभावित ट्रिपल्स पर एकल खोज के बजाय, एल्गोरिदम दो-ओरेकल खोज से प्रेरित एक नेस्टेड संरचना का उपयोग करता है। खोज को दो चरणों में विभाजित किया गया है:

   • चरण 1: ऐसे जोड़े $(x, y)$ खोजें जिनका आंतरिक उत्पाद (inner product) $\langle x, y \rangle \ge 1/3$ हो।
   • चरण 2: ऐसे जोड़े के मिलने के बाद, एक वेक्टर $z$ खोजें ताकि $\langle \frac{x-y}{\|x-y\|}, z \rangle \ge 2/3$ हो।
     एल्गोरिदम इन नेस्टेड चरणों में समाधान खोजने की संभावना को बढ़ाने के लिए एम्प्लीट्यूड एम्प्लीफिकेशन का उपयोग करता है।

2. रैंडम प्रोडक्ट कोड्स (RPCs) के माध्यम से लोकैलिटी-सेंसिटिव फ़िल्टरिंग:
   नेस्टेड खोज की लागत को अनुकूलित करने के लिए, लेखक रैंडम प्रोडक्ट कोड्स (RPCs) का उपयोग करके एक प्रीप्रोसेसिंग चरण पेश करते हैं।

   • प्रीप्रोसेसिंग: एल्गोरिदम "सेंटर पॉइंट्स" (RPCs) के दो सेटों, $C$ और $C'$, को सैंपल करता है और डेटा संरचनाएं (जो QCRAM में संग्रहीत हैं) बनाता है जो प्रत्येक लैटिस वेक्टर $x \in L$ को उन सेंटर पॉइंट्स $c \in C$ (और $c' \in C'$) से मैप करती है जो उसके "करीब" हैं (अर्थात, जिनका आंतरिक उत्पाद अधिक है)।
   • खोज प्रतिबंध (Search Restriction): खोज के दौरान, $x$ के लिए सभी संभावित $y$ की जाँच करने के बजाय, एल्गोरिदम खोज को केवल उन $y$ तक सीमित कर देता है जो $x$ के साथ एक करीबी सेंटर पॉइंट साझा करते हैं। इसी तरह, एक जोड़े $(x, y)$ के लिए, $z$ की खोज को उन वेक्टर्स तक सीमित कर दिया जाता है जो सामान्यीकृत अंतर $\frac{x-y}{\|x-y\|}$ के साथ एक सेंटर पॉइंट साझा करते हैं।
   • लागत संतुलन: यह लोकैलिटी फ़िल्टरिंग एल्गोरिदम को दो-चरणों की एम्प्लीट्यूड एम्प्लीफिकेशन की कम्प्यूटेशनल लागतों को संतुलित करने की अनुमति देती है। सेंटर पॉइंट्स के "पड़ोसों" पर ध्यान केंद्रित करके, एल्गोरिदम उन असंतुलित लागतों से बचता है जो पिछले सरल दो-ओरेकल दृष्टिकोणों में समस्या पैदा करती थीं।

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

• बेहतर समय जटिलता: यह पेपर एक क्वांटम एल्गोरिदम प्रस्तुत करता है जो $m \approx 2^{0.1887d}$ आकार की लिस्ट के साथ 3-टुपल सीविंग समस्या को $2^{0.2846d + o(d)}$ समय में हल करता है। यह समान मेमोरी रिजीम के लिए पिछली सर्वोत्तम ज्ञात क्वांटम समय जटिलता $2^{0.3098d}$ में सुधार करता है।
• मेमोरी दक्षता: एल्गोरिदम 3-टुपल सीविंग के लिए न्यूनतम मेमोरी आवश्यकता ($2^{0.1887d}$ क्लासिकल बिट्स और QCRAM बिट्स) को बनाए रखता है, जबकि केवल $2^{o(d)}$ क्यूबिट्स का उपयोग करता है। यह अन्य क्वांटम सीविंग दृष्टिकोणों के विपरीत है जिन्हें घातांकीय क्यूबिट्स या क्वांटम रीड-राइट मेमोरी (QQRAM) की आवश्यकता होती है।
• एल्गोरिदम संरचना: यह कार्य प्रदर्शित करता है कि RPCs का उपयोग करके एक प्रीप्रोसेसिंग चरण द्वारा समर्थित एक परिष्कृत नेस्टेड एम्प्लीट्यूड एम्प्लीफिकेशन रणनीति, जटिल क्वांटम वॉक संरचनाओं का उपयोग किए बिना, पिछले क्वांटम वॉक-आधारित या सरल एम्प्लीट्यूड एम्प्लीफिकेशन दृष्टिकोणों से बेहतर प्रदर्शन कर सकती है।

परिणाम

• सैद्धांतिक सीमा: मुख्य परिणाम (थ्योरम 3.1) यह स्थापित करता है कि एल्गोरिदम उच्च संभावना के साथ $2^{0.284551d + o(d)}$ समय में $m$ समाधान पाता है।
• SVP अनुप्रयोग: "यूनिफॉर्म ह्यूरिस्टिक" के तहत (जो मानता है कि सीविंग इटरेशन में लैटिस वेक्टर्स एक गोले पर स्वतंत्र यूनिफॉर्म सैंपल की तरह व्यवहार करते हैं), यह एल्गोरिदम $2^{0.2846d + o(d)}$ समय जटिलता और $2^{0.1887d}$ मेमोरी के साथ $\gamma$-SVP के लिए एक ह्यूरिस्टिक क्वांटम एल्गोरिदम प्रदान करता है।
• तुलना:
  • यह सबसे सीमित कुल मेमोरी $2^{0.1887d}$ के लिए सबसे तेज़ ज्ञात क्वांटम एल्गोरिदम है।
  • यह सबसे अच्छे ज्ञात क्लासिकल 2-टुपल सीविंग एल्गोरिदम ($2^{0.2925d}$) से तेज़ है।
  • हालाँकि, लेखक नोट करते हैं कि उनके 3-टुपल दृष्टिकोण का टाइम-मेमोरी प्रोडक्ट ($2^{0.4733d}$) सबसे अच्छे ज्ञात 2-टुपल क्वांटम दृष्टिकोण ($2^{0.4638d}$) की तुलना में थोड़ा खराब है, हालांकि बाद वाले को काफी अधिक मेमोरी और अधिक मांग वाले क्वांटम हार्डवेयर (QQRAM) की आवश्यकता होती है।

महत्व और दावे
लेखक अपने कार्य के महत्व को विनम्रतापूर्वक प्रस्तुत करते हैं:

• क्रमिक सुधार (Incremental Improvement): वे स्वीकार करते हैं कि एक्सपोनेंट में सुधार (0.3098 से 0.2846) अपेक्षाकृत छोटा है और वर्तमान क्रिप्टोग्राफिक कुंजी आकारों के लिए तत्काल खतरा पैदा करने की संभावना नहीं है, क्योंकि क्रिप्टोग्राफर पहले से ही क्वाड्रेटिक क्वांटम स्पीडअप (ग्रोवर का एल्गोरिदम) को ध्यान में रखते हैं, जो अक्सर यहाँ प्राप्त विशिष्ट स्पीडअप से अधिक होता है।
• टूलबॉक्स विस्तार: प्राथमिक योगदान यह प्रदर्शित करना है कि लैटिस सीविंग के लिए तकनीकों का "टूलबॉक्स" समाप्त नहीं हुआ है। विशेष रूप से, वे दिखाते हैं कि एक अच्छी तरह से चुने गए प्रीप्रोसेसिंग चरण (RPCs) के साथ मानक एम्प्लीट्यूड एम्प्लीफिकेशन को जोड़कर, अधिक जटिल क्वांटम वॉक संरचनाओं का उपयोग किए बिना भी सुधार प्राप्त किया जा सकता है।
• हार्डवेयर व्यवहार्यता: यह एल्गोरिदम अपने कम क्यूबिट काउंट ($2^{o(d)}$) और QQRAM के बजाय केवल QCRAM पर निर्भरता के कारण महत्वपूर्ण है, जो इसे लैटिस क्रिप्टोग्राफी पर क्वांटम हमलों के निकट-अवधि सैद्धांतिक विश्लेषण के लिए एक अधिक यथार्थवादी उम्मीदवार बनाता है।
• भविष्य की दिशाएँ: लेखक सुझाव देते हैं कि जबकि उनका वर्तमान दृष्टिकोण बुनियादी एम्प्लीट्यूड एम्प्लीफिकेशन का उपयोग करता है, यह अभी भी एक खुला प्रश्न है कि क्या क्वांटम वॉक 2-टुपल या 4-टुपल सीविंग में और सुधार कर सकते हैं, या क्या वर्तमान नेस्टेड दृष्टिकोण "मेनी सॉल्यूशंस" सेटिंग के लिए 3-टुपल सीविंग के लिए इष्टतम है।