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.
Contents
Network coding
Let
where
where the
Decoding at the receiver
Each receiver,
then
Thus we can invert the linear transformation to find the
History
Krohn, Freedman and Mazieres proposed a theory in 2004 that if we have a hash function
Then server can securely distribute
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
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
where
Let
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
If
There is a map
- (Bilinear)
e m ( P + R , Q ) = e m ( P , Q ) e m ( R , Q ) and e m ( P , Q + R ) = e m ( P , Q ) e m ( P , R ) . - (Non-degenerate)
e m ( P , Q ) = 1 for all P implies thatQ = O . - (Alternating)
e m ( P , P ) = 1 .
Also,
Homomorphic signatures
Let
The server chooses
Signature verification
Given
The verification crucially uses the bilinearity of the Weil-pairing.
System setup
The server computes
The signature is a point on the elliptic curve with coordinates in
Proof of security
Attacker can produce a collision under the hash function.
If given
such that
Proposition: There is a polynomial time reduction from discrete log on the cyclic group of order
If
If we have r > 2 then we can do one of two things. Either we can take
Then as long as
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.