A METHOD FOR PROVIDING A DIGITAL SIGNATURE TO A MESSAGE

Abstract

A method for providing a digital signature to a message, M, in accordance with a digital signature algorithm (DSA) or an elliptic curve digital signature algorithm (ECDSA) is disclosed. A secret key, x, is generated as a random secret sharing [x] among at least two parties, such as among at least three parties. Random secret sharings, [a] and [k], are generated among the at least two parties and [w]=[a][k], R=g.sup.k and W=R.sup.a are computed and their correctness verified. [w] is verified by checking whether or not g.sup.w=W. The message, M, is signed by generating a sharing, [s], among the at least two parties, using at least M, [w], R and [x].

Claims

1-12. (canceled)

13. A method for providing a digital signature to a message, M, in accordance with a digital signature algorithm, DSA, or an elliptic curve digital signature algorithm, ECDSA, the method comprising the steps of: providing a generator, g, for a cyclic group, G, of order q, where g∈G, a function, F, and a function, H, where g, G, F and H are specified by the DSA or ECDSA, generating a secret key, x, as a random secret sharing [x] among at least two parties, generating random secret sharings, [a] and [k], among the at least two parties and computing [w]=[a][k], computing a value, R, as R=g.sup.k, without revealing k, by performing the steps of: each of the at least two parties computing a share, R.sub.j, of the value, R, as R.sub.j=g.sup.k_j, and distributing the share to each of the other parties, and computing the value, R, from the shares, R.sub.j, ensuring that R is correct by verifying that R=g.sup.k is computed from at least t+1 shares of [k] originating from honest parties, by each of the parties checking that R is correct, based on the shares, R.sub.j, received from the other parties, computing an authenticator, W, as W=g.sup.ak, by computing R.sup.a, without revealing a or k, by performing the steps of: each of the at least two parties computing a share, W.sub.j, of the authenticator, W, as W.sub.j=R.sup.a_j, and distributing the share to each of the other parties, and computing the authenticator, W, from the shares, W.sub.j, ensuring that W is correct by verifying that W=R.sup.a is computed from at least t+1 shares of [a] originating from honest parties, by each of the parties checking that W is correct, based on the shares, W.sub.j, received from the other parties, verifying [w] by checking whether or not g.sup.w=W, and signing the message, M, by computing [k.sup.−1]=[a].Math.w.sup.−1, computing [x.Math.k.sup.−1]=[x].Math.[k.sup.−1], and generating a sharing, [s], among the at least two parties, as a function of M, R, [k.sup.−1] and [x.Math.k.sup.−1], by computing [s]=m.Math.w.sup.−1.Math.[a]+r.Math.w.sup.−1.Math.[a].Math.[x]+[d], where r=F(R), m=H(M), and [d] is a random sharing of zero, where s forms part of a signature pair (r, s).

14. The method according to claim 13, further comprising the step of aborting the signing process in the case that it is revealed that R or W is incorrect.

15. The method according to claim 13, further comprising the step of aborting the signing process in the case that the step of verifying [w] reveals that g.sup.w≈W.

16. The method according to claim 13, wherein the step of signing a message, M, is performed by computing [s]=m.Math.w.sup.−1.Math.[a]+r.Math.w.sup.−1.Math.[a].Math.[x]+[d]+m.Math.[e], where r=F(R), m=H(M), and [d] and [e] are random sharings of zero.

17. The method according to claim 13, wherein at least the steps of generating a secret key, x, generating random secret sharings, [a] and [k], computing a value, R, and computing an authenticator, W, are performed by pre-processing, prior to generation of the message, M.

18. The method according to claim 13, further comprising the step of computing a public key, y, as y=g.sup.x, and revealing y to each of the at least two parties.

19. The method according to claim 18, further comprising the step of verifying the signature, using the public key, y.

20. The method according to claim 19, wherein the step of verifying the signature comprises checking whether or not r=F(g.sup.m/s.Math.y.sup.r/s)

21. The method according to claim 19, wherein the step of verifying the signature comprises checking whether or not R.sup.s=g.sup.m.Math.y.sup.r.

22. The method according to claim 18, further comprising the step of checking correctness of y.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0084] The invention will now be described in further detail with reference to the accompanying drawings in which

[0085] FIG. 1 is a block diagram illustrating key generation and signature generation using a method according to a first embodiment of the invention,

[0086] FIG. 2 is a block diagram illustrating key generation using a method according to a second embodiment of the invention,

[0087] FIG. 3 is a block diagram illustrating signature generation using a method according to a third embodiment of the invention,

[0088] FIG. 4 is a block diagram illustrating signature generation using a method according to a fourth embodiment of the invention,

[0089] FIG. 5 is a block diagram illustrating key generation and signature generation using a method according to a fifth embodiment of the invention, and

[0090] FIG. 6 is a flow chart illustrating a method according to an embodiment of the invention.

DETAILED DESCRIPTION OF THE DRAWINGS

[0091] FIG. 1 is a block diagram illustrating key generation and signature generation using a method according to a first embodiment of the invention. The method involves the use of three parties, P1, P2 and P3, being individual or separate in the sense that information being available to one of the parties P1, P2, P3 may not be available to the other parties P1, P2, P3. The parties P1, P2, P3 may, e.g., be in the form of physically separated hardware servers. In this example the security threshold (t) is 1, i.e., if one of the parties P1, P2, P3 is malicious, that party will not be able to learn any information about x or otherwise be able to sign a message M with the secret key x unless the other (honest) parties agree to sign M.

[0092] A client 1 sends a request, KeyGen, to each of the parties P1, P2, P3, requesting that the parties P1, P2, P3 generate a key pair, ([x], y), comprising a secret key, [x], and a public key, y. The client 1 is arranged in the environment surrounding a system including the three parties P1, P2, P3, i.e. the client does not form part of the system which is to generate the key and the signature.

[0093] In response to receipt of the request KeyGen, the three parties P1, P2, P3 generate a secret key, [x], as a random secret sharing among the three parties P1, P2, P3. This may include several rounds of interaction between the parties P1, P2, P3, and it may, e.g., be performed in the manner described below with reference to FIG. 2. As a result, each of the parties P1, P2, P3 holds a share, x1, x2, x3 of the secret key x, but none of the parties P1, P2, P3 is in the possession of the entire secret key x.

[0094] The three parties P1, P2, P3 further compute a public key, y, as y=g.sup.x. The public key, y, is made public in the sense that each of the parties P1, P2, P3 is in the possession of y, and in the sense that y is communicated to the client 1 by each of the parties P1, P2, P3. Thus, y=gX is made public or ‘opened’, but x remains secret.

[0095] In the case that none of the parties P1, P2, P3 is malicious or corrupted, the public key, y, communicated to the client 1 by each of the parties P1, P2, P3 will be the same, i.e. the client 1 will receive three identical version of y from the three parties P1, P2, P3. Thus, if the client 1 receives three identical versions of y, it can conclude that none of the parties P1, P2, P3 is malicious or corrupted, i.e. that all of the parties P1, P2, P3 have acted correctly so far. On the other hand, in the case that the three versions of y received from the three parties P1, P2, P3 differ from each other, it can be concluded that at least one of the parties P1, P2 or P3 is malicious or corrupted. In that case the client 1 causes the process to abort.

[0096] When the key pair, ([x], y), has been generated, a signature process, which applies the generated key pair, ([x], y), is initiated by the client 1 sending a request, Sign, and a message, M, to be signed to each of the parties, P1, P2, P3.

[0097] In response to receipt of the request, Sign, and the message, M, the parties P1, P2, P3 engage in a signature generation process which may require several rounds of interaction among the parties and in which each party P1, P2, P3 applies its share x1, x2, x3 of [x] without revealing the share x1, x2, x3 to the other parties. At the end of the signature generation process, each party P1, P2, P3 is in the possession of a value R and a share, s1, s2, s3 of [s]. The signature generation process could, e.g., be performed in the manner described below with reference to FIG. 3.

[0098] Each of the parties P1, P2, P3 then returns R and its share, s1, s2 or s3, of [s] to the client 1. In response thereto the client 1 computes s from the received shares s1, s2, s3, e.g. using interpolation. Furthermore, the client 1 computes r=F(R), and may accept (r, s) as a valid signature only if identical versions of R are received from at least two of the three parties P1, P2, P3. Furthermore, an additional verification check, e.g. validating that R.sup.s=g.sup.m.Math.y.sup.r, may be performed by the client 1, in order for it to accept the signature, (r, s) as a valid signature.

[0099] FIG. 2 is a block diagram illustrating key generation using a method according to a second embodiment of the invention. The key generation illustrated in FIG. 2 may, e.g., be applied as part of the method illustrated in FIG. 1.

[0100] In the embodiment illustrated in FIG. 2, three parties P1, P2, P3 cooperate in computing a key pair ([x], y), where [x] is a secret key in the form of a secret sharing among the three parties P1, P2, P3, and y is a public key. According to this embodiment the shares are Shamir secret shares, and the security threshold is one, i.e., t=1.

[0101] In a first round of interactions between the parties P1, P2, P3, the secret key, [x], is generated as a random degree t Shamir secret sharing among the parties P1, P2, P3. To this end, each party P1, P2, P3 generates three random values, one for itself and one for each of the other parties P1, P2, P3, and forwards the generated values to the respective other parties P1, P2, P3. Thus, party P1 generates value x1,1 and keeps it for itself, generates value x1,2 and forwards it to party P2, and generates value x1,3 and forwards it to party P3. Similarly, party P2 generates value x2,1 and forwards it to party P1, generates value x2,2 and keeps it for itself, and generates value x2,3 and forwards it to party P3. Finally, party P3 generates value x3,1 and forwards it to party P1, generates value x3,2 and forwards it to party P2, and generates value x3,3 and keeps it for itself.

[0102] Thus, at the end of the first round of interaction among the parties P1, P2, P3, each party P1, P2, P3 is in the possession of three random values, i.e. a value generated by itself and a value received from each of the other parties P1, P2, P3. Based on these three values, each of the parties P1, P2, P3 generates a share, x1, x2, x3, of [x].

[0103] In a second round of interaction among the parties P1, P2, P3, the parties P1, P2, P3 compute a public key, y. To this end, each party computes yi=g.sup.xi, where g is a generator for a cyclic group, G, yi is a value generated by party Pi, and xi is the share of [x] being held by party Pi. Furthermore, each of the parties P1, P2, P3 communicates the value yi to each of the other parties P1, P2, P3. Thus, party P1 computes y1=g.sup.x1 and communicates y1 to parties P2 and P3, etc. Accordingly, each of the parties P1, P2, P3 is now in the possession of each of the three values, y1, y2 and y3.

[0104] Each of the parties P1, P2, P3 then checks that the values yi received from the other two parties are trustworthy. This may, e.g., include performing interpolation in the exponent. In the case that one of the parties P1, P2, P3 concludes that the value yi received from at least one of the other parties is not trustworthy, that party P1, P2, P3 outputs an ‘abort’ signal, and the signing process is consequently aborted.

[0105] In the case that none of the parties P1, P2, P3 outputs an ‘abort’ as described above, the signing process is allowed to continue, and each of the parties P1, P2, P3 generates a public key, y, based on the values y1, y2 and y3, and using interpolation. According to the DSA/ECDSA standard, y=1 is an illegal public key, and hence the process should be aborted if this is the case. It is noted that if the protocol aborts, it may be restarted, resulting in another key pair being generated. If it was found that y≈1, each of the parties P1, P2, P3 then forwards an ‘OK’ signal to each of the other parties P1, P2, P3, as part of a third round of interaction among the parties P1, P2, P3. Each of the parties P1, P2, P3 accepts its own version of y only if it receives an ‘OK’ signal from each of the other parties P1, P2, P3. Otherwise the signing process will be aborted.

[0106] In the case that ‘OK’ signals are received from the other parties P1, P2, P3 as described above, the public key, y, is output.

[0107] FIG. 3 is a block diagram illustrating signature generation using a method according to a third embodiment of the invention. As in FIG. 2, the secret sharings are Shamir sharings and the security threshold is one (t=1). The process starts in FIG. 3a and continues in FIG. 3b. The signature generation illustrated in FIG. 3 may, e.g., be applied as a part of the method illustrated in FIG. 1.

[0108] In the embodiment illustrated in FIG. 3, three parties P1, P2, P3 cooperate in generating a signature (r, s) for a message, M, using a secret key, [x], in the form of a secret sharing among the three parties, P1, P2, P3. The secret key, [x], could, e.g., be generated as a degree t Shamir sharing in the manner described above with reference to FIG. 2.

[0109] In a first round of interaction among the parties P1, P2, P3, illustrated in FIG. 3a, the parties generate random degree t secret sharings, [k] and [a]. This is performed essentially in the manner described above with reference to FIG. 2 with regard to the generation of [x]. The parties also generate three random degree 2t zero sharings, [b], [d], and [e], i.e. blinding sharings. Thus, at the end of the first round of interaction among the parties P1, P2, P3, each party P1, P2, P3 holds a share of each of [k], [a], [b], [d] and [e], and none of the parties P1, P2, P3 is in the possession of any information about the secrets a and k.

[0110] Next, in a second round of interaction among the parties P1, P2, P3, also illustrated in FIG. 3a, each of the parties P1, P2, P3 computes a value Ri as Ri=g.sup.ki, where g is a generator for a cyclic group, G, Ri is the value computed by party Pi, and ki is the share of [k] being held by party Pi. Thus, party P1 computes R1=g.sup.k1, party P2 computes R2=g.sup.k2, and party P3 computes R3=g.sup.k3.

[0111] Furthermore, each of the parties P1, P2, P3 computes a value wi as wi=ki.Math.ai+bi, where wi is the value computed by party Pi, and ki, ai and bi are the shares of [k], [a] and [b], respectively, being held by party Pi. Thus, party P1 computes w1=k1.Math.a1+b1, party P2 computes w2=k2.Math.a2+b2, and party P3 computes w3=k3.Math.a3+b3. The shares w1, w2, w3 held by the parties form a degree 2t Shamir sharing [w] where w equals ak if all parties performed the prescribed actions correctly.

[0112] Each of the parties then reveals the computed values Ri and wi to each of the other parties. Thus, each of the parties P1, P2, P3 is now in the possession of each of the three values R1, R2 and R3, and each of the three shares w1, w2 and w3, and accordingly R=g.sup.k and w=k.Math.a+b are now known by each of the parties P1, P2, P3, even though each of k and a remains secret. This may be referred to as ‘opening’ R and w. The sharing [b] may be referred to as a ‘blinder sharing’, since adding it to [ak] does not change the secret, but ‘blinds’ the individual shares of the sharing [ak], thereby making it impossible to derive any information about a or k from seeing the shares of [ak] except the product ak.

[0113] At the end of the second round of interaction among the parties P1, P2, P3, each of the parties P1, P2, P3 checks correctness of R. This is done based on the received values R1, R2 and R3, and using interpolation in the exponent. In the case that at least one of the parties P1, P2, P3 finds that R is incorrect, the process is aborted. Otherwise, the process continues.

[0114] Next, in a third round of interaction among the parties P1, P2, P3, illustrated in FIG. 3b, each of the parties P1, P2, P3 computes a value, Wi as Wi=R.sup.ai, where Wi is the value computed by party Pi, and ai is the share of [a] being held by party Pi. Furthermore, each party P1, P2, P3 reveals the computed values Wi to each of the other parties P1, P2, P3. Accordingly, each of the parties P1, P2, P3 is now in the possession of each of the values W1, W2, W3, and by using interpolation in the exponent W=R.sup.a can be computed by each of the parties P1, P2, P3, while the value a remains secret. This may be referred to as ‘opening’ W.

[0115] At the end of the third round of interaction among the parties P1, P2, P3, each of the parties P1, P2, P3 checks correctness of W, based on the received values W1, W2, W3, and using interpolation in the exponent. This is done using the values Wi in the same manner as correctness of R was checked using the values Ri in the second round of interaction. In the case that at least one of the parties P1, P2, P3 finds that W is incorrect, the process is aborted. Otherwise, the process is continued.

[0116] Finally, in a fourth round of interaction among the parties P1, P2, P3, each of the parties P1, P2, P3 computes w, based on the values w1, w2 and w3, and using interpolation.

[0117] Furthermore, each of the parties P1, P2, P3 verifies w by checking that W=g.sup.w. As described above, it is enforced that W=R.sup.a and R=g.sup.k. If this was not the case, the process would have aborted previously. It follows from this that W=g.sup.ka. So by checking that g.sup.w=W, it is ensured that w=a.Math.k. It is noted that [w] was computed, not as [a][k], but as [a][k]+[b], but since [b] is a sharing of zero, i.e. [b]=[0], adding [b] makes no difference for this check.

[0118] In the case that at least one of the parties P1, P2, P3 finds that W≈g.sup.w, then the signature process is aborted. Otherwise the process is continued, and each of the parties P1, P2, P3 computes a share si of a sharing [s] as:

si=m.Math.hi+r.Math.hi.Math.xi+m.Math.di+ei

where:

hi=ai.Math.w.sup.−1, [0119] r=F(R), where F is a predefined function, and [0120] m=H(M), where M is the message to be signed and H is a predefined function.

[0121] xi, di and ei are the shares of [x], [d] and [e], respectively, being held by party Pi. When each party computes its share si as described, it means that the parties collectively perform the computation [s]=m[k.sup.−1]+r[k.sup.−1][x]+m[d]+[e]. If all parties performs the actions as prescribed, this results in [s]=[k.sup.−1(m+rx)], i.e., s=k.sup.−1(m+rx) as required by DSA or ECDSA.

[0122] Each of the parties P1, P2, P3 reveals the share si to each of the other parties P1, P2, P3, and each of the parties P1, P2, P3 computes s using interpolation based on the received shares s1, s2, and s3 and then checks correctness of s by verifying the signature on the message M using the public key y, i.e., by checking that R=g.sup.m.Math.y.sup.r. If correctness of s is confirmed, the signature (r, s) is accepted as the final signature of the message, M.

[0123] FIG. 4 is a block diagram illustrating signature generation using a method according to a fourth embodiment of the invention. The process illustrated in FIG. 4 includes six rounds of interaction among three parties P1, P2, P3. The first three rounds of interaction among the parties P1, P2, P3 are identical to the first three rounds of interaction illustrated in FIG. 3 and described above.

[0124] In a fourth round of interaction among the parties P1, P2, P3, only party P1 computes s1 in the manner described above with reference to FIG. 3, i.e.:

s1=m.Math.h1+r.Math.h1.Math.x1+m.Math.d1+e1.

[0125] P1 then forwards s1 to party P2, and in a fifth round of interaction among the parties P1, P2, P3, party P2 computes s2 in the manner described above with reference to FIG. 3, and forwards s1 and s2 to party P3.

[0126] In a sixth round of interaction among the parties P1, P2, P3, party P3 computes s3 in the manner described above with reference to FIG. 3, and computes s based on the three shares s1, s2 and s3, and using interpolation. Party P3 then checks correctness of s, and ifs is correct, the signature (r, s) is accepted by party P3 as the resulting signature (r, s) of the message M.

[0127] Thus, in the embodiment illustrated in FIG. 4, the signature (r, s) is only received by party P3, whereas each of the parties P1, P2, P3 receives the signature (r, s) in the embodiment illustrated in FIG. 3. An embodiment like this may be practical, since in the online phase, each party P1, P2, P3 needs only send a single message to one party, whereas in the embodiment of FIG. 3, each party has to send a message to each of the other parties.

[0128] FIG. 5 is a block diagram illustrating key generation and signature generation using a method according to a fifth embodiment of the invention. The embodiment illustrated in FIG. 5 is very similar to the embodiment illustrated in FIG. 1, and it will therefore not be described in detail here.

[0129] However, in the embodiment illustrated in FIG. 5, the process is initiated by one of the parties, party P1, rather than by an external client. Thus, party P1 performs the steps which are performed by the client in the embodiment of FIG. 1, as well as the steps performed by party P1 in the embodiment of FIG. 1.

[0130] FIG. 6 is a flow chart illustrating a method according to an embodiment of the invention. The process is started in step 2. In step 3, a cyclic group, G, and a generator, g, for the cyclic group, G, are defined. Furthermore, functions F and H are defined. G, g, F and H are all specified by a digital signature algorithm (DSA) or an elliptic curve digital signature algorithm (ECDSA) which is to be used for generating the digital signature.

[0131] In step 4 a random secret sharing [x] is generated among at least two parties, where x is a secret key.

[0132] In step 5 random secret sharings [a] and [k] are generated among the at least two parties.

[0133] In step 6 the parties compute [w]=[a].Math.[k], and in step 7 the parties compute a value, R=g.sup.k. R may, e.g., be computed by each of the parties computing a share, as R.sub.j, as R.sub.j=g.sup.k_j, where k_j is the share of [k] being held by party j, and computing the value, R, from the shares, R.sub.j.

[0134] In step 8 it is investigated whether or not R is correct. If this is not the case, the process is forwarded to step 9, where the signing process is aborted, and the process is returned to step 5 in order to generate new secret sharings [a] and [k].

[0135] In the case that step 8 reveals that R is correct, the signing process is allowed to continue, and the process is forwarded to step 10, where the parties compute an authenticator, W=g.sup.ak. This is done by computing R.sup.a.

[0136] In step 11 it is investigated whether or not W is correct. If this is not the case the process is forwarded to step 9, where the signing process is aborted, and the process is returned to step 5 in order to generate new secret sharings [a] and [k].

[0137] In the case that step 11 reveals that W is correct, the process is forwarded to step 12, where it is investigated whether or not g.sup.w=W. Since W=R.sup.a and R=g.sup.k, then W=g.sup.ak. Since w=a.Math.k, g.sup.w=W if w has been correctly computed. Thus, if it can be verified that g.sup.w=W it can be concluded that w has been correctly computed. Thus, in the case that step 12 reveals that g.sup.wW, the process is forwarded to step 9, where the signing process is aborted, and the process returns to step 5 in order to generate new secret sharings [a] and [k].

[0138] In the case that it is verified in step 12 that g.sup.w=W, the process is forwarded to step 13, where a sharing [s] is generated among the parties, and a signature is applied to the message. Finally, the process is ended in step 14.