मशहूर क्रिप्टोग्राफी एल्गोरिदम को अपग्रेड मिला | क्वांटा पत्रिका

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

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

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

“यह वास्तव में रोमांचक था,” कहा क्रिस पीकर्ट, मिशिगन विश्वविद्यालय में एक क्रिप्टोग्राफर जो पेपर में शामिल नहीं था। उन्होंने कहा, यह उपकरण दशकों से अध्ययन का केंद्र रहा है। "यह हमेशा अच्छा होता है जब एक लक्ष्य जिस पर इतने लंबे समय से काम किया जा रहा हो... दिखाता है कि अभी भी आश्चर्य पाया जाना बाकी है।"

एलएलएल-प्रकार के एल्गोरिदम लैटिस की दुनिया में काम करते हैं: नियमित रूप से दूरी वाले बिंदुओं का अनंत संग्रह। इसकी कल्पना करने के एक तरीके के रूप में, कल्पना करें कि आप फर्श पर टाइल लगा रहे हैं। आप इसे वर्गाकार टाइलों से ढक सकते हैं, और उन टाइलों के कोने एक जाली बनाएंगे। वैकल्पिक रूप से, आप एक अलग जाली बनाने के लिए एक अलग टाइल आकार - मान लीजिए, एक लंबा समांतर चतुर्भुज - चुन सकते हैं।

एक जाली का वर्णन उसके "आधार" का उपयोग करके किया जा सकता है। यह वैक्टर का एक सेट है (अनिवार्य रूप से, संख्याओं की सूची) जिसे आप जाली में प्रत्येक बिंदु प्राप्त करने के लिए विभिन्न तरीकों से जोड़ सकते हैं। आइए एक जाली की कल्पना करें जिसके आधार पर दो वैक्टर हों: [3, 2] और [1, 4]। जाली केवल वे सभी बिंदु हैं जिन तक आप उन वैक्टरों की प्रतियों को जोड़कर और घटाकर पहुंच सकते हैं।

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

यह एलएलएल के लिए एक काम है: इसे (या इसके भाइयों को) एक बहु-आयामी जाली का आधार दें, और यह एक बेहतर जाली तैयार करेगा। इस प्रक्रिया को जाली आधार कमी के रूप में जाना जाता है।

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

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

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

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

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

नई तकनीक उपयोगी साबित होने लगी है। ऑरेल पेजफ्रांसीसी राष्ट्रीय अनुसंधान संस्थान इनरिया के गणितज्ञ ने कहा कि उन्होंने और उनकी टीम ने कुछ कम्प्यूटेशनल संख्या सिद्धांत कार्यों पर काम करने के लिए एल्गोरिदम का एक अनुकूलन रखा है।

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

क्वांटा अपने दर्शकों को बेहतर सेवा देने के लिए सर्वेक्षणों की एक श्रृंखला आयोजित कर रहा है। हमारा ले कंप्यूटर विज्ञान पाठक सर्वेक्षण और आपको निःशुल्क जीतने के लिए प्रवेश दिया जाएगा क्वांटा माल।