ट्रैपडोर फंक्शन: Difference between revisions

Revision as of 12:21, 1 June 2023

ट्रैपडोर कार्य का विचार। एक ट्रैपडोर कार्य f इसके ट्रैपडोर टी के साथ एक एल्गोरिथम 'जेन' द्वारा उत्पन्न किया जा सकता है। f की कुशलतापूर्वक गणना की जा सकती है, अर्थात, संभाव्य बहुपद समय में। चूँकि f के व्युत्क्रम की गणना सामान्यतः कठिन होती है जब तक कि ट्रैपडोर t नहीं दिया जाता है।^[1]

सैद्धांतिक कंप्यूटर विज्ञान और क्रिप्टोग्राफी में, एक ट्रैपडोर कार्य एक कार्य (गणित) है जो एक दिशा में गणना करना आसान है फिर भी विशेष जानकारी के बिना विपरीत दिशा में गणना करना कठिन है (इसके व्युत्क्रम कार्य को खोजना) जिसे ट्रैपडोर कहा जाता है। ट्रैपडोर कार्य एक तरफा कार्य का एक विशेष स्थिति है और सार्वजनिक कुंजी क्रिप्टोग्राफी में व्यापक रूप से उपयोग किया जाता है।^[2]

गणितीय शब्दों में यदि f एक ट्रैपडोर कार्य है तो कुछ गुप्त सूचना t उपस्थित है जैसे कि f(x) और t दिया गया है, x की गणना करना आसान है। एक ताला और उसकी चाबी पर विचार करें। ताला तंत्र में झोंपड़ी को धकेल कर कुंजी का उपयोग किए बिना पैडलॉक को खुले से बंद में बदलना तुच्छ है। पैडलॉक को आसानी से खोलने के लिए चूँकि उपयोग की जाने वाली कुंजी की आवश्यकता होती है। यहां की टी ट्रैपडोर है और पैडलॉक ट्रैपडोर कार्य है।

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

1970 के दशक के मध्य में व्हिटफ़ील्ड डिफी, मार्टिन हेलमैन और राल्फ मर्कल द्वारा असममित कुंजी एल्गोरिदम असममित (या सार्वजनिक कुंजी) एन्क्रिप्शन विधियों के प्रकाशन के साथ ट्रैपडोर कार्य क्रिप्टोग्राफी में प्रमुखता से आए वास्तव में, डिफी & हेलमैन (1976) शब्द गढ़ा। कई कार्य वर्गों का प्रस्ताव किया गया था और जल्द ही यह स्पष्ट हो गया कि ट्रैपडोर कार्यों को प्रारंभ में जितना सोचा गया था उससे कहीं अधिक कठिन है। उदाहरण के लिए एक प्रारंभिक सुझाव सबसेट योग समस्या के आधार पर योजनाओं का उपयोग करना था। यह अनुपयुक्त होने के अतिरिक्त जल्दी निकला है।

As of 2004^[update], सबसे प्रसिद्ध ट्रैपडोर कार्य (परिवार) उम्मीदवार आरएसए (एल्गोरिदम) और राबिन क्रिप्टोसिस्टम ऑफ़ कार्य हैं। दोनों को घातांक मॉडुलो के रूप में एक समग्र संख्या के रूप में लिखा गया है और दोनों प्रधान गुणनखंड की समस्या से संबंधित हैं।

असतत लॉगरिदम समस्या की कठोरता से संबंधित कार्य (या तो मॉड्यूल एक प्रमुख या अंडाकार वक्र क्रिप्टोग्राफी पर परिभाषित समूह में) ट्रैपडोर कार्यों के रूप में नहीं जाना जाता है क्योंकि समूह के बारे में कोई ज्ञात ट्रैपडोर जानकारी नहीं है जो कुशल गणना को असतत लघुगणक सक्षम बनाता है

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

परिभाषा

ट्रैपडोर कार्य एक तरफ़ा कार्य { f_k : D_k → R_k } (k ∈ K), का एक संग्रह है, जिसमें सभी K, D_k, R_k बाइनरी स्ट्रिंग्स {0, 1}* के उपसमुच्चय हैं, जो निम्नलिखित नियमो को पूरा करते हैं:

वहाँ एक संभाव्य बहुपद समय (पीपीटी) नमूना एल्गोरिथ्म जेन सेंट उपस्थित है। Gen s.t. Gen(1ⁿ) = (k, t_k) के साथ k ∈ K ∩ {0, 1}ⁿ और t_k ∈ {0, 1} संतुष्ट करता है |t_k | < p (n), जिसमें पी कुछ बहुपद है। प्रत्येक t_k को k के अनुरूप ट्रैपडोर कहा जाता है। प्रत्येक ट्रैपडोर का कुशलतापूर्वक नमूना लिया जा सकता है।
दिए गए इनपुट k में, एक पीपीटी एल्गोरिथ्म भी उपस्थित है जो x ∈ D_k को आउटपुट करता है अर्थात् प्रत्येक D_k कुशलता से नमूना लिया जा सकता है।
किसी भी k ∈ K के लिए, एक पीपीटी एल्गोरिथ्म उपस्थित है जो f_k की सही गणना करता है
किसी भी k ∈ K के लिए, एक पीपीटी एल्गोरिथम A st उपस्थित है। किसी भी x ∈ D_k, के लिए चलो y = A ( k, f_k(x), t_k ) और फिर हमारे पास f_k(y) = f_k(x) यानी ट्रैपडोर दिया गया है, इसे विपरीत करना आसान है।
किसी भी k ∈ K, के लिए, ट्रैपडोर t_k के बिना किसी भी पीपीटी एल्गोरिथम के लिए, f_k को सही विधि से विपरीत करने की संभावना (अर्थात, दिया गया f_k(x) एक पूर्व-छवि x' खोजें, जैसे कि f_k(x' ) = f_k(x)) नगण्य है।^[3]^[4]^[5]

यदि उपरोक्त संग्रह में प्रत्येक कार्य एक तरफ़ा क्रमचय है तो संग्रह को ट्रैपडोर क्रमचय भी कहा जाता है।^[6]

उदाहरण

निम्नलिखित दो उदाहरणों में, हम सदैव मानते हैं कि एक बड़ी समग्र संख्या का गुणनखंड करना कठिन है (पूर्णांक गुणनखंड देखें)।

आरएसए धारणा

इस उदाहरण में, $e$ ,मापांक $\phi (n)$ (यूलर का $n$ का संपूर्ण फलन) का व्युत्क्रम $d$ ट्रैपडोर है:

f(x)=x^{e}\mod n

यदि $n=pq$ का गुणनखंड ज्ञात है, तो $\phi (n)=(p-1)(q-1)$ की गणना की जा सकती है। इसके साथ $e$ के व्युत्क्रम $d$ की गणना की जा सकती है $d=e^{-1}\mod {\phi (n)}$ , और फिर दिया गया $y=f(x)$ हम पा सकते हैं $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ इसकी कठोरता आरएसए धारणा से होती है।^[7]

राबिन का द्विघात अवशेष अनुमान

मान लीजिए $n$ एक बड़ी संमिश्र संख्या है जैसे कि $n=pq$ जहाँ $p$ और $q$ बड़ी अभाज्य संख्याएँ हैं जैसे कि $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$ और विरोधी के लिए गोपनीय रखा। समस्या यह है कि दिए गए $a$ के अनुसार $z$ की गणना करना $a\equiv z^{2}{\pmod {n}}$ है। ट्रैपडोर $n$ का गुणनखंड है। ट्रैपडोर के साथ, z का समाधान $cx+dy,cx-dy,-cx+dy,-cx-dy$ के रूप में दिया जा सकता है, जहाँ $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ । अधिक विवरण के लिए चीनी शेष प्रमेय देखें। ध्यान दें कि अभाज्य संख्याएँ $p$ और $q$ दिए जाने पर, हम $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ और $y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$ यहां नियम $p\equiv 3{\pmod {4}}$ और $q\equiv 3{\pmod {4}}$ आश्वासन देती हैं कि समाधान $x$ और $y$ को अच्छी तरह से परिभाषित किया जा सकता है।^[8]

यह भी देखें

एक तरफ़ा कार्य

↑ Ostrovsky, pp. 6-9
↑ Bellare, M (June 1998). "कई-से-एक ट्रैपडोर फ़ंक्शंस और सार्वजनिक-कुंजी क्रिप्टोसिस्टम से उनका संबंध". Advances in Cryptology.
↑ Pass's Notes, def. 56.1
↑ Goldwasser's lecture notes, def. 2.16
↑ Ostrovsky, pp. 6-10, def. 11
↑ Pass's notes, def 56.1; Dodis's def 7, lecture 1.
↑ Goldwasser's lecture notes, 2.3.2; Lindell's notes, pp. 17, Ex. 1.
↑ Goldwasser's lecture notes, 2.3.4

संदर्भ

Diffie, W.; Hellman, M. (1976), "New directions in cryptography" (PDF), IEEE Transactions on Information Theory, 22 (6): 644–654, CiteSeerX 10.1.1.37.9720, doi:10.1109/TIT.1976.1055638
Pass, Rafael, A Course in Cryptography (PDF), retrieved 27 November 2015
Goldwasser, Shafi, Lecture Notes on Cryptography (PDF), retrieved 25 November 2015
Ostrovsky, Rafail, Foundations of Cryptography (PDF), retrieved 27 November 2015
Dodis, Yevgeniy, Introduction to Cryptography Lecture Notes (Fall 2008), retrieved 17 December 2015
Lindell, Yehuda, Foundations of Cryptography (PDF), retrieved 17 December 2015

[1] Ostrovsky, pp. 6-9

[2] Bellare, M (June 1998). "कई-से-एक ट्रैपडोर फ़ंक्शंस और सार्वजनिक-कुंजी क्रिप्टोसिस्टम से उनका संबंध". Advances in Cryptology.

[3] Pass's Notes, def. 56.1

[4] Goldwasser's lecture notes, def. 2.16

[5] Ostrovsky, pp. 6-10, def. 11

[6] Pass's notes, def 56.1; Dodis's def 7, lecture 1.

[7] Goldwasser's lecture notes, 2.3.2; Lindell's notes, pp. 17, Ex. 1.

[8] Goldwasser's lecture notes, 2.3.4

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 1: / Line 1: @@
 {{Short description|Cryptographic tool that is easy to compute in one direction and difficult in the other}}
-{{about|the mathematical cryptography function|the method of bypassing security|Backdoor (computing)}}
+{{about|गणितीय क्रिप्टोग्राफी कार्य |सुरक्षा को दरकिनार करने का विधि |पिछले दरवाजे (कंप्यूटिंग)}}
-[[File:Trapdoor permutation.svg|300px|thumb|ट्रैपडोर फ़ंक्शन का विचार। एक ट्रैपडोर फ़ंक्शन f इसके ट्रैपडोर टी के साथ एक एल्गोरिथम 'जेन' द्वारा उत्पन्न किया जा सकता है। f की कुशलतापूर्वक गणना की जा सकती है, अर्थात, संभाव्य बहुपद समय में। हालाँकि, f के व्युत्क्रम की गणना आम तौर पर कठिन होती है, जब तक कि ट्रैपडोर t नहीं दिया जाता है।<ref>Ostrovsky, pp. 6-9</ref>]][[सैद्धांतिक कंप्यूटर विज्ञान]] और [[क्रिप्टोग्राफी]] में, एक ट्रैपडोर फ़ंक्शन एक फ़ंक्शन (गणित) है जो एक दिशा में गणना करना आसान है, फिर भी विशेष जानकारी के बिना विपरीत दिशा में गणना करना मुश्किल है (इसके व्युत्क्रम फ़ंक्शन को खोजना), जिसे ट्रैपडोर कहा जाता है। ट्रैपडोर फ़ंक्शंस [[एक तरफा समारोह]] का एक विशेष मामला है और [[सार्वजनिक कुंजी क्रिप्टोग्राफी]] में व्यापक रूप से उपयोग किया जाता है।<ref>{{Cite journal|last=Bellare|first=M|date=June 1998|title=कई-से-एक ट्रैपडोर फ़ंक्शंस और सार्वजनिक-कुंजी क्रिप्टोसिस्टम से उनका संबंध|journal=Advances in Cryptology}}</ref>
+[[File:Trapdoor permutation.svg|300px|thumb|ट्रैपडोर कार्य का विचार। एक ट्रैपडोर कार्य f इसके ट्रैपडोर टी के साथ एक एल्गोरिथम 'जेन' द्वारा उत्पन्न किया जा सकता है। f की कुशलतापूर्वक गणना की जा सकती है, अर्थात, संभाव्य बहुपद समय में। चूँकि f के व्युत्क्रम की गणना सामान्यतः कठिन होती है जब तक कि ट्रैपडोर t नहीं दिया जाता है।<ref>Ostrovsky, pp. 6-9</ref>]][[सैद्धांतिक कंप्यूटर विज्ञान]] और [[क्रिप्टोग्राफी]] में, एक ट्रैपडोर कार्य एक कार्य (गणित) है जो एक दिशा में गणना करना आसान है फिर भी विशेष जानकारी के बिना विपरीत दिशा में गणना करना कठिन है (इसके व्युत्क्रम कार्य को खोजना) जिसे ट्रैपडोर कहा जाता है। ट्रैपडोर कार्य [[एक तरफा समारोह|एक तरफा कार्य]] का एक विशेष स्थिति है और [[सार्वजनिक कुंजी क्रिप्टोग्राफी]] में व्यापक रूप से उपयोग किया जाता है।<ref>{{Cite journal|last=Bellare|first=M|date=June 1998|title=कई-से-एक ट्रैपडोर फ़ंक्शंस और सार्वजनिक-कुंजी क्रिप्टोसिस्टम से उनका संबंध|journal=Advances in Cryptology}}</ref>
-गणितीय शब्दों में, यदि f एक ट्रैपडोर फ़ंक्शन है, तो कुछ गुप्त सूचना t मौजूद है, जैसे कि f(x) और t दिया गया है, x की गणना करना आसान है। एक [[ताला]] और उसकी चाबी पर विचार करें। ताला तंत्र में झोंपड़ी को धकेल कर, कुंजी का उपयोग किए बिना पैडलॉक को खुले से बंद में बदलना तुच्छ है। पैडलॉक को आसानी से खोलने के लिए, हालांकि, उपयोग की जाने वाली कुंजी की आवश्यकता होती है। यहां की टी ट्रैपडोर है और पैडलॉक ट्रैपडोर फंक्शन है।
+गणितीय शब्दों में यदि f एक ट्रैपडोर कार्य है तो कुछ गुप्त सूचना t उपस्थित है जैसे कि f(x) और t दिया गया है, x की गणना करना आसान है। एक [[ताला]] और उसकी चाबी पर विचार करें। ताला तंत्र में झोंपड़ी को धकेल कर कुंजी का उपयोग किए बिना पैडलॉक को खुले से बंद में बदलना तुच्छ है। पैडलॉक को आसानी से खोलने के लिए चूँकि उपयोग की जाने वाली कुंजी की आवश्यकता होती है। यहां की टी ट्रैपडोर है और पैडलॉक ट्रैपडोर कार्य है।
-एक सरल गणितीय ट्रैपडोर का एक उदाहरण 6895601 है जो दो अभाज्य संख्याओं का गुणनफल है। वे संख्याएँ क्या हैं? एक विशिष्ट [[ पशुबल का आक्रमण |पशुबल का आक्रमण]] |ब्रूट-फोर्स समाधान उत्तर खोजने तक 6895601 को कई अभाज्य संख्याओं से विभाजित करने का प्रयास करना होगा। हालाँकि, अगर किसी को बताया जाए कि 1931 संख्याओं में से एक है, तो वह किसी भी कैलकुलेटर में 6895601 ÷ 1931 दर्ज करके उत्तर पा सकता है। यह उदाहरण एक मजबूत ट्रैपडोर फ़ंक्शन नहीं है - आधुनिक कंप्यूटर एक सेकंड के भीतर सभी संभावित उत्तरों का अनुमान लगा सकते हैं - लेकिन इस नमूना समस्या को [[पूर्णांक गुणनखंडन]] द्वारा सुधारा जा सकता है।
+एक सरल गणितीय ट्रैपडोर का एक उदाहरण 6895601 है जो दो अभाज्य संख्याओं का गुणनफल है। वे संख्याएँ क्या हैं? एक विशिष्ट [[ पशुबल का आक्रमण |पशुबल का आक्रमण]] ब्रूट-फोर्स समाधान उत्तर खोजने तक 6895601 को कई अभाज्य संख्याओं से विभाजित करने का प्रयास करना होगा। चूँकि यदि किसी को बताया जाए कि 1931 संख्याओं में से एक है, तो वह किसी भी कैलकुलेटर में 6895601 ÷ 1931 अंकित  करके उत्तर पा सकता है। यह उदाहरण एक शसक्त ट्रैपडोर कार्य नहीं है - आधुनिक कंप्यूटर एक सेकंड के अंदर सभी संभावित उत्तरों का अनुमान लगा सकते हैं - किंतु इस नमूना समस्या को [[पूर्णांक गुणनखंडन]] द्वारा सुधारा जा सकता है।
-के दशक के मध्य में [[व्हिटफ़ील्ड डिफी]], [[मार्टिन हेलमैन]] और [[राल्फ मर्कल]] द्वारा असममित कुंजी एल्गोरिदम | असममित (या सार्वजनिक कुंजी) एन्क्रिप्शन तकनीकों के प्रकाशन के साथ ट्रैपडोर फ़ंक्शंस क्रिप्टोग्राफी में प्रमुखता से आए। वास्तव में, {{harvtxt|Diffie|Hellman|1976}} शब्द गढ़ा। कई कार्य वर्गों का प्रस्ताव किया गया था, और जल्द ही यह स्पष्ट हो गया कि ट्रैपडोर कार्यों को शुरू में जितना सोचा गया था, उससे कहीं अधिक कठिन है। उदाहरण के लिए, एक प्रारंभिक सुझाव [[सबसेट योग समस्या]] के आधार पर योजनाओं का उपयोग करना था। यह अनुपयुक्त होने के बजाय जल्दी निकला।
+के दशक के मध्य में [[व्हिटफ़ील्ड डिफी]], [[मार्टिन हेलमैन]] और [[राल्फ मर्कल]] द्वारा असममित कुंजी एल्गोरिदम असममित (या सार्वजनिक कुंजी) एन्क्रिप्शन विधियों के प्रकाशन के साथ ट्रैपडोर कार्य क्रिप्टोग्राफी में प्रमुखता से आए वास्तव में, {{harvtxt|डिफी|हेलमैन|1976}} शब्द गढ़ा। कई कार्य वर्गों का प्रस्ताव किया गया था और जल्द ही यह स्पष्ट हो गया कि ट्रैपडोर कार्यों को प्रारंभ में जितना सोचा गया था उससे कहीं अधिक कठिन है। उदाहरण के लिए एक प्रारंभिक सुझाव [[सबसेट योग समस्या]] के आधार पर योजनाओं का उपयोग करना था। यह अनुपयुक्त होने के अतिरिक्त जल्दी निकला है।
-{{As of|2004}}, सबसे प्रसिद्ध ट्रैपडोर फ़ंक्शन (परिवार) उम्मीदवार RSA (एल्गोरिदम) और [[राबिन क्रिप्टोसिस्टम]] ऑफ़ फ़ंक्शंस हैं। दोनों को घातांक मॉडुलो के रूप में एक समग्र संख्या के रूप में लिखा गया है, और दोनों प्रधान गुणनखंड की समस्या से संबंधित हैं।
+{{As of|2004}}, सबसे प्रसिद्ध ट्रैपडोर कार्य (परिवार) उम्मीदवार आरएसए (एल्गोरिदम) और [[राबिन क्रिप्टोसिस्टम]] ऑफ़ कार्य हैं। दोनों को घातांक मॉडुलो के रूप में एक समग्र संख्या के रूप में लिखा गया है और दोनों प्रधान गुणनखंड की समस्या से संबंधित हैं।
-असतत लॉगरिदम समस्या की कठोरता से संबंधित कार्य (या तो मॉड्यूल एक प्रमुख या अंडाकार वक्र क्रिप्टोग्राफी पर परिभाषित समूह में) ट्रैपडोर कार्यों के रूप में नहीं जाना जाता है, क्योंकि समूह के बारे में कोई ज्ञात ट्रैपडोर जानकारी नहीं है जो कुशल गणना को सक्षम बनाता है असतत लघुगणक।
+असतत लॉगरिदम समस्या की कठोरता से संबंधित कार्य (या तो मॉड्यूल एक प्रमुख या अंडाकार वक्र क्रिप्टोग्राफी पर परिभाषित समूह में) ट्रैपडोर कार्यों के रूप में नहीं जाना जाता है क्योंकि समूह के बारे में कोई ज्ञात ट्रैपडोर जानकारी नहीं है जो कुशल गणना को असतत लघुगणक सक्षम बनाता है
-क्रिप्टोग्राफी में ट्रैपडोर का बहुत विशिष्ट पूर्वोक्त अर्थ होता है और इसे [[ पिछले दरवाजे (कंप्यूटिंग) |पिछले दरवाजे (कंप्यूटिंग)]] के साथ भ्रमित नहीं होना चाहिए (इन्हें अक्सर परस्पर विनिमय के लिए उपयोग किया जाता है, जो गलत है)। एक बैकडोर एक जानबूझकर तंत्र है जिसे क्रिप्टोग्राफ़िक एल्गोरिदम (उदाहरण के लिए, एक कुंजी जोड़ी पीढ़ी एल्गोरिदम, डिजिटल हस्ताक्षर एल्गोरिदम इत्यादि) या ऑपरेटिंग सिस्टम में जोड़ा जाता है, उदाहरण के लिए, जो एक या अधिक अनधिकृत पार्टियों को बायपास करने या सुरक्षा को कम करने की अनुमति देता है। सिस्टम को किसी न किसी रूप में।
+क्रिप्टोग्राफी में ट्रैपडोर का बहुत विशिष्ट पूर्वोक्त अर्थ होता है और इसे [[ पिछले दरवाजे (कंप्यूटिंग) |पिछले दरवाजे (कंप्यूटिंग)]] के साथ भ्रमित नहीं होना चाहिए (इन्हें अधिकांशतः परस्पर विनिमय के लिए उपयोग किया जाता है, जो गलत है)। एक बैकडोर एक जानबूझकर तंत्र है जिसे क्रिप्टोग्राफ़िक एल्गोरिदम (उदाहरण के लिए एक कुंजी जोड़ी पीढ़ी एल्गोरिदम, डिजिटल हस्ताक्षर एल्गोरिदम इत्यादि) या ऑपरेटिंग प्रणाली  में जोड़ा जाता है उदाहरण के लिए, जो एक या अधिक अनधिकृत पार्टियों को बायपास करने या सुरक्षा प्रणाली  को किसी न किसी रूप में कम करने की अनुमति देता है।
 == परिभाषा ==
-ट्रैपडोर फ़ंक्शन एक तरफ़ा फ़ंक्शन {''f'' का एक संग्रह है<sub>''k''</sub> : डी<sub>''k''</sub> → आर<sub>''k''</sub> } (k ∈ K), जिसमें सभी K, D<sub>''k''</sub>, आर<sub>''k''</sub> बाइनरी स्ट्रिंग्स {0, 1} के सबसेट हैं<sup>*</sup>, निम्नलिखित शर्तों को पूरा करते हैं:
+ट्रैपडोर कार्य एक तरफ़ा कार्य { ''f<sub>k</sub>'' : ''D<sub>k</sub>'' → ''R<sub>k</sub>'' } (''k'' ∈ ''K''), का एक संग्रह है, जिसमें सभी ''K'', ''D<sub>k</sub>'', ''R<sub>k</sub>'' बाइनरी स्ट्रिंग्स {0, 1}* के उपसमुच्चय हैं, जो निम्नलिखित नियमो को पूरा करते हैं:
-* एक संभाव्य बहुपद समय (पीपीटी) नमूना एल्गोरिदम जेन सेंट मौजूद है। जनरल (1<sup>n</sup>) = (के, टी<sub>''k''</sub>) k ∈ K ∩ {0, 1} के साथ<sup>एन</sup> और टी<sub>''k''</sub> ∈ {0, 1}<sup>*</sup> संतुष्ट | टी<sub>''k''</sub> | <पी (एन), जिसमें पी कुछ बहुपद है। प्रत्येक टी<sub>''k''</sub> k के अनुरूप ट्रैपडोर कहा जाता है। प्रत्येक ट्रैपडोर का कुशलतापूर्वक नमूना लिया जा सकता है।
+*वहाँ एक संभाव्य बहुपद समय (पीपीटी) नमूना एल्गोरिथ्म जेन  सेंट  उपस्थित है। Gen s.t. Gen(1<sup>''n''</sup>) = (''k'', ''t<sub>k</sub>'') के साथ ''k'' ∈ ''K'' ∩ {0, 1}<sup>''n''</sup> और  ''t<sub>k</sub>'' ∈ {0, 1} संतुष्ट करता है |''t<sub>k</sub>'' | < ''p'' (''n''), जिसमें पी कुछ बहुपद है। प्रत्येक ''t<sub>k</sub>''  को k के अनुरूप ट्रैपडोर कहा जाता है। प्रत्येक ट्रैपडोर का कुशलतापूर्वक नमूना लिया जा सकता है।
-* दिए गए इनपुट k में, एक PPT एल्गोरिथ्म भी मौजूद है जो x ∈ D को आउटपुट करता है<sub>''k''</sub>. यानी प्रत्येक डी<sub>''k''</sub> कुशलता से नमूना लिया जा सकता है।
+* दिए गए इनपुट k में, एक पीपीटी एल्गोरिथ्म भी उपस्थित है जो ''x'' ∈ ''D<sub>k</sub>'' को आउटपुट करता है अर्थात् प्रत्येक ''D<sub>k</sub>'' कुशलता से नमूना लिया जा सकता है।
-* किसी भी k ∈ K के लिए, एक PPT एल्गोरिथ्म मौजूद है जो f की सही गणना करता है<sub>''k''</sub>.
+* किसी भी k ∈ K के लिए, एक पीपीटी एल्गोरिथ्म उपस्थित है जो ''f<sub>k</sub>'' की सही गणना करता है
-* किसी भी k ∈ K के लिए, एक PPT एल्गोरिथम A st मौजूद है। किसी भी एक्स ∈ डी के लिए<sub>''k''</sub>, चलो y = ए (के, एफ<sub>''k''</sub>(एक्स), टी<sub>''k''</sub> ), और फिर हमारे पास f<sub>''k''</sub>(वाई) = एफ<sub>''k''</sub>(एक्स)। यानी ट्रैपडोर दिया गया है, इसे पलटना आसान है।
+* किसी भी k ∈ K के लिए, एक पीपीटी एल्गोरिथम A st उपस्थित है। किसी भी ''x'' ∈ ''D<sub>k</sub>'', के लिए चलो  ''y'' = ''A'' ( ''k'', ''f<sub>k</sub>''(''x''), ''t<sub>k</sub>'' ) और फिर हमारे पास ''f<sub>k</sub>''(''y'') = ''f<sub>k</sub>''(''x'') यानी ट्रैपडोर दिया गया है, इसे विपरीत करना आसान है।
-* किसी भी के ∈ के लिए, ट्रैपडोर टी के बिना<sub>''k''</sub>, किसी भी पीपीटी एल्गोरिथ्म के लिए, एफ को सही ढंग से उलटने की संभावना<sub>''k''</sub> (यानी, दिया गया एफ<sub>''k''</sub>(एक्स), एक पूर्व-छवि एक्स 'इस तरह खोजें कि एफ<sub>''k''</sub>(एक्स ') = च<sub>''k''</sub>(x)) नगण्य है।<ref>Pass's Notes, def. 56.1</ref><ref>Goldwasser's lecture notes, def. 2.16</ref><ref>Ostrovsky, pp. 6-10, def. 11</ref>
+* किसी भी ''k'' ∈ ''K'', के लिए, ट्रैपडोर ''t<sub>k</sub>'' के बिना किसी भी पीपीटी एल्गोरिथम के लिए, ''f<sub>k</sub>''  को सही विधि से विपरीत करने की संभावना (अर्थात, दिया गया  ''f<sub>k</sub>''(''x'') एक पूर्व-छवि x' खोजें, जैसे कि ''f<sub>k</sub>''(''x''' ) = ''f<sub>k</sub>''(''x'')) नगण्य है।<ref>Pass's Notes, def. 56.1</ref><ref>Goldwasser's lecture notes, def. 2.16</ref><ref>Ostrovsky, pp. 6-10, def. 11</ref>
-यदि उपरोक्त संग्रह में प्रत्येक कार्य एक तरफ़ा क्रमचय है, तो संग्रह को ट्रैपडोर क्रमचय भी कहा जाता है।<ref>Pass's notes, def 56.1; Dodis's def 7, lecture 1.</ref>
+यदि उपरोक्त संग्रह में प्रत्येक कार्य एक तरफ़ा क्रमचय है तो संग्रह को ट्रैपडोर क्रमचय भी कहा जाता है।<ref>Pass's notes, def 56.1; Dodis's def 7, lecture 1.</ref>
 == उदाहरण ==
-निम्नलिखित दो उदाहरणों में, हम हमेशा मानते हैं कि एक बड़ी समग्र संख्या का गुणनखंड करना कठिन है (पूर्णांक गुणनखंड देखें)।
+निम्नलिखित दो उदाहरणों में, हम सदैव मानते हैं कि एक बड़ी समग्र संख्या का गुणनखंड करना कठिन है (पूर्णांक गुणनखंड देखें)।
 === आरएसए धारणा ===
-इस उदाहरण में, उलटा <math>d</math> का <math>e</math> मापांक <math>\phi(n)</math> (यूलर का कुल कार्य <math>n</math>) ट्रैपडोर है:
+इस उदाहरण में, <math>e</math> ,मापांक  <math>\phi(n)</math> (यूलर का <math>n</math> का संपूर्ण फलन) का व्युत्क्रम <math>d</math> ट्रैपडोर है:
 : <math>f(x) = x^e \mod n</math>
-यदि का गुणनखंडन <math>n=pq</math> जाना जाता है, तो <math>\phi(n)=(p-1)(q-1)</math> गणना की जा सकती है। इसके साथ उलटा <math>d</math> का <math>e</math> गणना की जा सकती है <math>d = e^{-1} \mod{\phi(n)}</math>, और फिर दिया <math>y = f(x)</math> हम ढूंढ सकते हैं <math>x = y^d \mod n = x^{ed} \mod n = x \mod n</math>.
-इसकी कठोरता आरएसए धारणा से होती है।<ref>Goldwasser's lecture notes, 2.3.2; Lindell's notes, pp. 17, Ex. 1.</ref>
+यदि <math>n=pq</math> का गुणनखंड ज्ञात है, तो <math>\phi(n)=(p-1)(q-1)</math> की गणना की जा सकती है। इसके साथ <math>e</math> के व्युत्क्रम <math>d</math> की गणना की जा सकती है <math>d = e^{-1} \mod{\phi(n)}</math>, और फिर दिया गया <math>y = f(x)</math> हम पा सकते हैं <math>x = y^d \mod n = x^{ed} \mod n = x \mod n</math> इसकी कठोरता आरएसए धारणा से होती है।<ref>Goldwasser's lecture notes, 2.3.2; Lindell's notes, pp. 17, Ex. 1.</ref>
 === राबिन का द्विघात अवशेष अनुमान ===
-होने देना <math>n</math> एक बड़ी समग्र संख्या हो जैसे कि <math>n = pq</math>, कहाँ <math>p</math> और <math>q</math> बड़े अभाज्य हैं जैसे कि <math>p \equiv 3 \pmod{4}, q \equiv 3 \pmod{4}</math>, और विरोधी के लिए गोपनीय रखा। समस्या गणना करना है <math>z</math> दिया गया <math>a</math> ऐसा है कि <math>a \equiv z^2 \pmod{n}</math>. ट्रैपडोर का गुणनखंड है <math>n</math>. ट्रैपडोर के साथ, z का समाधान इस प्रकार दिया जा सकता है <math>cx + dy, cx - dy, -cx + dy, -cx - dy</math>, कहाँ <math>a \equiv x^2 \pmod{p}, a \equiv y^2 \pmod{q}, c \equiv 1 \pmod{p}, c \equiv 0 \pmod{q}, d \equiv 0 \pmod{p}, d \equiv 1 \pmod{q}</math>. अधिक विवरण के लिए [[चीनी शेष प्रमेय]] देखें। ध्यान दें कि प्राइम्स दिए गए हैं <math>p</math> और <math>q</math>, हम ढूंढ सकते हैं <math>x \equiv a^{\frac{p+1}{4}} \pmod{p}</math> और <math>y \equiv a^{\frac{q+1}{4}} \pmod{q}</math>. यहाँ शर्तें <math>p \equiv 3 \pmod{4}</math> और <math>q \equiv 3 \pmod{4}</math> गारंटी है कि समाधान <math>x</math> और <math>y</math> अच्छी तरह से परिभाषित किया जा सकता है।<ref>Goldwasser's lecture notes, 2.3.4</ref>
+मान लीजिए <math>n</math> एक बड़ी संमिश्र संख्या है जैसे कि <math>n = pq</math> जहाँ <math>p</math> और <math>q</math> बड़ी अभाज्य संख्याएँ हैं जैसे कि <math>p \equiv 3 \pmod{4}, q \equiv 3 \pmod{4}</math> और विरोधी के लिए गोपनीय रखा। समस्या यह है कि दिए गए <math>a</math> के अनुसार <math>z</math> की गणना करना <math>a \equiv z^2 \pmod{n}</math> है। ट्रैपडोर <math>n</math> का गुणनखंड है। ट्रैपडोर के साथ, z का समाधान <math>cx + dy, cx - dy, -cx + dy, -cx - dy</math> के रूप में दिया जा सकता है, जहाँ <math>a \equiv x^2 \pmod{p}, a \equiv y^2 \pmod{q}, c \equiv 1 \pmod{p}, c \equiv 0 \pmod{q}, d \equiv 0 \pmod{p}, d \equiv 1 \pmod{q}</math>। अधिक विवरण के लिए चीनी शेष प्रमेय देखें। ध्यान दें कि अभाज्य संख्याएँ <math>p</math> और <math>q</math> दिए जाने पर, हम <math>x \equiv a^{\frac{p+1}{4}} \pmod{p}</math> और <math>y \equiv a^{\frac{q+1}{4}} \pmod{q}</math> यहां नियम <math>p \equiv 3 \pmod{4}</math> और <math>q \equiv 3 \pmod{4}</math> आश्वासन देती हैं कि समाधान <math>x</math> और <math>y</math> को अच्छी तरह से परिभाषित किया जा सकता है।<ref>Goldwasser's lecture notes, 2.3.4</ref>
 == यह भी देखें ==
-* वन-वे फंक्शन
+* एक तरफ़ा कार्य
 ==टिप्पणियाँ==

Anonymous

Search

ट्रैपडोर फंक्शन: Difference between revisions

Namespaces

More

Page actions

Revision as of 12:21, 1 June 2023

Contents

परिभाषा

उदाहरण

आरएसए धारणा

राबिन का द्विघात अवशेष अनुमान

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

ट्रैपडोर फंक्शन: Difference between revisions

Revision as of 12:21, 1 June 2023

परिभाषा

उदाहरण

आरएसए धारणा

राबिन का द्विघात अवशेष अनुमान

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories