Method for generating a message signature from a signature token encrypted by means of a homomorphic encryption function

• US 20160344557A1
• Filed: 05/02/2016
• Published: 11/24/2016
• Est. Priority Date: 05/06/2015
• Status: Active Grant

• Current Assignee: IDEMIA Identity and Security France SAS (Advent International Corporation)
• Original Assignee: Morpho (Advent International Corporation)
• Inventors: MOREL, Constance, CLEMOT, Olivier, CHABANNE, Herve, BRINGER, Julien
• Granted Patent: US 10,326,598 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/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

The invention relates to a method for generating a message signature intended to be validated by a verifier server, a client device being configured to hold a private key and a corresponding public key and comprising steps of:

• • offline precomputation (103) by a hardware security module of a signature token, a result of encryption by means of a homomorphic encryption function,
  • storage (104) of said signature token;
  • generation (105) of said signature of said encrypted message by means of said homomorphic encryption function from the result of the encryption by said homomorphic encryption function of the private key stored by the client device, of the signature token and of said message, said signature being intended to be validated by said verifier server by means of said public key.

Claims

1. A method for generating a signature of a message (m) intended to be validated by a verifier server (3), the signature protocol implemented for generating the signature comprising public parameters (Gr, n, g) such that g is an element of the group Gr of the order n with n a prime integer, a client device (2) being configured to hold a private key (d) and a corresponding public key (y),

said method being characterized in that it comprises steps of:

offline beforehand computation (103) by a hardware security module (4) of a signature token (φ

(r), φ

(1/k)) comprising a first part of signature token φ

(r) and a second part of signature token φ

(1/k), wherein k is a random integer comprised between 1 and n−

1, and r is an intermediate integer defined by r=f(g^k) where f is a function having values in Z_n, and the first part of signature token φ

(r) is generated by encrypting the intermediate integer r by means of said homomorphic encryption function (φ

) and the second part of signature token φ

(1/k) is generated by encrypting the inverse of the random 1/k by means of said homomorphic encryption function (φ

),

storage (104) of said signature token (φ

(r), (φ

(1/k));

generation (105) of said signature (r,s) of said message (m) encrypted by means of said homomorphic encryption function (φ

(r), φ

(s)) from the result (φ

(d)) of the encryption by said homomorphic encryption function of the private key stored by the client device (d), of the signature token (φ

(r), φ

(1/k)) and of said message (m), said signature being intended to be validated by said verifier server (3) by means of said public key (y).

2. The method for generating a signature according to the preceding claim, wherein said hardware security module also previously offline implements steps of:

generation (101) of the random k as integer belonging to [1;

n−

1]; and

computation (102) of the intermediate integer r.

3. The method for generating a signature according to any one of claim 1 or 2 wherein the signature protocol is the ECDSA protocol, the group Gr is the group comprising all the points of an elliptic curve provided with addition, the public key y and the private key d verify y=d*g, g being a point of the elliptic curve of the order n, the function f associates with a point of the elliptic curve the abscissa modulo n of said point, and the intermediate integer r is the abscissa of the point of the elliptic curve k*g modulo n.

4. The method for generating a signature according to one of claim 1 or 2, wherein the signature protocol is the DSA protocol, the group G, is the set Z_p provided with multiplication, where p is a prime integer number such that (p−

1) is a multiple of n, the public key y and the private key d such that 0<

d<

n verify y=g^d mod p, g=h<sup>((p−

1)n)</sup> mod p with h a random integer verifying 1<

h<

p−

1 and g different to 1, the function f is defined by f(x)=x mod n, and the intermediate integer r is r=(g^k mod p) mod n.

5. The method for generating a signature according to one of the preceding claims, wherein the signature of the message m encrypted by means of said homomorphic encryption function comprises a first part of signature encrypted by means of said homomorphic encryption function and generated by means of the formula:

φ

(s)=φ

((1/k)*(z+d.r)) and a second part of signature encrypted by means of said homomorphic encryption function equal to φ

(r), with 1/k the inverse of the random, z function of the message m, d the private key stored by the client device, r the intermediate integer and φ

the homomorphic encryption function.

6. The method for generating a signature according to one of the preceding claims, wherein the signature token further comprises the result φ

(r.1/k) of the encryption by said homomorphic encryption function of the product of the intermediate integer r with the inverse of the random 1/k.

7. The method for generating a signature according to the preceding claim, wherein the signature of the message m encrypted by means of said homomorphic encryption function comprises a first part of signature encrypted by means of said homomorphic encryption function and generated by means of the formula:

φ

(s) =φ

((1/k).z+d.(r.1/k)) and a second part of signature encrypted by means of said homomorphic encryption function equal to φ

(r),

with 1/k the inverse of the random, z function of the message m, d the private key stored by the client device, r the intermediate integer, r.1/k the product of the intermediate integer with the inverse of the random and φ

the homomorphic encryption function.

10. A computer program product comprising program code instructions for executing the steps of the method according to any one of the preceding claims when said program is executed on a computer.

8. The method for generating a signature of a message (m) intended to be validated by a verifier server (3), a client device (2) being configured to hold a private key (d) and a corresponding public key (y) wherein the public key y and the private key d verify y=d*g, g being a point of an elliptic curve of the order n, a prime integer,

said method being characterized in that it comprises steps implemented previously offline by a hardware security module (4) of:

generation (101) of a random k as integer belonging to [1, n−

1],

computation (102) of an intermediate integer r as abscissa of the point of the elliptic curve k*g modulo n;

computation (103) of a signature token (φ

(r), φ

(1/k)) comprising a first part of signature token φ

(r) generated by encrypting the intermediate integer r by means of said homomorphic encryption function (φ

), and a second part of signature token φ

(1/k), generated by encrypting the inverse of the random 1/k by means of said homomorphic encryption function (φ

),

the method further comprising implementing the steps of;

storage (104) of said signature token (φ

(r), φ

(1/k));

generation (105) of said signature (r,s) of said message (m) encrypted by means of said homomorphic encryption function (φ

(r), φ

(s)) from the result (φ

(d)) of the encryption by said homomorphic encryption function of the private key stored by the client device (d), of the signature token (φ

(r), φ

(1/k)) and of said message (m), said signature being intended to be validated by said verifier server (3) by means of said public key (y).

9. The method for generating a signature of a message (m) intended to be validated by a verifier server (3), a client device (2) being configured to hold a private key (d) and a corresponding public key (y), wherein the public key (y) and the private key d such that 0<

d<

n verify y=g^d mod p, n being a prime number, p being a prime number verifying (p−

1) is a multiple of n, g=0^13-1)^/n) mod p with h a random integer verifying 1 <

h<

p−

1 and g different to 1,

said method being characterized in that it comprises steps implemented previously offline by a hardware security module (4) of;

generation (101) of a random k as integer belonging to [1, n−

1],

computation (102) of an intermediate integer r=(g^k mod p) mod n;

computation (103) of a signature token (φ

(r), φ

(1/k)) comprising a first part of signature token φ

(r) generated by encrypting the intermediate integer r by means of said homomorphic encryption function (φ

), and a second part of signature token φ

(1/k), generated by encrypting the inverse of the random 1/k by means of said homomorphic encryption function (φ

),

the method further comprising implementing the steps of;

storage (104) of said signature token (φ

(r), φ

(1/k));

generation (105) of said signature (r,s) of said message (m) encrypted by means of said homomorphic encryption function (φ

(r), φ

(s)) from the result (φ

(d)) of the encryption by said homomorphic encryption function of the private key stored by the client device (d), of the signature token (φ

(r), φ

(1/k)) and of said message (m), said signature being intended to be validated by said verifier server (3) by means of said public key (y).

11. A system (1) for generating a signature of a message (m) intended to be validated by a verifier server (3), the signature protocol implemented for generating the signature comprising public parameters (Gr, n, g) such that g is an element of the group Gr of the order n with n a prime integer, a client device (2) being configured to hold a private key (d) and a corresponding public key (y), said system comprising:

a hardware security module (4) configured to compute beforehand, offline, a signature token (φ

(r), φ

(1/k)) comprising a first part φ

(r) of signature token and a second part φ

(1/k) of signature token, wherein k is a random integer comprised between 1 and n−

1, and r is an intermediate integer defined by r=f(g^k) where f is a function having values in Z_n, and the first part of signature token φ

(r) is generated by encrypting the intermediate integer r by means of said homomorphic encryption function (φ

) and the second part of signature token φ

(1/k) generated by encrypting the inverse of the random 1/k by means of said homomorphic encryption function (φ

),

a storage device (8 ) of said signature token (φ

(r), φ

(1/k)),

an intermediate server (7) or said hardware security module (4) configured to generate said signature (r,s) of said message (m) encrypted by means of said homomorphic encryption function (φ

(r), φ

(s)) from the result (φ

(d)) of the encryption by said homomorphic encryption function (φ

) of the private key stored by the client device (d), of the signature token (φ

(r), φ

(1/k)) and of said message (m),

a verifier server (3) configured to validate said signature by means of said public key (y).