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

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

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

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

होने देना $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