क्रिप्टोग्राफी युक्तियाँ कठिन समस्या को थोड़ा आसान बनाती हैं | क्वांटा पत्रिका

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

शोधकर्ताओं ने लंबे समय से सोचा है कि क्या वास्तव में ऐसा कभी होता है, उन्होंने कहा राहुल इलंगो, मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी में जटिलता सिद्धांत का अध्ययन करने वाला एक स्नातक छात्र। "आप पूछ सकते हैं, 'क्या ऐसी समस्याएं हैं जिनके लिए अनुमान लगाना और जांचना ही सर्वोत्तम है?'"

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

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

"वे वास्तव में सुंदर और महत्वपूर्ण परिणाम हैं," कहा एरिक एलेन्डररटगर्स विश्वविद्यालय में एक सैद्धांतिक कंप्यूटर वैज्ञानिक।

कठोरता को परिभाषित करना

नए परिणाम जटिलता सिद्धांत के आगमन से काफी पहले, सोवियत संघ में पहली बार अध्ययन किए गए एक प्रश्न की जांच के लिए नवीनतम हैं। एलेंडर ने कहा, "इससे पहले कि मैं ग्रेड स्कूल में था, रूस में लोग इसे तैयार कर रहे थे।"

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

न्यूनतम सर्किट आकार की समस्या संपीड़न समस्या का एक उदाहरण है। आप बिट्स की एक लंबी स्ट्रिंग - 0s और 1s - के साथ एक सर्किट के व्यवहार का वर्णन कर सकते हैं और फिर पूछ सकते हैं कि क्या कम बिट्स का उपयोग करके उसी व्यवहार को पुन: उत्पन्न करने का कोई तरीका है। सभी संभावित सर्किट लेआउट की जांच करने में समय लगेगा जो स्ट्रिंग में बिट्स की संख्या के साथ तेजी से बढ़ता है।

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

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

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

वन वे ट्रैफ़िक

आधुनिक क्रिप्टोग्राफी गुप्त संदेशों को सुरक्षित रखने के लिए कठिन कम्प्यूटेशनल समस्याओं का उपयोग करती है। लेकिन कम्प्यूटेशनल कठोरता केवल तभी उपयोगी होती है जब यह असममित हो - यदि कोडित संदेशों को समझना कठिन है लेकिन संदेशों को पहले स्थान पर एनकोड करना कठिन नहीं है।

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

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

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

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

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

डेटा संरचनाओं पर निर्माण

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

कई कम्प्यूटेशनल समस्याओं की तरह, फ़ंक्शन व्युत्क्रम को विस्तृत खोज द्वारा हल किया जा सकता है। आउटपुट स्ट्रिंग को देखते हुए, बस हर संभव इनपुट को फ़ंक्शन में प्लग करें जब तक कि आपको सही उत्तर देने वाला इनपुट न मिल जाए।

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

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

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

2020 में पास और लियू की सफलता के बाद, ये पुराने परिणाम अचानक नए प्रासंगिक हो गए। फिएट-नाओर एल्गोरिदम संपूर्ण खोज की तुलना में मनमाने कार्यों को तेजी से उलट सकता है। क्या यह संपीड़न समस्याओं के लिए भी काम कर सकता है?

वर्दी से बाहर

प्रश्न उठाने वाले पहले शोधकर्ता जटिलता सिद्धांतकार थे राहुल संथानम ऑक्सफोर्ड विश्वविद्यालय और उनके स्नातक छात्र हनलिन रेन. उन्होंने ए में ऐसा किया 2021 कागज यह साबित करते हुए कि शोधकर्ताओं ने जितना सोचा था उससे कहीं अधिक संपीड़न समस्याएं और फ़ंक्शन व्युत्क्रम आपस में जुड़े हुए थे।

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

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

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

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

पास ने एक साल बाद उसी विचार पर ठोकर खाई, जब फिएट ने क्रिप्टोग्राफी में नाओर के योगदान का जश्न मनाने वाली एक कार्यशाला में क्लासिक एल्गोरिदम के बारे में बात की। उन्होंने कहा, "फंक्शन इनवर्जन का उपयोग करने का यह विचार तब से मेरे दिमाग में था।" बाद में उन्होंने तेल अवीव विश्वविद्यालय के शोधकर्ता के साथ मिलकर इस समस्या पर काम करना शुरू किया नोम मजोर.

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

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

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

व्युत्क्रम अभिसरण

गैर-समान एल्गोरिदम के लिए नया प्रमाण एक स्वाभाविक प्रश्न उठाता है: समान एल्गोरिदम के बारे में क्या? क्या उनका उपयोग करके संपूर्ण खोज की तुलना में संपीड़न समस्याओं को तेजी से हल करने का कोई तरीका है?

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

संथानम ने कहा, "मुझे बहुत आश्चर्य होगा।" "इसके लिए बिल्कुल नए विचार की आवश्यकता होगी।"

लेकिन एलेन्डर ने कहा कि शोधकर्ताओं को इस संभावना से इनकार नहीं करना चाहिए। उन्होंने कहा, "मेरे लिए एक अच्छी कामकाजी परिकल्पना यह रही है कि अगर किसी चीज़ को करने का एक गैर-समान तरीका है, तो बहुत संभव है कि एक समान तरीका भी हो।"

किसी भी तरह से, इस काम ने जटिलता सिद्धांतकारों को क्रिप्टोग्राफी में पुराने प्रश्नों में दिलचस्पी पैदा कर दी है। युवल ईशाईइज़राइल के हाइफ़ा में टेक्नियन के एक क्रिप्टोग्राफर ने कहा कि यही इसे सबसे रोमांचक बनाता है।

उन्होंने कहा, "विभिन्न समुदायों के बीच हितों के इस अभिसरण को देखकर मैं वास्तव में खुश हूं।" "मुझे लगता है कि यह विज्ञान के लिए बहुत अच्छा है।"