Method for enhancing security of public key encryption schemas

• US 20040120519A1
• Filed: 01/20/2004
• Published: 06/24/2004
• Est. Priority Date: 12/18/2000
• Status: Active Grant

• Current Assignee: Gemalto SA (Thales SA)
• Original Assignee: Gemalto SA (Thales SA)
• Inventors: Paillier, Pascal, Joye, Marc, Coron, Jean-Sebastien
• Granted Patent: US 7,424,114 B2
• Time in Patent Office: Days
• US Class Current: 380/30
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy

Abstract

There exist numerous public key probabilistic encryption algorithms. Most of said algorithms do not have a maximum security level against someone capable of chosen ciphertext attacks. The method consists in a construct enabling to enhance the security of any public key probabilistic or deterministic encryption algorithm to achieve optimal security level.

Claims

1. A public key encryption method taking at the input a message M to be encrypted and the public key pk and returning at the output the encrypted message C, said method using a public key probabilistic encryption algorithm EP taking at the input a message mp and a random number u and returning at the output an encrypted item cp, said method also using a secret key encryption algorithm ES taking at the input a message ms and returning at the output an encrypted item cs, said public key probabilistic encryption method using the key pk for encrypting a message, also using a hash function F taking at the input a random number r and the message M, a hash function G and a hash function H, characterised in that it comprises the following eight steps:

a) Randomly generating a random number r;

b) Applying the hash function F to the message M and to the random number r in order to obtain s;

c) Applying the hash function H to s and performing an Exclusive OR of the result with r in order to obtain t;

d) Defining the intermediate message w=s∥

t, where ∥

denotes the concatenation of two bit strings;

e) Applying the encryption algorithm EP to the intermediate message w and to a random number u in order to obtain c1, using the public key pk;

f) Applying the hash function G to w and c1 in order to obtain k;

g) Applying the encryption algorithm ES to the message M using the key k in order to obtain the encrypted item c2;

h) The encrypted message C is C=c1∥

c2.

2. A public key decryption method corresponding to the public key encryption method according to claim 1, said method taking at the input an encrypted message C and the private key sk, sk corresponding to the public key pk of the probabilistic encryption algorithm EP, and returning at the output the plain text message M, said method being characterised in that it comprises the following steps:

i) Splitting the encrypted message C into c1 and c2;

j) Applying to cl a decryption algorithm EP<sup>−

1</sup> corresponding to the encryption algorithm EP, using a private key sk in order to obtain the intermediate message w=s∥

t;

k) Applying the hash function G to w and c1 in order to obtain k;

l) Applying the decryption algorithm ES<sup>−

1</sup> corresponding to the encryption algorithm ES to the encrypted message c2 using the key k in order to obtain the message M;

m) Applying the hash function H to s and performing an Exclusive OR with t in order to obtain r;

n) Applying the hash function F to the message M and to the random number r in order to obtain s′

;

o) Verifying that s′

=s;

If s′ and

s are different, rejecting the encrypted message C;

Otherwise, going to step h;

p) Returning the plain text message M.

5. A method according to claims 1 and 3, characterised in that the steps d are replaced by the calculation w=i∥

s∥

t or w=s∥

i∥

t or w=s∥

t∥

i, where i is any value which may contain useful information like for example the binary size of the message M or the identity of the entity which encrypted M and sent the encrypted message C.

6. A method according to claims 2 and 4, characterised in that the steps b make it possible to obtain w=i∥

s∥

t or w=s∥

i∥

t or w=s∥

t∥

i, and deduce therefrom the value i for any calculation or verification purpose.

7. A method according to claims 1 and 3, characterised in that the secret key encryption algorithm ES is replaced in the steps g of claim 1 and g of claim 3 by an Exclusive OR operation between the message M to be encrypted and the key k, in order to obtain the encrypted item c2.

8. A method according to claims 2 and 4, characterised in that the secret key decryption algorithm ES⁻

1 is replaced in the steps d of claim 2 and d of claim 4 by an Exclusive OR operation between the message c2 to be encrypted and the key k, in order to obtain the encrypted item M.

9. A method according to any one of the preceding claims, characterised in that the method is used in a portable electronic object of the smart card type.

3. A public key encryption method taking at the input a message M to be encrypted and the public key pk and returning at the output the encrypted message C, said method using a public key deterministic encryption algorithm EP taking at the input a message mp and returning at the output an encrypted item cp, said method also using a secret key encryption algorithm ES taking at the input a message ms and returning at the output an encrypted item cs, said public key deterministic encryption method using the key pk for encrypting a message, also using a hash function F taking at the input a random number r and the message M, a hash function G and a hash function H, characterised in that it comprises the following nine steps:

i) Randomly generating a random number r;

j) Applying the hash function F to the message M and to the random number r in order to obtain s;

k) Applying the hash function H to s and performing an Exclusive OR of the result with r in order to obtain t;

l) Defining the intermediate message w=s∥

t, where ∥

denotes the concatenation of two bit strings;

m) Applying the encryption algorithm EP to the intermediate message w in order to obtain c1, using the public key pk;

n) Applying the hash function G to w and c1 in order to obtain k;

o) Applying the encryption algorithm ES to the message M using the key k in order to obtain the encrypted item c2;

p) The encrypted message C is C=c1∥

c2.

4. A public key decryption method corresponding to the public key encryption method according to claim 3, said method taking at the input an encrypted message C and the private key sk, sk corresponding to the public key pk of the deterministic encryption algorithm EP, and returning at the output the plain text message M, said method being characterised in that it comprises the following steps:

i) Splitting the encrypted message C into c1 and c2;

j) Applying to c1 a decryption algorithm EP<sup>−

1</sup> corresponding to the encryption algorithm EP, using a private key sk in order to obtain the intermediate message w=s∥

t;

k) Applying the hash function G to w and c1 in order to obtain k;

l) Applying the decryption algorithm ES<sup>−

1</sup> corresponding to the encryption algorithm ES to the encrypted message c2 using the key k in order to obtain the message M;

m) Applying the hash function H to s and performing an Exclusive OR with t in order to obtain r;

n) Applying the hash function F to the message M and to the random number r in order to obtain s′

;

o) Verifying that s′

=s;

If s′ and

s are different, rejecting the encrypted message C;

Otherwise, going to step h;

p) Returning the plain text message M.