Homomorphic signatures for network coding: Difference between revisions

Revision as of 21:59, 6 May 2011

Latest revision as of 09:58, 19 August 2024

(42 intermediate revisions by 18 users not shown)

Line 1:

[[Network coding]] has been shown to optimally use [[Bandwidth (computing)|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 packet]]s spreads quickly since the output of (even an) honest node is corrupted if at least one of the incoming packets is corrupted.

==Introduction==

[http://en.wikipedia.org/wiki/Network_coding Network Coding] has been shown to optimally use [http://en.wikipedia.org/wiki/Bandwidth_%28computing%29 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 [http://en.wikipedia.org/wiki/Network_packet 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 [http://en.wikipedia.org/wiki/Hash_function [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 [http://en.wikipedia.org/wiki/Homomorphic_encryption[homomorphic Homomorphicencryption]] signature scheme for use with network coding to prevent pollution attacks.<ref>{{Cite http://journal |citeseerx.ist.psu.edu/viewdoc/download?doi = 10.1.1.60.4738&rep=rep1&type=pdf</ref>. The|title 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= infeasibleSignatures for aNetwork nodeCoding to|year sign= a2006 linear|url combination= of the packets without disclosing what [httphttps://enciteseerx.wikipediaist.psu.orgedu/wikiviewdoc/Linear_combination linear combination] was used in the generation of the packetsummary?doi=10.1.1.60.4738 Furthermore,|archive-url we= can prove that the signature scheme is secure under well known [httphttps://enweb.wikipediaarchive.org/wikiweb/Cryptography cryptographic] assumptions of the hardness of the [http20211121060603/https://enciteseerx.wikipediaist.orgpsu.edu/wikiviewdoc/Discrete_logarithm#Cryptographysummary?doi=10.1.1.60.4738 Discrete|archive-Logdate problem]= and2021-11-21 the|url-status computational= [httpbot://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93Hellman Diffieunknown |access-Hellmandate problem= on2021-11-21 elliptic curves].}}</ref>

==Network Coding==

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

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 [[Cryptography|cryptographic]] assumptions of the hardness of the [[discrete logarithm]] problem and the computational [[Elliptic curve Diffie–Hellman]].

<math>y(e) = \sum_{f:out(f)=v}(m_e(f)y(f))</math>

==Network Codingcoding==

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

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

: <math>y(e) = \sum_{f:\mathrm{out}(f)=v}(m_e(f)y(f))</math>

<math>\begin{bmatrix} y'\\ y_2' \\. \\. \\. \\ y_k' \end{bmatrix} = G_t \begin{bmatrix} w_1\\ w_2 \\. \\. \\. \\ w_k \end{bmatrix}</math>

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

: <math>\begin{bmatrix} y'\\ y_2' \\. \\. \\.vdots \\ y_k' \end{bmatrix} = G_t \begin{bmatrix} w_1\\ w_2 \\. \\. \\.vdots \\ w_k \end{bmatrix}</math>

where the <math>y_i'</math> are the vectors formed by removing the first <math>k</math> coordinates of the vector <math>y_i</math>.

==Decoding at the receiver==

Each [http://en.wikipedia.org/wiki/Receiver_%28information_theory%29[Receiver (information theory)|receiver]], <math>t \in T</math>, gets <math>k</math> vectors <math>y_1, . . .\ldots , y_k</math> which are random linear combinations of the <math>v_i</math>’s.

In fact, if

: <math>y_i = (\alpha_{i_1}, . . .\ldots , \alpha_{i_k}, a_{i_1}, . . .\ldots , a_{i_d})</math>

then

: <math>y_i = \sum_{1 \le j \le k}(\alpha_{ij}v_j).</math>.

Thus we can invert the linear transformation to find the <math>v_i</math>’s with high [http://en.wikipedia.org/wiki/Probability [probability]].

==History==

Krohn, Freedman and Mazieres proposed a theory<ref>http{{cite book |last1=Krohn |first1=Maxwell N. |last2=Freedman |first2=Michael J |last3=Mazières |first3=David |title=IEEE Symposium on Security and Privacy, 2004. Proceedings. 2004 |chapter=On-the-fly verification of rateless erasure codes for efficient content distribution |date=2004 |pages=226–240 |doi=10.1109/SECPRI.2004.1301326 |chapter-url=https://www.cs.princeton.edu/~mfreed/docs/authcodes-ieee04sp04.pdf |access-date=17 November 2022 |___location=Berkeley, California, USA |language=en-us |issn=1081-6011|isbn=0-7695-2136-3|s2cid=6976686 }}</ref> in 2004 that if we have a hash function

<math>H : V \longrightarrow G</math> such that:

* <math>H</math> is [http://en.wikipedia.org/wiki/Collision_resistance[Collision resistance|collision resistant]] – it is hard to find <math>x</math> and <math>y</math> such that <math>H(x)</math> = <math>H(y)</math>;

* <math>H</math> is a [http://en.wikipedia.org/wiki/Homomorphism [homomorphism]] – <math>H(x</math> + <math>y</math>) = <math>H(x) + H(y)</math>.

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

: <math>y = \sum_{1 \leq i\leq k} (\alpha_iv_i)</math>

we can check ifwhether

: <math>H(y) = \sum_{1 \leq i\leq k} (\alpha_iH(v_i))</math>

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

==Advantages of Homomorphichomomorphic Signaturessignatures==

# Establishes authentication in addition to detecting pollution.

# No need for distributing secure hash digests.

Line 45 ⟶ 50:

# Public information does not change for subsequent file transmission.

==Signature Schemescheme==

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

===Elliptic curves Cryptographycryptography over a finite field===

[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography [Elliptic curvescurve Cryptographycryptography]] over a finite field] is an approach to [http://en.wikipedia.org/wiki/Public-key_cryptography [public-key cryptography]] based on the algebraic structure of [http://en.wikipedia.org/wiki/Elliptic_curve [elliptic curves]] over [http://en.wikipedia.org/wiki/Finite_field [finite fieldsfield]]s.

Let <math>\mathbb{F}_q</math> be a finite field such that <math>q</math> is not a power of 2 or 3. Then an elliptic curve <math>E</math> over <math>\mathbb{F}_q</math> is a curve given by an equation of the form

: <math> y^2 = x^3 + ax + b, \, </math>,

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

Let <math>K \supseteq \mathbb{F}_q</math> , then,

: <math>E(K) = \{(x, y) | y^2 = x^3 + ax + b\} \bigcup \{O\}</math> forms an [http://en.wikipedia.org/wiki/Abelian_group abelian group] with O as identity. The [http://en.wikipedia.org/wiki/Group_%28mathematics%29 group operations] can be performed efficiently.

forms an [[abelian group]] with O as identity. The [[Group (mathematics)|group operations]] can be performed efficiently.

===Weil Pairing===

[http://en.wikipedia.org/wiki/Weil_pairing Weil Pairing] is a construction of [http://en.wikipedia.org/wiki/Roots_of_unity roots of unity] by means of functions on an [http://en.wikipedia.org/wiki/Elliptic_curve elliptic curve] <math>E</math>, in such a way as to constitute a [http://en.wikipedia.org/wiki/Pairing pairing] ([http://en.wikipedia.org/wiki/Bilinear_form bilinear form], though with [http://en.wikipedia.org/wiki/Multiplicative_notation multiplicative notation]) on the [http://en.wikipedia.org/wiki/Torsion_subgroup torsion subgroup] of <math>E</math>. Let <math>E/\mathbb{F}_q</math> be an elliptic curve and let <math>\mathbb{\bar{F}}_q</math> be an algebraic closure of <math>\mathbb{F}_q</math>. If <math>m</math> is an integer, relatively prime to the characteristic of the field <math>\mathbb{F}_q</math>, then the group of <math>m</math>-torsion points,

===Weil Pairingpairing===

[http://en.wikipedia.org/wiki/Weil_pairing [Weil Pairingpairing]] is a construction of [http://en.wikipedia.org/wiki/Roots_of_unity [roots of unity]] by means of functions on an [http://en.wikipedia.org/wiki/Elliptic_curve [elliptic curve]] <math>E</math>, in such a way as to constitute a [http://en.wikipedia.org/wiki/Pairing [pairing]] ([http://en.wikipedia.org/wiki/Bilinear_form [bilinear form]], though with [http://en.wikipedia.org/wiki/Multiplicative_notation [multiplicative notation]]) on the [http://en.wikipedia.org/wiki/Torsion_subgroup [torsion subgroup]] of <math>E</math>. Let <math>E/\mathbb{F}_q</math> be an elliptic curve and let <math>\mathbb{\bar{F}}_q</math> be an algebraic closure of <math>\mathbb{F}_q</math>. If <math>m</math> is an integer, relatively prime to the characteristic of the field <math>\mathbb{F}_q</math>, then the group of <math>m</math>-torsion points,

<math>E[m] = {P \in E(\mathbb{\bar {F}}_q) : mP = O}</math>.

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

: <math>E[m] \cong (\mathbb{Z}/m\mathbb{Z}) * (\mathbb{Z}/m\mathbb{Z})</math>

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

#(Bilinear) <math>e_m(P + R,Q) = e_m(P,Q)e_m(R,Q)</math>\text{ &and <math>}e_m(P,Q + R) = e_m(P,Q)e_m(P, R)</math>.

#(Non-degenerate) <math>e_m(P,Q) = 1</math> for all ''P'' implies that <math>Q = O</math>.

#(Alternating) <math>e_m(P, P) = 1</math>.

Also, <math>e_m</math> can be computed efficiently.<ref>{{Cite journal |citeseerx = 10.1.1.88.8848|title = Improved Weil and Tate pairings for elliptic and hyperelliptic curves|url = https://archive.org/details/arxiv-math0311391|pages = 169–183|year = 2004|bibcode = 2003math.....11391E|last1 = Eisentraeger|first1 = Kirsten|last2 = Lauter|first2 = Kristin|last3 = Montgomery|first3 = Peter L.|arxiv = math/0311391}}</ref>

Also, <math>e_m</math> can be computed efficiently<ref>http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBsQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.88.8848%26rep%3Drep1%26type%3Dpdf&rct=j&q=Improved%20Weil%20and%20Tate%20pairings%20for%20elliptic%20and%20hyperelliptic%20curves&ei=Fyi-Te_nMdCitgejkIzGBQ&usg=AFQjCNFTlKZaFlQ_BZyXDh6nKSDpntTTlA&sig2=VDWSZSuKNVeefL0EhmOCqA&cad=rja</ref>.

===Homomorphic Signaturessignatures===

Let <math>p</math> be a prime and <math>q</math> a prime power. Let <math>V/\mathbb{F}_p</math> be a vector space of dimension <math>D</math> and <math>E/\mathbb{F}_q</math> be an elliptic curve such that <math>P_1, . . .\ldots , P_D \in E[p]</math>.

Define <math>h : V \longrightarrow E[p]</math> as follows:

<math>h(u_1, . . .\ldots , u_D) = \sum_{1 \leq i\leq D} (u_iP_i)</math>.

The function <math>h</math> is an arbitrary homomorphism from <math>V</math> to <math>E[p]</math>.

The server chooses <math>s_1, . . .\ldots , s_D</math> secretly in <math>\mathbb{F}_p</math> and publishes a point <math>Q</math> of p-torsion such that <math>e_p(P_i,Q) \not= 1</math> and also publishes <math>(P_i, s_iQ)</math> for <math>1 \leq i \leq D</math>.

The signature of the vector <math>v = u_1, . . .\ldots , u_D</math> is

<math>\sigma(v) = \sum_{1 \leq i\leq D} (u_is_iP_i)</math>

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

===Signature Verificationverification===

Given <math>v = u_1, . . .\ldots , u_D</math> and its signature <math>\sigma</math>, verify that

: <math>

<math>e_p(\sigma,Q) = e_p \sum_{1 \leq i \leq D} (u_is_iP_i,Q)</math>

\begin{align}

<math>e_p(\sigma,Q) & = e_p \left(\sum_{1 \leq i \leq D} (u_is_iP_iu_i s_i P_i), Q \right)</math> \\

<math> & = \prod_i e_p(u_i s_i P_i,Q)</math> \\

<math> & = \prod_i e_p(u_i P_i, s_iQ)</math>

\end{align}

</math>

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

<math> = \prod_i e_p(u_i s_i P_i,Q)</math>

==System Setupsetup==

<math> = \prod_i e_p(u_i P_i, s_iQ)</math>

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

==System Setup==

The server computes <math>\sigma(v_i)</math> for each <math>1 \leq i \leq k</math>. Transmits <math>v_i, \sigma(v_i)</math>.

At each edge <math>e</math> while computing

<math>y(e) = \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)y(f))</math>

also compute

<math>\sigma(y(e)) = \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)\sigma(y(f)))</math>

on the elliptic curve <math>E</math>.

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

==Proof of Securitysecurity==

Attacker can produce a collision under the hash function.

If given <math>(P_1, . . .\ldots , P_r)</math> points in <math>E[p]</math> find

<math>a = (a_1, . . .\ldots , a_r) \in \mathbb{F}_p^r</math> and <math>b = (b_1, . . .\ldots , b_r) \in \mathbb{F}_p^r</math>

such that <math>a \not= b</math> and

<math>\sum_{1 \leq i \leq r} (a_iP_i) = \sum_{1 \leq j \leq r} (b_jP_j)</math>.

: <math>\sum_{1 \leq i \leq r} (a_iP_i) = \sum_{1 \leq j \leq r} (b_jP_j).</math>.

Proposition: There is a polynomial time reduction from Discrete Log on the cyclic group of order <math>p</math> on elliptic curves to Hash-Collision.

Proposition: There is a polynomial time reduction from Discretediscrete Loglog on the [[cyclic group]] of order <math>p</math> on elliptic curves to Hash-Collision.

If <math>r = 2</math>, then we get <math>xP+yQ = uP+vQ</math>. Thus <math>(x-u)P+(y-v)Q = 0</math>.

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

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

: <math>ar_1P + \sum_{2 \leq i \leq r}(b_ir_iQ) = 0.</math>.

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

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.<ref>http{{cite book |last1=Boneh |first1=Dan |last2=Lynn |first2=Ben |last3=Shacham |first3=Hovav |title=Advances in Cryptology — ASIACRYPT 2001 |chapter=Short Signatures from the Weil Pairing |series=Lecture Notes in Computer Science |date=2001 |volume=2248 |pages=514–532 |doi=10.1007/3-540-45682-1_30 |chapter-url=https://csewebhovav.net/ucsd.edu/~hovav/dist/sigs.pdf |access-date=17 November 2022 |language=en|isbn=978-3-540-45682-7}}</ref>. Here it is shown that forging a signature is at least as hard as solving the [http://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93Hellman computational[elliptic curve Diffie-Hellman problemDiffie–Hellman]] on the elliptic curveproblem. 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-HellmanDiffie–Hellman on elliptic curves and probably as hard as computing discrete-logs.

==See Alsoalso==

*[[HomomorphicNetwork Encryptioncoding]]

*[[Homomorphic encryption]]

*[[Elliptic Curve Cryptography]]

*[[Elliptic-curve cryptography]]

*[[Weil Pairingpairing]]

*[[Elliptic Curve Diffie-Hellman]]

*[[Elliptic-curve Curve DSADiffie–Hellman]]

*[[Elliptic Curve CryptographyDigital Signature Algorithm]]

*[[Digital Signature Algorithm]]

Line 143 ⟶ 155:

{{Reflist}}

==External Linkslinks==

#[http://research.microsoft.com/pubs/69452/imc06.pdf Comprehensive View of a Live Network Coding P2P System]

#[http://research.microsoft.com/en-us/um/people/klauter/CISS_06.pdf Signatures for Network Coding(presentation) CISS 2006, Princeton]

#[https://web.archive.org/web/20110606191907/http://www.cse.buffalo.edu/~atri/courses/coding-theory/fall07.html University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra]

[[Category:Finite fields]]

[[Category:Coding theory]]

[[Category:Information theory]]

[[Category:Error detection and correction]]