METHOD FOR CONFIDENTIAL EXECUTION OF A PROGRAM OPERATING ON DATA ENCRYPTED BY A HOMOMORPHIC ENCRYPTION

Abstract

A method of executing a program operating on data encrypted by a homomorphic encryption. Execution of a program instruction includes the homomorphic evaluation of an associated function in the ciphertext space, homomorphic masking of the result of the evaluation with a previously encrypted random sequence decryption of the evaluation result thus masked followed by a new encryption and then homomorphic unmasking in the ciphertext space. The result of execution of the instruction does not appear in plain text at any time during execution of the instruction.

Claims

1. A method of executing a program operating on data encrypted with a homomorphic encryption, said program comprising a plurality of instructions, each instruction being represented by a function of said data, execution of said instruction including a homomorphic evaluation by a processor of said function starting from said encrypted data, wherein: (a) the result of said evaluation is masked by a first summation operation with a random sequence previously encrypted by said homomorphic encryption, said first summation operation in the ciphertext space corresponding to a modulo 2 summation operation in the plaintext space; (b) the result of said evaluation thus masked is firstly decrypted and then reencrypted with said homomorphic encryption; (c) the result obtained in step (b) is unmasked by a second summation operation with said random sequence previously encrypted by said homomorphic encryption, said second summation operation in the ciphertext space corresponding to a modulo 2 summation operation in the plaintext space, the result of the second summation operation being stored in a memory zone.

2. The method of executing a program according to claim 1, wherein steps (a),(b) and (c) are performed by a coprocessor distinct from said processor.

3. The method of executing a program according to claim 1, wherein said instructions are stored in the form of functions expressed in the plaintext space, said instructions being translated during the boot by expressing said functions in the ciphertext space before being stored in a program memory.

4. The method of executing a program according to claim 1, wherein said instructions are stored in a program memory in the form of functions expressed in the plaintext space, said functions being translated on the fly, as they are executed, expressing said functions in the ciphertext space.

5. The method of executing a program according to claim 1, wherein the encryption is a fully homomorphic encryption.

6. The method of executing a program according to claim 1, wherein the encryption is a somewhat homomorphic encryption.

7. The method of executing a program according to claim 6, wherein the encryption is a BGV encryption.

8. The method of executing a program according to claim 6, wherein the encryption is a ATV encryption.

9. The method of executing a program according to claim 6, wherein the encryption is a YASHE encryption.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0039] Other characteristics and advantages of the invention will become clear after reading a preferred embodiment of the invention with reference to the appended figures among which:

[0040] FIG. 1 diagrammatically represents a first example execution of a program on data encrypted by a homomorphic encryption;

[0041] FIG. 2 diagrammatically represents a second example execution of a program on data encrypted by a homomorphic encryption;

[0042] FIG. 3 diagrammatically represents the principle of a method of confidential execution on data encrypted by a homomorphic encryption according to one embodiment of the invention.

DETAILED PRESENTATION OF PARTICULAR EMBODIMENTS

[0043] In the following description, we will consider a program comprising a plurality of instructions that can be executed sequentially by a processor (CPU or microcontroller). The instructions operate on data stored in a memory zone (for example flash memory, RAM, registers). These data are stored in a form encrypted by means of a homomorphic encryption, for example a somewhat homomorphic encryption (SHE), characterised by its public key pk and its secret key sk.

[0044] Each instruction is evaluated homomorphically. More precisely, each instruction can be expressed in the form of a logical operation (combination of AND, OR, NOT elementary operations) or an arithmetic operation (combination of elementary addition and multiplication operations), either in the plaintext space (function F) or equivalently (function F) in the ciphertext space. The translation from F to F can be made offline, in other words before the program is stored. The translation could be made during the boot, in this case all translated instructions being stored in a program memory, or it can be made by the processor on the fly, instruction by instruction.

[0045] FIG. 3 diagrammatically represents the principle of a method of confidential execution on data encrypted by a homomorphic encryption according to one embodiment of the invention.

[0046] 310 denotes the memory space in which encrypted data are stored and 315 denotes the memory space in which program instructions are stored (in this case assumed to be expressed in the ciphertext space).

[0047] Each new instruction F.sub.n is evaluated homomorphically in 320, in other words an evaluation result H.Eval.sub.pk(F.sub.n) is obtained as in the second approach envisaged in the introduction part.

[0048] However, unlike the second case envisaged above, the result of the evaluation is homomorphically masked before it is decrypted.

[0049] More precisely, a random mask r is generated in 330 by means of a cryptographic quality pseudo-random sequence generator or preferably random sequence generator known in itself.

[0050] A pseudo-random sequence generator is generally composed of one or several shift registers looped back on themselves and/or between themselves, the outputs of which are combined linearly or non-linearly. The size of the mask is also chosen to be equal to the length of the evaluation result H.Eval.sub.pk(F.sub.n).

[0051] A pseudo-random generator uses a physical entropy source, for example such as a thermal noise of a resistance, and encrypts it using a symmetric encryption.

[0052] The mask could be determined as the sum of an arbitrary number of random or pseudo-random numbers. This arbitrary number can also be random or semi-random, so as to resist higher order attacks.

[0053] In 340, a homomorphic encryption is then made on the random mask r using the same cryptosystem (and particularly the same public key pk) as that used to encrypt the data.

[0054] Alternatively, the masks could have been generated in encrypted form directly or previously stored in encrypted form in a memory.

[0055] In all cases, the mask thus encrypted, H.Enc.sub.pk(r) is then added by means of a summation operation in the ciphertext space (in other words by means of the operation denoted ⊕) to the result of the homomorphic evaluation result H.Eval.sub.pk(F.sub.n). By definition, the ⊕ summation operation corresponds to the summation operation in the plaintext space, +, in this case considered as a modulo 2 addition (in other words bit by bit with no carry over). Advantageously, the homomorphic encryption is chosen such that the summation operation ⊕ is also a modulo 2 summation operation. This is the case particularly for the ATV and BGV encryption algorithms mentioned above

[0056] The result of the evaluation, masked by the random mask, is then decrypted using the secret key sk in 360. Advantageously, the secret key is stored in a secure register in the processor. This decryption prevents propagation of noise from one instruction to the next, as explained above. The result of the decryption is simply F.sub.n(M.sub.1, . . . , m.sub.M)+r.

[0057] The result of the decryption is then encrypted again using the homomorphic encryption 370, then unmasked in 380 by adding it to the encrypted random mask H.Enc.sub.pk(r) by means of the ⊕ operation (advantageously a bit by bit summation making use of an XOR as described above) in 380.

[0058] The sum thus obtained is then stored in the memory zone 310.

[0059] Due to the homomorphic masking before the result decryption operation, the result of the F.sub.n(m.sub.1, . . . , m.sub.M) instruction does not appear unencrypted at any step in its execution by the processor.

[0060] Since the demasking operation in 380 was done homomorphically in the ciphertext space, it does not reveal the result of the instruction.

[0061] It will be understood that the unmasked result H.Enc.sub.pk(F.sub.n(m.sub.1, . . . , m.sub.M)+r)⊕H.Enc.sub.pk(r) is in encrypted form and that there is no security problem with storing it in the memory zone. Its processing by a later instruction will consist of homomorphic encryption of F.sub.n(m.sub.1, . . . , m.sub.M) , and will therefore be identical to the processing that would be done on F.sub.n(m.sub.1, . . . , m.sub.M), because:

Dec.sub.pk(H.Enc.sub.pk(F.sub.n(m.sub.1, . . . , m.sub.M)+r)⊕H.Enc.sub.pk(r))=

Dec.sub.pk(H.Enc.sub.pk(F.sub.n(m.sub.1, . . . , m.sub.M)+r))+Dec.sub.pk(H.Enc.sub.pk(r))=  (9)

F.sub.n(m.sub.1, . . . , m.sub.M)+r+r=F.sub.n(m.sub.1, . . . , m.sub.M)

[0062] Unlike the second approach illustrated in FIG. 2, the next instruction only needs to take account of noise corresponding to a single operation in the ciphertext space, in fact the masking operation. Since the dimensions of this noise are well chosen, there is no need for additional decryption (bootstrapping step).

[0063] In one hardware implementation, operations 320 to 380 can be done by the processor itself, or according to another embodiment, can be distributed between the processor and a dedicated coprocessor. In this case, operations 330 to 380 that do not need access to the instruction, can be handled by the coprocessor, that limits its actions to homomorphic masking on the result of the instruction before storing it in memory.

[0064] Decryption in 360 is potentially vulnerable to physical attacks (and particularly attacks through auxiliary channels) aimed at determining the secret key sk of the cryptosystem. The circuit designed for decryption could also be made robust using a generic transformation method like that described for example in the paper by Y. Ishai et al. entitled “Private circuits: securing hardware against probing attacks” published in Proc. of Annual International Cryptology Conference, 2003.