Content deleted Content added
clean-up of titles per WP:MOS |
|||
Line 1:
[
▲[http://en.wikipedia.org/wiki/Network_coding Network Coding] has been shown to optimally use [http://en.wikipedia.org/wiki/Bandwidth_%28computing%29 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 [http://en.wikipedia.org/wiki/Network_packet network packets] 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 [http://en.wikipedia.org/wiki/Hash_function 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 [http://en.wikipedia.org/wiki/Homomorphic_encryption Homomorphic] 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 [http://en.wikipedia.org/wiki/Linear_combination linear 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 [http://en.wikipedia.org/wiki/Discrete_logarithm#Cryptography Discrete-Log problem] and the computational [http://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93Hellman Diffie-Hellman problem on elliptic curves].
▲==Network Coding==
Let <math>G = (V, E)</math> be a [http://en.wikipedia.org/wiki/Directed_graph directed graph] where <math>V</math> is a set, whose elements are called vertices or [http://en.wikipedia.org/wiki/Node_%28networking%29 nodes], and <math>E</math> is a set of [http://en.wikipedia.org/wiki/Ordered_pair ordered pairs] 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 [http://en.wikipedia.org/wiki/Vector_space vector 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 linearly independent]. We denote the [http://en.wikipedia.org/wiki/Linear_subspace linear 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
Line 45 ⟶ 44:
# Public information does not change for subsequent file transmission.
==Signature
The homomorphic property of the signatures allows nodes to sign any linear comination of the incoming packets without contacting the signing authority.
===Elliptic curves
[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography Elliptic curves Cryptography over a finite field] is an approach to [http://en.wikipedia.org/wiki/Public-key_cryptography public-key cryptography] based on the algebraic structure of [http://en.wikipedia.org/wiki/Elliptic_curve elliptic curves] over [http://en.wikipedia.org/wiki/Finite_field finite fields].
Line 59 ⟶ 58:
<math>E(K) = \{(x, y) | y^2 = x^3 + ax + b\} \bigcup \{O\}</math> forms an [http://en.wikipedia.org/wiki/Abelian_group abelian group] with O as identity. The [http://en.wikipedia.org/wiki/Group_%28mathematics%29 group operations] can be performed efficiently.
===Weil
[http://en.wikipedia.org/wiki/Weil_pairing Weil Pairing] is a construction of [http://en.wikipedia.org/wiki/Roots_of_unity roots of unity] by means of functions on an [http://en.wikipedia.org/wiki/Elliptic_curve elliptic curve] <math>E</math>, in such a way as to constitute a [http://en.wikipedia.org/wiki/Pairing pairing] ([http://en.wikipedia.org/wiki/Bilinear_form bilinear form], though with [http://en.wikipedia.org/wiki/Multiplicative_notation multiplicative notation]) on the [http://en.wikipedia.org/wiki/Torsion_subgroup torsion 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>.
Line 75 ⟶ 74:
Also, <math>e_m</math> can be computed efficiently<ref>http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBsQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.88.8848%26rep%3Drep1%26type%3Dpdf&rct=j&q=Improved%20Weil%20and%20Tate%20pairings%20for%20elliptic%20and%20hyperelliptic%20curves&ei=Fyi-Te_nMdCitgejkIzGBQ&usg=AFQjCNFTlKZaFlQ_BZyXDh6nKSDpntTTlA&sig2=VDWSZSuKNVeefL0EhmOCqA&cad=rja</ref>.
===Homomorphic
Let <math>p</math> be a prime and <math>q</math> a prime power. Let <math>V/\mathbb{F}_p</math> be a vector space of dimension <math>D</math> and <math>E/\mathbb{F}_q</math> be an elliptic curve such that <math>P_1, . . . , P_D \in E[p]</math>.
Line 87 ⟶ 86:
Note: This signature is homomorphic since the computation of h is a homomorphism.
===Signature
Given <math>v = u_1, . . . , u_D</math> and its signature <math>\sigma</math> verify that
Line 99 ⟶ 98:
The verification cruicially uses the bilinearity of the Weil-pairing.
==System
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
Line 109 ⟶ 108:
The signature is a point on the elliptic curve with coordinates in <math>\mathbb{F}_q</math>. Thus the size of the signature is <math>2 log q</math> bits (which is some constant times <math>log(p)</math> bits, depending on the relative size of <math>p</math> and <math>q</math>), and this is the transmission overhead. The computation of the signature <math>h(e)</math> at each vertex requires <math>O(d_{in} log p log^{1+\epsilon} q)</math> bit operations, where <math>d_{in}</math> is the in-degree of the vertex <math>in(e)</math>. The verification of a signature requires <math>O((d + k) log^{2+\epsilon} q)</math> bit operations.
==Proof of
Attacker can produce a collision under the hash function.
Line 132 ⟶ 131:
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>http://cseweb.ucsd.edu/~hovav/dist/sigs.pdf</ref>. Here it is shown that forging a signature is at least as hard as solving the [http://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93Hellman computational curve Diffie-Hellman problem] on the elliptic curve. The only known way to solve this problem on elliptic curves is via computing discrete-logs. Thus forging a signature is at least as hard as solving the computational co-Diffie-Hellman on elliptic curves and probably as hard as computing discrete-logs.
==See
*[[Network coding]]
*[[Homomorphic Encryption]]
Line 144 ⟶ 143:
{{Reflist}}
==External
#[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]
| |||