Diffie–Hellman problem
डिफ्फी-हेलमैन समस्या (डी. एच. पी.) एक गणितीय समस्या है जिसे पहली बार क्रिप्टोग्राफी के संदर्भ में व्हिटफील्ड डिफ्फी और मार्टिन हेलमैन द्वारा प्रस्तावित किया गया था। इस समस्या के लिए प्रेरणा यह है कि कई सुरक्षा प्रणालियाँ एकतरफा कार्यों का उपयोग करती हैंः गणितीय संचालन जो गणना करने के लिए तेज़ होते हैं, लेकिन उन्हें उलटना मुश्किल होता है। उदाहरण के लिए, वे एक संदेश को एन्क्रिप्ट करने में सक्षम करते हैं, लेकिन एन्क्रिप्शन को उलटना मुश्किल है। यदि डी. एच. पी. को हल करना आसान होता, तो इन प्रणालियों को आसानी से तोड़ दिया जाता। समस्या विवरण डिफी-हेलमैन समस्या को अनौपचारिक रूप से इस प्रकार कहा गया हैः एक तत्व जी और जीएक्स और जीआई के मूल्यों को देखते हुए, जीएक्सआई का मूल्य क्या है? औपचारिक रूप से, g किसी समूह का जनरेटर है (आमतौर पर एक परिमित क्षेत्र या एक दीर्घवृत्ताकार वक्र समूह का गुणक समूह) और x और y यादृच्छिक रूप से चुने गए पूर्णांक हैं। उदाहरण के लिए, डिफी-हेलमैन कुंजी विनिमय में, एक ईवसड्रॉपर प्रोटोकॉल के हिस्से के रूप में जीएक्स और जीआई का आदान-प्रदान देखता है, और दोनों पक्ष साझा कुंजी जीएक्सआई की गणना करते हैं। डी. एच. पी. को हल करने का एक तेज़ साधन एक जासूसी करने वाले को डिफ्फी-हेलमैन कुंजी विनिमय और एलगैमल एन्क्रिप्शन सहित इसके कई रूपों की गोपनीयता का उल्लंघन करने की अनुमति देगा। कम्प्यूटेशनल जटिलता क्रिप्टोग्राफी में, कुछ समूहों के लिए, यह माना जाता है कि डी. एच. पी. कठिन है, और इसे अक्सर डिफी-हेलमैन धारणा कहा जाता है। यह समस्या कुछ दशकों से जांच के दायरे में बनी हुई है और अभी तक कोई "आसान" समाधान प्रचारित नहीं किया गया है। 2006 तक, डी. एच. पी. को हल करने के लिए ज्ञात सबसे कुशल साधन असतत लघुगणक समस्या (डी. एल. पी.) को हल करना है, जो कि जी और जी. एक्स. दिए गए एक्स का पता लगाना है। वास्तव में, यह दिखाने की दिशा में महत्वपूर्ण प्रगति की गई है कि कई समूहों में डी. एच. पी. लगभग डी. एल. पी. जितना ही कठिन है। आज तक इस बात का कोई प्रमाण नहीं है कि सामान्य समूहों (नेचेव और शूप द्वारा) को छोड़कर डी. एच. पी. या डी. एल. पी. एक कठिन समस्या है। इस बात का प्रमाण कि दोनों में से कोई भी समस्या कठिन है, इसका तात्पर्य है कि पी ≤ एन. पी.। अन्य रूप डिफी-हेलमैन समस्या के कई रूपों पर विचार किया गया है। सबसे महत्वपूर्ण प्रकार निर्णयात्मक डिफी-हेलमैन समस्या (डी. डी. एच. पी.) है, जो जी. एक्स. आई. को एक यादृच्छिक समूह तत्व से अलग करने के लिए है, जो जी, जी. एक्स. और जी. आई. को दिया गया है। कभी-कभी डी. एच. पी. को डी. डी. एच. पी. से अधिक स्पष्ट रूप से अलग करने के लिए कम्प्यूटेशनल डिफी-हेलमैन समस्या (सी. डी. एच. पी.) कहा जाता है। हाल ही में जोड़ी वाले समूह लोकप्रिय हो गए हैं, और इन समूहों में डी. डी. एच. पी. आसान है, फिर भी डी. एच. पी. को अभी भी कठिन माना जाता है। डी. एच. पी. के कम महत्वपूर्ण रूपों के लिए संदर्भ देखें। संदर्भ बी. डेन बोअर, डिफी-हेलमैन क्रिप्टोलॉजी में प्रगति-क्रिप्टो 88, कंप्यूटर विज्ञान में व्याख्यान टिप्पणियाँ 403, स्प्रिंगर, पृष्ठ 530,1988 में कुछ अभाज्य संख्याओं के लिए असतत लॉग के रूप में मजबूत हैं। यू. एम. मौरर और एस. वुल्फ, डिफी-हेलमैन ऑरेकल इन एडवांसेज इन क्रिप्टोलॉजी-क्रिप्टो 96, (एन. कोब्लिट्ज़, एड। ), लेक्चर नोट्स इन कंप्यूटर साइंस 1070, स्प्रिंगर, पीपी। 268-282,1996। डी. बोनेह और आर. जे. लिप्टोन, ब्लैक-बॉक्स क्षेत्रों के लिए एल्गोरिदम और क्रिप्टोलॉजी में प्रगति में क्रिप्टोटोग्राफी के लिए उनका अनुप्रयोग-क्रिप्टो 96, (एन. कोब्लिट्ज़, एड। ), लेक्चर नोट्स इन कंप्यूटर साइंस 1070, स्प्रिंगर, पीपी। 283-297,1996। ए. मुजेरो, एन. पी. स्मार्ट और एफ. वेरकाउटेरन, व्यावहारिक अनुप्रयोगों में उपयोग किए जाने वाले दीर्घवृत्ताकार वक्रों के लिए डी. एच. पी. और डी. एल. पी. के बीच समानता, एल. एम. एस. जे. कम्प्यूट। गणित., 7, पृ. 50-72,2004। [www.lms.ac.uk] देखें। डी. आर. एल. ब्राउन और आर. पी. गैलेंट, द स्टेटिक डिफी-हेलमैन प्रॉब्लम, आई. ए. सी. आर. ईप्रिंट 2004/306। वी. आई. नेचेव, असतत लघुगणक के लिए एक निर्धारित एल्गोरिथ्म की जटिलता, गणितीय नोट्स, 55 (2), पीपी। 165-172,1994। वी. शूप, लोअर बाउंड्स फॉर डिस्क्रीट लॉगरिदम एंड रिलेटेड प्रॉब्लेम्स इन एडवांसेज इन क्रिप्टोलॉजी-EUROCRYPT 97, (डब्ल्यू. फुमी, एड। ), लेक्चर नोट्स इन कंप्यूटर साइंस 1233, स्प्रिंगर, पीपी। 256-266,1997। कम्प्यूटेशनल कठोरता धारणाएँ सीमित क्षेत्र