Method and system for distributing network coding content using digital sign

Method and system for network coded content distribution using digital signature

[0001] Technical Field

[0002] The present invention relates to network distribution, and more particularly to network coded content distribution using digital signatures.

[0003] Background Art

[0004] The increased network bandwidth allows a large amount and various types of media content to be distributed on the Internet. Peer-to-peer networks handle the problem of broadcasting data from a single source to multiple receivers on the network by allowing intermediate nodes to also send data. To send a large file, conventional distributed systems usually segment the file into smaller parts for transmission. The problem with this solution is that bandwidth utilization does not need to be optimal, because there may be bottlenecks. Network coding used in conjunction with large-scale content distribution mechanisms solves this problem. Network coding allows all nodes in the network to complete partial coding of input data. It has been shown that this can produce optimal network capacity utilization both in theory and in practice. However, in this regard, due to security issues, any consideration of using network coding to distribute content lacks real-world applicability. For example, conventional network coding systems and technologies do not allow authentication and verification of transmitted data.

[0005] Summary of the Invention

[0006] This overview is provided to introduce in a simplified form some concepts that will be further described in the detailed description below. This summary is not intended to determine the key features or essential features of the claimed subject matter, nor is it intended to be used to help determine the scope of the claimed subject matter.

[0007] In view of the above reasons, a digital signature for network coding is described. In one aspect, a homomorphic digital signature generated from an elliptic curve is used to digitally sign the segmented content block for distribution. According to an implemented distribution scheme, a linear combination of packets including the digitally signed content is distributed to the destination device. The linear combination of the packets includes common information when the segmented block is digitally signed. The homomorphic digital signature and public information allow one or more packets of a linear combination of the packet to be received to verify and authenticate independently of the secure transmission of the key and hash digest used to digitally sign the one or more packets Content associated with one of these groups.

[0008] Brief Description of the Drawings

[0009] In the drawings, the leftmost digit of a component reference number identifies the specific drawing in which the component first appears.

[0010] FIG. 1 shows an exemplary system that utilizes digital signatures when distributing content based on a network coding distribution scheme according to one embodiment.

[0011] FIG. 2 shows an exemplary process of using a digital signature in a network code distribution scheme according to an embodiment. [0012] FIG. 3 shows an example of a suitable computing environment in which a digital signature for network coding can be implemented in whole or in part.

[0013] Specific embodiments

[0014]

[0015] The following describes systems (for example, systems, devices, computer-readable media, etc.) and methods for digital signatures for network coding with reference to FIGS. 1-3. These systems and methods solve the above-mentioned security problems and other existing security restrictions that use network coding to distribute content in a distributed network. To this end, the system and method utilize homomorphic hashing in network coding operations. Given a hash function, it is computationally infeasible and linear to find the conflict for this hash function. The system and method calculate the hash of the linear combination of the input message according to the input hash value. The calculated hash is based on the theory of elliptic curves used in the signature scheme to determine whether the message has been altered or whether this inserts useless information into the message. Know a certain

The signature of these messages, the system and method to sign the linear combination of the message. The signature scheme is homomorphic, which means that the linear combination of the signature is the same as the linear combination of the signature. This allows the system and method to directly detect malicious nodes that inject useless information into the network (ie, pollution attacks) and add authentication to the network coding scheme.

[0016] The system and method for digital signatures in network coding are safe when assuming that the discrete logarithm problem on the elliptic curve is difficult (a common assumption in cryptography). The system and method achieve the same security level of homomorphic hashing by working on a smaller domain to provide performance advantages relative to other solutions of the same security level. Security is effectively implemented using local calculations.

[0017] In view of the above, the system and method for digital signatures in network coding, after knowing the signatures of certain files to be distributed, generates signatures of any linear combination of these files. This allows the data recipient to sign the packets combined at each node in the network without having to contact the data source to sign these packets. This means that the system and method do not need to protect the security of the transmission of the hash digest for the distributed vector. The signature allows the authentication of the data. In addition, a small bit length is sufficient to ensure security, which is essentially because there is no known (general) sub-exponential algorithm that can be used for the discrete logarithm of a point group on an elliptic curve over a finite field.

[0018] These and other aspects of the system and method for digital signatures in network coding are now described in more detail.

[0019] Sample Piece System

[0020] Although not required, the system and method for digital signatures for network coding are described in the general context of computer-executable instructions (program modules) executed by computing devices such as personal computers. Program modules generally include routines, programs, objects, components, and data structures that perform specific tasks or implement specific abstract data types. Although the system and method are described in the foregoing context, the actions and operations described below can also be implemented by hardware.

[0021] FIG. 1 shows an exemplary system 100 for digital signatures in network coding according to one embodiment. In this implementation, the system 100 represents a content distribution system. The system 100 includes one or more server computing devices 102 coupled to any number of client computing devices 106 through a network 104. The server 102 implements the operations of digitally signing content and using network coding operations to distribute the signed content to the client device 106 as a linear combination of packets. In response to receiving the linear combination of packets, the client device 106 verifies and authenticates the digitally signed content embedded in the received packet. If the client 106 verifies the received content, and if the client 106 is not the final destination for the received content within the system 104, the client 106 implements digital signing of the received content and uses a network encoding operation to verify the received content. And the newly signed content is distributed to the operations of different clients 106 as a new linear combination of packets. In view of the above, depending on whether the corresponding computing device 102 and 106 is the final destination for any received digitally signed content in the system 100, each computing device 102 and 106 can perform digital signing and use network coding to distribute content and One or more of the operations to verify and authenticate the received content.

[0022] Referring to FIG. 1, each server 102 and client device 106 includes one or more respective processors 108 (eg, 108- 1 and 108-2) _oThe system memory 110 includes computer program modules 112 (for example, 112-1 and 112-2) and program data 114 (for example, 114-1 and 114-2). The processor 108 fetches and merges corresponding ones of the program modules 112 Execute computer program instructions. The program module 112 includes a digital signature for the network encoding module 116 (for example, 116-1 and 116-2) and other program modules 118 (for example, 118-1 and 118-2) such as an operating system and a content distribution module. The digital signature for the network encoding module ("encoding module") 116 includes program logic for the secure and reliable distribution of content between the corresponding server 102 and the client 106 over the network. For the purpose of exemplary illustration, the content to be distributed is shown as the corresponding part of the "other program data" 120 (for example, 120-1 and 120-2). That is, the encoding module 116 performs the use of digital

One or more operations of signing the distribution of content to the client device 106 and verifying and authenticating the received digitally signed content.

[0023] In this example, the encoding module 116-1 of the server 102 initially segments the content to be distributed into smaller data blocks. These block segments are shown as corresponding parts of the segment content in "Other Data" 120-1. The server 102 uses the digital signature scheme to calculate the corresponding homomorphic digital signature 122-1 for each block segment, and signs the block segment with the corresponding signature 122-1 to create the corresponding signed block 124-1. In the system 100, When the result obtained by adding two vectors in a vector space and hashing to an elliptic curve is the same as the sum of the respective hashes of the two vectors on the elliptic curve, homomorphism is shown. An exemplary such scheme for signing block segmentation is described in the section below entitled "Exemplary Homomorphic Signature Scheme". The server 102 transmits the signed block 124-1 as a linear combination of packets (or vectors) through the network 104 to one or more client devices 106. The operation of an exemplary network coding that generates a linear combination of this grouping is described in more detail in the section entitled "Network Coding Model" below.

[0024] In response to receiving a random linear combination of packets including signed blocks, the client device 106 verifies the signature of the server 102 for each signed block 118. An exemplary bilinear verification process based on We subscription pairing is described in the section entitled "Exemplary Homomorphic Signature Scheme" below. These verification operations allow the client 106 to identify the dishonest server 102 within the content distribution system 100. In response to verifying and authenticating each signed block 124-1, if the client device 106 is not the final destination for the random linear combination of received packets, the client device 106 implements the above (and below) for the server 102 The described operation is to digitally re-sign the data to points on the elliptic curve using a homomorphic hash function, and use a network coding operation to redistribute the signed data to the destination device.

[0025] That is, if the client device 106 is not designated by the linear combination of packets as the ultimate recipient of the received content, and if the received content has been successfully verified and authenticated, it knows that the content in the received content Certain digital signature encoding module 116-2: (a) re-sign the received content; and (b) use the new re-signed content as a new linear combination of the packet ("the corresponding part of the other data 116-2 ) Redistribute to different client devices 106. The process is iterated until the corresponding client device 106 is the final destination for the content in the linear combination of packets received from the server 102 and/or client device 106. These subsequent operations allow the data receiving client device 106 to sign the packet combined at each node in the network 104 without contacting the source (for example, the server 102 and/or another client device 106) to sign a new packet of the packet. Grouping in linear combination.

[0026] Elliptic Curve Background

[0027] This section presents various aspects of elliptic curves over finite fields. The finite field is called the elliptic curve E (sometimes abbreviated as E/Fq). With reference to the finite field, q>3 is a prime number, and P²(F_qThe projective curve in) is given by the equation of the form

[0028] Y²Z = Χ³+ΑΧΖ+ΒΖ³

[0029] where A, B e F_qAnd 4A³+27B² # 0_oThe curve has two affine parts: the part of Z + 0 has affine type y² = x³+Ax+B (obtained by setting x = now and Ding = ); and the part where Z = 0 has only one (projective) point, that is (0:1:0), which is represented as 0. Let K be the domain that contains the name (not necessarily limited), then the set can be given

[0030] E(K)={(x,y) ε KXK: y² = χ³+Αχ+Β} U {0}

[0031] The structure of the abelian group, where 0 is the identity of the group. In addition, group operations can be calculated efficiently. In particular, if P and Q are points on E and their coordinates are in Fq, then P+Q and-can be calculated for any ε> 0 in 0 (logZq) bit operations. Po Hasses law gives the group E (F_q) A rigorous estimate of the size:

[0032] q + }-2y[q <6E(F_q)<q + l + 2y/q

[0033] The School-Elkies-Atkin algorithm is to calculate eE (F_q) Is a deterministic polynomial time algorithm.

[0034] We order pairing

[0035] Let E/Fq be an elliptic curve, and let tile be the algebraic closure of Fq. If m is an integer whose characteristics of the domain Fq are relatively prime, then the group of m-torsion points = {Pe: mP = 0} has the following structure:

[0036] E[m] = Z/mZXZ/mZ

[0037] Existence mapping e_m ,E[m] x E[m] T;, which has the following properties:

[0038] · Mapping e_mIs bilinear:

[0039] eJSj+Sa,T)=e(S" T)e(S₂, Τ)

[0040] e_m (S, Tj+T₂) = e (S, TJ e (S, T₂)

[0041] Alternate: e_m(T, T) = 1, so e_m(T, S) = e_m(S, T)^_o

[0042] Non-degenerate: If e^S, Τ)=1, then for all S mounds E[m], T=0.

[0043] Let E/bi be an elliptic curve, and let S and T be two m torsion points on E, the coordinates of which are in the bid. There is one that can be compared to e in O(logmlogZq) bit operation_m(S, T) Deterministic algorithm for evaluation. When it is clear from the context, write e_mWhen discarding the subscript m.

[0044] Network coding model

[0045] The standard network coding framework for content distribution is as follows. Let G = (V, E) be a directed graph. The source se V (for example, the server 102 and/or the client 106) wishes to send certain data (content to be distributed) to the set of vertices 7. Choose a vector space W/F (for example, dimension d), and treat the data to be sent (for example, segment content) as a vector W], ···, w_kBranch of ew. The source then creates an augmented vector v by setting dagger=(answer pan, 1,...,...,%,...,!^)_P -, v_k, Where w" is the j-th coordinate called by the vector. Without loss of generality, it can be assumed that the vector ν: is linearly independent. Use V to denote the subspace spanned by these vectors (F_p^k+dof). Each edge ee E calculates the linear combination y(e) of the vector entering the vertex v = in(e), that is

[0046] y(e)=Σ resistance(/)y(/) f:oul(f)=v

[0047] where m_e e F_pOConsider that the source has k input edges carrying k vectors. Through induction, the vector y(e) on any edge is a linear combination y(e) = Σ and is a vector in V. The k-dimensional vector g(e) =<gi (e),..., gk(e)> is simply the first k coordinates of the vector y(e). The matrix whose rows are vectors g(ej,...,g(ej) is called the global coding matrix for t, and denoted as where e: is the input edge for te T. In practice, the coding vector is randomly selected , So matrix 6 is very likely to be irreversible. Therefore, when any receiver receives...,yk, it can find Wi,...,Wk by solving the following equation

<td>[0048]</td><td>&gt;1'</td><td>=^G，</td><td>W]^W2: 5</td>

<td></td><td></td><td></td><td></td>

[0049] where_YiIs a vector formed by removing the first k coordinates of the vector yi.

[0050] Example Tongjie Signature Scheme

[0051] The network encoding module 116 implements the following exemplary homomorphic signature scheme. Let p be a prime number (shown as the corresponding part of "other program data" 120), and q is a scene of a different prime number, and p<<q_oSet V/F_pIs a vector space with dimension d+k, and suppose E/ is an elliptic curve, so that R"...,Rk,P" -,P_dBoth are (different) p torsion points on Eg). A function hm,...very ",...Mountain: V - E(Fq) can be defined as follows: for v =<5,..., Uq Vi, ···, v_d> ε V [0052] (V)⁼ X x ^Uj^RJ + Σ ^Vt^Pi

[0053] Letter>h_E1,...,Rk,η,...,Pd is the group E[p] (additive abelian group) from vector space V to P torsion point on the curve (corresponding part of "other program data" 120) ) Homomorphism.

[0054] Assume that the server 102 (or the client 106) wishes to transfer -, v_ke V is distributed to the client device 106, and the server selects S],..., Sk and mouth,..., mouth which are secret in %. These secrets are shown as corresponding parts of "Other Program Data" 120. The server 102 then signs the packet V by calculating: (i.e., signed block 124)

[0055] Force production nA,... "(V,)

[0056] The server publishes R"..., 1ζ, P"..., Pd, Q, SjQ(l W j W k) and r: Q(l W i W d) (that is, the server publishes "other program data" 120 Data section). Here Q is another p torsion point far away from other points on the elliptic curve, so that e_p(Rj, Q) # 1 and ep(Pi, Q) work 1 (1 W j W k and 1 W i W d).

[0057] The signature hj (ie, the homomorphic digital signature 122) is also appended to the data_VjAnd send it according to the distribution plan. Now, in the calculation

[0058] y0=Σ resistance (»(/) f:out(f)=in(e)

[0059] On any edge e, the encoding module 116 also calculates

[0060]elegant)=Σ called (/)(/) /:oui(/)=irt(e)

[0061] And send h(e) together with data y(e) as a linear combination of packets. Since the calculation of the signature h(e) is homomorphic, we get that if y(e) then

[0062] Force (e)=Σ ah

[0063] Exemplary verification process

[0064] Next, the verification process implemented by the corresponding client device 106 is described. Suppose y(e)=U[, ···, u_k, v_P -, v_d>, the digital signature used for the network encoding module 116-2 determines whether

[0065] Π © (Bird,^sjQ)Π choke£ must be 0 = °(square 2),. ) !&lt;. J&lt;k

[0066] This works because if h(e) is a legal signature of y(e), then by definition

[0067] = Σ ^uJ^SJ^Rj ⁺ X x

1 ί " 1 mouth wound

[0068] Thus

[0069] e(force (e), Q) = e(^ UjSjRj + j<>k

[0070] ⁼ Π choking £,0) (according to bilinearity)

[0071] ⁼ Π e (round e (v, £, should) (again according to bilinearity) spoon sm

[0072] Verify the bilinearity of pairing using We. Note that all items in the above verification can be obtained from the vector y(e)

Calculation, or can be calculated from public information.

[0073] The signature 122 is a point on the elliptic curve whose coordinates are in Fq, so the size of the signature is 0 (logq) bits, and this is the transmission overhead. The calculation of the signature h(e) requires 0(d_inlogplog^1+Eq) Bit operation, where (1 Di is the degree of in(e). The verification of the signature requires 0 ((d+k) logplogZq) bit operation.

[0074] Security Proof

[0075] The notation in the previous section is also used in this section. In order to interfere with the described signature scheme, the adversary can either generate a hash conflict for the functions 5 grumble....sm.HH, ..., rdPd, or can forge the signature so that the verification can pass. Note that in this case, the enemy does not know the point SjRp ···, s_kR_kAnd rf, ···, r_dP_do First show that even if the enemy knows these points, it is still as difficult to generate a conflict as calculating discrete logarithms. Then make the claim more precise:

[0076] Problem: Hash conflict. Fixed an integer r> lo input: the points P1,..., Pr in the cyclic subgroup of order p (prime number) on the given elliptic curve E/Fq. Output: tuple a = (a"...,aj ,b = @,···,),;, makes aZb and

[0077] Σ afi = Σ bjPj

[0078] Proposition 1. There is a reduction in time from the discrete logarithm on the cyclic group of order p on the elliptic curve to the polynomial time of the hash collision.

[0079] Proof: First deal with the situation when r=2. Let P and Q be E(F_q) ± is not the point where the order of the identity is p. Assume that Q is in the subgroup generated by P. The goal is to find a such that Q = aP, and to do this, apply the claimed algorithm for resolving hash collisions to points P and Q. This algorithm produces two different counter-daggers, blades, ("*) Qiu used, so that

[0080] xP+yQ = uP+vQ

[0081] This gives the relation (xu)P+(yv)Q=0. It is argued that x # u and y work ν. Assuming x = u, then (yv) Q = 0 is obtained, but Q is a point of order p (prime number), so yu = Omod p, in other words, y = ν in Fp. This contradicts the fact that (X, y) and (u, ν) are different pairs in Fp?. Thus, Q = -(xu) (yv)* is obtained, where the inverse modulo P is used.

[0082] If r>2, you can do the following two things. Or you can take Pi = P and P2 = Q as above, and set Pi = 0, i> 2 (in this case, the proof is simplified to the case of r = 2), or you can take Pi = rjP and Pi = slander, Where the mouth is from F_pRandomly selected in. Obtain an equation (discrete logarithm of Q) in an unknown number. It is quite possible that the resulting equation does not include the unknown. However, this will only happen with a very small probability, as discussed below. Suppose the algorithm used for hash collision is given

[0083] ^ari^P+ X x ^bi^riQ = °

2 scoops of the same

[0084] The discrete logarithm of Q can be solved as long as the work 2 is as good as modp. However, the oracle used for hash collision is unknown, so the order of the process can be interchanged. In other words, given a pair of 2 W i Wr, what is the probability that the selected mouth satisfies workers 2 mouths and =0? It is clear that the probability of the latter is Qi, and it is very possible to solve the discrete logarithm of Q.

[0085] Incremental cryptography: The case of hashing and signing by Bellare, Μ., Goldreich, Q., Goldwasser, S., Advancesin Cryptology CRYPTO^z 94. Santa Barbara, California, 1994. The proof put forward to draw the conclusion of the above proposition. The proof deals with finite fields, but the argument is also applicable to the case of elliptic curves.

[0086] It has been shown that it is difficult to generate a hash collision in the scheme implemented by the digital signature for the network encoding module 116. The other method an adversary can use to block the scheme is by forging signatures. However, forging a signature is at least as difficult as solving the so-called computational co-Diffie-Heliman (co-Diffie-He 1 Iman) problem on the elliptic curve. The only known way to solve this problem on elliptic curves is by calculating the discrete logarithm. Thus, forging a signature is at least as difficult as solving the computational Diffie-Hellman on the elliptic curve, and probably as difficult as computing the discrete logarithm.

[0087] Example software design

[0088] The notation proposed above when describing the network coding model and the exemplary global signature scheme is also used in this section. To initialize the signature scheme, the module 116 of FIG. 1 selects a prime number P and an elliptic curve whose entire P torsion is defined in the appropriate domain as described below. An exemplary technique for selecting an elliptic curve is described in the following section entitled "Finding a suitable elliptic curve". The module 116 also identifies a set of p torsion points required to define the homomorphic signature 122. In this section, all these issues are discussed and an example is also provided.

[0089] In summary:

[0090] Choose a large prime number p.

[0091] Choose a suitable prime number (described below in the section entitled "Finding a suitable elliptic curve") 1 and an elliptic curve Eo of points with multiples of p on%

[0092] Find the extension Fq of the domain% such that (here E[p] refers to the set of all p torsion points).

[0093] Since GE(FJ=Omod p, it has p torsion point. Suppose 0ZPWE(FJ is the p torsion point on the curve. Take %=a: P(l W i W k) and Pj = bf (l W j W d), where a: and S are randomly selected from the set 1, -,ρ-1.

[0094] Q is the point such that e(RpQ) #1 and e(P[,Q)=1. To ensure this, choose F. The p torsion point defined above but not defined on the smaller domain% is sufficient. In fact, let Q be such a point, then if e(%, Q) = 1, this means that for any A, B and E[p], e(A, B) = 1 (because% and Q generate E[p]), which is a non-degenerate contradiction with We set pairing.

[0095] Finally, the module 116 randomly selects keys S],..., Sk and..., r from Fp*_do

[0096] Find a suitable elliptic curve

[0097] Generally speaking, if there is an elliptic curve E on the finite field K, the degree of the elliptic curve E on the field K is Θ (p²) Defines the P torsion point on the extension. The P torsion point is defined in a small domain, so that the operation of the module 116 can be performed in polynomial time. In this section, we discuss how to select the appropriate domain% and the elliptic curve whose p torsion points in this domain are defined on the small relative expansion of the base domain.

[0098] The known complex multiplication theory of elliptic curves can be used to generate an elliptic curve with a specific number of points on a finite field. The details about the algorithm are not necessary for the use here, but its running time is utilized, so the algorithm will be described next. Suppose we want to generate an elliptic curve E/Η with exactly N points (where 1 is a prime number), where N falls in the interval 0 + 1-2a/7vNS0 + 1 + 2V7. Write N as l+1-t and set Dy? = t²-41, where D or D/4 is squarefree (note that D is negative due to the Hasse limit). Therefore, the algorithm to generate this elliptic curve at time D|^o(1)Run within.

[0099] In the system 100, an elliptic curve with a point of a smaller multiple of p is found, which indicates that the domain% on which this curve should be found must have Z + 1-2V7S plus ρ" + 1 + 2λ/7. In addition, t²-41 should have a small square-free part, because this determines the running time of the method that generates this curve. Choose the prime number 1, so that for the small (negative) D, 41 = 4p²-Dy²,and

And 1 three-lmod p; and set t = 2p_oThus, 1+1-t = l+l-2p = Omod p, and therefore the number of points on the elliptic curve will be a multiple of P, and because |D| is small, the time to generate this curve will be reasonable.

[0100] To generate this prime number 1, select (negative) D (|D| is smaller). Determine 1/4 (p²-Dy²) Is a prime number, y = 0, 1,... Since we are only interested in the prime numbers of three -lmod p, the above check is only for making -Dy² = -4mod p which y values are entered. The Lang-Trotter conjecture suggests that there will be many y values that produce prime numbers. This also involves the Hardy-Littlewood conjecture about the prime value of the quadratic polynomial. Now, the complex multiplication produces an elliptic curve E with some p torsion points on F]. However, an elliptic curve is required such that E[p] is defined on the small degree expansion of %. This is where the additional constraint 1 = -lmod p is used. Since 1 is three Tmod p, the order of 1 in Fp* is 2. Now, the Koblitz-Balasubramanian rule shows that in this case, all P torsion points are defined on the extension of the base field with degree 2, in other words E[p]^F_（2. Now, get the elliptic curve E/F, the corresponding part of "other program data" 120), and know that all P torsion points are defined on E[l], but how to find these points? This is the subject of the next paragraph.

[0101] Comment 1. The theory of complex multiplication shows that the curve E depends only on the quantity D. More precisely, for each D, there is a finite list of elliptic curves in the digital domain K Ει, -, E_ffl, So that Emodl meets the requirements here. This is shown in the section entitled "Examples" below.

[0102] Find D torsion point

[0103] Let E/F] be the elliptic curve identified using the method given above. Then GE(FJ = l+l-2p, and let m be the largest divisor of GE(FJ, which is relatively prime to p. Let P be a random point on the curve E(FJ. Assuming mP#0, then mP Is the point of the p-th power torsion rate (according to Lagrange's law). Let i 2 1 be such that mpT = 0 but mp^1_1P # 0 is the smallest integer. Then mpip is a p torsion rate point. Of course, if mP=0 is found, it is repeated by finding another random point P. For a random point P, the probability of mP = 0 is at most and therefore, it is very possible to find a non-trivial p torsion point.

[0104] This gives the p torsion part defined in %. To find the part of P torsion defined on bid 2, repeat the above process on bid 2. To perform this process, you need to know the number of points on E(FQ. It seems that if E is defined on a finite field K, then the number of points on E on any extension of K is determined by GE(K) The theory predicts that for the curve E, eE(F_（2） = £²+la²-a²The α center in Qi is the two roots of the following equation (in C)

[0105] Φ²-2ρΦ+1 = 0

[0106] Example

[0107] This example was generated using the computer algebra package MAGMA. For this example, take D = -4. For any prime number P, the appropriate prime number 1 is to satisfy 41 = 4p²+4y²The 1, makes 1 tri-lmod p. This congruence means that y? = -lmod P, in other words -1 should be the quadratic remainder modulo p. This in turn means that p = lmod 4, and the value of y to be searched should all be equal to one of the square roots of -lmod p.

[0108] Let p be a prime number as follows:

[0109] 26330018368571742206574632566065508402231508999153

[0110] Search for the qualitative value of Yu+A with special properties. Complex multiplication shows that the elliptic curve

[0111] E: y² = x³+x (affine type)

[0112] is a suitable elliptic curve. MAGMA indicates that GE (Fj is:

[0113] 351688192729081689963486221568344816704455675519621986306651119145697

6613264142

[0114] 847616337439963943072004,

CN 101300570 Β

[0115] This is actually three Omod po according to MAGMA, E(F₁₂The number of points on) is

[0116] 123684584905047707258686141200578231465582664681874593612259486008465

0180144846

[0117] 014265383739300784290963417699135578021643493118755085472626923470388

5776384142

[0118] 268869493894468081319453336772812036965744626464,

[0119] And these three Omod hearts this is E[p] is E(F₁₂) Is a necessary condition for subgroups. It shows that E[ρ] is actually contained in E(FQ by finding the two points that generate the ρ torsion subgroup. Following the method outlined in §5.2, find out the total P torsion that generates E(FQ) Two P torsion points P and Q

[0120] P = (2767010499835095322341063384520824402927117627734637325336838767 59414814860205

[0121] 8330843763239769722154862,7368956190748628704419932604283633092123419

52700619

[0122] 999020137331297834986221601940750818713297548511336)

[0123] Q = (1703436933427828756143890099348804522750690840443235518664737403 67532495756430

[0124] 3078396992524604785250333u+157128874698661854995016811716722095152507

76009

[0125] 77567312986377817436996986291386148589353156799909434396,

[0126] 293262979414624776596432402939618431893907517428095829765520553326321

029472

[0127] 565240814005665686795414190u+2827229136528454163001184937157406163795

[0128] 191623737718932812446648142173368705416653836715431228856385081)。

[0129] Here, u is a variable that gives the homomorphic empty square ["]/(/(")) for the quadratic irreducible f Qiu Fju]. P and Q

We set the match as

[0130] e_p(P, Q) = 18803618029983537254653390382035462993205409477769908010460

[0131] 37660415779359581593172656075406185808275672u+

[0132] 31284655683961117025378938265048897550540714

[0133] 78912095275807108199402549356171889616725860797979581965315.

[0134] Exemplary Procedure

[0135] FIG. 2 shows an exemplary process 200 for a digital signature for network encoding according to one embodiment. For illustrative purposes, the operations of the process 200 are described with respect to the components of the system 100 of FIG. 1. The leftmost digit of a component reference number indicates the specific drawing in which the component is first described.

[0136] At block 202, the server 102 digitally signs the corresponding block in a set of segmented blocks of the content to be distributed with the corresponding homomorphic digital signature 122 (FIG. 1). This is achieved by transforming the vector (for example, the corresponding block of the segmented block) into a set of points on the elliptic curve. These transformations are performed using a homomorphic (additive abelian group) homomorphic anti-collision hash function from a vector space to a set of prime torsion points on an elliptic curve.

[0137] At block 204, the server 102 encapsulates the packet together with the public

The information (for example, some different prime number (P) torsion points on the elliptic curve) is distributed together through the network 104 to the destination device (for example, the corresponding client device 106). Packets and information are distributed using a distribution scheme. In one implementation, the distribution scheme is a network coding distribution scheme. The secret information such as the key and the hash digest used to digitally sign the segmented content (ie, vector) in the operation of block 202 is not distributed by the server 102 along with the linear combination of the packet and the public information.

[0138] At block 206, the client device 106 receives one or more of the linear combinations of distributed packets. At block 208, the client device 106 uses the public information distributed by the server along with the received packet to verify and authenticate the content encapsulated within the received packet. At block 210, the client device 106 determines whether it is the final destination device to receive the received packet. If not, then operation continues as described above at block 202, where the client device 106 actually becomes the server 102. More specifically, in this situation, after the client device 106 knows the digital signature of some of the linear combinations of packets, it can generate a signature of any linear combination of packets (ie, the received packet). This allows the client device 106 to digitally re-sign the packet without contacting the source (ie, in this iteration, the server 102). In addition, this allows the client device to detect any node (eg, server 102 and/or client 106) that maliciously claims to have sent a linear combination of inputs, while in fact injecting some other data or useless information. With this in mind, the client device distributes the re-signed packet and the associated public information for digitally signing the segmented block to the destination device in a new linear combination. The operations of blocks 202 to 210 are iteratively repeated by any number of servers 102 and client devices 106 until the distributed content reaches the destination device.

[0139] Sample operating environment

[0140] FIG. 3 shows an example of a suitable computing environment in which a digital signature for network coding is implemented in whole or in part. The exemplary computing environment 300 is only an example of a suitable computing environment for the exemplary system of FIG. 1 and the exemplary operation of FIG. 2, and does not impose any limitation on the scope of use or functions of the systems and methods described herein. Neither should the computing environment 300 be interpreted as having any dependency or requirement on any component or combination of components shown in the computing environment 300.

[0141] The methods and systems described herein can be operated using numerous other general-purpose or special-purpose computing systems, environments, or configurations. Examples of well-known computing systems, environments and/or configurations suitable for use include, but are not limited to: personal computers, server computers, multi-processor systems, microprocessor-based systems, network PCs, minicomputers, mainframes, including any Distributed computing environment of the above system or equipment, etc. The compact or subset form of the framework can also be implemented in clients with limited resources such as handheld computers or other computing devices. The present invention can be practiced in a distributed computing environment in which tasks are performed by remote processing devices linked through a communication network. In a distributed computing environment, program modules can be located in local and remote memory storage devices.

[0142] Referring to FIG. 3, an exemplary system for digital signatures for network encoding includes a general-purpose computing device in the form of a computer 310 that implements, for example, the system 100 of FIG. 1. The aspects of the computer 310 described below are exemplary implementations of the computing devices 102 and 104 of FIG. 1. The components of the computer 310 may include, but are not limited to, a processing unit 320, a system memory 330, and a system bus 321 that couples various system components including the system memory to the processing unit 320. The system bus 321 may be any of several bus structures, including a memory bus or a memory controller, a peripheral bus, and a local bus using any of various bus architectures. As an example and not a limitation, this type of architecture includes industry standard architecture (ISA) bus, microchannel architecture (MCA) bus, enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and peripheral components Interconnect (PCI) bus (also known as Mezzanine bus).

[0143] The computer 310 generally includes various computer-readable media. The computer-readable medium can be

Any available media accessed by 310, including volatile and non-volatile media, removable and non-removable media. By way of example and not limitation, computer-readable media includes computer storage media and communication media. Computer storage media include volatile and nonvolatile, removable and non-removable media implemented by any method or technology for storing information such as computer readable instructions, data structures, program modules, or other data. Computer storage media include, but are not limited to, RAM, ROM, EEPROM, flash memory or other memory technologies, CD-ROM, digital versatile disk (DVD) or other optical disk storage, magnetic cassettes, magnetic tapes, magnetic disk storage or other magnetic storage devices, or Any other medium that can be used to store the desired information and that can be accessed by the computer 310.

[0144] Communication media usually embody computer readable instructions, data structures, program modules or other data in modulated data signals such as carrier waves or other transmission mechanisms, and include any information delivery media. The term "modulated data signal" refers to a signal that has one or more characteristics set or changed in a manner that encodes the information in the signal. By way of example and not limitation, communication media include wired media, such as a wired network or direct-wired connection, and wireless media, such as acoustic, RF, infrared, and other wireless media. A combination of any of the above should also be included within the scope of computer-readable media.

[0145] The system memory 330 includes computer storage media in the form of volatile and/or nonvolatile memory, such as read only memory (ROM) 331 and random access memory (RAM) 332. The basic input/output system 333 (BIOS) includes basic routines that help transfer information between components in the computer 310 at startup, and it is usually stored in the ROM 331. The RAM 332 generally contains data and/or program modules that are immediately accessible and/or currently operating by the processing unit 320. As an example and not a limitation, FIG. 3 shows an operating system 334, application programs 333, other program modules 336, and program data 337.

[0146] The computer 310 may also include other removable/non-removable, volatile/nonvolatile computer storage media. For example only, FIG. 3 shows a hard disk drive 341 that reads and writes to a non-removable, nonvolatile magnetic medium, a disk drive 331 that reads and writes to a removable, nonvolatile magnetic disk 332, and a A non-volatile optical disc 336, such as a CD ROM or other optical media, an optical disc drive 333 for reading and writing. Other removable/non-removable, volatile/non-volatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, tape cassettes, flash memory cards, digital versatile disks, digital video tapes, solid state RAM, solid state ROM and so on. The hard disk drive 341 is usually connected to the system bus 321 through a non-removable memory interface, such as the interface 340, and the magnetic disk drive 331 and the optical disk drive 333 are usually connected to the system bus 321 through a removable memory interface, such as the interface 330.

[0147] The drive and its associated computer storage medium discussed above and shown in FIG. 3 provide computer 310 with storage of computer readable instructions, data structures, program modules, and other data. For example, in FIG. 3, the hard disk drive 341 is shown to store the operating system 344, application programs 343, other program modules 346, and program data 347. Note that these components may be the same as or different from the operating system 334, application programs 333, other program modules 336, and program data 337. The application program 333 includes, for example, the program module 122 of FIG. 1. The program data 337 includes, for example, the program data 114 of FIG. 1. Here, the operating system 344, the application program 343, the other program modules 346, and the program data 347 are given different numbers to indicate that they are at least different copies.

[0148] The user can input commands and information to the computer 310 through input devices, such as a keyboard 362 and a pointing device 361 (usually a mouse, trackball, or touch pad). Other input devices (not shown) may include microphones, joysticks, game pads, satellite dishes, scanners, and so on. These and other input devices are usually connected to the processing unit 320 through a user input interface 360 coupled to the system bus 321, but may also be connected through other interfaces and bus structures, such as a parallel port, a game port, or a universal serial bus (USB).

[0149] The monitor 391 or other types of display devices are also connected to the system bus through an interface, such as a video interface 390

321. In addition to the monitor, the computer may also include other peripheral output devices, such as a printer 396 and an audio device 397, which are connected through an output peripheral interface 393.

[0150] The computer 310 may use one or more remote computers, such as the logical connection of the remote computer 380, to operate in a networked environment. In one implementation, the remote computer 380 represents the computing device 102 or networked computer 104 of FIG. 1. The remote computer 380 may be a personal computer, a server, a router, a network PC, a peer-to-peer device, or other common network nodes, and as its specific implementation function may include many or all of the elements described with respect to the computer 310, although in FIG. 3 Only the memory storage device 381 is shown in. The logical connection described in FIG. 3 includes a local area network (LAN) 371 and a wide area network (WAN) 373, but may also include other networks. This type of network environment is common in offices, enterprise-wide computer networks, intranets, and the Internet.

[0151] When used in a LAN network environment, the computer 310 is connected to the LAN 371 through a network interface or adapter 370. When used in a WAN network environment, the computer 310 usually includes a modem 372 or other device for establishing communication through the WAN 373, such as the Internet. The modem 372 may be internal or external, and it is connected to the system bus 321 through the user input interface 360 or other appropriate mechanisms. In a networked environment, the program modules or parts thereof described with respect to the computer 310 can be stored in a remote memory storage device. As an example and not a limitation, FIG. 3 shows that the remote application 383 resides on the memory device 381. It can be understood that the network connections shown are exemplary, and other means of establishing a communication link between computers may also be used.

[0152] Conclusion

[0153] Although the system and method for digital signature in network coding are described in a language dedicated to structural features and/or method operations or actions, it is understood that the implementation defined in the appended claims is not necessarily Limited to the specific features or actions described. Rather, the specific features and operations of the system 100 are disclosed as exemplary forms of implementing the claimed subject matter.