LOW LATENCY CALCULATION TRANSCRYPTION METHOD

Abstract

A method for confidentially processing data stored on a platform is described. A transcryption module, receiving a request for access to a data block, transmits the access request to an access request prediction module which returns a list of data blocks. The transcryption module determines whether a corresponding key stream block is present in the cache. The homomorphic calculation module calculates homomorphic ciphertexts of key stream blocks corresponding to the data blocks of the list. The transcryption module transcrypts the data blocks by adding them with the homomorphic ciphertexts of the corresponding key stream blocks. The transcryption module transmits the data blocks thus transcrypted to the request management module.

Claims

1. A method for confidentially processing data stored on a platform, the data being stored in a database, in a form encrypted by stream encryption, using a key stream generated from a symmetric key, the confidential processing being carried out upon request from a client having previously generated a private key-public key pair of a homomorphic cryptosystem and having transmitted said public key to the platform, the method comprising: a request management module RQM receiving a request from the client PR(i.sub.a), generates a plurality of requests for access arq.sub.1, . . . , arq.sub.N to data blocks B.sub.1, . . . , B.sub.N and transmits these requests to a transcryption module TCA; the transcryption module TCA, receiving a request for access arq.sub.n to a data block, transmits the access request to an access request prediction module which returns thereto a list of data blocks the access to which is predicted; the transcryption module TCA reads the data block from the database and determines whether a corresponding key stream block is present in the cache, and if not, adds it to the list of data blocks, the list of data blocks being provided to a homomorphic calculation module KSHC; the homomorphic calculation module KSHC is configured to calculate, in the homomorphic domain, homomorphic ciphertexts of key stream blocks corresponding to the data blocks of said list, and to transmit the homomorphic ciphertexts of the key stream blocks to the transcryption module as they are obtained; the transcryption module TCA stores the homomorphic ciphertexts of the key stream blocks in the cache, and transcrypts the data blocks the access to which is requested by adding them respectively with the homomorphic ciphertexts of the corresponding key stream blocks, read from the cache; the transcryption module TCA transmits the data blocks thus transcrypted to the request management module RQM which performs, in the homomorphic domain, processing on the data blocks thus transcrypted corresponding to the request; the request management module RQM transmits to the client the processing result, in homomorphically encrypted form.

2. The method for confidentially processing data according to claim 1, wherein the request management, transcryption, access request prediction and homomorphic calculation modules are software agents.

3. The method for confidentially processing data according to claim 1, wherein the request management, transcryption, access request prediction and homomorphic calculation modules are installed on a same machine.

4. The method for confidentially processing data according to claim 1, wherein the request management, transcryption, access request prediction modules are located on a first machine and the homomorphic calculation module is installed on a second machine.

5. The method for confidentially processing data according to claim 4, wherein the second machine is equipped with a homomorphic encryption hardware accelerator.

6. The method for confidentially processing data according to claim 4, wherein the second machine is a server, the first machine asynchronously transmitting, to the server, requests for homomorphic ciphertexts of key stream blocks for transcryption operations to be performed or for predicted transcryption operations.

7. The method for confidentially processing data according to claim 1, wherein the platform hosts a plurality of databases, each database being fed by a data provider and being associated with a symmetric encryption key, the data blocks stored in a database being encrypted by the data provider feeding the database, by means of a key stream generated from the symmetric key associated with this database.

8. The method for confidentially processing data according to claim 1, wherein the cache is managed by a FIFO type replacement algorithm.

9. The method for confidentially processing data according to claim 1, wherein the cache is managed by an LRU or MRU type replacement algorithm.

10. The method for confidentially processing data according to claim 1, wherein the platform comprises a plurality of access prediction modules, each access prediction module being configured to predict the requests for access to a database associated with this module.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0057] Further characteristics and advantages of the invention will appear upon reading a preferential embodiment of the invention, described with reference to the appended figures in which:

[0058] FIG. 1 schematically represents a first method for confidentially executing a data processing request, making use of a known transcryption step of the state of the art;

[0059] FIG. 2 schematically represents a second method for confidentially executing a data processing request, making use of a known transcryption step of the state of the art;

[0060] FIG. 3 schematically represents a method for confidentially executing a data processing request making use of a transcryption step according to one embodiment of the invention.

DETAILED DISCLOSURE OF PARTICULAR EMBODIMENTS

[0061] In the following, an applicative context such as that represented in FIG. 2 is considered. More generally, the remote platform may be queried by a plurality of clients, each client having its own homomorphic (asymmetric) cryptosystem and transmitting the public key of said cryptosystem to the platform as well as to the data provider. Similarly, the remote platform will be able to receive and store data from a plurality of data providers, each provider having its own symmetric key and transmitting it to the platform, after encrypting it by means of the public key of a homomorphic cryptosystem of a client having access rights. For example, data providers could be patients transmitting their genomic data in encrypted form to a platform and clients could be physicians wishing to look up these genomic data. It will be assumed in the following that clients and data providers can identify and authenticate themselves to the platform and that clients have access rights to the data they wish to process. In some cases, clients may be the same as access providers or only as a subset of them. For example, in the aforesaid example, in addition to physicians, patients themselves will be able to access their own genomic data and have these data processed in a confidential manner. Finally, the access rights of different clients may differ, for example, they may be limited to some databases hosted by the platform, to some data fields or to some types of processing only. However, the management of access rights does not fall within the scope of the present invention.

[0062] The transcryption method according to the present invention involves several agents: a processing request management module, RQM, a transcription module, TCA, an access prediction module, AP, and a homomorphic calculation module, KSHC. These modules are, as a general rule, software agents forming part of the remote platform, but some of them, in particular the calculation module, may be made as dedicated processors or processors equipped with hardware accelerators. Some elements of the platform may be distributed in the Cloud or hosted by remote servers.

[0063] Without loss of generality, in the following, the case of a client wishing to have the platform perform confidential processing on data previously provided by an access provider will be considered. Data of the access provider are stored in a database of the platform, in a form encrypted by the symmetric key of the access provider.

[0064] Processing requests may relate to different fields of a record or different records present in a database hosted by the platform. For example, in the first case, a physician may wish to access a given gene in a cohort of patients, and in the second case, to different genes in a patient's genome.

[0065] Each request received by the management module RQM specifies, for example by means of an index, on which data processing has to be performed. At the end of the processing, the management module returns the processing result, in a form encrypted by the public key of the client's homomorphic cryptosystem.

[0066] FIG. 3 schematically represents the timing chart of a method for confidentially processing data using a transcryption method according to the invention.

[0067] The request management module RQM, the transcription module TCA, the access prediction module AP, and the homomorphic encryption module KSHC, are represented in the figure.

[0068] When the RQM module receives a data processing request, it generates a sequence of requests for access to the data to be processed. Each access request is relating to a data block. These access requests, referred to as arq.sub.1, . . . , arq.sub.N, are transmitted to the transcryption module, TCA, as and when required for processing.

[0069] When the transcryption module receives an access request, arq.sub.n, it forwards it to the access prediction module, AP. Further, it reads, from the database, the data block, B.sub.n, requested in the access request arq.sub.n and homomorphically encrypts it by means of the public key HE.pk. It is reminded that the data block B.sub.n is stored in encrypted form by the symmetric key ksym (that is, by bit-by-bit addition of the key stream Kstr), B.sub.n=a.sub.n+Kstr.sub.n where a.sub.n represents the data in plaintext and Kstr.sub.n the key stream block used for encrypting a.sub.n.

[0070] The transcryption module also has access to a cache containing homomorphic ciphertexts of the key stream blocks, Enc(HE.pk,Kstr.sub.p) where p is a block index in the key stream.

[0071] If the block Enc(HE.pk,Kstr.sub.n) is present in the cache, the transcryption module performs the transcryption operation:

Enc(HE.pk,Kstr.sub.n)⊕Enc(HE.pk,B.sub.n)=Enc(HE.pk,a.sub.n)  (5)

and returns the result to the request management module.

[0072] If the block Enc(HE.pk,Kstr.sub.n) is not present in the cache, it waits for this block.

[0073] The access prediction module AP predicts, from the request, arq.sub.n, all the data blocks B.sub.q, q∈Ω.sub.n the access to which can be requested during the next access requests. This prediction can be made from predetermined rules (known a priori) depending on the application or be the result of supervised or unsupervised learning. In all cases, the prediction module AP returns the ordered list Ω.sub.n of indices of these data blocks to the transcryption module.

[0074] If the cache does not contain the block Enc(HE.pk,Kstr.sub.n), the index n is added to the ordered list Ω.sub.n and placed at the top of the list.

[0075] The transcryption module transmits the ordered list Ω.sub.n to the homomorphic encryption module KSHC. This module successively generates in the homomorphic domain, the homomorphic ciphertexts of the key stream blocks, Enc(HE.pk,Kstr.sub.q), q∈Ω.sub.n and returns them to the transcryption module as they are calculated. This generation is carried out by calculation in the homomorphic domain from the transcryption token, Enc(HE.pk,ksym).

[0076] As soon as the transcryption module receives the block, Enc((HE.pk,Kstr.sub.n), it performs the transcryption operation expressed in (5) and returns the result to the request management module.

[0077] Subsequent blocks are stored in the cache as they are received.

[0078] The process continues with a new access request, arq.sub.n+1 transmitted by the request management module to the transcryption module. The latter forwards the access request to the access prediction module, which can again predict all the data blocks B.sub.q, q∈Ω.sub.n+1 the access to which may be requested in subsequent access requests. However, this prediction is optional insofar as the elements of the set Ω.sub.n+1 may already be present in the set Ω.sub.n. If the prediction module makes a new prediction, only the elements of Ω.sub.n+1 that do not belong to Ω.sub.n are transmitted to the module KSHC. The latter generates, in the homomorphic domain, homomorphic ciphertexts of key stream blocks corresponding to the indices of Ω.sub.n+1−Ω.sub.n and transmits them to the transcryption module as they are calculated.

[0079] The transcryption module stores the new homomorphic ciphertexts of the key stream blocks in the cache as they are received.

[0080] The cache is managed by means of a cache line replacement algorithm or CRP (Cache Replacement Policy) which can be independent of block usage, for example a FIFO (First In First Out) type replacement algorithm, or dependent on block usage, for example an LRU (Last Recently Used) or MRU (Most Recently Used) type algorithm.

[0081] Those skilled in the art will understand that the prediction module allows anticipation of accesses and calculation of the homomorphic ciphertexts of key streams blocks, which dramatically reduces the latency of the transcryption operation.

[0082] When the request management module has all the transcrypted blocks available Enc(HE.pk,a.sub.n), n=1, . . . , N, it performs processing in the homomorphic domain and returns the result Enc(HE.pk,r) to the client with r=F(a).

[0083] The client can then decrypt the result with the private key of the homomorphic cryptosystem to obtain the result in plaintext, r.

[0084] The different modules RQM, TCA, AP, and KSHC can be installed on a same machine or on distinct machines.

[0085] According to a first embodiment, the different modules are installed on a same machine. The a priori knowledge on the requests are then those which are addressed to this machine. The homomorphic ciphertexts of the key stream blocks can be calculated in pipeline mode in a time interval between two requests.

[0086] According to a second embodiment, the modules RQM, TCA, AP are installed on a first machine and the module KSHC is installed on a second machine, for example a server asynchronously receiving requests for homomorphic ciphertexts of key stream blocks.

[0087] This second machine Is then specialised in generating the homomorphic ciphertexts of the key stream blocks Enc(HE.pk,Kstr.sub.q), that is in calculating, in the homomorphic domain, this key stream from the transcryption token Enc(HE.pk,ksym). The second machine can be equipped with hardware accelerators so that the homomorphic calculation is as fast as possible. The first machine can transmit, to the second machine, requests for calculating homomorphic ciphertexts of key stream blocks for a transcryption operation to be performed, or even speculatively anticipate future requests.

[0088] According to a third embodiment, the module KSHC is made by implementing an infrastructure dispensed in the Cloud or distributed over a plurality of servers, optimised for calculation in the homomorphic domain. Here again, this Infrastructure can comprise hardware accelerators so as to reduce calculating time.

[0089] Whatever the embodiment contemplated, the platform can host several databases, with each database being fed by a data provider. In other words, each database is associated with a symmetric key. The modules RQM, TCA, AP, and KSHC can be common to all these databases but, in this case, the AP module will use distinct prediction rules according to the different databases. In the same way, the module KSHC will generate homomorphic ciphertexts of different key streams for the different symmetric keys. Alternatively, as many modules AP and modules KSHC as there are databases can be provided, each module AP being then specialised in predicting accesses in the database with which it is associated and each module KSHC being specialised in calculating, in the homomorphic domain, key stream blocks for the symmetric key associated therewith.