Content deleted Content added
→History: correcting two bizarre misuses of TeX |
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
| (20 intermediate revisions by 12 users not shown) | |||
Line 1:
[[Network coding]] has been shown to optimally use [[Bandwidth (computing)|bandwidth]] in a network, maximizing information flow but the scheme is very inherently vulnerable to pollution attacks by malicious nodes in the network. A node injecting garbage can quickly affect many receivers. The pollution of [[network packet]]s spreads quickly since the output of (even an) honest node is corrupted if at least one of the incoming packets is corrupted.
An attacker can easily corrupt a packet even if it is encrypted by either forging the signature or by producing a collision under the [[hash function]]. This will give an attacker access to the packets and the ability to corrupt them. Denis Charles, Kamal Jain and Kristin Lauter designed a new [[homomorphic encryption]] signature scheme for use with network coding to prevent pollution attacks.<ref> The homomorphic property of the signatures allows nodes to sign any linear combination of the incoming packets without contacting the signing authority. In this scheme it is computationally infeasible for a node to sign a linear combination of the packets without disclosing what [[linear combination]] was used in the generation of the packet. Furthermore, we can prove that the signature scheme is secure under well known [[Cryptography|cryptographic]] assumptions of the hardness of the [[discrete logarithm]] problem and the computational [[Elliptic curve Diffie–Hellman]]. ==Network coding==
Line 6 ⟶ 10:
: <math>y(e) = \sum_{f:\mathrm{out}(f)=v}(m_e(f)y(f))</math>
where <math>m_e(f) \in \mathbb{F}_p</math>. We consider the source as having <math>k</math> input edges carrying the <math>k</math> vectors <math>w_i</math>. By [[Mathematical induction|induction]], one has that the vector <math>y(e)</math> on any edge is a linear combination <math>y(e) = \sum_{1 \le i \le k}(g_i(e)v_i)</math> and is a vector in <math>V</math> . The k-dimensional vector <math>g(e) = (g_1(e), \ldots , g_k(e))</math> is simply the first ''k'' coordinates of the vector <math>y(e)</math>. We call the [[Matrix (mathematics)|matrix]] whose rows are the vectors <math>g(e_1), \ldots , g(e_k)</math>, where <math>e_i</math> are the incoming edges for a vertex <math>t \in T</math>, the global encoding matrix for <math>t</math> and denote it as <math>G_t</math>. In practice the encoding vectors are chosen at random so the matrix <math>G_t</math> is invertible with high probability. Thus, any receiver, on receiving <math>y_1, \ldots , y_k</math> can find <math>w_1,\ldots ,w_k</math> by solving
: <math>\begin{bmatrix} y'\\ y_2' \\
where the <math>y_i'</math> are the vectors formed by removing the first <math>k</math> coordinates of the vector <math>y_i</math>.
Line 25 ⟶ 29:
==History==
Krohn, Freedman and Mazieres proposed a theory<ref>
<math>H : V \longrightarrow G</math> such that:
* <math>H</math> is [[Collision resistance|collision resistant]] – it is hard to find <math>x</math> and <math>y</math> such that <math>H(x) = H(y)</math>;
Line 77 ⟶ 81:
#(Alternating) <math>e_m(P, P) = 1</math>.
Also, <math>e_m</math> can be computed efficiently.<ref>{{Cite journal |citeseerx = 10.1.1.88.8848|title = Improved Weil and Tate pairings for elliptic and hyperelliptic curves|url = https://archive.org/details/arxiv-math0311391|pages = 169–183|year = 2004|bibcode = 2003math.....11391E|last1 = Eisentraeger|first1 = Kirsten|last2 = Lauter|first2 = Kristin|last3 = Montgomery|first3 = Peter L.|arxiv = math/0311391}}</ref>
===Homomorphic signatures===
Line 97 ⟶ 101:
: <math>
\begin{align}
e_p(\sigma,Q) & = e_p \left(\sum_{1 \leq i \leq D}
& = \prod_i e_p(u_i s_i P_i,Q) \\
& = \prod_i e_p(u_i P_i, s_iQ)
Line 108 ⟶ 112:
The server computes <math>\sigma(v_i)</math> for each <math>1 \leq i \leq k</math>. Transmits <math>v_i, \sigma(v_i)</math>.
At each edge <math>e</math> while computing
<math>y(e) = \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)y(f))</math>
also compute
<math>\sigma(y(e)) = \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)\sigma(y(f)))</math>
on the elliptic curve <math>E</math>.
Line 137 ⟶ 141:
Then as long as <math>\sum_{2 \leq i \leq r} b_ir_i \not\equiv 0 \bmod p</math>, we can solve for the discrete log of Q. But the <math>r_i</math>’s are unknown to the oracle for Hash-Collision and so we can interchange the order in which this process occurs. In other words, given <math>b_i</math>, for <math>2 \leq i \leq r</math>, not all zero, what is the probability that the <math>r_i</math>’s we chose satisfies <math>\sum_{2 \leq i \leq r} (b_ir_i) = 0</math>? It is clear that the latter probability is <math>1 \over p</math> . Thus with high probability we can solve for the discrete log of <math>Q</math>.
We have shown that producing hash collisions in this scheme is difficult. The other method by which an adversary can foil our system is by forging a signature. This scheme for the signature is essentially the Aggregate Signature version of the Boneh-Lynn-Shacham signature scheme.<ref>
==See also==
*[[Network coding]]
*[[Homomorphic encryption]]
*[[Elliptic
*[[Weil pairing]]
*[[Elliptic
*[[Elliptic
*[[Digital Signature Algorithm]]
Line 154 ⟶ 158:
#[http://research.microsoft.com/pubs/69452/imc06.pdf Comprehensive View of a Live Network Coding P2P System]
#[http://research.microsoft.com/en-us/um/people/klauter/CISS_06.pdf Signatures for Network Coding(presentation) CISS 2006, Princeton]
#[https://web.archive.org/web/20110606191907/http://www.cse.buffalo.edu/~atri/courses/coding-theory/fall07.html University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra]
[[Category:Finite fields]]
| |||