SIGNING METHOD DELIVERING A PARTIAL SIGNATURE ASSOCIATED WITH A MESSAGE, THRESHOLD SIGNING METHOD, SIGNATURE VERIFICATION METHOD, AND CORRESPONDING COMPUTER PROGRAM AND ELECTRONIC DEVICES

• US 20150229480A1
• Filed: 02/10/2015
• Published: 08/13/2015
• Est. Priority Date: 02/10/2014
• Status: Active Grant

• Current Assignee: Magnolia Licensing LLC (IP Edge LLC)
• Original Assignee: Thomson Licensing (Vantiva SA)
• Inventors: JOYE, Marc, Libert, Benoit
• Granted Patent: US 9,979,551 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

In one embodiment, it is proposed a signing method delivering a partial signature associated with a message, said partial signature being used in a threshold signing method, the signing method being executed on an electronic device. Such signing method is remarkable in that it comprises signing a hash of said message with a one-time linearly homomorphic structure preserving signature method with a partial secret key, said partial secret key being obtained from an output of a secret sharing scheme, and said signing delivering said partial signature associated with said message.

Claims

1. Signing method delivering a partial signature associated with a message M, said partial signature being used in a threshold signing method, the signing method being executed on an electronic device, and wherein it comprises signing a hash of said message M with a one-time linearly homomorphic structure preserving signature method with a partial secret key, said partial secret key being obtained from an output of a secret sharing scheme, and said signing delivering said partial signature associated with said message M, and wherein said message M is a sequence of binary elements and said hash H(M) belongs to a Cartesian product ^K+1, where is a group and K≧

1.

2. Signing method according to claim 1, wherein said one-time linearly homomorphic structure preserving signature method comprises determining K+1 elements as a function of said hash H(M) and said partial secret key, each of said element belonging to , and said K+1 elements corresponding to said partial signature.

3. Signing method according to claim 1, wherein said determining comprises the determination of said elements being equal to from Π

_k=1^K+1H_k<sup>−

ui(j)[k]</sup> from said partial private key that is equal to SK_j={u₁(j), . . . , u_k+1=(j)}, with u_i(j)ε

_p^K+1, for iε

{1, . . . , K+1} and where H(M)=(H₁, . . . , H_K+1)ε

^K+1.

4. Signing method according to claim 1, wherein said secret sharing scheme is an (t, n) elements Shamir secret sharing scheme.

5. Signing method according to claim 1, wherein said secret sharing scheme is a dynamic secret sharing scheme.

6. Signing method according to claim 5, wherein said dynamic secret sharing scheme is based on Pedersen'"'"'s protocol.

7. Threshold signing method delivering a threshold signature associated with a message M, said signature being obtained from a combination of a set of t+1 partial signatures provided by t+1 devices among n devices, and wherein each partial signature is obtained through the execution of a signing method according to any claims 1 to 6, and said combination is defined as a function of parameters defining a secret sharing scheme, said secret sharing scheme being a (t, n) threshold secret sharing scheme.

8. Threshold signing method according to claim 7, wherein it comprises verifying said t+1 partial signatures from a vector of verification keys, said verifying being done before performing said combination, and comprising a verification of K pairing product equations.

9. Threshold signing method according to claim 7, wherein said combination comprises multiplying elements of said t+1 partial signatures and using Lagrange interpolation in the exponent.

10. Signature verification method of a threshold signature associated with a message M, said threshold signature being obtained from an execution of a threshold signing method of claim 7, and wherein it comprises the verification of K pairing product equations involving public key'"'"'s parameters and an obtained threshold signature.

11. A computer-readable and non-transient storage medium storing a computer program comprising a set of computer-executable instructions to implement a method for cryptographic computations when the instructions are executed by a computer, wherein the instructions comprise instructions, which when executed, configure the computer to perform signing method of claim 1.

12. Electronic device being able to deliver a partial signature associated with a message M, said partial signature being used in a threshold signing method, wherein it comprises a hardware component configured to sign a hash of said message M with a one-time linearly homomorphic structure preserving signature hardware unit with a partial secret key, said partial secret key being obtained from an output of a secret sharing scheme, and said hardware component configured to sign delivering said partial signature associated with said message M and said message M is a sequence of binary elements and said hash H(M) belongs to a Cartesian product ^K+1, where is a group and K≧

1.

13. Electronic device being able to deliver a threshold signature associated with a message M, said signature being obtained from a combination of a set of t+1 partial signatures provided by t+1 devices among r devices, wherein it comprises a hardware module configured to obtain t+1 partial signatures obtained through the electronic device according to claim 12, and it comprises a hardware module configured to combine said set of t+1 partial signatures that is defined as a function of parameters defining a secret sharing scheme, said secret sharing scheme being a (t, n) threshold secret sharing scheme.

14. Electronic device being able to verify a threshold signature associated with a message M, said threshold signature being obtained from an electronic device according to claim 13, wherein it comprises a hardware module configured to perform a verification of K pairing product equations involving public key'"'"'s parameters and an obtained threshold signature.