नेटवर्क कोडिंग के लिए समरूपता हस्ताक्षर: Difference between revisions

From Vigyanwiki
No edit summary
 
(4 intermediate revisions by 4 users not shown)
Line 1: Line 1:
नेटवर्क कोडिंग को सूचना प्रवाह को अधिकतम करने वाले नेटवर्क में [[बैंडविड्थ (कंप्यूटिंग)]] का अधिकतम उपयोग करने के लिए दिखाया गया है, लेकिन नेटवर्क में मेलिसियस (विद्वेषपूर्ण) नोड्स द्वारा अतिक्रमण (पॉलुशन) के आक्षेपों के लिए योजना बहुत स्वाभाविक रूप से दुर्बल है। गारवेज अंतःक्षेपी एक नोड कई अभिग्राही को शीघ्रता से प्रभावित कर सकता है। [[नेटवर्क पैकेट]] का अतिक्रमण तेजी से प्रसारित होता है क्योंकि (एक भी) उपयुक्त नोड का आउटपुट अनुपयोगी हो जाता है यदि इनकमिंग पैकेटों में से कम से कम एक विकृत होता है।
नेटवर्क कोडिंग को सूचना संचार को अधिकतम करने वाले नेटवर्क में [[बैंडविड्थ (कंप्यूटिंग)]] का अधिकतम उपयोग करने के लिए दिखाया गया है, लेकिन नेटवर्क में विद्वेषपूर्ण (मेलिसियस) नोड्स द्वारा अतिक्रमण (पॉलुशन) के आक्षेपों के लिए योजना बहुत स्वाभाविक रूप से दुर्बल है। गारवेज अंतःक्षेपी एक नोड कई अभिग्राही को शीघ्रता से प्रभावित कर सकता है। [[नेटवर्क पैकेट]] का अतिक्रमण तेजी से प्रसारित होता है क्योंकि (एक भी) उपयुक्त नोड का आउटपुट अनुपयोगी हो जाता है यदि इनकमिंग पैकेटों में से कम से कम एक विकृत होता है।


आक्षेपक आसानी से एक पैकेट को विकृत कर सकता है, तथापि वह संकेत या [[हैश फंकशन|हैश फलन]] के अंतर्गत संघट्टन उत्पन्न करके एन्क्रिप्ट किया गया हो। यह एक आक्षेपक को पैकेट तक अभिगम्य और उन्हें विकृत करने की क्षमता देगा। डेनिस चार्ल्स, कमल जैन और क्रिस्टिन लॉटर ने अतिक्रमण आक्षेपों को रोकने के लिए नेटवर्क कोडिंग के साथ उपयोग के लिए एक नई [[होमोमोर्फिक एन्क्रिप्शन|समरूपी एन्क्रिप्शन]] संकेत योजना तैयार की।<ref>{{Cite journal |citeseerx = 10.1.1.60.4738|title = नेटवर्क कोडिंग के लिए हस्ताक्षर|year = 2006 |url=https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.4738 |archive-url = https://archive.org/details/signatures_for_network_coding |archive-date = 2021-11-20 |url-status = live}}</ref>
आक्षेपक आसानी से एक पैकेट को विकृत कर सकता है, तथापि वह संकेत या [[हैश फंकशन|हैश फलन]] के अंतर्गत संघट्टन उत्पन्न करके एन्क्रिप्ट किया गया हो। यह एक आक्षेपक को पैकेट तक अभिगम्य और उन्हें विकृत करने की क्षमता देगा। डेनिस चार्ल्स, कमल जैन और क्रिस्टिन लॉटर ने अतिक्रमण आक्षेपों को रोकने के लिए नेटवर्क कोडिंग के साथ उपयोग के लिए एक नई [[होमोमोर्फिक एन्क्रिप्शन|समरूपी एन्क्रिप्शन]] संकेत योजना तैयार की।<ref>{{Cite journal |citeseerx = 10.1.1.60.4738|title = नेटवर्क कोडिंग के लिए हस्ताक्षर|year = 2006 |url=https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.4738 |archive-url = https://archive.org/details/signatures_for_network_coding |archive-date = 2021-11-20 |url-status = live}}</ref>
Line 6: Line 6:


== नेटवर्क कोडिंग ==
== नेटवर्क कोडिंग ==
मान लीजिए <math>G = (V, E)</math> एक [[निर्देशित ग्राफ]] है, जहां <math>V</math> एक समुच्चय है, जिसके अवयवों को शीर्ष या [[नोड (नेटवर्किंग)]] कहा जाता है, और <math>E</math> शीर्षों के क्रमित युग्मों का एक समुच्चय है, जिन्हें चाप, निर्देशित कोर, या तीर कहा जाता है। स्रोत <math>s \in V</math> एक फ़ाइल <math>D</math> को शीर्षों के एक समुच्चय <math>T \subseteq V</math> में संचारित करना चाहता है। एक वेक्टर समष्टि <math>W/\mathbb{F}_p</math>(आयाम d के बारे में) चयन करता है, जहाँ <math>p</math> अभाज्य संख्या है, और संचरित होने वाले डेटा को सदिशों <math>w_1 ,\ldots , w_k \in W</math> के एक समुच्चय के रूप में देखता है। स्रोत तब <math>v_1,\ldots , v_k</math> व्यवस्थित करके <math> v_i = (0, \ldots , 0, 1, \ldots , 0, w_{i_1}, \ldots , w{i_d})</math> संवर्धित वेक्टर बनाता है। जहाँ <math>w_{i_j}</math> वेक्टर <math>w_i</math> का j-वाँ निर्देशांक है। और <math>(i-1)</math> में पहले '1' के प्रकट होने से पहले <math>v_i</math> शून्य होते है। कोई सामान्यता के हानि के बिना मान सकता है कि वेक्टर <math>v_i</math> रैखिक रूप से स्वतंत्र हैं। हम <math>V</math> द्वारा इन वैक्टरों द्वारा फैलाए गए रैखिक उप-समष्टि <math>\mathbb{F}_p^{k+d}</math> को निरूपित करते हैं। प्रत्येक निवर्तमान कोर <math>e \in E</math> शीर्ष <math>y(e)</math> में प्रवेश करने वाले वेक्टर के एक रैखिक संयोजन <math>v = in(e)</math> की गणना करता है, जहां कोर की उत्पत्ति होती है, अर्थात
मान लीजिए <math>G = (V, E)</math> एक [[निर्देशित ग्राफ]] है, जहां <math>V</math> एक समुच्चय है, जिसके अवयवों को शीर्ष या [[नोड (नेटवर्किंग)]] कहा जाता है, और <math>E</math> शीर्षों के क्रमित युग्मों का एक समुच्चय है, जिन्हें चाप, निर्देशित कोर, या तीर कहा जाता है। स्रोत <math>s \in V</math> एक फ़ाइल <math>D</math> को शीर्षों के एक समुच्चय <math>T \subseteq V</math> में संचारित करना चाहता है। एक वेक्टर समष्टि <math>W/\mathbb{F}_p</math>(आयाम d के बारे में) चयन करता है, जहाँ <math>p</math> अभाज्य संख्या है, और संचरित होने वाले डेटा को सदिशों <math>w_1 ,\ldots , w_k \in W</math> के एक समुच्चय के रूप में देखता है। स्रोत तब <math>v_1,\ldots , v_k</math> व्यवस्थित करके <math> v_i = (0, \ldots , 0, 1, \ldots , 0, w_{i_1}, \ldots , w{i_d})</math> संवर्धित वेक्टर बनाता है। जहाँ <math>w_{i_j}</math> वेक्टर <math>w_i</math> का j-वाँ निर्देशांक है। और <math>(i-1)</math> में पहले '1' के प्रकट होने से पहले <math>v_i</math> शून्य होते है। कोई सामान्यता के हानि के बिना मान सकता है कि वेक्टर <math>v_i</math> रैखिक रूप से स्वतंत्र हैं। हम <math>V</math> द्वारा इन वैक्टरों द्वारा फैलाए गए रैखिक उप-समष्टि <math>\mathbb{F}_p^{k+d}</math> को निरूपित करते हैं। प्रत्येक निवर्तमान कोर <math>e \in E</math> शीर्ष <math>y(e)</math> में प्रवेश करने वाले वेक्टर के एक रैखिक संयोजन <math>v = in(e)</math> की गणना करता है, जहां कोर की उत्पत्ति होती है, अर्थात


: <math>y(e) = \sum_{f:\mathrm{out}(f)=v}(m_e(f)y(f))</math>
: <math>y(e) = \sum_{f:\mathrm{out}(f)=v}(m_e(f)y(f))</math>
जहाँ <math>m_e(f) \in \mathbb{F}_p</math> प्राप्त होता है। हम मानते हैं कि स्रोत में <math>k</math> इनपुट कोर हैं जो <math>k</math> वेक्टर <math>w_i</math> का अनुसरण करता है। प्रेरण द्वारा, एक यह है कि वेक्टर <math>y(e)</math> किसी भी कोर पर एक रैखिक संयोजन <math>y(e) = \sum_{1 \le i \le k}(g_i(e)v_i)</math> और <math>V</math> में एक वेक्टर है। k-आयामी वेक्टर <math>g(e) = (g_1(e), \ldots , g_k(e))</math> वेक्टर <math>y(e)</math> का केवल पहला k निर्देशांक है। हम उस [[मैट्रिक्स (गणित)|आव्यूह (गणित)]] को कहते हैं जिसके पद   <math>g(e_1), \ldots , g(e_k)</math> वेक्टर होते हैं, जहाँ <math>e_i</math> एक शीर्ष <math>t \in T</math> के लिए प्रवेशी कोर हैं, जिसके लिए सार्वभौमिक एन्कोडिंग आव्यूह <math>t</math> और इसे <math>G_t</math>से निरूपित करें। व्यवहार में एन्कोडिंग वेक्टर यादृच्छिक रूप से चयन किए जाते हैं इसलिए आव्यूह <math>G_t</math> उच्च प्रायिकता के साथ परिवर्तनीय होते है। इस प्रकार, कोई भी अभिग्राही <math>y_1, \ldots , y_k</math> प्राप्त करने पर <math>w_1,\ldots ,w_k</math> हल करके खोज सकता है।
जहाँ <math>m_e(f) \in \mathbb{F}_p</math> प्राप्त होता है। हम मानते हैं कि स्रोत में <math>k</math> इनपुट कोर हैं जो <math>k</math> वेक्टर <math>w_i</math> का अनुसरण करता है। प्रेरण द्वारा, एक यह है कि वेक्टर <math>y(e)</math> किसी भी कोर पर एक रैखिक संयोजन <math>y(e) = \sum_{1 \le i \le k}(g_i(e)v_i)</math> और <math>V</math> में एक वेक्टर है। k-आयामी वेक्टर <math>g(e) = (g_1(e), \ldots , g_k(e))</math> वेक्टर <math>y(e)</math> का केवल पहला k निर्देशांक है। हम उस [[मैट्रिक्स (गणित)|आव्यूह (गणित)]] को कहते हैं जिसके पद <math>g(e_1), \ldots , g(e_k)</math> वेक्टर होते हैं, जहाँ <math>e_i</math> एक शीर्ष <math>t \in T</math> के लिए प्रवेशी कोर हैं, जिसके लिए सार्वभौमिक एन्कोडिंग आव्यूह <math>t</math> और इसे <math>G_t</math>से निरूपित करें। व्यवहार में एन्कोडिंग वेक्टर यादृच्छिक रूप से चयन किए जाते हैं इसलिए आव्यूह <math>G_t</math> उच्च प्रायिकता के साथ परिवर्तनीय होते है। इस प्रकार, कोई भी अभिग्राही <math>y_1, \ldots , y_k</math> प्राप्त करने पर <math>w_1,\ldots ,w_k</math> हल करके खोज सकता है।


: <math>\begin{bmatrix} y'\\ y_2' \\ \vdots \\ y_k' \end{bmatrix} = G_t \begin{bmatrix} w_1\\ w_2 \\ \vdots \\ w_k \end{bmatrix}</math>
: <math>\begin{bmatrix} y'\\ y_2' \\ \vdots \\ y_k' \end{bmatrix} = G_t \begin{bmatrix} w_1\\ w_2 \\ \vdots \\ w_k \end{bmatrix}</math>
जहां <math>y_i'</math> वेक्टर <math>y_i</math> के पहले k निर्देशांक को हटाकर बनाए गए वेक्टर हैं।
जहां <math>y_i'</math> वेक्टर <math>y_i</math> के पहले k निर्देशांक को हटाकर बनाए गए वेक्टर हैं।


== अभिग्राही पर डिकोडिंग ==
== अभिग्राही पर डिकोडिंग ==
प्रत्येक [[रिसीवर (सूचना सिद्धांत)|अभिग्राही (सूचना सिद्धांत)]] <math>t \in T</math> को <math>k</math> वेक्टर <math>y_1, \ldots , y_k</math> प्राप्त होता है जो <math>v_i</math>'के यादृच्छिक रैखिक संयोजन हैं। वास्तव में,  
प्रत्येक [[रिसीवर (सूचना सिद्धांत)|अभिग्राही (सूचना सिद्धांत)]] <math>t \in T</math> को <math>k</math> वेक्टर <math>y_1, \ldots , y_k</math> प्राप्त होता है जो <math>v_i</math>'के यादृच्छिक रैखिक संयोजन हैं। वास्तव में,  


यदि
यदि
Line 23: Line 23:


: <math>y_i = \sum_{1 \le j \le k}(\alpha_{ij}v_j).</math>
: <math>y_i = \sum_{1 \le j \le k}(\alpha_{ij}v_j).</math>
इस प्रकार हम उच्च [[संभावना|प्रायिकता]] वाले <math>v_i</math> का पता लगाने के लिए रैखिक परिवर्तन को प्रतिवर्त कर सकते हैं।
इस प्रकार हम उच्च [[संभावना|प्रायिकता]] वाले <math>v_i</math> का पता लगाने के लिए रैखिक परिवर्तन को प्रतिवर्त कर सकते हैं।


== इतिहास ==
== इतिहास ==
क्रोह्न, फ्रीडमैन और माज़िएरेस ने 2004 में एक सिद्धांत<ref>{{cite journal |last1=Krohn |first1=Maxwell N. |last2=Freedman |first2=Michael J |last3=Mazières |first3=David |title=कुशल सामग्री वितरण के लिए रेटलेस इरेज़र कोड का ऑन-द-फ़्लाई सत्यापन|journal=IEEE Symposium on Security and Privacy, 2004. Proceedings. 2004 |date=2004 |pages=226–240 |doi=10.1109/SECPRI.2004.1301326 |url=https://www.cs.princeton.edu/~mfreed/docs/authcodes-sp04.pdf |access-date=17 November 2022 |location=Berkeley, California, USA |language=en-us |issn=1081-6011|isbn=0-7695-2136-3|s2cid=6976686 }}</ref> प्रस्तावित किया था कि यदि हमारे पास एक हैश फलन <math>H : V \longrightarrow G</math> है जैसे कि:
क्रोह्न, फ्रीडमैन और माज़िएरेस ने 2004 में एक सिद्धांत<ref>{{cite journal |last1=Krohn |first1=Maxwell N. |last2=Freedman |first2=Michael J |last3=Mazières |first3=David |title=कुशल सामग्री वितरण के लिए रेटलेस इरेज़र कोड का ऑन-द-फ़्लाई सत्यापन|journal=IEEE Symposium on Security and Privacy, 2004. Proceedings. 2004 |date=2004 |pages=226–240 |doi=10.1109/SECPRI.2004.1301326 |url=https://www.cs.princeton.edu/~mfreed/docs/authcodes-sp04.pdf |access-date=17 November 2022 |location=Berkeley, California, USA |language=en-us |issn=1081-6011|isbn=0-7695-2136-3|s2cid=6976686 }}</ref> प्रस्तावित किया था कि यदि हमारे पास एक हैश फलन <math>H : V \longrightarrow G</math> है जैसे कि:
*  <math>H</math> [[टक्कर प्रतिरोध|एक संघट्ट]] प्रतिरोधी है- <math>x</math> और <math>y</math> को जांच करना कठिन है जैसे कि <math>H(x) = H(y)</math>;
*  <math>H</math> [[टक्कर प्रतिरोध|एक संघट्ट]] प्रतिरोधी है- <math>x</math> और <math>y</math> को जांच करना कठिन है जैसे कि <math>H(x) = H(y)</math>;
* <math>H</math> समाकारिता - <math>H(x+y) = H(x) + H(y)</math> होती है।
* <math>H</math> समाकारिता - <math>H(x+y) = H(x) + H(y)</math> होती है।


तब सर्वर सुरक्षित रूप से प्रत्येक अभिग्राही को <math>H(v_i)</math> वितरित कर सकता है और जांच कर सकता है कि क्या
तब सर्वर सुरक्षित रूप से प्रत्येक अभिग्राही को <math>H(v_i)</math> वितरित कर सकता है और जांच कर सकता है कि क्या


: <math>y =  \sum_{1 \leq i\leq k} (\alpha_iv_i)</math>
: <math>y =  \sum_{1 \leq i\leq k} (\alpha_iv_i)</math>
Line 50: Line 50:
[[परिमित क्षेत्र]] पर [[अण्डाकार वक्र|दीर्घवृत्तीय वक्र]] क्रिप्टोग्राफी, परिमित क्षेत्रों पर दीर्घवृत्तीय वक्रों की बीजगणितीय संरचना के आधार पर सार्वजनिक-कुंजी क्रिप्टोग्राफ़ी के लिए एक दृष्टिकोण है।
[[परिमित क्षेत्र]] पर [[अण्डाकार वक्र|दीर्घवृत्तीय वक्र]] क्रिप्टोग्राफी, परिमित क्षेत्रों पर दीर्घवृत्तीय वक्रों की बीजगणितीय संरचना के आधार पर सार्वजनिक-कुंजी क्रिप्टोग्राफ़ी के लिए एक दृष्टिकोण है।


मान लीजिए <math>\mathbb{F}_q</math> एक परिमित क्षेत्र हो जैसे कि <math>q</math> 2 या 3 की घात नहीं है। तब <math>E</math> के ऊपर एक दीर्घवृत्तीय वक्र <math>\mathbb{F}_q</math> एक वक्र है जो समीकरण के रूप में दिया गया है
मान लीजिए <math>\mathbb{F}_q</math> एक परिमित क्षेत्र हो जैसे कि <math>q</math> 2 या 3 की घात नहीं है। तब <math>E</math> के ऊपर एक दीर्घवृत्तीय वक्र <math>\mathbb{F}_q</math> एक वक्र है जो समीकरण के रूप में दिया गया है
: <math> y^2 = x^3 + ax + b, \, </math>
: <math> y^2 = x^3 + ax + b, \, </math>
जहाँ <math>a, b  \in  \mathbb{F}_q</math> जैसे कि <math>4a^3 + 27b^2 \not= 0</math>
जहाँ <math>a, b  \in  \mathbb{F}_q</math> जैसे कि <math>4a^3 + 27b^2 \not= 0</math>
Line 60: Line 60:


=== [[ वील पेयरिंग ]] ===
=== [[ वील पेयरिंग ]] ===
वेइल पेयरिंग एक [[अण्डाकार वक्र|दीर्घवृत्तीय वक्र]] पर फलनों के माध्यम से एकांक के वर्ग का निर्माण है, इस तरह से <math>E</math> के [[मरोड़ उपसमूह|आघूर्ण बल उपसमूह]] पर एक युग्म ([[द्विरेखीय रूप]], हालांकि गुणक संकेतन के साथ) का निर्माण करने के लिए <math>E</math> को लेते है। मान लीजिए <math>E/\mathbb{F}_q</math> एक दीर्घवृत्तीय वक्र हो और <math>\mathbb{\bar{F}}_q</math> का एक बीजगणितीय समापन <math>\mathbb{F}_q</math> हो। यदि <math>m</math> एक पूर्णांक है, <math>\mathbb{F}_q</math> क्षेत्र की विशेषता के लिए अपेक्षाकृत प्रमुख है, तब <math>m</math>- आघूर्ण बल बिंदुओं का समूह <math>E[m] = {P \in  E(\mathbb{\bar {F}}_q) : mP = O}</math> होता है।
वेइल पेयरिंग एक [[अण्डाकार वक्र|दीर्घवृत्तीय वक्र]] पर फलनों के माध्यम से एकांक के वर्ग का निर्माण है, इस तरह से <math>E</math> के [[मरोड़ उपसमूह|आघूर्ण बल उपसमूह]] पर एक युग्म ([[द्विरेखीय रूप]], हालांकि गुणक संकेतन के साथ) का निर्माण करने के लिए <math>E</math> को लेते है। मान लीजिए <math>E/\mathbb{F}_q</math> एक दीर्घवृत्तीय वक्र हो और <math>\mathbb{\bar{F}}_q</math> का एक बीजगणितीय समापन <math>\mathbb{F}_q</math> हो। यदि <math>m</math> एक पूर्णांक है, <math>\mathbb{F}_q</math> क्षेत्र की विशेषता के लिए अपेक्षाकृत प्रमुख है, तब <math>m</math>- आघूर्ण बल बिंदुओं का समूह <math>E[m] = {P \in  E(\mathbb{\bar {F}}_q) : mP = O}</math> होता है।


यदि <math>E/\mathbb{F}_q</math> दीर्घवृत्तीय वक्र है और <math>\gcd(m, q) = 1</math> तब
यदि <math>E/\mathbb{F}_q</math> दीर्घवृत्तीय वक्र है और <math>\gcd(m, q) = 1</math> तब


: <math>E[m] \cong  (\mathbb{Z}/m\mathbb{Z}) * (\mathbb{Z}/m\mathbb{Z})</math>
: <math>E[m] \cong  (\mathbb{Z}/m\mathbb{Z}) * (\mathbb{Z}/m\mathbb{Z})</math>
एक मानचित्र <math>e_m : E[m] * E[m] \rightarrow \mu_m(\mathbb{F}_q)</math> है, जैसे कि:
एक मानचित्र <math>e_m : E[m] * E[m] \rightarrow \mu_m(\mathbb{F}_q)</math> है, जैसे कि:


#(द्विरेखीय) <math>e_m(P + R,Q) = e_m(P,Q)e_m(R,Q)\text{ and }e_m(P,Q + R) = e_m(P,Q)e_m(P, R)</math>.
#(द्विरेखीय) <math>e_m(P + R,Q) = e_m(P,Q)e_m(R,Q)\text{ and }e_m(P,Q + R) = e_m(P,Q)e_m(P, R)</math>.
#(गैर-परिवर्तनीय) <math>e_m(P,Q) = 1</math> सभी P के लिए यह दर्शाता है कि <math>Q = O</math> होता है।
#(गैर-परिवर्तनीय) <math>e_m(P,Q) = 1</math> सभी P के लिए यह दर्शाता है कि <math>Q = O</math> होता है।
#(प्रत्यावर्ती) <math>e_m(P, P) = 1</math>.
#(प्रत्यावर्ती) <math>e_m(P, P) = 1</math>.


Line 76: Line 76:
=== समरूपी संकेत ===
=== समरूपी संकेत ===


मान लीजिए <math>p</math> एक अभाज्य संख्या है और <math>q</math> एक अभाज्य शक्ति है। मान लीजिए कि <math>V/\mathbb{F}_p</math> आयाम <math>D</math> का सदिश स्थान है और <math>E/\mathbb{F}_q</math> दीर्घवृत्तीय वक्र है जैसे कि <math>P_1, \ldots , P_D  \in  E[p]</math>मे होता है। परिभाषित <math>h : V \longrightarrow E[p]</math> इस प्रकार <math>h(u_1, \ldots , u_D) =  \sum_{1 \leq i\leq D} (u_iP_i)</math> है। फलन <math>h</math> से <math>V</math> को <math>E[p]</math> तक एक स्वेच्छ समाकारिता है।
मान लीजिए <math>p</math> एक अभाज्य संख्या है और <math>q</math> एक अभाज्य शक्ति है। मान लीजिए कि <math>V/\mathbb{F}_p</math> आयाम <math>D</math> का सदिश स्थान है और <math>E/\mathbb{F}_q</math> दीर्घवृत्तीय वक्र है जैसे कि <math>P_1, \ldots , P_D  \in  E[p]</math>मे होता है। परिभाषित <math>h : V \longrightarrow E[p]</math> इस प्रकार <math>h(u_1, \ldots , u_D) =  \sum_{1 \leq i\leq D} (u_iP_i)</math> है। फलन <math>h</math> से <math>V</math> को <math>E[p]</math> तक एक स्वेच्छ समाकारिता है।


सर्वर <math>s_1, \ldots , s_D</math> मे गुप्त रूप से <math>\mathbb{F}_p</math> चयन करता है और <math>Q</math> आघूर्ण बल का एक बिंदु <math>e_p(P_i,Q) \not=  1</math> और   <math>(P_i, s_iQ)</math> के लिए <math>1 \leq i \leq D</math> प्रकाशित भी करता है। वेक्टर के संकेत <math>v = u_1, \ldots , u_D</math> है
सर्वर <math>s_1, \ldots , s_D</math> मे गुप्त रूप से <math>\mathbb{F}_p</math> चयन करता है और <math>Q</math> आघूर्ण बल का एक बिंदु <math>e_p(P_i,Q) \not=  1</math> और <math>(P_i, s_iQ)</math> के लिए <math>1 \leq i \leq D</math> प्रकाशित भी करता है। वेक्टर के संकेत <math>v = u_1, \ldots , u_D</math> है
  <math>\sigma(v) =  \sum_{1 \leq i\leq D} (u_is_iP_i)</math>
  <math>\sigma(v) =  \sum_{1 \leq i\leq D} (u_is_iP_i)</math>
ध्यान दे: यह संकेत समरूपी है क्योंकि h की गणना एक समाकारिता है।
ध्यान दे: यह संकेत समरूपी है क्योंकि h की गणना एक समाकारिता है।
Line 95: Line 95:
सत्यापन महत्वपूर्ण रूप से वेल-पेयरिंग की द्विरेखीयता का उपयोग करता है।
सत्यापन महत्वपूर्ण रूप से वेल-पेयरिंग की द्विरेखीयता का उपयोग करता है।


== सिस्टम सेटअप ==
== प्रणाली संस्थापन ==
सर्वर गणना करता है <math>\sigma(v_i)</math> प्रत्येक के लिए <math>1 \leq i \leq k</math>. संचारित <math>v_i, \sigma(v_i)</math>.
सर्वर प्रत्येक <math>\sigma(v_i)</math> के लिए <math>1 \leq i \leq k</math> की गणना करता है। और <math>v_i, \sigma(v_i)</math> को प्रसारित करता है। प्रत्येक कोर पर <math>e</math> की गणना करते समय<math>y(e) =  \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)y(f))</math>दीर्घवृत्तीय वक्र
हर कोर पर <math>e</math> गणना करते समय
दीर्घवृ<math>\sigma(y(e)) =  \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)\sigma(y(f)))</math> पर <math>E</math> की भी गणना करें।
<math>y(e) =  \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)y(f))</math>
गणना भी करें
<math>\sigma(y(e)) =  \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)\sigma(y(f)))</math>
दीर्घवृत्तीय वक्र पर <math>E</math>.


संकेत दीर्घवृत्तीय वक्र पर निर्देशांक के साथ एक बिंदु है <math>\mathbb{F}_q</math>. इस प्रकार संकेत का आकार है <math>2 \log q</math> बिट्स (जो कुछ स्थिर समय है <math>log(p)</math> बिट्स, के सापेक्ष आकार के आधार पर <math>p</math> और <math>q</math>), और यह ट्रांसमिशन ओवरहेड है। संकेत की गणना <math>h(e)</math> प्रत्येक शीर्ष पर की आवश्यकता है <math>O(d_{in} \log p \log^{1+\epsilon} q)</math> बिट ऑपरेशंस, जहां <math>d_{in}</math> वर्टेक्स की इन-डिग्री है <math>in(e)</math>. एक संकेत के सत्यापन की आवश्यकता है <math>O((d + k) \log^{2+\epsilon} q)</math> बिट संचालन।
संकेत <math>\mathbb{F}_q</math> में निर्देशांक के साथ दीर्घवृत्तीय वक्र पर एक बिंदु है। इस प्रकार हस्ताक्षर का आकार <math>2 \log q</math> बिट्स है (जो कुछ स्थिर समय <math>log(p)</math> बिट्स है, जो <math>p</math> और <math>q</math> के सापेक्ष आकार पर निर्भर करता है), और यह संचारण शीर्ष है। प्रत्येक शीर्ष पर हस्ताक्षर <math>h(e)</math> की गणना के लिए <math>O(d_{in} \log p \log^{1+\epsilon} q)</math> बिट संचालन की आवश्यकता होती है, जहाँ <math>d_{in}</math> में <math>in(e)</math> शीर्ष की घात है। संकेत के सत्यापन के लिए <math>O((d + k) \log^{2+\epsilon} q)</math> बिट संचालन की आवश्यकता होती है।


== सुरक्षा का प्रमाण ==
== सुरक्षा का प्रमाण ==


आक्षेपक हैश फ़ंक्शन के अंतर्गत टक्कर उत्पन्न कर सकता है।
आक्षेपक हैश फलन के अंतर्गत संघट्ट उत्पन्न कर सकता है।


यदि दिया <math>(P_1, \ldots , P_r)</math> में इंगित करता है <math>E[p]</math> पाना
यदि दिया गया है कि <math>(P_1, \ldots , P_r)</math> में <math>E[p]</math> प्राप्त <math>a = (a_1, \ldots , a_r)  \in  \mathbb{F}_p^r</math> और <math>b = (b_1, \ldots , b_r)  \in  \mathbb{F}_p^r</math> प्रदर्शित करता है। जैसे कि <math>a \not= b</math> और
<math>a = (a_1, \ldots , a_r)  \in  \mathbb{F}_p^r</math> और <math>b = (b_1, \ldots , b_r)  \in  \mathbb{F}_p^r</math>
जैसे कि <math>a \not= b</math> और


: <math>\sum_{1 \leq i \leq r} (a_iP_i) = \sum_{1 \leq j \leq r} (b_jP_j).</math>
: <math>\sum_{1 \leq i \leq r} (a_iP_i) = \sum_{1 \leq j \leq r} (b_jP_j).</math>
प्रस्ताव: क्रम के [[चक्रीय समूह]] पर असतत लॉग से बहुपद समय में कमी होती है <math>p</math> दीर्घवृत्तीय वक्रों पर हैश-संघट्टन के लिए।
प्रस्ताव: दीर्घवृत्तीय वक्रों पर हैश-संघट्टन के लिए क्रम <math>p</math> के [[चक्रीय समूह]] पर असतत लॉग से बहुपद समय में कमी होती है


यदि <math>r = 2</math>, तो हमें मिलता है <math>xP+yQ = uP+vQ</math>. इस प्रकार <math>(x-u)P+(y-v)Q = 0</math>.
यदि <math>r = 2</math>, तो हमें <math>xP+yQ = uP+vQ</math> प्राप्त होता है। इस प्रकार <math>(x-u)P+(y-v)Q = 0</math> प्राप्त होता है। हम यह दावा करते हैं कि <math>x \not = u</math> और <math>y \not =  v</math> है। मान लीजिए कि <math>x = u</math>, तो हमारे पास <math>(y-v)Q = 0</math> होगा, लेकिन <math>Q</math> क्रम <math>p</math> (अभाज्य) का एक बिंदु है, इस प्रकार <math>y-u \equiv 0 \bmod p</math> होता है। दूसरे शब्दों में <math>y = v</math> में <math>\mathbb{F}_p</math> होता है। यह इस धारणा का खंडन करता है कि <math>(x, y)</math> और <math>(u, v)</math> भिन्न युग्म <math>\mathbb{F}_2</math> हैं। इस प्रकार हमारे पास वह <math>Q = -(x-u)(y-v)^{-1}P</math> है, जहां व्युत्क्रम को मापांक <math>p</math> के रूप में लिया जाता है।
हम यह दावा करते हैं <math>x \not = u</math> और <math>y \not =  v</math>. लगता है कि <math>x = u</math>, तो हमारे पास होगा <math>(y-v)Q = 0</math>, लेकिन <math>Q</math> व्यवस्था का प्रश्न है <math>p</math> (एक प्रधान) इस प्रकार <math>y-u \equiv 0 \bmod p</math>. दूसरे शब्दों में <math>y = v</math> में <math>\mathbb{F}_p</math>. यह धारणा के विपरीत है कि <math>(x, y)</math> और <math>(u, v)</math> में भिन्न जोड़े हैं <math>\mathbb{F}_2</math>. इस प्रकार हमारे पास वह है <math>Q = -(x-u)(y-v)^{-1}P</math>, जहां व्युत्क्रम को मॉड्यूलो के रूप में लिया जाता है <math>p</math>.


यदि हमारे पास r > 2 है तो हम दो चीजों में से एक कर सकते हैं। या तो हम ले सकते हैं <math>P_1 = P</math> और <math>P_2 = Q</math> पहले की तरह और सेट करें <math>P_i = O</math> के लिए <math>i</math> > 2 (इस मामले में सबूत उस मामले में कम हो जाता है जब <math>r = 2</math>), या हम ले सकते हैं <math>P_1 = r_1P</math> और <math>P_i = r_iQ</math> कहाँ <math>r_i</math> से यादृच्छिक रूप से चुने जाते हैं <math>\mathbb{F}_p</math>. हमें एक अज्ञात में एक समीकरण मिलता है (का असतत लघुगणक <math>Q</math>). यह बहुत संभव है कि जो समीकरण हमें प्राप्त होता है उसमें अज्ञात शामिल न हो। हालाँकि, यह बहुत कम प्रायिकता के साथ होता है जैसा कि हम आगे तर्क देते हैं। मान लीजिए हैश-संघट्टन के लिए एल्गोरिदम ने हमें वह दिया है
यदि हमारे पास r > 2 है है तो हम दो में से एक कार्य कर सकते हैं या तो हम पहले की तरह <math>P_1 = P</math> और <math>P_2 = Q</math> ले सकते हैं और <math>P_i = O</math> को <math>i</math> > 2 के लिए सेट कर सकते हैं (इस स्थिति में प्रमाण स्थिति में कम हो जाता है जब <math>r = 2</math>), या हम <math>P_1 = r_1P</math> और <math>P_i = r_iQ</math> ले सकते हैं। जहाँ <math>r_i</math> से <math>\mathbb{F}_p</math> यादृच्छिक रूप से चयन किए जाते हैं। हमें एक अज्ञात में एक समीकरण ( <math>Q</math> का असतत लघुगणक) मिलता है। यह बहुत संभव है कि जो समीकरण हमें प्राप्त होता है उसमें अज्ञात सम्मिलित न हो। हालाँकि, यह बहुत कम प्रायिकता के साथ होता है जैसा कि हम आगे तर्क देते हैं। मान लीजिए हैश-संघट्टन के लिए एल्गोरिदम ने हमें वह दिया है


: <math>ar_1P + \sum_{2 \leq i \leq r}(b_ir_iQ) = 0.</math>
: <math>ar_1P + \sum_{2 \leq i \leq r}(b_ir_iQ) = 0.</math>
फिर जब तक <math>\sum_{2 \leq i \leq r} b_ir_i \not\equiv 0 \bmod p</math>, हम Q के असतत लॉग के लिए हल कर सकते हैं। लेकिन <math>r_i</math>हैश-कोलिज़न के लिए ओरेकल के लिए अज्ञात हैं और इसलिए हम उस क्रम को बदल सकते हैं जिसमें यह प्रक्रिया होती है। दूसरे शब्दों में दिया <math>b_i</math>, के लिए <math>2 \leq i \leq r</math>, सभी शून्य नहीं, इसकी क्या प्रायिकता है कि <math>r_i</math>हमने संतुष्ट चुना है <math>\sum_{2 \leq i \leq r} (b_ir_i) = 0</math>? यह स्पष्ट है कि बाद की प्रायिकता है <math>1 \over p</math> . इस प्रकार उच्च प्रायिकता के साथ हम के असतत लॉग के लिए हल कर सकते हैं <math>Q</math>.
फिर जब तक <math>\sum_{2 \leq i \leq r} b_ir_i \not\equiv 0 \bmod p</math> हम Q के असतत लॉग के लिए हल कर सकते हैं। लेकिन <math>r_i</math>हैश-संघट्ट के लिए ओरेकल के लिए अज्ञात हैं और इसलिए हम उस क्रम को बदल सकते हैं जिसमें यह प्रक्रिया होती है। दूसरे शब्दों में, दिया हुआ है कि <math>b_i</math>, <math>2 \leq i \leq r</math> के लिए, सभी शून्य नहीं है, इसकी क्या प्रायिकता है कि हमने जो <math>r_i</math>चयन किया है वह <math>\sum_{2 \leq i \leq r} (b_ir_i) = 0</math> को संतुष्ट करता है। यह स्पष्ट है कि बाद वाली प्रायिकता <math>1 \over p</math> होती है। इस प्रकार उच्च प्रायिकता के साथ हम <math>Q</math> के असतत लॉग के लिए हल कर सकते हैं।


हमने दिखाया है कि इस योजना में हैश संघट्टन उत्पन्न करना कठिन है। दूसरा तरीका जिसके द्वारा एक विरोधी हमारे सिस्टम को विफल कर सकता है, वह है जाली संकेत। संकेत के लिए यह योजना अनिवार्य रूप से बोन-लिन-शाचम संकेत योजना का समग्र संकेत संस्करण है।<ref>{{cite journal |last1=Boneh |first1=Dan |last2=Lynn |first2=Ben |last3=Shacham |first3=Hovav |title=वील पेयरिंग से लघु हस्ताक्षर|journal=Advances in Cryptology — ASIACRYPT 2001 |series=Lecture Notes in Computer Science |date=2001 |volume=2248 |pages=514–532 |doi=10.1007/3-540-45682-1_30 |url=https://hovav.net/ucsd/dist/sigs.pdf |access-date=17 November 2022 |language=en|isbn=978-3-540-45682-7}}</ref> यहाँ यह दिखाया गया है कि एक संकेत बनाना कम से कम उतना ही कठिन है जितना कि दीर्घवृत्तीय वक्र डिफी-हेलमैन समस्या को हल करना। दीर्घवृत्तीय वक्रों पर इस समस्या को हल करने का एकमात्र ज्ञात तरीका असतत-लॉग की गणना करना है। इस प्रकार एक संकेत बनाना कम से कम उतना ही कठिन है जितना कि दीर्घवृत्तीय वक्रों पर कम्प्यूटेशनल सह-डिफी-हेलमैन को हल करना और शायद असतत-लॉग की गणना करना जितना कठिन है।
हमने दिखाया है कि इस योजना में हैश संघट्टन उत्पन्न करना कठिन है। दूसरा तरीका जिसके द्वारा विपक्षी हमारे प्रणाली को वह एक फोर्जन संकेत विफल कर सकता है। संकेत के लिए यह योजना अनिवार्य रूप से बोन-लिन-शाचम संकेत योजना का समग्र संकेत संस्करण है।<ref>{{cite journal |last1=Boneh |first1=Dan |last2=Lynn |first2=Ben |last3=Shacham |first3=Hovav |title=वील पेयरिंग से लघु हस्ताक्षर|journal=Advances in Cryptology — ASIACRYPT 2001 |series=Lecture Notes in Computer Science |date=2001 |volume=2248 |pages=514–532 |doi=10.1007/3-540-45682-1_30 |url=https://hovav.net/ucsd/dist/sigs.pdf |access-date=17 November 2022 |language=en|isbn=978-3-540-45682-7}}</ref> यहाँ यह दिखाया गया है कि एक संकेत बनाना कम से कम उतना ही कठिन है जितना कि दीर्घवृत्तीय वक्र डिफी-हेलमैन समस्या को हल करना। दीर्घवृत्तीय वक्रों पर इस समस्या को हल करने का एकमात्र ज्ञात तरीका असतत-लॉग की गणना करना है। इस प्रकार एक संकेत बनाना कम से कम उतना ही कठिन है जितना कि दीर्घवृत्तीय वक्रों पर कम्प्यूटेशनल सह-डिफी-हेलमैन को हल करना और संभव्यता असतत-लॉग की गणना करना जितना कठिन है।


== यह भी देखें ==
== यह भी देखें ==
Line 143: Line 136:
#[http://research.microsoft.com/en-us/um/people/klauter/CISS_06.pdf Signatures for Network Coding(presentation) CISS 2006, Princeton]
#[http://research.microsoft.com/en-us/um/people/klauter/CISS_06.pdf Signatures for Network Coding(presentation) CISS 2006, Princeton]
#[https://web.archive.org/web/20110606191907/http://www.cse.buffalo.edu/~atri/courses/coding-theory/fall07.html University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra]
#[https://web.archive.org/web/20110606191907/http://www.cse.buffalo.edu/~atri/courses/coding-theory/fall07.html University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra]
[[Category: परिमित क्षेत्र]] [[Category: कोडिंग सिद्धांत]] [[Category: सूचना सिद्धांत]] [[Category: त्रुटि का पता लगाना और सुधार]]


 
[[Category:CS1 English-language sources (en)]]
 
[[Category:CS1 errors]]
[[Category: Machine Translated Page]]
[[Category:Created On 11/05/2023]]
[[Category:Created On 11/05/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:कोडिंग सिद्धांत]]
[[Category:त्रुटि का पता लगाना और सुधार]]
[[Category:परिमित क्षेत्र]]
[[Category:सूचना सिद्धांत]]

Latest revision as of 17:25, 17 May 2023

नेटवर्क कोडिंग को सूचना संचार को अधिकतम करने वाले नेटवर्क में बैंडविड्थ (कंप्यूटिंग) का अधिकतम उपयोग करने के लिए दिखाया गया है, लेकिन नेटवर्क में विद्वेषपूर्ण (मेलिसियस) नोड्स द्वारा अतिक्रमण (पॉलुशन) के आक्षेपों के लिए योजना बहुत स्वाभाविक रूप से दुर्बल है। गारवेज अंतःक्षेपी एक नोड कई अभिग्राही को शीघ्रता से प्रभावित कर सकता है। नेटवर्क पैकेट का अतिक्रमण तेजी से प्रसारित होता है क्योंकि (एक भी) उपयुक्त नोड का आउटपुट अनुपयोगी हो जाता है यदि इनकमिंग पैकेटों में से कम से कम एक विकृत होता है।

आक्षेपक आसानी से एक पैकेट को विकृत कर सकता है, तथापि वह संकेत या हैश फलन के अंतर्गत संघट्टन उत्पन्न करके एन्क्रिप्ट किया गया हो। यह एक आक्षेपक को पैकेट तक अभिगम्य और उन्हें विकृत करने की क्षमता देगा। डेनिस चार्ल्स, कमल जैन और क्रिस्टिन लॉटर ने अतिक्रमण आक्षेपों को रोकने के लिए नेटवर्क कोडिंग के साथ उपयोग के लिए एक नई समरूपी एन्क्रिप्शन संकेत योजना तैयार की।[1]

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

नेटवर्क कोडिंग

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

जहाँ प्राप्त होता है। हम मानते हैं कि स्रोत में इनपुट कोर हैं जो वेक्टर का अनुसरण करता है। प्रेरण द्वारा, एक यह है कि वेक्टर किसी भी कोर पर एक रैखिक संयोजन और में एक वेक्टर है। k-आयामी वेक्टर वेक्टर का केवल पहला k निर्देशांक है। हम उस आव्यूह (गणित) को कहते हैं जिसके पद वेक्टर होते हैं, जहाँ एक शीर्ष के लिए प्रवेशी कोर हैं, जिसके लिए सार्वभौमिक एन्कोडिंग आव्यूह और इसे से निरूपित करें। व्यवहार में एन्कोडिंग वेक्टर यादृच्छिक रूप से चयन किए जाते हैं इसलिए आव्यूह उच्च प्रायिकता के साथ परिवर्तनीय होते है। इस प्रकार, कोई भी अभिग्राही प्राप्त करने पर हल करके खोज सकता है।

जहां वेक्टर के पहले k निर्देशांक को हटाकर बनाए गए वेक्टर हैं।

अभिग्राही पर डिकोडिंग

प्रत्येक अभिग्राही (सूचना सिद्धांत) को वेक्टर प्राप्त होता है जो 'के यादृच्छिक रैखिक संयोजन हैं। वास्तव में,

यदि

तब

इस प्रकार हम उच्च प्रायिकता वाले का पता लगाने के लिए रैखिक परिवर्तन को प्रतिवर्त कर सकते हैं।

इतिहास

क्रोह्न, फ्रीडमैन और माज़िएरेस ने 2004 में एक सिद्धांत[2] प्रस्तावित किया था कि यदि हमारे पास एक हैश फलन है जैसे कि:

  • एक संघट्ट प्रतिरोधी है- और को जांच करना कठिन है जैसे कि ;
  • समाकारिता - होती है।

तब सर्वर सुरक्षित रूप से प्रत्येक अभिग्राही को वितरित कर सकता है और जांच कर सकता है कि क्या

हम जांच सकते हैं कि क्या

इस पद्धति के साथ समस्या यह है कि सर्वर को प्रत्येक अभिग्राही को सुरक्षित जानकारी स्थानांतरित करने की आवश्यकता होती है। हैश फलन एक अलग सुरक्षित चैनल के माध्यम से नेटवर्क में सभी नोड्स को प्रेषित करने की आवश्यकता है। और की गणना करना कीमती है और का सुरक्षित संचरण सस्ता भी नहीं है।

समरूप संकेतों के लाभ

  1. अतिक्रमण का पता लगाने के साथ-साथ प्रमाणीकरण स्थापित करता है।
  2. सुरक्षित हैश संकलन वितरित करने की कोई आवश्यकता नहीं है।
  3. सामान्य रूप से छोटी बिट लंबाई पर्याप्त होगी। लंबाई 180 बिट्स के संकेतों में 1024 बिट आरएसए संकेतों जितनी सुरक्षा होती है।
  4. बाद में फ़ाइल प्रसारण के लिए सार्वजनिक सूचना नहीं बदलती है।

संकेत योजना

संकेत की समरूपी संपत्ति नोड्स को संकेत करने वाले प्राधिकरण से संपर्क किए बिना इनकमिंग पैकेटों के किसी भी रैखिक संयोजन पर संकेत करने की स्वीकृति देती है।

सीमित क्षेत्र पर दीर्घवृत्तीय वक्र क्रिप्टोग्राफी (कूटलेखन)

परिमित क्षेत्र पर दीर्घवृत्तीय वक्र क्रिप्टोग्राफी, परिमित क्षेत्रों पर दीर्घवृत्तीय वक्रों की बीजगणितीय संरचना के आधार पर सार्वजनिक-कुंजी क्रिप्टोग्राफ़ी के लिए एक दृष्टिकोण है।

मान लीजिए एक परिमित क्षेत्र हो जैसे कि 2 या 3 की घात नहीं है। तब के ऊपर एक दीर्घवृत्तीय वक्र एक वक्र है जो समीकरण के रूप में दिया गया है

जहाँ जैसे कि

मान लीजिए तब,

पहचान के रूप में O के साथ एक एबेलियन समूह बनाता है। समूह (गणित) संचालन कुशलता से किया जा सकता है।

वील पेयरिंग

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

यदि दीर्घवृत्तीय वक्र है और तब

एक मानचित्र है, जैसे कि:

  1. (द्विरेखीय) .
  2. (गैर-परिवर्तनीय) सभी P के लिए यह दर्शाता है कि होता है।
  3. (प्रत्यावर्ती) .

इसके अतिरिक्त की कुशलता से गणना की जा सकती है।[3]


समरूपी संकेत

मान लीजिए एक अभाज्य संख्या है और एक अभाज्य शक्ति है। मान लीजिए कि आयाम का सदिश स्थान है और दीर्घवृत्तीय वक्र है जैसे कि मे होता है। परिभाषित इस प्रकार है। फलन से को तक एक स्वेच्छ समाकारिता है।

सर्वर मे गुप्त रूप से चयन करता है और आघूर्ण बल का एक बिंदु और के लिए प्रकाशित भी करता है। वेक्टर के संकेत है


ध्यान दे: यह संकेत समरूपी है क्योंकि h की गणना एक समाकारिता है।

संकेत सत्यापन

दिया गया और उसके संकेत , सत्यापित करें कि

सत्यापन महत्वपूर्ण रूप से वेल-पेयरिंग की द्विरेखीयता का उपयोग करता है।

प्रणाली संस्थापन

सर्वर प्रत्येक के लिए की गणना करता है। और को प्रसारित करता है। प्रत्येक कोर पर की गणना करते समयदीर्घवृत्तीय वक्र दीर्घवृ पर की भी गणना करें।

संकेत में निर्देशांक के साथ दीर्घवृत्तीय वक्र पर एक बिंदु है। इस प्रकार हस्ताक्षर का आकार बिट्स है (जो कुछ स्थिर समय बिट्स है, जो और के सापेक्ष आकार पर निर्भर करता है), और यह संचारण शीर्ष है। प्रत्येक शीर्ष पर हस्ताक्षर की गणना के लिए बिट संचालन की आवश्यकता होती है, जहाँ में शीर्ष की घात है। संकेत के सत्यापन के लिए बिट संचालन की आवश्यकता होती है।

सुरक्षा का प्रमाण

आक्षेपक हैश फलन के अंतर्गत संघट्ट उत्पन्न कर सकता है।

यदि दिया गया है कि में प्राप्त और प्रदर्शित करता है। जैसे कि और

प्रस्ताव: दीर्घवृत्तीय वक्रों पर हैश-संघट्टन के लिए क्रम के चक्रीय समूह पर असतत लॉग से बहुपद समय में कमी होती है ।

यदि , तो हमें प्राप्त होता है। इस प्रकार प्राप्त होता है। हम यह दावा करते हैं कि और है। मान लीजिए कि , तो हमारे पास होगा, लेकिन क्रम (अभाज्य) का एक बिंदु है, इस प्रकार होता है। दूसरे शब्दों में में होता है। यह इस धारणा का खंडन करता है कि और भिन्न युग्म हैं। इस प्रकार हमारे पास वह है, जहां व्युत्क्रम को मापांक के रूप में लिया जाता है।

यदि हमारे पास r > 2 है है तो हम दो में से एक कार्य कर सकते हैं या तो हम पहले की तरह और ले सकते हैं और को > 2 के लिए सेट कर सकते हैं (इस स्थिति में प्रमाण स्थिति में कम हो जाता है जब ), या हम और ले सकते हैं। जहाँ से यादृच्छिक रूप से चयन किए जाते हैं। हमें एक अज्ञात में एक समीकरण ( का असतत लघुगणक) मिलता है। यह बहुत संभव है कि जो समीकरण हमें प्राप्त होता है उसमें अज्ञात सम्मिलित न हो। हालाँकि, यह बहुत कम प्रायिकता के साथ होता है जैसा कि हम आगे तर्क देते हैं। मान लीजिए हैश-संघट्टन के लिए एल्गोरिदम ने हमें वह दिया है

फिर जब तक हम Q के असतत लॉग के लिए हल कर सकते हैं। लेकिन हैश-संघट्ट के लिए ओरेकल के लिए अज्ञात हैं और इसलिए हम उस क्रम को बदल सकते हैं जिसमें यह प्रक्रिया होती है। दूसरे शब्दों में, दिया हुआ है कि , के लिए, सभी शून्य नहीं है, इसकी क्या प्रायिकता है कि हमने जो चयन किया है वह को संतुष्ट करता है। यह स्पष्ट है कि बाद वाली प्रायिकता होती है। इस प्रकार उच्च प्रायिकता के साथ हम के असतत लॉग के लिए हल कर सकते हैं।

हमने दिखाया है कि इस योजना में हैश संघट्टन उत्पन्न करना कठिन है। दूसरा तरीका जिसके द्वारा विपक्षी हमारे प्रणाली को वह एक फोर्जन संकेत विफल कर सकता है। संकेत के लिए यह योजना अनिवार्य रूप से बोन-लिन-शाचम संकेत योजना का समग्र संकेत संस्करण है।[4] यहाँ यह दिखाया गया है कि एक संकेत बनाना कम से कम उतना ही कठिन है जितना कि दीर्घवृत्तीय वक्र डिफी-हेलमैन समस्या को हल करना। दीर्घवृत्तीय वक्रों पर इस समस्या को हल करने का एकमात्र ज्ञात तरीका असतत-लॉग की गणना करना है। इस प्रकार एक संकेत बनाना कम से कम उतना ही कठिन है जितना कि दीर्घवृत्तीय वक्रों पर कम्प्यूटेशनल सह-डिफी-हेलमैन को हल करना और संभव्यता असतत-लॉग की गणना करना जितना कठिन है।

यह भी देखें

संदर्भ

  1. "नेटवर्क कोडिंग के लिए हस्ताक्षर". 2006. CiteSeerX 10.1.1.60.4738. Archived from the original on 2021-11-20. {{cite journal}}: Cite journal requires |journal= (help)
  2. Krohn, Maxwell N.; Freedman, Michael J; Mazières, David (2004). "कुशल सामग्री वितरण के लिए रेटलेस इरेज़र कोड का ऑन-द-फ़्लाई सत्यापन" (PDF). IEEE Symposium on Security and Privacy, 2004. Proceedings. 2004 (in English). Berkeley, California, USA: 226–240. doi:10.1109/SECPRI.2004.1301326. ISBN 0-7695-2136-3. ISSN 1081-6011. S2CID 6976686. Retrieved 17 November 2022.
  3. Eisentraeger, Kirsten; Lauter, Kristin; Montgomery, Peter L. (2004). "अण्डाकार और हाइपरेलिप्टिक वक्रों के लिए बेहतर वेइल और टेट पेयरिंग": 169–183. arXiv:math/0311391. Bibcode:2003math.....11391E. CiteSeerX 10.1.1.88.8848. {{cite journal}}: Cite journal requires |journal= (help)
  4. Boneh, Dan; Lynn, Ben; Shacham, Hovav (2001). "वील पेयरिंग से लघु हस्ताक्षर" (PDF). Advances in Cryptology — ASIACRYPT 2001. Lecture Notes in Computer Science (in English). 2248: 514–532. doi:10.1007/3-540-45682-1_30. ISBN 978-3-540-45682-7. Retrieved 17 November 2022.


बाहरी संबंध

  1. Comprehensive View of a Live Network Coding P2P System
  2. Signatures for Network Coding(presentation) CISS 2006, Princeton
  3. University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra