Homomorphic signatures for network coding
Network coding has been shown to optimally use 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 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. 

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.

Network coding
Let  be a directed graph where  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. A source  wants to transmit a file  to a set  of the vertices. One chooses a vector space (say of dimension ), where  is a prime, and views the data to be transmitted as a bunch of vectors . The source then creates the augmented vectors  by setting  where  is the -th coordinate of the vector . There are  zeros before the first '1' appears in . One can assume without loss of generality that the vectors  are linearly independent. We denote the linear subspace (of  ) spanned by these vectors by  . Each outgoing edge  computes a linear combination, , of the vectors entering the vertex  where the edge originates, that is to say

 

where . We consider the source as having  input edges carrying the  vectors . By induction, one has that the vector  on any edge is a linear combination  and is a vector in  . The k-dimensional vector  is simply the first k coordinates of the vector . We call the matrix whose rows are the vectors , where  are the incoming edges for a vertex , the global encoding matrix for  and denote it as . In practice the encoding vectors are chosen at random so the matrix  is invertible with high probability. Thus, any receiver, on receiving  can find  by solving

  

where the  are the vectors formed by removing the first  coordinates of the vector .

Decoding at the receiver
Each receiver, , gets  vectors  which are random linear combinations of the ’s.
In fact, if

 

then

 

Thus we can invert the linear transformation to find the ’s with high probability.

History
Krohn, Freedman and Mazieres proposed a theory in 2004 that if we have a hash function 
 such that: 
   is collision resistant – it is hard to find  and  such that ;
  is a homomorphism – .

Then server can securely distribute  to each receiver, and to check if

 

we can check whether

 

The problem with this method is that the server needs to transfer secure information to each of the receivers. The hash functions  needs to be transmitted to all the nodes in the network through a separate secure channel. is expensive to compute and secure transmission of  is not economical either.

Advantages of homomorphic signatures
 Establishes authentication in addition to detecting pollution.
 No need for distributing secure hash digests.
 Smaller bit lengths in general will suffice. Signatures of length 180 bits have as much security as 1024 bit RSA signatures.
 Public information does not change for subsequent file transmission.

Signature scheme
The homomorphic property of the signatures allows nodes to sign any linear combination of the incoming packets without contacting the signing authority.

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 elliptic curves over finite fields.

Let  be a finite field such that  is not a power of 2 or 3. Then an elliptic curve  over  is a curve given by an equation of the form
 

where  such that 

Let , then,

 

forms an abelian group with O as identity. The group operations can be performed efficiently.

Weil pairing
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 . Let  be an elliptic curve and let  be an algebraic closure of . If  is an integer, relatively prime to the characteristic of the field , then the group of -torsion points,
.

If  is an elliptic curve and  then

 

There is a map  such that:

(Bilinear) .
(Non-degenerate)  for all P implies that .
(Alternating) .

Also,  can be computed efficiently.

Homomorphic signatures

Let  be a prime and  a prime power. Let  be a vector space of dimension  and  be an elliptic curve such that .
Define  as follows:
.
The function  is an arbitrary homomorphism from  to .

The server chooses  secretly in  and publishes a point  of p-torsion such that  and also publishes   for .
The signature of the vector  is 

Note: This signature is homomorphic since the computation of h is a homomorphism.

Signature verification

Given  and its signature , verify that

 

The verification crucially uses the bilinearity of the Weil-pairing.

System setup
The server computes  for each . Transmits .
At each edge  while computing

also compute

on the elliptic curve .

The signature is a point on the elliptic curve with coordinates in . Thus the size of the signature is  bits (which is some constant times  bits, depending on the relative size of  and ), and this is the transmission overhead. The computation of the signature  at each vertex requires  bit operations, where  is the in-degree of the vertex . The verification of a signature requires  bit operations.

Proof of security

Attacker can produce a collision under the hash function.

If given  points in  find
 and 

such that  and

 

Proposition: There is a polynomial time reduction from discrete log on the cyclic group of order  on elliptic curves to Hash-Collision.

If , then we get . Thus .
We claim that  and . Suppose that , then we would have , but  is a point of order  (a prime) thus . In other words  in . This contradicts the assumption that  and  are distinct pairs in . Thus we have that , where the inverse is taken as modulo .

If we have r > 2 then we can do one of two things. Either we can take  and  as before and set  for  > 2 (in this case the proof reduces to the case when ), or we can take  and  where  are chosen at random from . We get one equation in one unknown (the discrete log of ). It is quite possible that the equation we get does not involve the unknown. However, this happens with very small probability as we argue next. Suppose the algorithm for Hash-Collision gave us that

 

Then as long as , we can solve for the discrete log of Q. But the ’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 , for , not all zero, what is the probability that the ’s we chose satisfies ? It is clear that the latter probability is  . 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. This scheme for the signature is essentially the Aggregate Signature version of the Boneh-Lynn-Shacham signature scheme. 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. 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 also
Network coding
Homomorphic encryption
Elliptic curve cryptography
Weil pairing
Elliptic curve Diffie–Hellman
Elliptic curve DSA
Digital Signature Algorithm

References

External links
Comprehensive View of a Live Network Coding P2P System
Signatures for Network Coding(presentation) CISS 2006, Princeton
University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra

Finite fields
Coding theory
Information theory
Error detection and correction