Digital signatures with re-randomized presignatures

1 . A computer-implemented method for performing a digital signature according to a public key signature scheme, the method comprising:

computing a presignature;

receiving a signing request to perform the digital signature on a message;

re-randomizing the presignature comprising

computing a non-predictable public re-randomization value; and

utilizing the non-predictable public re-randomization value for the re-randomizing of the presignature, wherein the non-predictable public re-randomization value is generated after receiving the signing request; and

performing the digital signature on the message with the re-randomized presignature.

2 . The computer-implemented method according claim 1 , wherein

computing the presignature comprises computing a random nonce; and

re-randomizing the presignature comprises re-randomizing the nonce.

3 . The computer-implemented method according to claim 1 , wherein re-randomizing the presignature comprises performing an algebraic operation on the presignature.

4 . The computer-implemented method according to claim 1 , wherein re-randomizing the presignature comprises performing a linear operation on the presignature.

5 . The computer-implemented method according to claim 1 , wherein the digital signature is a threshold signature.

6 . The computer-implemented method according to claim 1 , further comprising performing a pseudo-random generation of the non-predictable public re-randomization value.

7 . The computer-implemented method according to claim 1 , wherein computing the non-predictable public re-randomization value comprises deriving the non-predictable public re-randomization value by applying a hash function to at least the message or a hash of the message, or applying the hash function to the public key of the digital signature and/or to other inputs.

8 . The computer-implemented method according to claim 1 , wherein computing the non-predictable public re-randomization value comprises deriving the non-predictable public re-randomization value from a random beacon.

9 . The computer-implemented method according to claim 1 , wherein the digital signature is a digital signature according to a signature algorithm based on discrete logarithms.

10 . The computer-implemented method according to claim 1 , wherein the digital signature is a digital signature according to a signature algorithm based on elliptic curves, the digital signature algorithm comprising Elliptic Curve Digital Signature Algorithm (ECDSA).

11 . The computer-implemented method according to claim 10 , wherein the digital signature algorithm operates on an elliptic curve E generated by a point G of order q, in particular prime order q, and wherein

computing the presignature comprises

generating a random element r′ by:

r

′

→

Z

q

*

;

and

computing

R

′

←

r

′

⁢

G

∈

E

;

wherein re-randomizing the presignature comprises computing

r

:=

r

′

+

δ

;

R

:=

R

′

+

δ

⁢

G

;

wherein δ is the non-predictable public value.

12 . The computer-implemented method according to claim 1 , the method further comprising:

providing a master secret key pair, the master secret key pair comprising a first master secret key and a second master secret key;

providing a master public key pair, the master public key pair comprising a first master public key and a second master public key′;

deriving a secret subkey from the master secret key pair; and

deriving a public subkey from the master public key pair.

13 . The computer-implemented method according to claim 12 , wherein

deriving the secret subkey from the master secret key pair comprises performing a first algebraic operation on the master secret key pair; and

deriving the public subkey from the master public key pair comprises performing a second algebraic operation on the master public key pair, wherein the first algebraic operation and the second algebraic operation are linear operations.

14 . The computer-implemented method according to claim 12 , wherein

deriving the secret subkey from the master secret key pair comprises performing a mixed key derivation such that the secret subkey depends on both the first master secret key and the second master secret key and the public subkey depends on both the first master public key and the second master public key.

15 . The computer-implemented method according to claim 12 , wherein the digital signature algorithm operates on an elliptic curve E defined over Z p and generated by a point G of order q, in particular prime order q,

wherein

(

D

,

D

′

)

:=

(

dG

,

d

′

⁢

G

)

;

 and

wherein

D is the first master public key;

D′ is the second master public key

d is the first master secret key;

d′ is the second master secret key;

the method further comprising:

providing a discriminant e, wherein the discriminant e∈Z q ;

deriving the secret subkey from the master secret key pair by computing

d″:=d+ed′; and

deriving the public subkey D″ from the master public key pair by computing D″:=D+eD′, wherein

D is the first master public key;

D′ is the second master public key;

d is the first master secret key;

d′ is the second master secret key;

d″ is the secret subkey; and

D″ is the public subkey;

wherein the method further comprises deriving the discriminant e by a hash function, wherein the hash function is applied on a set of hash input data, the hash input data comprising an arbitrary identifier, the master public key pair and/or further input data, wherein the arbitrary identifier uniquely identifies ownership and/or context of the public subkey or the secret subkey.

16 . The computer-implemented method according to claim 1 , further comprising:

providing a master key pair comprising a master public key and a master secret key;

deriving subkey pairs comprising a public subkey and a secret subkey from the master key pair by applying an additive shift operation on the master key pair.

17 . The computer-implemented method according to claim 16 , comprising:

providing a discriminant e, in particular a discrimant e∈Z q ;

computing the secret subkey by

d′:=d+e; and

computing the public subkey by

D

′

:=

D

+

eG

.

18 . A computing system for performing a digital signature according to a public key signature scheme, the computing system comprising a processor and a memory, wherein the computing system is configured to

compute a presignature;

receive a signing request to perform the digital signature on a message;

re randomize the presignature, wherein to re-randomize the presignature, the computing system is to

compute a non-predictable public re-randomization value; and

utilize the non-predictable public re-randomization value for the re-randomizing of the presignature, wherein the non-predictable public re-randomization value is generated after receiving the signing request; and

perform the digital signature on the message with the re-randomized presignature.

19 . A computer program product for performing a digital signature according to a public key signature scheme, the computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computing system to cause the computing system to perform a method comprising:

computing a presignature;

receiving a signing request to perform the digital signature on a message;

re-randomizing the presignature comprising

computing a non-predictable public re-randomization value; and

utilizing the non-predictable public re-randomization value for the re-randomizing of the presignature, wherein the non-predictable public re-randomization value is generated after receiving the signing request; and

performing the digital signature on the message with the re-randomized presignature.