Homomorphic signatures for network coding

From BitcoinWiki
This is the approved revision of this page, as well as being the most recent.
Jump to: navigation, search

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[edit]

Let G = (V, E) be a directed graph where V is a set, whose elements are called vertices or nodes, and E is a set of ordered pairs of vertices, called arcs, directed edges, or arrows. A source s \in V wants to transmit a file D to a set T \subseteq V of the vertices. One chooses a vector space W/\mathbb{F}_p(say of dimension d), where p is a prime, and views the data to be transmitted as a bunch of vectors w_1 ,\ldots , w_k \in W. The source then creates the augmented vectors v_1,\ldots , v_k by setting  v_i = (0, \ldots , 0, 1, \ldots , 0, w_{i_1}, \ldots , w{i_d}) where w_{i_j} is the j-th coordinate of the vector w_i. There are (i-1) zeros before the first '1' appears in v_i. One can assume without loss of generality that the vectors v_i are linearly independent. We denote the linear subspace (of \mathbb{F}_p^{k+d} ) spanned by these vectors by V . Each outgoing edge e \in E computes a linear combination, y(e), of the vectors entering the vertex v = in(e) where the edge originates, that is to say

y(e) = \sum_{f:\mathrm{out}(f)=v}(m_e(f)y(f))

where m_e(f) \in \mathbb{F}_p. We consider the source as having k input edges carrying the k vectors w_i. By induction, one has that the vector y(e) on any edge is a linear combination y(e) = \sum_{1 \le i \le k}(g_i(e)v_i) and is a vector in V . The k-dimensional vector g(e) = (g_1(e), \ldots , g_k(e)) is simply the first k coordinates of the vector y(e). We call the matrix whose rows are the vectors g(e_1), \ldots , g(e_k), where e_i are the incoming edges for a vertex t \in T, the global encoding matrix for t and denote it as G_t. In practice the encoding vectors are chosen at random so the matrix G_t is invertible with high probability. Thus any receiver, on receiving y_1, \ldots , y_k can find w_1,\ldots ,w_k by solving

\begin{bmatrix} y'\\ y_2' \\ \vdots \\ y_k' \end{bmatrix} = G_t \begin{bmatrix} w_1\\ w_2 \\ \vdots \\ w_k \end{bmatrix}

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

Decoding at the receiver[edit]

Each receiver, t \in T, gets k vectors y_1, \ldots , y_k which are random linear combinations of the v_i’s. In fact, if

y_i = (\alpha_{i_1}, \ldots , \alpha_{i_k}, a_{i_1}, \ldots , a_{i_d})


y_i = \sum_{1 \le j \le k}(\alpha_{ij}v_j).

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


Krohn, Freedman and Mazieres proposed a theory in 2004 that if we have a hash function H : V \longrightarrow G such that:

Then server can securely distribute H(v_i) to each receiver, and to check if

y = \sum_{1 \leq i\leq k} (\alpha_iv_i)

we can check whether

H(y) = \sum_{1 \leq i\leq k} (\alpha_iH(v_i))

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

Advantages of homomorphic signatures[edit]

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

Signature scheme[edit]

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[edit]

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 \mathbb{F}_q be a finite field such that q is not a power of 2 or 3. Then an elliptic curve E over \mathbb{F}_q is a curve given by an equation of the form

 y^2 = x^3 + ax + b, \,

where a, b \in \mathbb{F}_q such that 4a^3 + 27b^2 \not= 0

Let K \supseteq \mathbb{F}_q, then,

E(K) = \{(x, y) | y^2 = x^3 + ax + b\} \bigcup \{O\}

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

Weil pairing[edit]

Weil pairing is a construction of roots of unity by means of functions on an elliptic curve E, in such a way as to constitute a pairing (bilinear form, though with multiplicative notation) on the torsion subgroup of E. Let E/\mathbb{F}_q be an elliptic curve and let \mathbb{\bar{F}}_q be an algebraic closure of \mathbb{F}_q. If m is an integer, relatively prime to the characteristic of the field \mathbb{F}_q, then the group of m-torsion points, E[m] = {P \in E(\mathbb{\bar {F}}_q) : mP = O}.

If E/\mathbb{F}_q is an elliptic curve and \gcd(m, q) = 1 then

E[m] \cong (\mathbb{Z}/m\mathbb{Z}) * (\mathbb{Z}/m\mathbb{Z})

There is a map e_m : E[m] * E[m] \rightarrow \mu_m(\mathbb{F}_q) such that:

  1. (Bilinear) e_m(P + R,Q) = e_m(P,Q)e_m(R,Q)\text{ and }e_m(P,Q + R) = e_m(P,Q)e_m(P, R).
  2. (Non-degenerate) e_m(P,Q) = 1 for all P implies that Q = O.
  3. (Alternating) e_m(P, P) = 1.

Also, e_m can be computed efficiently.

Homomorphic signatures[edit]

Let p be a prime and q a prime power. Let V/\mathbb{F}_p be a vector space of dimension D and E/\mathbb{F}_q be an elliptic curve such that P_1, \ldots , P_D \in E[p]. Define h : V \longrightarrow E[p] as follows: h(u_1, \ldots , u_D) = \sum_{1 \leq i\leq D} (u_iP_i). The function h is an arbitrary homomorphism from V to E[p].

The server chooses s_1, \ldots , s_D secretly in \mathbb{F}_p and publishes a point Q of p-torsion such that e_p(P_i,Q) \not= 1 and also publishes (P_i, s_iQ) for 1 \leq i \leq D. The signature of the vector v = u_1, \ldots , u_D is \sigma(v) = \sum_{1 \leq i\leq D} (u_is_iP_i) Note: This signature is homomorphic since the computation of h is a homomorphism.

Signature verification[edit]

Given v = u_1, \ldots , u_D and its signature \sigma, verify that

e_p(\sigma,Q) & = e_p \left(\sum_{1 \leq i \leq D} (u_i s_i P_i), Q \right) \\
& = \prod_i e_p(u_i s_i P_i,Q) \\ 
& = \prod_i e_p(u_i P_i, s_iQ)

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

System setup[edit]

The server computes \sigma(v_i) for each 1 \leq i \leq k. Transmits v_i, \sigma(v_i). At each edge e while computing y(e) = \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)y(f)) also compute \sigma(y(e)) = \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)\sigma(y(f))) on the elliptic curve E.

The signature is a point on the elliptic curve with coordinates in \mathbb{F}_q. Thus the size of the signature is 2 \log q bits (which is some constant times log(p) bits, depending on the relative size of p and q), and this is the transmission overhead. The computation of the signature h(e) at each vertex requires O(d_{in} \log p \log^{1+\epsilon} q) bit operations, where d_{in} is the in-degree of the vertex in(e). The verification of a signature requires O((d + k) \log^{2+\epsilon} q) bit operations.

Proof of security[edit]

Attacker can produce a collision under the hash function.

If given (P_1, \ldots , P_r) points in E[p] find a = (a_1, \ldots , a_r) \in \mathbb{F}_p^r and b = (b_1, \ldots , b_r) \in \mathbb{F}_p^r

such that a \not= b and

\sum_{1 \leq i \leq r} (a_iP_i) = \sum_{1 \leq j \leq r} (b_jP_j).

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

If r = 2, then we get xP+yQ = uP+vQ. Thus (x-u)P+(y-v)Q = 0. We claim that x \not = u and y \not = v. Suppose that x = u, then we would have (y-v)Q = 0, but Q is a point of order p (a prime) thus y-u \equiv 0 \bmod p. In other words y = v in \mathbb{F}_p. This contradicts the assumption that (x, y) and (u, v) are distinct pairs in \mathbb{F}_2. Thus we have that Q = -(x-u)(y-v)^{-1}P, where the inverse is taken as modulo p.

If we have r > 2 then we can do one of two things. Either we can take P_1 = P and P_2 = Q as before and set P_i = O for i > 2 (in this case the proof reduces to the case when r = 2), or we can take P_1 = r_1P and P_i = r_iQ where r_i are chosen at random from \mathbb{F}_p. We get one equation in one unknown (the discrete log of Q). 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

ar_1P + \sum_{2 \leq i \leq r}(b_ir_iQ) = 0.

Then as long as \sum_{2 \leq i \leq r} b_ir_i \not\equiv 0 \bmod p, we can solve for the discrete log of Q. But the r_i’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 b_i, for 2 \leq i \leq r, not all zero, what is the probability that the r_i’s we chose satisfies \sum_{2 \leq i \leq r} (b_ir_i) = 0? It is clear that the latter probability is 1 \over p . Thus with high probability we can solve for the discrete log of Q.

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 on BitcoinWiki[edit]