💻 computer science

Quantum Key Search Algorithms under Side-channel Attack

यह शोध पत्र एक उन्नत क्वांटम कुंजी खोज एल्गोरिदम का प्रस्ताव करता है जो क्लासिकल विधियों की तुलना में सुपर-क्वाड्रेटिक स्पीडअप प्राप्त करने के लिए साइड-चैनल हमले से प्रेरित त्रुटि वितरणों का लाभ उठाता है और ग्लेसर (Glaser) जैसे मौजूदा क्वांटम दृष्टिकोणों से बेहतर प्रदर्शन करता है, जबकि कुशल डिक स्टेट (Dicke state) कार्यान्वयन के माध्यम से इनपुट स्टेट तैयारी की चुनौतियों का भी समाधान करता है।

मूल लेखक: Yunteng Yang, Jianhong Shi, Hailong Zhang, Hongwei Li, Xiangqun Fu, Yonghui Yang, Yubing Zhu, Yanyang Zhou

प्रकाशित 2026-08-12

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

CC BY 4.0

मूल लेखक: Yunteng Yang, Jianhong Shi, Hailong Zhang, Hongwei Li, Xiangqun Fu, Yonghui Yang, Yubing Zhu, Yanyang Zhou

मूल पेपर CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

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

फिर, वैज्ञानिकों ने एक जादुई उपकरण की खोज की जिसे "क्वांटम कंप्यूटर" कहा जाता है। इसे केवल एक तेज़ कैलकुलेटर के रूप में नहीं, बल्कि एक जादूगर के रूप में सोचें जो एक ही समय में कई चाबियों को देख सकता है। ग्रोवर के एल्गोरिदम (Grover's algorithm) नामक एक प्रसिद्ध ट्रिक का उपयोग करके, यह जादूगर पुराने तरीके की तुलना में बहुत तेज़ी से सही चाबी ढूंढ सकता है—यह समय को एक अरब प्रयासों से घटाकर लगभग तीस हज़ार तक कम कर देता है। लेकिन यहाँ एक मोड़ है: क्या होगा अगर आपको शून्य से शुरुआत न करनी पड़े? क्या होगा यदि एक चालाक चोर ने पहले ही तिजोरी में झाँक लिया हो और सही चाबी का एक "नॉइज़ी" (noisy), धुंधला संस्करण प्राप्त कर लिया हो? शायद उसने देखा कि चाबी "लगभग" 101010 थी, लेकिन कुछ बिट्स धुंधले थे। इसे "साइड-चैनल अटैक" (side-channel attack) कहा जाता है। यह तिजोरी पर उंगली के निशान मिलने जैसा है जो आपको एक संकेत देता है, भले ही वह एकदम सटीक न हो। बड़ा सवाल वैज्ञानिकों के लिए यह है: क्या हम इन धुंधले संकेतों का उपयोग क्वांटम जादूगर को और भी स्मार्ट और तेज़ बनाने के लिए कर सकते हैं?

इन्फॉर्मेशन इंजीनियरिंग यूनिवर्सिटी के शोधकर्ताओं की एक टीम द्वारा लिखा गया यह शोध पत्र ठीक इसी परिदृश्य में गहराई से उतरता है। वे पूछते हैं: यदि हमलावर के पास एक नॉइज़ी की (key) है जिसमें कुछ त्रुटियां हैं (जैसे समाधान की एक धुंधली तस्वीर), तो हम वास्तविक की को पहले से कहीं अधिक तेज़ी से खोजने के लिए क्वांटम कंप्यूटर का उपयोग कैसे कर सकते हैं?

शोधकर्ताओं ने पहले देखा कि एक सामान्य कंप्यूटर इस स्थिति को कैसे संभालता। उन्होंने महसूस किया कि यदि आप जानते हैं कि की "लगभग" सही है, तो आपको रैंडम अंदाज़े नहीं लगाने चाहिए। इसके बजाय, आपको उस की से शुरुआत करनी चाहिए जो नॉइज़ी की के बिल्कुल समान दिखती है, फिर उन कीज़ का अनुमान लगाना चाहिए जिनमें केवल एक छोटी सी गलती है, फिर दो गलतियाँ, और इसी तरह। यह एक लाइब्रेरी में खोज करने जैसा है जहाँ आप पीछे के कमरे से किताबें उठाने के बजाय उन किताबों से शुरुआत करते हैं जो आपकी खोजी जा रही किताब जैसी दिखती हैं। उन्होंने गणना की कि इस "स्मार्ट" क्लासिकल विधि में कितने अनुमान लगाने की आवश्यकता होगी।

इसके बाद, उन्होंने क्वांटम मैकेनिक्स की शक्ति के साथ एक नया क्वांटम एल्गोरिदम बनाया। उन्होंने गौर किया कि पिछले क्वांटम तरीके खोज स्थान (search space) को ऐसे ब्लॉक्स में विभाजित करने की कोशिश करते थे जो एक ज्यामितीय पैटर्न (1, फिर 10, फिर 100) की तरह बढ़ते थे। हालाँकि, शोधकर्ताओं ने पाया कि "नॉइज़ी की" के संकेत वास्तव में गलतियों की संख्या (हैमिंग डिस्टेंस/Hamming distance) के आधार पर एक बहुत ही विशिष्ट पैटर्न बनाते हैं। ज्यामितीय पैटर्न का उपयोग करने के बजाय, उन्होंने चाबियों को इस आधार पर समूहों में विभाजित करने का निर्णय लिया कि उनमें कितनी त्रुटियां हैं: 0 त्रुटियों वाली चाबियों का एक समूह, 1 त्रुटि वाली चाबियों का एक समूह, 2 त्रुटियों का एक समूह, और इसी तरह।

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

जब उन्होंने अपने नए तरीके का परीक्षण करने के लिए सिमुलेशन चलाए, तो परिणाम प्रभावशाली थे। उन्होंने एक 256-बिट की (एक बहुत लंबी, सुरक्षित की) का उपयोग किया जिसमें त्रुटि दर केवल 1% थी (यानी नॉइज़ी की 99% सही थी)।

एक मानक क्लासिकल कंप्यूटर को बिना किसी संकेत के लगभग $2^{256}$ अनुमान लगाने की आवश्यकता होती।
नॉइज़ी हिंट के साथ, एक स्मार्ट क्लासिकल कंप्यूटर को अभी भी लगभग $2^{62.29}$ अनुमान लगाने की आवश्यकता होती।
उनके नए क्वांटम एल्गोरिदम को केवल लगभग $2^{19.77}$ अनुमानों की आवश्यकता थी।

इसका अर्थ यह है कि उनकी क्वांटम विधि, स्मार्ट क्लासिकल विधि की तुलना में काफी तेज़ है। उन्होंने एक "स्पीडअप फैक्टर" (speedup factor) 3.15 की गणना की, जो पिछले तरीकों (जैसे ग्लेसर द्वारा किए गए) द्वारा प्राप्त 2.73 के स्पीडअप से अधिक है। सरल शब्दों में, उनका क्वांटम जादूगर न केवल एक साथ अधिक चाबियाँ देख रहा है; बल्कि वह सही चाबियों को पहले देख रहा है, क्योंकि उन्होंने अपने खोज को व्यवस्थित करने का एक विशिष्ट तरीका अपनाया है।

पेपर स्पष्ट रूप से पुराने, ज्यामितीय रूप से बढ़ने वाले ब्लॉक रणनीति (जैसे मोंटानारो का एल्गोरिदम) के उपयोग के विरुद्ध तर्क देता है। वे दिखाते हैं कि क्योंकि त्रुटियां एक विशिष्ट "बर्नौली डिस्ट्रीब्यूशन" (रैंडम फ्लिप्स का एक पैटर्न) का पालन करती हैं, इसलिए ज्यामितीय दृष्टिकोण सबसे कुशल नहीं है। उनका "हैमिंग डिस्टेंस" दृष्टिकोण, जो त्रुटियों की सटीक संख्या के आधार पर कीज़ को समूहित करता है, वास्तविकता के अधिक अनुकूल है।

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

तकनीकी सारांश: साइड-चैनल हमले के तहत क्वांटम की (Key) खोज एल्गोरिदम

समस्या विवरण
यह शोध क्रिप्टोग्राफिक एल्गोरिदम में की (key) खोज समस्या को संबोधित करता है जब एक हमलावर के पास साइड-चैनल हमलों (SCAs) से प्राप्त एक शोरयुक्त (noisy) की होती है। इस परिदृश्य में, हमलावर एक ऐसी की $Y$ प्राप्त करता है जो वास्तविक लक्ष्य की $k^*$ से कुछ बिट परिवर्तनों (हैमिंग दूरी) से भिन्न होती है। की स्पेस का संभाव्यता वितरण (probability distribution) समान नहीं है; इसके बजाय, यह बिट एरर रेट (BER), $\alpha$ द्वारा निर्धारित $n$ -फोल्ड बर्नौली वितरण (Bernoulli distribution) का अनुसरण करता है। चुनौती इस गैर-समान की स्पेस को कुशलतापूर्वक खोजने की है ताकि $k^*$ को खोजा जा सके, जिसमें शोरयुक्त की द्वारा प्रदान की गई पूर्व जानकारी का लाभ उठाया जा सके। जबकि शास्त्रीय ब्रूट-फोर्स सर्च के लिए $O(N)$ क्वेरीज़ की आवश्यकता होती है और मानक ग्रोवर एल्गोरिदम $O(\sqrt{N})$ प्रदान करता है, दोनों ही SCA द्वारा प्रेरित विशिष्ट बर्नौली वितरण की संरचना का पूर्ण उपयोग करने में विफल रहते हैं। इसके अलावा, मौजूदा क्वांटम दृष्टिकोण, जैसे मोंटानारो का एल्गोरिदम, समान पोस्टीरियर संभावनाओं वाले की ब्लॉक्स के लिए आवश्यक विशिष्ट प्रारंभिक सुपरपोजिशन अवस्थाओं (initial superposition states) को तैयार करने में कठिनाई का सामना करते हैं।

कार्यप्रणाली
लेखक एक व्यापक रूपरेखा प्रस्तावित करते हैं जो सैद्धांतिक मॉडलिंग, एल्गोरिदम डिजाइन और स्टेट प्रिपरेशन (state preparation) तक फैली हुई है:

संभाव्यता मॉडलिंग (Probabilistic Modeling): अध्ययन स्वतंत्र और समान रूप से वितरित (i.i.d.) बिट फ्लिप्स के साथ $\alpha$ की संभावना मानकर की स्पेस वितरण को मॉडल करता है। बेयस प्रमेय (Bayes' theorem) का उपयोग करते हुए, यह दिखाया गया है कि किसी भी उम्मीदवार की (candidate key) की पोस्टीरियर संभावना केवल शोरयुक्त की $Y$ से उसकी हैमिंग दूरी $d$ पर निर्भर करती है। यह स्थापित करता है कि समान हैमिंग दूरी वाली कीओं का पोस्टीरियर संभाव्यता समान होता है।
शास्त्रीय आधार रेखा (Classical Baseline): एक शास्त्रीय की सर्च एल्गोरिदम व्युत्पन्न किया गया है जो पोस्टीरियर संभावना के अवरोही क्रम (descending order) में उम्मीदवार कीओं का भ्रमण करता है (अर्थात, हैमिंग दूरी $d=0$ से $d=n$ तक)। अपेक्षित क्वेरी जटिलता $G_c$ को प्रत्येक दूरी पर उम्मीदवार कीओं के द्विपद वितरण (binomial distribution) के आधार पर कड़ाई से गणना की गई है।
सुधारित क्वांटम एल्गोरिदम:
- विभाजन रणनीति (Partition Strategy): मोंटानारो के एल्गोरिदम के विपरीत, जो की स्पेस को ज्यामितीय रूप से बढ़ते ब्लॉकों $\{1, c, c^2, \dots\}$ में विभाजित करता है, यह शोध पत्र की स्पेस को हैमिंग दूरी $d$ के आधार पर $(n+1)$ ब्लॉकों $\{R_0, R_1, \dots, R_n\}$ में विभाजित करने का प्रस्ताव करता है। प्रत्येक ब्लॉक $R_d$ में ठीक $d$ बिट एरर वाली $\binom{n}{d}$ उम्मीदवार की होती है।
- खोज निष्पादन (Search Execution): एल्गोरिदम इन ब्लॉकों के माध्यम से घटती संभावना (बढ़ती $d$ ) के क्रम में पुनरावृत्ति करता है। प्रत्येक ब्लॉक $R_d$ के लिए, यह उस ब्लॉक की कीओं का एक समान सुपरपोजिशन (uniform superposition) तैयार करता है और ग्रोवर एल्गोरिदम लागू करता है।
- जटिलता विश्लेषण (Complexity Analysis): क्वांटम क्वेरी जटिलता $G_q$ को प्रत्येक ब्लॉक में लक्ष्य की के होने की संभावना के भार के साथ प्रत्येक ब्लॉक पर ग्रोवर सर्च की लागत को जोड़कर व्युत्पन्न किया गया है।
प्रारंभिक अवस्था तैयारी (Initial State Preparation): प्रत्येक ब्लॉक $R_d$ $R_{d}$ के लिए विशिष्ट सुपरपोजिशन अवस्था तैयार करने की कठिनाई को दूर करने के लिए, लेखक उम्मीदवार की अवस्था और डिके स्टेट (Dicke state) $|D^n_d\rangle$ $∣ D_{d}^{n} ⟩$ के बीच समानता स्थापित करते हैं। वे सिद्ध करते हैं कि $Y$ $Y$ से हैमिंग दूरी $d$ $d$ पर स्थित कीओं का समान सुपरपोजिशन, डिके स्टेट $|D^n_d\rangle$ $∣ D_{d}^{n} ⟩$ पर टेंसर उत्पाद के रूप में पाउली-X गेट्स ( $X^{\otimes Y}$ $X^{\otimes Y}$ ) को लागू करके उत्पन्न किया जा सकता है।
- कार्यान्वयन (Implementation): डिके स्टेट को एक शॉर्ट-डेप्थ, डिवाइड-एंड-कॉन्कर सर्किट (बार्ट्शी और आइडनबेंज के कार्य पर आधारित) का उपयोग करके तैयार किया जाता है जिसमें कोई सहायक क्विबिट (auxiliary qubits) की आवश्यकता नहीं होती है। अंतिम अवस्था को शोरयुक्त की $Y$ के आधार पर $O(d)$ X-गेट्स लागू करके प्राप्त किया जाता है।

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

सैद्धांतिक व्युत्पत्ति: यह शोध पत्र साइड-चैनल हमले की स्थितियों के तहत शास्त्रीय और क्वांटम की खोज के लिए कम्प्यूटेशनल जटिलता का एक कठोर व्युत्पत्ति प्रदान करता है, जो विशेष रूप से $n$ -फोल्ड बर्नौली वितरण को मॉडल करता है।
एल्गोरिदम सुधार: यह एक बेहतर क्वांटम की सर्च एल्गोरिदम पेश करता है जो हैमिंग-डिस्टेंस-आधारित ब्लॉक विभाजन रणनीति का उपयोग करता है। यह रणनीति दर्शाई गई है कि मोंटानारो के एल्गोरिदम में उपयोग किए जाने वाले ज्यामितीय विभाजन की तुलना में SCA परिदृश्यों में वास्तविक की वितरण के साथ अधिक सुसंगत है।
स्टेट प्रिपरेशन समाधान: यह कार्य समस्या को डिके स्टेट प्रिपरेशन में बदलकर इनपुट स्टेट प्रिपरेशन की बाधा को हल करता है। यह प्रदर्शित करता है कि आवश्यक अवस्था को $O(nd)$ CNOT गेट्स और कम सर्किट डेप्थ ( $n/d$ के लिए आयन ट्रैप टोपोलॉजी हेतु $O(d \log \frac{n}{d})$ या सुपरकंडक्टिंग टोपोलॉजी हेतु $O(\sqrt{nd})$ ) के साथ बिना किसी सहायक क्विबिट के उत्पन्न किया जा सकता है।

परिणाम
1% के बिट एरर रेट ( $\alpha = 0.01$ ) के साथ 256-बिट क्रिप्टोग्राफिक की के लिए सिमुलेशन परिणाम महत्वपूर्ण प्रदर्शन लाभ प्रदर्शित करते हैं:

जटिलता में कमी: SCA स्थितियों के तहत शास्त्रीय एल्गोरिदम के लिए क्वेरी जटिलता $2^{256}$ (SCA के बिना) से घटकर $2^{62.29}$ हो जाती है। प्रस्तावित क्वांटम एल्गोरिदम इसे और घटाकर $2^{19.77}$ कर देता है।
स्पीडअप फैक्टर: प्रस्तावित क्वांटम एल्गोरिदम SCA स्थितियों के तहत शास्त्रीय एल्गोरिदम के सापेक्ष 3.15 का स्पीडअप फैक्टर प्राप्त करता है। इसकी तुलना ग्लेज़र एट अल. द्वारा रिपोर्ट किए गए 2.73 के स्पीडअप फैक्टर से की गई है (जिन्होंने मोंटानारो के एल्गोरिदम का विश्लेषण किया था) समान स्थितियों के तहत। लेखक नोट करते हैं कि उनकी खोज दक्षता [9] में प्रस्तावित मोंटानारो के ज्यामितीय-ग्रोथ एल्गोरिदम द्वारा प्राप्त दक्षता की तुलना में 15.38% अधिक है।
सीमाओं के साथ तुलना: शोध पत्र का दावा है कि व्युत्पन्न क्वांटम क्वेरी जटिलता ( $2^{19.77}$ ), इस विशिष्ट वितरण परिदृश्य में ग्लेज़र द्वारा मोंटानारो के एल्गोरिदम के लिए अनुमानित ऊपरी/निचली सीमाओं ( $2^{21.59}$ और $2^{17.59}$ ) की तुलना में अधिक सटीक और टाइट (tighter) है।
संसाधन दक्षता: स्टेट प्रिपरेशन योजना को शॉर्ट-डेप्थ सर्किट के लिए व्यवहार्य दिखाया गया है, जिसमें $n=256$ और $d=4$ के लिए विशिष्ट संसाधन गणना प्रदान की गई है (जैसे, 1024 CNOT गेट्स, 0 अनिसिला क्विबिट्स)।

महत्व
शोध पत्र का दावा है कि इसका शोध साइड-चैनल हमलों के तहत क्वांटम क्रिप्टोएनालिसिस के लिए सैद्धांतिक विश्लेषण से लेकर व्यावहारिक कार्यान्वयन तक एक पूर्ण-चेन समाधान प्रदान करता है। साइड-चैनल शोर (बर्नौली वितरण) की विशिष्ट संरचना का लाभ उठाकर, प्रस्तावित एल्गोरिदम शास्त्रीय समकक्षों की तुलना में सुपर-क्वाड्रेटिक स्पीडअप प्राप्त करता है, जो मोंटानारो जैसे पिछले क्वांटम सर्च अनुकूलनों से बेहतर है। आवश्यक प्रारंभिक अवस्थाओं को शॉर्ट-डेप्थ, अनिसिला-मुक्त सर्किट का उपयोग करके तैयार करने की क्षमता, व्यावहारिक क्वांटम की सर्च के कार्यान्वयन के लिए एक महत्वपूर्ण बाधा को दूर करती है। लेखक का तर्क है कि ये परिणाम उन परिदृश्यों के लिए अधिक सटीक जटिलता अनुमान और अधिक कुशल खोज रणनीति प्रदान करते हैं जहाँ शोरयुक्त की के रूप में पूर्व जानकारी उपलब्ध होती है। भविष्य के कार्य के रूप में विशिष्ट सिफर्स (AES, SM4) के साथ इस एल्गोरिदम के एकीकरण और क्वांटम शोर के प्रभाव का विश्लेषण करने की पहचान की गई है।

इसी तरह के और पेपर