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

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

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

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

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

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

$y(e)=\sum _{f:\mathrm {out} (f)=v}(m_{e}(f)y(f))$

जहाँ $m_{e}(f)\in \mathbb {F} _{p}$ प्राप्त होता है। हम मानते हैं कि स्रोत में $k$ इनपुट कोर हैं जो $k$ सदिश $w_{i}$ का अनुसरण करता है। प्रेरण द्वारा, एक यह है कि सदिश $y(e)$ किसी भी कोर पर एक रैखिक संयोजन $y(e)=\sum _{1\leq i\leq k}(g_{i}(e)v_{i})$ और $V$ में एक सदिश है। k-आयामी सदिश $g(e)=(g_{1}(e),\ldots ,g_{k}(e))$ सदिश $y(e)$ का केवल पहला k निर्देशांक है। हम उस आव्यूह (गणित) को कहते हैं जिसके पद $g(e_{1}),\ldots ,g(e_{k})$ सदिश होते हैं, जहाँ $e_{i}$ एक शीर्ष $t\in T$ के लिए आने वाले किनारे हैं, जिसके लिए सार्वभौमिक एन्कोडिंग आव्यूह $t$ और इसे $G_{t}$से निरूपित करें। व्यवहार में एन्कोडिंग सदिश यादृच्छिक रूप से चयन किए जाते हैं इसलिए आव्यूह $G_{t}$ उच्च प्रायिकता के साथ परिवर्तनीय होते है। इस प्रकार, कोई भी प्राप्तकर्ता $y_{1},\ldots ,y_{k}$ प्राप्त करने पर $w_{1},\ldots ,w_{k}$ हल करके खोज सकता है।

${\begin{bmatrix}y'\\y_{2}'\\\vdots \\y_{k}'\end{bmatrix}}=G_{t}{\begin{bmatrix}w_{1}\\w_{2}\\\vdots \\w_{k}\end{bmatrix}}$

जहां $y_{i}'$ सदिश $y_{i}$ के पहले k निर्देशांक को हटाकर बनाए गए सदिश हैं।

रिसीवर पर डिकोडिंग edit

प्रत्येक रिसीवर (सूचना सिद्धांत), $t\in T$, हो जाता है $k$ सदिश $y_{1},\ldots ,y_{k}$ जो के यादृच्छिक रैखिक संयोजन हैं $v_{i}$'एस। वास्तव में, अगर

$y_{i}=(\alpha _{i_{1}},\ldots ,\alpha _{i_{k}},a_{i_{1}},\ldots ,a_{i_{d}})$

तब

$y_{i}=\sum _{1\leq j\leq k}(\alpha _{ij}v_{j}).$

इस प्रकार हम खोजने के लिए रैखिक परिवर्तन को उल्टा कर सकते हैं $v_{i}$उच्च संभावना के साथ है।

इतिहास

क्रोहन, फ्रीडमैन और माजिएरेस ने एक सिद्धांत प्रस्तावित किया 2004 में कि अगर हमारे पास हैश फ़ंक्शन है

$H:V\longrightarrow G$ ऐसा है कि:

• $H$ टक्कर प्रतिरोध है - इसे खोजना कठिन है $x$ और $y$ ऐसा है कि $H(x)=H(y)$;
• $H$ एक समरूपता है - $H(x+y)=H(x)+H(y)$.

तब सर्वर सुरक्षित रूप से वितरित कर सकता है $H(v_{i})$ प्रत्येक रिसीवर के लिए, और यह जांचने के लिए कि क्या

$y=\sum _{1\leq i\leq k}(\alpha _{i}v_{i})$

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

$H(y)=\sum _{1\leq i\leq k}(\alpha _{i}H(v_{i}))$

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

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

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

संकेत योजना

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

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

मान लीजिए $\mathbb {F} _{q}$ एक परिमित क्षेत्र हो जैसे कि $q$ 2 या 3 की शक्ति नहीं है। फिर एक अंडाकार वक्र $E$ ऊपर $\mathbb {F} _{q}$ रूप के समीकरण द्वारा दिया गया वक्र है

$y^{2}=x^{3}+ax+b,\,$

कहाँ $a,b\in \mathbb {F} _{q}$ ऐसा है कि $4a^{3}+27b^{2}\not =0$ मान लीजिए $K\supseteq \mathbb {F} _{q}$, तब,

$E(K)=\{(x,y)|y^{2}=x^{3}+ax+b\}\bigcup \{O\}$

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

वील पेयरिंग

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

अगर $E/\mathbb {F} _{q}$ एक दीर्घवृत्ताकार वक्र है और $\gcd(m,q)=1$ तब

$E[m]\cong (\mathbb {Z} /m\mathbb {Z} )*(\mathbb {Z} /m\mathbb {Z} )$

एक नक्शा है $e_{m}:E[m]*E[m]\rightarrow \mu _{m}(\mathbb {F} _{q})$ ऐसा है कि:

1. (बिलिनियर) $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)$.
2. (गैर पतित) $e_{m}(P,Q)=1$ सभी के लिए P का तात्पर्य है $Q=O$.
3. (वैकल्पिक) $e_{m}(P,P)=1$.

भी, $e_{m}$ कुशलता से गणना की जा सकती है।

समरूपी संकेत

मान लीजिए $p$ एक प्रधान बनें और $q$ एक प्रमुख शक्ति। मान लीजिए $V/\mathbb {F} _{p}$ आयाम का एक सदिश समष्टि बनें $D$ और $E/\mathbb {F} _{q}$ एक दीर्घवृत्ताकार वक्र हो जैसे कि $P_{1},\ldots ,P_{D}\in E[p]$. परिभाषित करना $h:V\longrightarrow E[p]$ निम्नलिखित नुसार: $h(u_{1},\ldots ,u_{D})=\sum _{1\leq i\leq D}(u_{i}P_{i})$. कार्यक्रम $h$ से एक मनमाना समरूपता है $V$ को $E[p]$.

सर्वर चुनता है $s_{1},\ldots ,s_{D}$ गुप्त रूप से $\mathbb {F} _{p}$ और एक बिंदु प्रकाशित करता है $Q$ पी-मरोड़ का ऐसा है कि $e_{p}(P_{i},Q)\not =1$ और प्रकाशित भी करता है $(P_{i},s_{i}Q)$ के लिए $1\leq i\leq D$. सदिश के संकेत $v=u_{1},\ldots ,u_{D}$ है

$\sigma (v)=\sum _{1\leq i\leq D}(u_{i}s_{i}P_{i})$

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

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

दिया गया $v=u_{1},\ldots ,u_{D}$ और उसके संकेत $\sigma$, सत्यापित करें कि

${\begin{aligned}e_{p}(\sigma ,Q)&=e_{p}\left(\sum _{1\leq i\leq D}(u_{i}s_{i}P_{i}),Q\right)\\&=\prod _{i}e_{p}(u_{i}s_{i}P_{i},Q)\\&=\prod _{i}e_{p}(u_{i}P_{i},s_{i}Q)\end{aligned}}$

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

सिस्टम सेटअप

सर्वर गणना करता है $\sigma (v_{i})$ प्रत्येक के लिए $1\leq i\leq k$. संचारित $v_{i},\sigma (v_{i})$. हर कोर पर $e$ गणना करते समय $y(e)=\sum _{f\in E:\mathrm {out} (f)=\mathrm {in} (e)}(m_{e}(f)y(f))$ गणना भी करें $\sigma (y(e))=\sum _{f\in E:\mathrm {out} (f)=\mathrm {in} (e)}(m_{e}(f)\sigma (y(f)))$ दीर्घवृत्ताकार वक्र पर $E$.

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

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

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

अगर दिया $(P_{1},\ldots ,P_{r})$ में इंगित करता है $E[p]$ पाना $a=(a_{1},\ldots ,a_{r})\in \mathbb {F} _{p}^{r}$ और $b=(b_{1},\ldots ,b_{r})\in \mathbb {F} _{p}^{r}$ ऐसा है कि $a\not =b$ और

$\sum _{1\leq i\leq r}(a_{i}P_{i})=\sum _{1\leq j\leq r}(b_{j}P_{j}).$

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

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

अगर हमारे पास r > 2 है तो हम दो चीजों में से एक कर सकते हैं। या तो हम ले सकते हैं $P_{1}=P$ और $P_{2}=Q$ पहले की तरह और सेट करें $P_{i}=O$ के लिए $i$ > 2 (इस मामले में सबूत उस मामले में कम हो जाता है जब $r=2$), या हम ले सकते हैं $P_{1}=r_{1}P$ और $P_{i}=r_{i}Q$ कहाँ $r_{i}$ से यादृच्छिक रूप से चुने जाते हैं $\mathbb {F} _{p}$. हमें एक अज्ञात में एक समीकरण मिलता है (का असतत लघुगणक $Q$). यह बहुत संभव है कि जो समीकरण हमें प्राप्त होता है उसमें अज्ञात शामिल न हो। हालाँकि, यह बहुत कम संभावना के साथ होता है जैसा कि हम आगे तर्क देते हैं। मान लीजिए हैश-संघट्टन के लिए एल्गोरिदम ने हमें वह दिया है

$ar_{1}P+\sum _{2\leq i\leq r}(b_{i}r_{i}Q)=0.$

फिर जब तक $\sum _{2\leq i\leq r}b_{i}r_{i}\not \equiv 0{\bmod {p}}$, हम Q के असतत लॉग के लिए हल कर सकते हैं। लेकिन $r_{i}$हैश-कोलिज़न के लिए ओरेकल के लिए अज्ञात हैं और इसलिए हम उस क्रम को बदल सकते हैं जिसमें यह प्रक्रिया होती है। दूसरे शब्दों में दिया $b_{i}$, के लिए $2\leq i\leq r$, सभी शून्य नहीं, इसकी क्या प्रायिकता है कि $r_{i}$हमने संतुष्ट चुना है $\sum _{2\leq i\leq r}(b_{i}r_{i})=0$? यह स्पष्ट है कि बाद की संभावना है $1 \over p$ . इस प्रकार उच्च संभावना के साथ हम के असतत लॉग के लिए हल कर सकते हैं $Q$.

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

यह भी देखें

• नेटवर्क कोडिंग
• समरूपी एन्क्रिप्शन
• दीर्घवृत्ताकार-वक्र क्रिप्टोग्राफी
• वील पेयरिंग
• दीर्घवृत्ताकार-वक्र डिफी-हेलमैन
• दीर्घवृत्ताकार वक्र डिजिटल संकेत एल्गोरिथ्म
• डिजिटल संकेत एल्गोरिथम

बाहरी संबंध

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