Computational indistinguishability
कम्प्यूटेशनल जटिलता और क्रिप्टोग्राफी में, वितरण के दो परिवार कम्प्यूटेशनल रूप से अप्रभेद्य हैं यदि कोई कुशल एल्गोरिथ्म उनके बीच अंतर नहीं बता सकता है सिवाय नगण्य संभावना के। औपचारिक परिभाषा एक सुरक्षा पैरामीटर एन (जो आमतौर पर इनपुट की लंबाई को संदर्भित करता है) द्वारा अनुक्रमित दो वितरण समूह होने दें और हम कहते हैं कि वे कम्प्यूटेशनल रूप से अप्रभेद्य हैं यदि किसी भी गैर-समान संभावित बहुपद समय एल्गोरिथ्म ए के लिए, निम्नलिखित मात्रा एन में एक नगण्य कार्य हैः निरूपित। दूसरे शब्दों में, प्रत्येक कुशल एल्गोरिथ्म व्यवहार के रूप में महत्वपूर्ण रूप से नहीं बदलता है जब डीएन या एन के अनुसार सीमा में नमूने दिए जाते हैं। कम्प्यूटेशनल अप्रभेद्यता की एक और व्याख्या यह है कि सक्रिय रूप से दो समूहों के बीच अंतर करने की कोशिश करने वाले बहुपद-समय एल्गोरिदम ऐसा नहीं कर सकते हैंः कि ऐसा कोई भी एल्गोरिदम केवल अनुमान लगाने की तुलना में नगण्य रूप से बेहतर प्रदर्शन करेगा। परिभाषा में निहित संबंधित धारणाएँ यह शर्त है कि एल्गोरिथ्म को वितरणों में से एक से एकल नमूने के आधार पर निर्णय लेना चाहिए। एक ऐसी स्थिति की कल्पना की जा सकती है जिसमें दो वितरणों के बीच अंतर करने की कोशिश करने वाला एल्गोरिथ्म, जितनी आवश्यकता हो उतने नमूनों तक पहुंच सकता है। इसलिए दो समूह जिन्हें कई नमूनों को देखते हुए बहुपद-समय एल्गोरिदम द्वारा अलग नहीं किया जा सकता है, उन्हें बहुपद-समय नमूनाकरण द्वारा अप्रभेद्य माना जाता है। यदि बहुपद-समय एल्गोरिथ्म बहुपद समय में नमूने उत्पन्न कर सकता है, या एक यादृच्छिक दैवज्ञ तक पहुंच है जो इसके लिए नमूने उत्पन्न करता है, तो बहुपद-समय नमूने द्वारा अप्रभेद्यता कम्प्यूटेशनल अप्रभेद्यता के बराबर है। संदर्भ बाहरी लिंक येहुदा लिंडेल। क्रिप्टोग्राफी का परिचय डोनाल्ड बीवर और सिल्वियो मिकाली और फिलिप रोगवे, द राउंड कॉम्प्लेक्सिटी ऑफ सिक्योर प्रोटोकॉल (एक्सटेंडेड एब्स्ट्रैक्ट), 1990, पीपी। 503-513 शफी गोल्डवासर और सिल्वियो मिकाली। संभावित एन्क्रिप्शन। जे. सी. एस. एस., 28 (2): 270-299,1984 ओडेड गोल्डरिच। क्रिप्टोग्राफी की नींवः खंड 2-बुनियादी अनुप्रयोग। कैम्ब्रिज यूनिवर्सिटी प्रेस, 2004। जोनाथन काट्ज़, येहुदा लिंडेल, "आधुनिक क्रिप्टोग्राफी का परिचयः सिद्धांत और प्रोटोकॉल", चैपमैन एंड हॉल/सी. आर. सी., 2007 एल्गोरिथमिक सूचना सिद्धांत