Method of RSA signature or decryption protected using a homomorphic encryption

1. A method of secure generation of a RSA signature of a message m by a client device with the secure RSA key or of secure RSA decryption by a client device of an RSA encrypted message m encrypted with a public RSA key forming a key pair with a secure private RSA key, comprising the steps of:

receiving from a server a generated encrypted key share components ed j (i) with j in [1, J] and i in [0, n/b−1], the encrypted share components ed j (i) comptuted by the server by:

generating a private RSA key d and a RSA modulus integer N, where N and d are integers;

splitting the private key d in J key shares d j of length n, with n=log 2 N, j in [1, J], J being an integer, and such that d=d 1 +d 2 + . . . +d J mod phi(N), where each key share d j is equal to (d j (0) . . . d j (i) . . . d j (n/b−1) ) with each key share component dj (i) in {0 . . . 2{circumflex over ( )}b−1} and i in [0, n/b−1], b being an integer inferior to n and phi the Euler's totient function whereby i and j form an index couple (i,j);

encrypting with a fully homomorphic encryption (FHE) algorithm each key share component d j (i) of the private RSA key d by using a Fully Homomorphic Encryption secret key p s associated with a set S s comprising the index couple (i,j), to generate an encrypted key share component ed j (i) of said secure RSA key,

said set S s being a set of integer couples, among a predetermined integer number u of disjoint sets {S 1 , S 2 . . . , S S , S S+1 , . . . S u } generated such that: U{S s }={(i,j) such that i in [0, n/b−1], j in [1, J]} and each said set among {S 1 , . . . S u } being associated with a Fully Homomorphic Encryption (FHE) secret key,

the client device, computing an intermediate value Y S for each set S S in {S 1 , . . . , S u } from said encrypted key share components ed j (i) whose index couple (i,j) is comprised in S S and from said message m, such that said computed intermediate value is a part of the RSA signature of said message m, under FHE-encrypted form;

the client device, performing a cryptographic operation selected from generating the RSA signature of said message m by combining said computed intermediate values for all sets or decrypting the encrypted message m by combining said computed intermediate values for all sets.

2. The method of claim 1 wherein said FHE secret keys of said sets are all identical.

3. The method of claim 1 wherein {S 1 , . . . S u } comprises at least a first set and a second set such that the FHE secret key associated with the first set is different from the FHE secret key associated with the second set.

4. The method of claim 1 wherein the fully homomorphic encryption algorithm is a DGHV (Dijik, Gentry, Halevi, Vaikuntanathan) Scheme such that a ciphertext c for a data m in ZN, FHE encrypted with a FHE secret key p, is equal to q·p+N·r+m where q is a random integer, r is a random integer and N is the RSA modulus such that |p|>C S (2 log N+log r) with C S the maximum number of elements of any set S S in {S 1 , . . . , S U }, and such that the ciphertext c is deciphered by computing m=(c mod p) mod N.

5. The method of claim 1 , wherein the order in which intermediate values Y S are computed for every sets S s in {S 1 , . . . , S u } is random.

6. The method of secure generation of an RSA signature of a message m or of secure RSA decryption by a client device of an RSA encrypted message m encrypted with a public RSA key forming a key pair with a secure private RSA key, h(m) d mod N, according to the claim 1 , wherein the computation (T 2 ) of an intermediate value Y S for a set S S in (S 1 , . . . , S u ) comprises:

for all (i,j) in S s , computing z (i) =h(m) (2 {circumflex over ( )} b) {circumflex over ( )} i mod N and computing y j (i) =Σ w=0 2 b −1 (Π v=0,v≠w 2 b −1 (ed j (i) −v)/(w−v))z (i) {circumflex over ( )} w

calculating the product of y j (i) for all (i,j) in the set S s .

7. The method of claim 6 , wherein for each w in [0; 2 b−1 ], the values ed j (i) {circumflex over ( )} w , resulting from the encryption with said FHE algorithm of the value of each key share component d j (i) to the power w d j (i) {circumflex over ( )} w by using the FHE secret key p s of said set S s comprising the index couple (i,j), are computed and stored by the server, and then transmitted to the client device to compute said intermediate values or wherein for each w in [0; 2 b−1 ], the value Π v=0,v≠w 2 b −1 (ed j (i) −v)/(w−v) resulting from the encryption with said FHE algorithm of the value Π v=0,v≠w 2 b −1 (d j (i) −v)/(w−v) by using the FHE secret key p s of said set S s comprising the index couple (i,j), are computed and stored by the server, and then transmitted to the client device to compute said intermediate values.