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

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

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

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

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

मान लीजिए $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