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

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

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

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

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

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

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

प्रत्येक अभिग्राही (सूचना सिद्धांत) $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