अभिकलनात्मक कठोरता धारणाएँ

अभिकलनात्मक कठोरता धारणाएँ अप्रमाणित लेकिन सु-अध्ययनित अनुमान हैं — जैसे गुणनखंडन, असतत लघुगणक और जालक समस्याओं की कठिनाई — जिन पर क्रिप्टोग्राफिक योजनाओं की सुरक्षा अंततः टिकी हुई है।

Definition

एक अभिकलनात्मक कठोरता धारणा एक अनुमान है कि एक विशेष अभिकलनात्मक समस्या को किसी भी यथार्थवादी विरोधी द्वारा कुशलता से (बहुपद समय में) हल नहीं किया जा सकता है, जो उस नींव के रूप में कार्य करता है जिस पर सिद्ध सुरक्षा का निर्माण होता है।

Scope

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

Core questions

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

Key concepts

• एकतरफा कार्य
• ट्रैपडोर कार्य
• पूर्णांक गुणनखंडन धारणा
• असतत लघुगणक धारणा
• RSA और डिफि-हेलमैन धारणाएँ
• त्रुटियों के साथ सीखना (LWE)
• सबसे खराब स्थिति बनाम औसत-स्थिति कठोरता
• P बनाम NP
• धारणा पदानुक्रम

Key theories

एक न्यूनतम धारणा के रूप में एकतरफा कार्य

एकतरफा कार्यों का अस्तित्व — गणना करने में आसान, उलटने में कठिन — सममित क्रिप्टोग्राफी के अधिकांश के लिए आवश्यक और पर्याप्त है और सबसे बुनियादी धारणा है; लगभग सभी क्रिप्टोग्राफी कम से कम इसे पूर्वकल्पित करती है।

संख्या-सैद्धांतिक और जालक धारणाएँ

सार्वजनिक-कुंजी क्रिप्टोग्राफी संरचित समस्याओं पर टिकी हुई है — पूर्णांक गुणनखंडन, RSA समस्या, और असतत लघुगणक (शास्त्रीय रूप से), और जालक में त्रुटियों के साथ सीखना और सबसे छोटी-सदिश समस्याएँ (पोस्ट-क्वांटम) — प्रत्येक दशकों के क्रिप्टविश्लेषणात्मक जांच द्वारा समर्थित है।

Mechanisms

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

Clinical relevance

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

Evidence & guidelines

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

History

कठोरता पर निर्भरता 1976 में सार्वजनिक-कुंजी क्रिप्टोग्राफी के साथ उभरी, जब डिफि और हेलमैन ने सुरक्षा को असतत लघुगणक से जोड़ा, और RSA को गुणनखंडन से जोड़ा। 1980 के दशक ने एकतरफा कार्यों और सबसे खराब स्थिति/औसत-स्थिति अंतर को औपचारिक रूप दिया। अजताई के सबसे खराब स्थिति से औसत-स्थिति न्यूनीकरण (1996) और रेगेव की त्रुटियों के साथ सीखने की समस्या (2005) ने जालक धारणाओं को स्थापित किया, जिन्होंने क्वांटम-प्रतिरोधी नींव के रूप में प्रमुखता प्राप्त की और नए पोस्ट-क्वांटम मानकों को रेखांकित किया।

Key figures

• Whitfield Diffie
• Martin Hellman
• Oded Goldreich
• Oded Regev
• Andrew Yao

Seminal works

• diffie1976
• goldreich2001
• katz2020

Frequently asked questions

हम इन समस्याओं को कठिन क्यों नहीं साबित कर सकते?

किसी समस्या को सुपर-पॉलीनोमियल समय की आवश्यकता साबित करना जटिलता सिद्धांत (विशेष रूप से P बनाम NP) में गहरे खुले प्रश्नों को हल करेगा, जो अनसुलझे रहते हैं। इसलिए क्रिप्टोग्राफी उन धारणाओं पर निर्भर करती है जिनकी संभाव्यता उन्हें कुशलता से हल करने के दशकों के असफल प्रयासों से आती है।

यदि कोई कठोरता धारणा टूट जाती है तो क्या होता है?

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