Method for providing a digital signature to a message

1. 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 k , without revealing k, by performing the steps of:

each of the at least two parties computing a share, R j , of the value, R, as R j =g k_j , and distributing the share to each of the other parties, and

computing the value, R, from the shares, R j ,

ensuring that R is correct by verifying that R=g 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 j , received from the other parties,

computing an authenticator, W, as W=g ak , by computing R a , without revealing a or k, by performing the steps of:

each of the at least two parties computing a share, W j , of the authenticator, W, as W j =R a_j , and distributing the share to each of the other parties, and

computing the authenticator, W, from the shares, W j ,

ensuring that W is correct by verifying that W=R 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 j , received from the other parties,

verifying [w] by checking whether or not g w =W, and

signing the message, M, by computing [k −1 ]=[a]·w −1 , computing [x·k −1 ]=[x]·[k −1 ], and generating a sharing, [s], among the at least two parties, as a function of M, R, [k −1 ] and [x·k −1 ], by computing [s]=m·w −1 ·[a]+r·w −1 ·[a]·[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).

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

3. The method according to claim 1 , further comprising the step of aborting the signing process in the case that the step of verifying [w] reveals that g w ≠W.

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

5. The method according to claim 1 , 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.

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

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

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

9. The method according to claim 7 , wherein the step of verifying the signature comprises checking whether or not R s =g m ·y r .

10. The method according to claim 6 , further comprising the step of checking correctness of y.