Naor–Reingold pseudorandom function
1997 में, मोनी नॉर और उमर रीनगोल्ड ने निजी कुंजी के साथ-साथ सार्वजनिक-कुंजी क्रिप्टोग्राफी में विभिन्न क्रिप्टोग्राफिक आदिम के लिए कुशल निर्माण का वर्णन किया। उनका परिणाम एक कुशल सूडोरैंडम कार्य का निर्माण है। मान लीजिए कि p और l, l |p −1 के साथ अभाज्य संख्याएँ हैं। गुणक क्रम l का एक तत्व चुनें। फिर प्रत्येक (n + 1)-आयामी सदिश a = (a0, a1,., an) के लिए वे उस फलन को परिभाषित करते हैं जहाँ x = x1. xn पूर्णांक x का बिट प्रतिनिधित्व है, 0 ≤ x ≤ 2n − 1, यदि आवश्यक हो तो कुछ अतिरिक्त अग्रणी शून्य के साथ। उदाहरण लीजिए कि p = 7 और l = 3; तो l |p −1। गुणक क्रम 3 का g = 4 ω चुनें (चूँकि 43 = 64 ω1 मॉड 7)। एन = 3, ए = (1,1,2,1) और एक्स = 5 (5 का बिट प्रतिनिधित्व 101 है) के लिए, हम निम्नानुसार गणना कर सकते हैंः दक्षता नाओर-रिंगोल्ड निर्माण में फलन का मूल्यांकन बहुत कुशलता से किया जा सकता है। किसी भी दिए गए बिंदु पर फलन के मूल्य की गणना एक मॉड्यूलर घातांक और एन-मॉड्यूलर गुणन के साथ तुलनीय है। इस फलन की गणना बंधी हुई गहराई और बहुपद आकार के सीमा परिपथों द्वारा समानांतर में की जा सकती है। नाओर-रिंगोल्ड फ़ंक्शन का उपयोग सममित कूटलेखन, प्रमाणीकरण और डिजिटल हस्ताक्षर सहित कई क्रिप्टोग्राफिक योजनाओं के आधार के रूप में किया जा सकता है। फ़ंक्शन की सुरक्षा मान लीजिए कि एक हमलावर फ़ंक्शन के कई आउटपुट देखता है, जैसे। , और गणना करना चाहता है। सरलता के लिए मान लें कि x1 = 0, तो हमलावर को और प्राप्त करने के लिए कम्प्यूटेशनल डिफ्फी-हेलमैन (सी. डी. एच.) को हल करने की आवश्यकता होती है। सामान्य तौर पर, k से k + 1 पर जाने से बिट पैटर्न बदल जाता है और जब तक कि k + 1 2 की शक्ति नहीं है, तब तक कोई भी घातांक को विभाजित कर सकता है ताकि गणना पहले के दो परिणामों के बीच डिफ्फी-हेलमैन कुंजी की गणना के अनुरूप हो। यह हमलावर अगले अनुक्रम तत्व की भविष्यवाणी करना चाहता है। इस तरह का हमला बहुत बुरा होगा-लेकिन एक कठिन डिफी-हेलमैन समस्या (डी. एच. पी.) के साथ समूहों में काम करके इसका मुकाबला करना भी संभव है। उदाहरण-एक हमलावर कार्य के कई परिणाम देखता है जैसे। , जैसा कि पिछले उदाहरण में, और। फिर, हमलावर इस फलन के अगले अनुक्रम तत्व की भविष्यवाणी करना चाहता है। हालाँकि, हमलावर जानने और जानने के परिणाम की भविष्यवाणी नहीं कर सकता है। ऐसे अन्य हमले हैं जो एक छद्म संख्या जनरेटर के लिए बहुत खराब होंगेः उपयोगकर्ता आउटपुट से यादृच्छिक संख्या प्राप्त करने की उम्मीद करता है, इसलिए निश्चित रूप से धारा अनुमानित नहीं होनी चाहिए, लेकिन इससे भी अधिक, यह एक यादृच्छिक स्ट्रिंग से अप्रभेद्य होनी चाहिए। आइए कार्य का मूल्यांकन करने के लिए एक दैवज्ञ तक पहुंच के साथ एल्गोरिथ्म को निरूपित करें। मान लीजिए कि निर्णयात्मक डिफ्फी-हेलमैन धारणा के लिए, नॉर और रीनगोल्ड दिखाते हैं कि प्रत्येक संभावित बहुपद समय एल्गोरिथ्म के लिए और पर्याप्त रूप से बड़ा n नगण्य है। पहली संभाव्यता को बीज s = (p, g, a) के चयन पर लिया जाता है और दूसरी संभाव्यता को उदाहरण जनरेटर द्वारा p, g पर प्रेरित यादृच्छिक वितरण और सभी कार्यों के समूह के बीच फलन के यादृच्छिक चयन पर लिया जाता है। रैखिक जटिलता क्रिप्टोग्राफिक उद्देश्यों के लिए एक अनुक्रम कितना उपयोगी हो सकता है, इसका एक प्राकृतिक माप इसकी रैखिक जटिलता का आकार है। एक रिंग पर एक n-तत्व अनुक्रम W (x), x = 0,1,2,., n-1 की रैखिक जटिलता सबसे छोटे रैखिक पुनरावृत्ति संबंध W (x + l) = Al − 1 W (x + l − 1) +. + A0 W (x), x = 0,1,2,., n-l − 1 के साथ A0,., Al − 1 ω की लंबाई है, जो इस अनुक्रम से संतुष्ट होती है। कुछ> 0 के लिए, n ≤ (1 +), किसी भी, पर्याप्त रूप से बड़े l के लिए, अनुक्रम की रैखिक जटिलता, 0 ≤ x ≤ 2n-1, संभवतः अधिकांश वैक्टरों को छोड़कर सभी के लिए संतुष्ट करता है। इस कार्य की सीमा के नुकसान हैं, अर्थात् यह बहुत ही दिलचस्प मामले पर लागू नहीं होता है वितरण की एकरूपता का सांख्यिकीय वितरण लगभग सभी वैक्टरों के लिए एक समान वितरण के करीब है। सेट की विसंगति को मान लीजिए। इस प्रकार, यदि p की बिट लंबाई है तो सभी वैक्टरों के लिए a ω बाउंड धारण करता है, जहां और हालांकि इस गुण का कोई तत्काल क्रिप्टोग्राफिक निहितार्थ नहीं लगता है, व्युत्क्रम तथ्य, अर्थात् गैर-समान वितरण, यदि सही है, तो इस फ़ंक्शन के अनुप्रयोगों के लिए विनाशकारी परिणाम होंगे। दीर्घवृत्ताकार वक्र में अनुक्रम इस फलन का दीर्घवृत्ताकार वक्र संस्करण भी दिलचस्प है। विशेष रूप से, यह संबंधित प्रणाली की क्रिप्टोग्राफिक सुरक्षा में सुधार करने में मदद कर सकता है। मान लीजिए कि पी> 3 अभाज्य है और ई को एक दीर्घवृत्ताकार वक्र माना जाता है, फिर प्रत्येक सदिश ए उपसमूह में एक परिमित अनुक्रम को इस प्रकार परिभाषित करता हैः जहां पूर्णांक का बिट प्रतिनिधित्व है। नाओर-रिंगोल्ड दीर्घवृत्ताकार वक्र अनुक्रम को इस प्रकार परिभाषित किया गया है कि यदि निर्णयात्मक डिफ्फी-हेलमैन धारणा धारण करती है, तो सूचकांक k बहुपद समय में गणना करने के लिए पर्याप्त नहीं है, भले ही कोई हमलावर यादृच्छिक <ID1:// en. विकीपीडिया. org/विकि/एलिप्टिक _ कर्व के लिए बहुपद रूप से कई प्रश्न करता है। स्यूडोरैंडम नंबर जनरेटर क्रिप्टोग्राफी