Signing method delivering a partial signature associated with a message, threshold signing method, signature verification method, and corresponding computer program and electronic devices

• US 9,979,551 B2
• Filed: 02/10/2015
• Issued: 05/22/2018
• Est. Priority Date: 02/10/2014
• Status: Expired due to Fees

• Current Assignee: Magnolia Licensing LLC (IP Edge LLC)
• Original Assignee: Thomson Licensing (Vantiva SA)
• Inventors: Joye, Marc, Libert, Benoit
• Primary Examiner(s): Parsons, Theodore C
• Application Number:
  US14/618,004
• Publication Number:
  US 20150229480A1
• Time in Patent Office: 1,197 Days
• 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. A signing method for delivering a digital partial signature associated with a message M, said digital partial signature being used in a threshold signing method that provides adaptive security in the random oracle model without using reliable erasures at any time, the signing method being executed on an electronic device, wherein the signing method 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;

delivering said digital partial signature associated with said message M, 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; and

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 K+1 elements belonging to , and said K+1 elements corresponding to said digital partial signature, and wherein said determining comprises the determination of said K+1 elements being equal to Π

_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.

2. The signing method according to claim 1, wherein said secret sharing scheme is a (t,n) elements Shamir secret sharing scheme.

3. The signing method according to claim 1, wherein said secret sharing scheme is a dynamic secret sharing scheme.

4. The signing method according to claim 3, wherein said dynamic secret sharing scheme is based on Pedersen'"'"'s protocol.

5. A threshold signing method for delivering a digital threshold signature associated with a message M, said threshold signing method comprising:

generating said digital threshold signature from a combination of a set of t+1 digital partial signatures provided by t+1 devices among n devices, wherein each digital partial signature being obtained through an execution of the signing method according to any of claims 1, and 2 to 4, and wherein said combination is defined as a function of parameters defining a (t,n) threshold secret sharing scheme; and

delivering said digital threshold signature associated with said message M;

and wherein said threshold signing method provides adaptive security in the random oracle model without using reliable erasures at any time.

6. The threshold signing method according to claim 5, comprising:

verifying said t+1 digital partial signatures from a vector of verification keys, said verifying being done before performing said combination and comprising performing a verification of K pairing product equations.

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

8. A digital signature verification method for verifying a digital threshold signature associated with a message M, said digital signature verification method comprising:

obtaining said digital threshold signature through an execution of the threshold signing method of claim 5; and

performing a verification of K pairing product equations involving a public key'"'"'s parameters and said obtained digital threshold signature, and wherein said digital signature verification method provides adaptive security in the random oracle model without using reliable erasures at any time.

9. A non-transitory computer-readable 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, when executed, configure the computer to perform a signing method for delivering a digital partial signature associated with a message M, said digital partial signature being used in a threshold signing method that provides adaptive security in the random oracle model without using reliable erasures at any time, wherein the signing method 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;

delivering said digital partial signature associated with said message M, 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; and

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 K+1 elements belonging to , and said K+1 elements corresponding to said digital partial signature, and wherein said determining comprises the determination of said K+1 elements being equal to Π

_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.

10. An electronic device for delivering a digital partial signature associated with a message M, said digital partial signature being used in a threshold signing method that provides adaptive security in the random oracle model without using reliable erasures at any time, wherein said electronic device 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;

deliver said digital partial signature associated with said message M, 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, and wherein said one-time linearly homomorphic structure preserving signature hardware unit is configured to determine K+1 elements as a function of said hash H(M) and said partial secret key, each of said K+1 elements belonging to , and said K+1 elements corresponding to said digital partial signature, and wherein said one-time linearly homomorphic structure preserving signature hardware unit is further configured to perform the determination of said K+1 elements from determination of Π

_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.

11. An electronic device for delivering a digital threshold signature associated with a message M, wherein said electronic device comprises a hardware component configured to:

generate said digital threshold signature from a combination of a set of t+1 digital partial signatures provided by t+1 devices among n devices, wherein each digital partial signature is obtained from an electronic device according to claim 10, and wherein said combination is defined as a function of parameters defining a (t,n) threshold secret sharing scheme; and

deliver said digital threshold signature associated with said message M,

and wherein said digital threshold signature provides adaptive security in the random oracle model without using reliable erasures at any time.

12. An electronic device for verifying a digital threshold signature associated with a message M, wherein said electronic device comprises a hardware component configured to:

obtain said digital threshold signature from an electronic device according to claim 11; and

perform a verification of K pairing product equations involving a public key'"'"'s parameters and said obtained digital threshold signature, and wherein digital threshold signature verification provides adaptive security in the random oracle model without using reliable erasures at any time.