A node injecting garbage can quickly affect many receivers.
The pollution of 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 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.
[1] 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 cryptographic assumptions of the hardness of the discrete logarithm problem and the computational Elliptic curve Diffie–Hellman.
is a set, whose elements are called vertices or nodes, and
is a set of ordered pairs of vertices, called arcs, directed edges, or arrows.
is a prime, and views the data to be transmitted as a bunch of vectors
In practice the encoding vectors are chosen at random so the matrix
In fact, if then Thus we can invert the linear transformation to find the
Krohn, Freedman and Mazieres proposed a theory[2] in 2004 that if we have a hash function
needs to be transmitted to all the nodes in the network through a separate secure channel.
Elliptic curve cryptography over a finite field is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields.
Weil pairing is a construction of roots of unity by means of functions on an elliptic curve
, in such a way as to constitute a pairing (bilinear form, though with multiplicative notation) on the torsion subgroup of
is an integer, relatively prime to the characteristic of the field
, verify that The verification crucially uses the bilinearity of the Weil-pairing.
The signature is a point on the elliptic curve with coordinates in
Attacker can produce a collision under the hash function.
and Proposition: There is a polynomial time reduction from discrete log on the cyclic group of order
Suppose the algorithm for Hash-Collision gave us that Then as long as
’s are unknown to the oracle for Hash-Collision and so we can interchange the order in which this process occurs.
Thus with high probability we can solve for the discrete log of
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.
[4] Here it is shown that forging a signature is at least as hard as solving the elliptic curve Diffie–Hellman problem.
The only known way to solve this problem on elliptic curves is via computing discrete-logs.