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

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

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

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

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

होने देना $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}}$ है $j$-वेक्टर का समन्वय $w_{i}$. वहाँ हैं $(i-1)$ पहले '1' के प्रकट होने से पहले शून्य $v_{i}$. कोई सामान्यता के नुकसान के बिना मान सकता है कि वैक्टर $v_{i}$ रैखिक स्वतंत्रता हैं। हम रैखिक उपसमष्टि को निरूपित करते हैं (का $\mathbb {F} _{p}^{k+d}$ ) द्वारा इन वैक्टरों द्वारा फैलाया गया $V$ . प्रत्येक निवर्तमान किनारा $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$ . के-आयामी वेक्टर $g(e)=(g_{1}(e),\ldots ,g_{k}(e))$ सदिश का केवल पहला k निर्देशांक है $y(e)$. हम उस मैट्रिक्स (गणित) को कहते हैं जिसकी पंक्तियाँ सदिश होती हैं $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}'$ पहले को हटाकर बनने वाले वैक्टर हैं $k$ वेक्टर के निर्देशांक $y_{i}$.

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

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