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

From Vigyanwiki
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>


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


== नेटवर्क कोडिंग ==
== नेटवर्क कोडिंग ==
मान लीजिए <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 निर्देशांक को हटाकर बनाए गए वेक्टर हैं।


== रिसीवर पर डिकोडिंग '''edit''' ==
== अभिग्राही पर डिकोडिंग ==
प्रत्येक [[रिसीवर (सूचना सिद्धांत)]], <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>'के यादृच्छिक रैखिक संयोजन हैं। वास्तव में,  
वास्तव में, अगर
 
यदि


: <math>y_i = (\alpha_{i_1}, \ldots , \alpha_{i_k}, a_{i_1}, \ldots , a_{i_d})</math>
: <math>y_i = (\alpha_{i_1}, \ldots , \alpha_{i_k}, a_{i_1}, \ldots , a_{i_d})</math>
Line 22: 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> का पता लगाने के लिए रैखिक परिवर्तन को प्रतिवर्त कर सकते हैं।


== इतिहास ==
== इतिहास ==
क्रोहन, फ्रीडमैन और माजिएरेस ने एक सिद्धांत प्रस्तावित किया<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> 2004 में कि अगर हमारे पास हैश फ़ंक्शन है
क्रोह्न, फ्रीडमैन और माज़िएरेस ने 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 : 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 36: Line 36:


: <math>H(y) =    \sum_{1 \leq i\leq k} (\alpha_iH(v_i))</math>
: <math>H(y) =    \sum_{1 \leq i\leq k} (\alpha_iH(v_i))</math>
इस पद्धति के साथ समस्या यह है कि सर्वर को प्रत्येक रिसीवर को सुरक्षित जानकारी स्थानांतरित करने की आवश्यकता होती है। हैश कार्य करता है <math>H</math> एक अलग सुरक्षित चैनल के माध्यम से नेटवर्क में सभी नोड्स को प्रेषित करने की आवश्यकता है।<math>H</math> के संचरण की गणना और सुरक्षित करना महंगा है <math>H</math> किफायती भी नहीं है।
इस पद्धति के साथ समस्या यह है कि सर्वर को प्रत्येक अभिग्राही को सुरक्षित जानकारी स्थानांतरित करने की आवश्यकता होती है। हैश फलन <math>H</math> एक अलग सुरक्षित चैनल के माध्यम से नेटवर्क में सभी नोड्स को प्रेषित करने की आवश्यकता है। और <math>H</math> की गणना करना कीमती है और <math>H</math> का सुरक्षित संचरण सस्ता भी नहीं है।


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


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


=== एक सीमित क्षेत्र === पर दीर्घवृत्ताकार [[सार्वजनिक कुंजी क्रिप्टोग्राफी]]
==== सीमित क्षेत्र पर दीर्घवृत्तीय वक्र [[सार्वजनिक कुंजी क्रिप्टोग्राफी|क्रिप्टोग्राफी (कूटलेखन)]] ====
[[परिमित क्षेत्र]] पर [[[[अण्डाकार वक्र|दीर्घवृत्ताकार वक्र]] क्रिप्टोग्राफी]], परिमित क्षेत्रों पर दीर्घवृत्ताकार वक्रों की बीजगणितीय संरचना के आधार पर सार्वजनिक-कुंजी क्रिप्टोग्राफ़ी के लिए एक दृष्टिकोण है।
[[परिमित क्षेत्र]] पर [[अण्डाकार वक्र|दीर्घवृत्तीय वक्र]] क्रिप्टोग्राफी, परिमित क्षेत्रों पर दीर्घवृत्तीय वक्रों की बीजगणितीय संरचना के आधार पर सार्वजनिक-कुंजी क्रिप्टोग्राफ़ी के लिए एक दृष्टिकोण है।


मान लीजिए <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>
मान लीजिए <math>K \supseteq \mathbb{F}_q</math>, तब,
 
मान लीजिए <math>K \supseteq \mathbb{F}_q</math> तब,


: <math>E(K) = \{(x, y) | y^2 = x^3 + ax + b\} \bigcup  \{O\}</math>
: <math>E(K) = \{(x, y) | y^2 = x^3 + ax + b\} \bigcup  \{O\}</math>
पहचान के रूप में O के साथ एक [[एबेलियन समूह]] बनाता है। [[समूह (गणित)]] कुशलता से किया जा सकता है।
पहचान के रूप में O के साथ एक [[एबेलियन समूह]] बनाता है। [[समूह (गणित)]] संचालन कुशलता से किया जा सकता है।


=== [[ वील पेयरिंग ]] ===
=== [[ वील पेयरिंग ]] ===
वेइल पेयरिंग एक [[अण्डाकार वक्र|दीर्घवृत्ताकार वक्र]] पर कार्यों के माध्यम से एकता की जड़ों का निर्माण है <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</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[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>.


भी, <math>e_m</math> कुशलता से गणना की जा सकती है।<ref>{{Cite journal |citeseerx = 10.1.1.88.8848|title = अण्डाकार और हाइपरेलिप्टिक वक्रों के लिए बेहतर वेइल और टेट पेयरिंग|url = https://archive.org/details/arxiv-math0311391|pages = 169–183|year = 2004|bibcode = 2003math.....11391E|last1 = Eisentraeger|first1 = Kirsten|last2 = Lauter|first2 = Kristin|last3 = Montgomery|first3 = Peter L.|arxiv = math/0311391}}</ref>
इसके अतिरिक्त <math>e_m</math> की कुशलता से गणना की जा सकती है।<ref>{{Cite journal |citeseerx = 10.1.1.88.8848|title = अण्डाकार और हाइपरेलिप्टिक वक्रों के लिए बेहतर वेइल और टेट पेयरिंग|url = https://archive.org/details/arxiv-math0311391|pages = 169–183|year = 2004|bibcode = 2003math.....11391E|last1 = Eisentraeger|first1 = Kirsten|last2 = Lauter|first2 = Kristin|last3 = Montgomery|first3 = Peter L.|arxiv = math/0311391}}</ref>




=== समरूपी संकेत ===
=== समरूपी संकेत ===


मान लीजिए <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>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>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>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>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 105: Line 101:
गणना भी करें
गणना भी करें
<math>\sigma(y(e)) =  \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)\sigma(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>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> बिट संचालन।


== सुरक्षा का प्रमाण ==
== सुरक्षा का प्रमाण ==
Line 113: Line 109:
आक्षेपक हैश फ़ंक्शन के अंतर्गत टक्कर उत्पन्न कर सकता है।
आक्षेपक हैश फ़ंक्शन के अंतर्गत टक्कर उत्पन्न कर सकता है।


अगर दिया <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 = (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 \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> यहाँ यह दिखाया गया है कि एक संकेत बनाना कम से कम उतना ही कठिन है जितना कि दीर्घवृत्तीय वक्र डिफी-हेलमैन समस्या को हल करना। दीर्घवृत्तीय वक्रों पर इस समस्या को हल करने का एकमात्र ज्ञात तरीका असतत-लॉग की गणना करना है। इस प्रकार एक संकेत बनाना कम से कम उतना ही कठिन है जितना कि दीर्घवृत्तीय वक्रों पर कम्प्यूटेशनल सह-डिफी-हेलमैन को हल करना और शायद असतत-लॉग की गणना करना जितना कठिन है।


== यह भी देखें ==
== यह भी देखें ==
* नेटवर्क कोडिंग
* नेटवर्क कोडिंग
* समरूपी एन्क्रिप्शन
* समरूपी एन्क्रिप्शन
* [[अण्डाकार-वक्र क्रिप्टोग्राफी|दीर्घवृत्ताकार-वक्र क्रिप्टोग्राफी]]
* [[अण्डाकार-वक्र क्रिप्टोग्राफी|दीर्घवृत्तीय-वक्र क्रिप्टोग्राफी]]
*वील पेयरिंग
*वील पेयरिंग
*दीर्घवृत्ताकार-वक्र डिफी-हेलमैन
*दीर्घवृत्तीय-वक्र डिफी-हेलमैन
*[[अण्डाकार वक्र डिजिटल हस्ताक्षर एल्गोरिथ्म|दीर्घवृत्ताकार वक्र डिजिटल संकेत एल्गोरिथ्म]]
*[[अण्डाकार वक्र डिजिटल हस्ताक्षर एल्गोरिथ्म|दीर्घवृत्तीय वक्र डिजिटल संकेत एल्गोरिथ्म]]
* [[डिजिटल हस्ताक्षर एल्गोरिथम|डिजिटल संकेत एल्गोरिथम]]
* [[डिजिटल हस्ताक्षर एल्गोरिथम|डिजिटल संकेत एल्गोरिथम]]



Revision as of 09:10, 14 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