Homomorphic signatures for network coding
has been shown to optimally use 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 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 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 was used in the generation of the packet. Furthermore, we can prove that the signature scheme is secure under well known assumptions of the hardness of the problem and the computational .
Contents
Network coding
Let be a where is a set, whose elements are called vertices or , and is a set of of vertices, called arcs, directed edges, or arrows. A source wants to transmit a file to a set of the vertices. One chooses a (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 . We denote the (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 , 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 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 , , 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 .
History
Krohn, Freedman and Mazieres proposed a theory in 2004 that if we have a hash function such that:
- is – it is hard to find and such that ;
- is a – .
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
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
over a finite field is an approach to based on the algebraic structure of over .
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 with O as identity. The can be performed efficiently.
Weil pairing
is a construction of by means of functions on an , in such a way as to constitute a (, though with ) on the 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:
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 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 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.
Twitter
Telegram
