|
[[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 [[Networknetwork 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 [[Hashhash 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 [[Homomorphichomomorphic encryption]] signature scheme for use with network coding to prevent pollution attacks<ref>http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.4738&rep=rep1&type=pdf</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 [[Linearlinear combination]] was used in the generation of the packet. Furthermore, we can prove that the signature scheme is secure under well known [http://en.wikipedia.org/wiki/[Cryptography |cryptographic]] assumptions of the hardness of the [[Discretediscrete logarithm]] problem and the computational [[Elliptic_curve_Diffie-HellmanElliptic curve Diffie–Hellman]].
==Network coding==
Let <math>G = (V, E)</math> be a [[Directeddirected graph]] where <math>V</math> is a set, whose elements are called vertices or [http://en.wikipedia.org/wiki/Node_%28networking%29[Node nodes(networking)|node]]s, and <math>E</math> is a set of [[Orderedordered pair]]s of vertices, called arcs, directed edges, or arrows. A source <math>s \in V</math> wants to transmit a file <math>D</math> to a set <math>T \subseteq V</math> of the vertices. One chooses a [[Vectorvector space]] <math>W/\mathbb{F}_p</math>(say of dimension <math>d</math>), where <math>p</math> is a prime, and views the data to be transmitted as a bunch of vectors <math>w_1 . . . , w_k \in W</math>. The source then creates the augmented vectors <math>v_1, . . . , v_k</math> by setting <math> v_i = (0, . . . , 0, 1, . . . , 0, w_{i_1}, . . . , w{i_d})</math> where <math>w_{i_j}</math> is the <math>j</math>-th coordinate of the vector <math>w_i</math>. There are <math>(i-1)</math> zeros before the first '1' appears in <math>v_i</math>. One can assume without loss of generality that the vectors <math>v_i</math> are [http://en.wikipedia.org/wiki/Linear_independence[Linear independence|linearly independent]]. We denote the [[Linearlinear subspace]] (of <math>\mathbb{F}_p^{k+d}</math> ) spanned by these vectors by <math>V</math> . Each outgoing edge <math>e \in E</math> computes a linear combination, <math>y(e)</math>, of the vectors entering the vertex <math>v = in(e)</math> where the edge originates, that is to say
<math>y(e) = \sum_{f: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 [http://en.wikipedia.org/wiki/Mathematical_induction[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), . . . , g_k(e))</math> is simply the first k-coordinates of the vector <math>y(e)</math>. We call the [http://en.wikipedia.org/wiki/Matrix_%28mathematics%29[Matrix (mathematics)|matrix]] whose rows are the vectors <math>g(e_1), . . . , 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, . . . , y_k</math> can find <math>w_1, . . . ,w_k</math> by solving
<math>\begin{bmatrix} y'\\ y_2' \\. \\. \\. \\ y_k' \end{bmatrix} = G_t \begin{bmatrix} w_1\\ w_2 \\. \\. \\. \\ w_k \end{bmatrix}</math>
==Decoding at the receiver==
Each [http://en.wikipedia.org/wiki/Receiver_%28information_theory%29[Receiver (information theory)|receiver]], <math>t \in T</math>, gets <math>k</math> vectors <math>y_1, . . . , y_k</math> which are random linear combinations of the <math>v_i</math>’s.
In fact, if
<math>y_i = \sum_{1 \le j \le k}(\alpha_{ij}v_j)</math>.
Thus we can invert the linear transformation to find the <math>v_i</math>’s with high [[Probabilityprobability]].
==History==
Krohn, Freedman and Mazieres proposed a theory<ref>http://www.cs.princeton.edu/~mfreed/docs/authcodes-ieee04.pdf</ref> in 2004 that if we have a hash function
<math>H : V \longrightarrow G</math> such that:
* <math>H</math> is [http://en.wikipedia.org/wiki/Collision_resistance[Collision resistance|collision resistant]] – it is hard to find <math>x</math> and <math>y</math> such that <math>H(x)</math> = <math>H(y)</math>;
* <math>H</math> is a [[Homomorphismhomomorphism]] – <math>H(x</math> + <math>y</math>) = <math>H(x)H(y)</math>.
Then server can securely distribute <math>H(v_i)</math> to each receiver, and to check if
The problem with this method is that the server needs to transfer secure information to each of the receivers. The hash functions <math>H</math> needs to be transmitted to all the nodes in the network through a separate secure channel.<math>H</math> is expensive to compute and secure transmission of <math>H</math> is not economical either.
==Advantages of Homomorphichomomorphic Signaturessignatures==
# Establishes authentication in addition to detecting pollution.
# No need for distributing secure hash digests.
===Elliptic curves cryptography over a finite field===
[[Elliptic curve cryptography]] over a finite field is an approach to [[public-key cryptography]] based on the algebraic structure of [[Ellipticelliptic curves]] over [[Finitefinite field]]s.
Let <math>\mathbb{F}_q</math> be a finite field such that <math>q</math> is not a power of 2 or 3. Then an elliptic curve <math>E</math> over <math>\mathbb{F}_q</math> is a curve given by an equation of the form
Let <math>K \supseteq \mathbb{F}_q</math> then,
<math>E(K) = \{(x, y) | y^2 = x^3 + ax + b\} \bigcup \{O\}</math> forms an [[Abelianabelian group]] with O as identity. The [http://en.wikipedia.org/wiki/Group_%28mathematics%29[Group (mathematics)|group operations]] can be performed efficiently.
===Weil pairing===
[[Weil pairing]] is a construction of [[Rootsroots of unity]] by means of functions on an [[Ellipticelliptic curve]] <math>E</math>, in such a way as to constitute a [[Pairingpairing]] ([[Bilinearbilinear form]], though with [[Multiplicativemultiplicative notation]]) on the [[Torsiontorsion subgroup]] of <math>E</math>. Let <math>E/\mathbb{F}_q</math> be an elliptic curve and let <math>\mathbb{\bar{F}}_q</math> be an algebraic closure of <math>\mathbb{F}_q</math>. If <math>m</math> is an integer, relatively prime to the characteristic of the field <math>\mathbb{F}_q</math>, then the group of <math>m</math>-torsion points,
<math>E[m] = {P \in E(\mathbb{\bar {F}}_q) : mP = O}</math>.
| 