FR3150380A1 - Method for determining an encrypted message, associated refreshing, extraction and aggregation method - Google Patents

Abstract

The invention relates to a method for determining an encrypted message c(X) corresponding to an encrypted version of a message µ(X), the message µ(X) being in the form of a polynomial of degree less than or equal to N-1 whose coefficients have values in . The method comprises a step of encrypting the message µ(X) by totally homomorphic encryption, from a private key s(X), in the encrypted message c(X) being in the form of a polynomial belonging to a space , with Tq[X] a space of polynomials of degree less than or equal to N-1 whose coefficients have values in and a cyclotomic polynomial of order M, with , t a prime number strictly greater than 3 and α a non-zero integer or , with ti prime numbers and αi non-zero integers, at least one of the prime numbers ti being strictly greater than 3. Figure to be published with the abstract: Figure 1

Description

Method for determining an encrypted message, associated refreshing, extraction and aggregation method TECHNICAL FIELD OF THE INVENTION

The present invention relates generally to the field of homomorphic cryptography.

The invention relates more particularly to a method for determining an encrypted message.

It also relates to associated refreshing, extraction and aggregation processes.

Finally, it concerns a device for determining an encrypted message and a cryptographic system comprising such a device.

TECHNOLOGICAL BACKGROUND OF THE INVENTION

Homomorphic cryptography, which allows calculations or processing to be performed on encrypted data without first decrypting it, has attracted a lot of attention recently.

Indeed, the digital processing of personal data has become omnipresent in our daily lives. Protecting the confidentiality of this data, and the privacy of the individuals concerned, has therefore become critical, as this personal data tends to circulate more and more in the digital systems environments used on a daily basis.

In this context, homomorphic encryption and processing techniques appear to be a very promising solution, because they make it possible to process data while preserving the privacy of this data in a particularly secure manner, since the latter is not decrypted during processing.

• à un serveur de services et traitements, externe, généralement distant, d’effectuer des opérations « en aveugle » sur des données chiffrées, sans les déchiffrer, ce serveur ne disposant d’ailleurs pas de la clef nécessaire pour déchiffrer les données,
• les données, chiffrées, étant fournies par une autre entité, distincte (un client, au sens informatique), qui, elle, dispose de la clef de chiffrement.

Homomorphic cryptography methods therefore respond, among other things, to the technical challenge of enabling:

• to an external, generally remote, service and processing server to perform “blind” operations on encrypted data, without decrypting it, this server not having the key necessary to decrypt the data,
• the data, encrypted, being provided by another, distinct entity (a client, in the IT sense), which has the encryption key.

These data processing operations may consist of performing individual operations, data by data, to format or filter them for example. They may also involve data comparison, sorting or aggregation operations.

• s est une clé secrète,
• a est un vecteur choisi au hasard, pour projeter la clé secrète s, et
• e est une composante de bruit aléatoire, ajoutée à μ+a.s.

Homomorphic cryptography can be based on the so-called " learning with errors " ( LWE ) encryption scheme, in which the encrypted message is derived from the unencrypted message μ according to the following formula: b=μ+e+as, where:

• s is a secret key,
• a is a randomly chosen vector, to project the secret key s, and
• e is a random noise component, added to μ+as

To decrypt the message, a person with the secret key s can calculate the quantity b-a.s (equal to μ+e), then round the result to remove the noise component e and recover the message μ. Of course, the noise term e must be and remain sufficiently small if the message μ is to be recovered.

Homomorphic operations, such as the addition of two encrypted messages, are implemented on encrypted messages to allow their processing without decrypting them. These operations can become particularly complex when dealing with messages in the form of long integers.

To perform homomorphic operations on a longer (plaintext) message, it is then common practice to decompose the message concerned into binary messages (classical binary decomposition). Each binary message is encrypted separately and the operation is then performed, homomorphically, bit by bit. But in this process, it is necessary to take into account the (encrypted) carry resulting from each binary addition, and to propagate this carry to the next binary operation. It is therefore a serial process, consuming in time. In addition, each binary operation is performed homomorphically, which multiplies the number of homomorphic operations (and therefore makes the complete implementation of the operation complex).

In this context, the invention relates to a homomorphic encryption method which allows to efficiently process messages longer than binary messages.

The invention relates to a method for determining an encrypted message c(X) corresponding to an encrypted version of a message µ(X), the message µ(X) being in the form of a polynomial of degree less than or equal to N-1 whose coefficients have values in a space with p a non-zero integer, N being a non-zero integer,
said method comprising a step of encrypting the message µ(X) by totally homomorphic encryption, from a private key s(X) in the form of a polynomial of degree less than or equal to N-1, in the encrypted message c(X) in the form of a polynomial belonging to a space , with T _q [X] a space of polynomials of degree less than or equal to N-1 whose coefficients have values in with q a non-zero integer greater than p and a cyclotomic polynomial of order M, with , t a prime number strictly greater than 3 and α a non-zero integer or , with t _i prime numbers and α _i non-zero integers, at least one of the prime numbers t _i being strictly greater than 3.

Thus, the use of cyclotomic polynomials for the encrypted message allows to improve the cryptographic processing of long messages. Indeed, the homomorphic processing of long messages is greatly facilitated by the properties of cyclotomic polynomials.

On the one hand, the use of cyclotomic polynomials for the encrypted message, considering a given set of parameters (i.e. with fixed values of p and t) allows to consider long messages, other than in binary form for homomorphic cryptographic processing. On the other hand, in the case of messages of usual sizes, the use of cyclotomic polynomials for the determination of the encrypted message allows to improve the performance of cryptographic processing (in particular, to improve the speed of implementation of these cryptographic processings).

According to this aspect of the invention, the fully homomorphic encryption is implemented by a polynomial encryption function with coefficients in a space defined by a torus T .

The invention also relates to a method for transforming an encrypted message c(X) determined according to the method introduced previously into an encrypted element. , said encrypted element belonging to a subspace of space , comprising a step of determining said encrypted element by applying a linear application to the message µ(X), said linear application being a trace operator defined as follows: , with G a subset of the integers between 0 and M-1 and prime to M and predefined weights.

Thus, the trace operator introduced allows the encrypted message to be transformed, without decrypting it. Using the trace operator allows, for example, the encrypted message to be "cleaned" (without decrypting it) in order to keep only certain terms useful for the intended application.

The invention also relates to a method for refreshing the encrypted message c corresponding to an encrypted version of a message ρ, said message ρ being defined in the torus T , said refreshing method comprising a step of determining a refreshed encrypted message c', the refreshed encrypted message c' comprising a noise component e' smaller than a noise component e of the encrypted message c, the refreshed encrypted message c' being determined on the basis of a polynomial obtained according to the determination method as introduced previously.

According to this aspect of the invention, the step of determining the refreshed encrypted message c' comprises a step of calculating a zero-order coefficient of the polynomial with a functional refresh polynomial belonging to the space , with , the notation corresponding to the integer closest to the number x and the notation corresponding to the modulo operator.

The invention also relates to a method for extracting a homomorphic encrypted element c _β from an encrypted message c(X) in the form of a polynomial belonging to the space , the encrypted message c(X) being determined by a determination method as introduced previously, the homomorphic encrypted element c _β being obtained by determining the coefficient of order 0 of a polynomial , being a cyclotomic polynomial of order M, with , t being a prime number strictly greater than 3 and α a non-zero integer, being a non-zero integer, said homomorphic encrypted element c _β corresponding to an encrypted element of a linear combination of coefficients of the message µ(X).

According to this aspect of the invention, the extraction method comprises a step of determining the non-zero integer β so as to verify the following inequality: , said homomorphic encrypted element c _β corresponding to an encrypted element of a coefficient of order β of the message µ(X).

The invention also relates to a method for aggregating a plurality of encrypted messages c ⁽ⁱ⁾ , i being a natural integer, each encrypted message c ⁽ⁱ⁾ belonging to a space T ⁿ⁺¹ , n being a non-zero natural integer, each encrypted message c ⁽ⁱ⁾ corresponding to an encrypted version of an associated message µ ⁽ⁱ⁾ , this encryption being implemented by means of a private encryption key s, the aggregation method comprising steps of:
- determination of an encrypted key according to the determination method as previously introduced, and
- aggregating said plurality of encrypted messages c ⁽ⁱ⁾ so as to obtain an encrypted message appearing in the form of a polynomial.

According to this aspect of the invention, the encrypted message appearing in the form of a polynomial is determined on the basis of a polynomial encryption with coefficients in the space defined by the torus T .

The invention further relates to a device for determining an encrypted message c(X) corresponding to an encrypted version of a message µ(X), the message µ(X) being in the form of a polynomial of degree less than or equal to N-1 whose coefficients have values in a space with p a non-zero integer, N being a non-zero integer,
the determination device comprising at least one processor and a storage device, the processor comprising:
- a module for encrypting the message µ(X) by totally homomorphic encryption, from a private key s(X) in the form of a polynomial of degree less than or equal to N-1, in the encrypted message c(X) in the form of a polynomial belonging to a space , withT _q[X] a space of polynomials of degree less than or equal to N-1 whose coefficients have values in with q a non-zero integer greater than p and a cyclotomic polynomial of order M, with , t a prime number strictly greater than 3 and α a non-zero integer or , with t_iprime numbers and α_i non-zero integers, at least one of the prime numbers t_ibeing strictly greater than 3.

The invention also relates to a cryptographic system comprising:
- a device for determining an encrypted message c(X) as introduced previously, and
- a cryptographic processing server configured to implement at least one cryptographic processing operation on the encrypted message c(X).

The invention finally relates to a computer program comprising instructions executable by a processor and designed to implement a method as introduced previously when these instructions are executed by said processor.

The invention and its various applications will be better understood by reading the description which follows and by examining the figures which accompany it.

BRIEF DESCRIPTION OF THE FIGURES

Other characteristics and advantages of the invention will emerge clearly from the description given below, for information purposes only and in no way limiting, with reference to the appended figures, among which:

schematically represents an example of a cryptographic system in accordance with the invention,

represents, in the form of a flowchart, an example of a method for determining an encrypted message in accordance with the invention,

represents, in the form of a flowchart, an example of an extraction method in accordance with the invention,

represents, in the form of a flowchart, an example of an aggregation method in accordance with the invention, and

represents, in the form of a flowchart, an example of a refreshing method according to the invention.

DETAILED DESCRIPTION

The present invention aims to improve the homomorphic processing of messages. More particularly, the present invention relates to a homomorphic encryption method which then makes it possible to perform operations on encrypted messages without decrypting them. According to the present invention, these encrypted messages are associated with plaintext messages (i.e. unencrypted messages) each of which is longer than a single bit and which are processed, in a homomorphic manner, without being broken down into individual binary messages.

By definition in this description, the expression " plaintext message " means an unencrypted message. In other words, a plaintext message can be exploited (for example during its transmission or its storage) without requiring recourse to decryption, nor to a homomorphic processing technique.

To implement this method, the invention firstly concerns a cryptographic system 1. The schematically represents an example of such a cryptographic system 1.

As shown in this figure, the cryptographic system 1 comprises an entity 2, a cryptographic processing server 3 and a recipient entity 4.

The entity 2 is configured to encrypt one or more messages (and, optionally, to collect these messages beforehand), with a private encryption key s. This entity 2 comprises, for example, a device 2A for determining an encrypted message c(X) as described below. The device 2A for determining the encrypted message c(X) comprises, for example, a processor and a storage device (not shown).

This entity 2 is also configured to transmit the corresponding encrypted message(s) to the cryptographic processing server 3. The encrypted message(s) transmitted are for example accompanied by a processing request (in particular to the cryptographic processing server 3).

For this purpose, the entity 2 comprises, for example, a set of functional modules. Each of the different modules is, for example, produced by means of computer program instructions stored in a memory of the entity 2 and designed to implement the module concerned when these instructions are executed by a processor of the entity 2.

In practice, entity 2 is distinct from cryptographic processing server 3. This entity 2 is, for example, an external database, or a client (in the IT sense).

The cryptographic processing server 3 is configured to perform processing operations (function application, extraction, refreshing, sorting) on the encrypted message(s) received. This cryptographic processing is implemented homomorphically, i.e. without decryption of the messages. The cryptographic processing server 3 does not have the private encryption key s used to produce the encrypted message(s), from one or more unencrypted plaintext messages. In other words, the cryptographic processing server 3 is programmed to implement different processing operations homomorphically.

The cryptographic processing server 3 comprises, for example, a communication module, for receiving and/or transmitting data (in practice one or more encrypted messages), and a calculation module, for carrying out the homomorphic cryptographic processing operations mentioned above.

The modules in question are for example in the form of a dedicated electronic circuit, such as a communication card (for the communication module), or a cryptographic calculation circuit comprising at least one processor or one programmable circuit, and a memory (for the calculation module). The cryptographic processing server 3 itself can thus take the form of its own electronic device.

Alternatively, the modules of the cryptographic processing server may also each take the form of a set of instructions whose execution by a computer system (for example by a computer) leads to the performance of steps of receiving and/or transmitting data (for the communication module), or of processing data (for the cryptographic calculation module). The cryptographic processing server 3 may in particular take the form of delocalized IT services, available, via a communication network (for example via the Internet, or via an intranet), in a delocalized IT structure, for example of the “cloud” type (delocalized structure on several separate electronic support devices, distant from each other, networked).

A communication channel 5 connects the entity 2 and the cryptographic processing server 3. This is, for example, a communication channel for which the transmitted data is likely to be intercepted. It may be a wireless communication channel, or a wired communication channel.

In practice, entity 2 and cryptographic processing server 3 may be distant from each other, for example located in different buildings.

Alternatively, it may also be elements belonging to the same computer system, for example within the same electronic device (for example within the same computer, or the same portable electronic device).

As shown in the , the cryptographic system 1 also comprises the recipient entity 4. This recipient entity 4 is configured to receive the result of the cryptographic processing implemented by the cryptographic processing server 3 (result which is itself encrypted because the processing carried out is a homomorphic cryptographic processing). The recipient entity 4 is here distinct from the cryptographic processing server 3.

A communication channel 6 connects the cryptographic processing server 3 and the recipient entity 4. This communication channel 6 is configured to transmit the result of the cryptographic processing from the cryptographic processing server 3 to the recipient entity 4. This is for example a communication channel for which the transmitted data is likely to be intercepted. It may be a wireless communication channel, or a wired communication channel.

Alternatively, the recipient entity 4 may be the entity 2 itself, and the communication channels 5 and 6 may form the same bidirectional communication channel.

The present invention firstly relates to a method for determining an encrypted message c(X). This determination method is for example implemented by the device 2A for determining the encrypted message c(X) of the entity 2 of the cryptographic system 1. Generally speaking, the determination method is implemented by computer.

There is a flowchart representing an example of a method for determining the encrypted message c(X) implemented by the cryptographic system 1 described above.

In general, this determination method aims to determine the encrypted message c(X) corresponding to an encrypted version of a plain message µ(X).

As shown in Figure 2, the method begins at step E2, during which entity 2 receives the plaintext message µ(X). Here, this plaintext message µ(X) is in the form of a polynomial of degree less than or equal to N-1 with N a non-zero integer. This polynomial has coefficients whose values are taken in a space T _p called a "discrete torus", with p a non-zero integer. More particularly, the discrete torus T _p is defined as follows: .

The method then continues to step E4. In this step, entity 2 receives a private encryption key s(X). This private encryption key s(X) is also a polynomial of degree less than or equal to N-1. The coefficients of the polynomial representing the private encryption key s(X) have values in the space ℤ.

It is important to note here that the private encryption key s(X) is known only to entity 2 (in cryptographic system 1). In particular, this private encryption key s(X) is not known, for example, to the cryptographic processing server 3 which implements the various processing operations on the encrypted message c(X).

The determination method then comprises step E6 of determining the encrypted message c(X). In other words, this step E6 corresponds to a step of encrypting the plaintext message µ(X), from the private encryption key s(X), so as to determine the encrypted message c(X).

Advantageously according to the invention, the encryption implemented during this step E6 is a fully homomorphic encryption (or FHE for “ Fully Homomorphic Encryption ” according to the commonly used Anglo-Saxon name).

In this description, the term " fully homomorphic encryption " means an encryption system that allows analytic functions to be performed directly on encrypted data without any limitation on the number of executions while obtaining the same encrypted results as if the functions were performed on plaintext.

Advantageously according to the invention, the encrypted message c(X) is in the form of a polynomial belonging to a space defined as follows . The space T _q [X] is a space of polynomials of degree less than or equal to N-1 whose coefficients have values in the discrete torus with q a non-zero integer greater than p (introduced previously to define the discrete torus used for the values of the coefficients of the polynomial defining the plaintext message µ(X)).

The rating denotes a cyclotomic polynomial of order M. By definition, and as is known, the cyclotomic polynomial of order M corresponds to the unitary polynomial whose complex roots are exactly the M-th primitive roots of unity.

It is worth noting that the degree of the cyclotomic polynomial of order M is equal to . This degree corresponds to the number of non-negative integers less than M and prime to M. The degree then corresponds to the usual Euler indicator function.

Advantageously according to the invention, the order M is defined by , with t a prime number strictly greater than 3 and α a non-zero integer or , with t _i prime numbers and α _i non-zero integers, at least one of the prime numbers t _i being strictly greater than 3. The symbol ∏ corresponds to the product operation.

Thus, the use of cyclotomic polynomials for the encrypted message makes it possible to improve the cryptographic processing of long messages. Indeed, the homomorphic processing (i.e. by applying homomorphic operations to the encrypted message according to the method according to the invention) of long messages is greatly facilitated by the properties of cyclotomic polynomials.

On the one hand, the use of cyclotomic polynomials for the encrypted message, considering a given set of parameters (i.e. with fixed values of p and t) allows to consider long messages, other than in binary form for homomorphic cryptographic processing. On the other hand, in the case of messages of usual sizes, the use of cyclotomic polynomials for the determination of the encrypted message allows to improve the performance of cryptographic processing (in particular, to improve the speed of implementation of these cryptographic processings).

In a first preferred example of implementation of the present invention, the order M is defined as follows: , with t a prime number strictly greater than 3 and α a non-zero integer. Preferably, the prime number t is greater than 23. For example, the prime number t is equal to 31.

In this case, the following relationship holds:

.

In practice, the cyclotomic polynomial of order M is defined here (for the case ) in the following manner: . Furthermore, the following relationship is verified: .

Moreover, in this case, the degree of the cyclotomic polynomial is given by: .

This embodiment is particularly interesting because the use of a prime number t greater than or equal to 3 and the choice of a message size p which coincides with t ( ), allows to free oneself from the compatibility condition mentioned in the following (usually known under the name of nega-cyclicity condition in the case where ). The absence of this compatibility condition in the case of the present invention allows, as indicated above, to improve the cryptographic processing of longer messages (for given parameters) or to improve the performance of cryptographic processing implemented on messages of usual sizes. Such advantages cannot be obtained in the case where without being limited to the processing of binary messages ( ).

Furthermore, the fact that the degree of the cyclotomic polynomial ( ) depends on the two parameters ( And ) allows to adjust it as best as possible in order to target a more suitable encryption security value. This advantage cannot be obtained either in the case where or in the case where the degree is a power of 2. This adjustment of the two parameters also makes it possible to improve the performance of the cryptographic treatments implemented.

In a second preferred example of implementation of the present invention, the order M is defined as follows: , with t ₁ and t ₂ prime numbers strictly greater than 3 and α ₁ , α ₂ non-zero integers. Preferably, the prime numbers t ₁ and t ₂ are greater than 23.

In this case, the following relations hold, with t ₁ and t ₂ distinct prime numbers strictly greater than 3:

.

In practice, fully homomorphic encryption is implemented by applying, to the plaintext message µ(X) (and with the use of the private encryption key s(X)), a polynomial encryption function with coefficients in the space defined by the torus T. In other words, fully homomorphic encryption is implemented by a polynomial encryption function based on the so-called " learning with error " (LWE) method. In other words, fully homomorphic encryption is implemented by applying a TRLWE (for " Torus Ring Learning With Errors ") type function.

Advantageously according to the present invention, the use of the cyclotomic polynomial of order M makes it possible to express in a practical manner the modulo (also noted in this description).

We consider a polynomial of degree less than or equal to M-1.

According to the first preferred example introduced previously, with , and noting , the following expression, corresponding to the result of the polynomial R modulo , is verified:

.

According to the second preferred example introduced previously, with , and noting , the following expression, corresponding to the result of the polynomial R modulo , is verified:

, with a polynomial of degree .

In the case where α ₁ = α ₂ = 1, the polynomial is expressed as follows:

.

In practice, multiplication operations, , and division by are for example implemented directly. Alternatively, they can be implemented using a Fourier transform modulo .

As previously indicated, the cryptographic system 1 (and more particularly the cryptographic processing server 3) is configured to implement, in a homomorphic manner, different operations for processing encrypted messages.

These different processing operations all rely on a common tool, namely the method for determining an encrypted message as introduced above. In other words, whatever the processing operation considered, it relies on an encrypted message determined according to the method described above (i.e. an encrypted message defined from the cyclotomic polynomial of order M, with the properties defined above).

The cryptographic system 1 is for example configured to implement extraction, aggregation (or “ packing ” according to the commonly used terminology of Anglo-Saxon origin) and refresh (or “ boostrapping ” according to the commonly used terminology of Anglo-Saxon origin) operations as described below.

Extraction operation

This processing operation aims to extract a homomorphic encrypted element c _β associated with an encrypted message c(X). This encrypted message c(X) is obtained by implementing the determination method described above. In other words, the encrypted message c(X) is in the form of a polynomial belonging to the space previously introduced (the coefficients of this polynomial having values in T _q ).

β is defined as a non-zero integer less than or equal to the degree of the polynomial representing the encrypted message c(X) (β is therefore less than or equal to N-1). By convention in this description, we then note that if , (in other words, with this convention, we define as ).

We consider here the cyclotomic polynomial of order M, with , with t a prime number strictly greater than 3 and α a non-zero integer.

The present invention relates here to a method for extracting the homomorphic encrypted element c _β from the encrypted message c(X). The represents, in the form of a flowchart, an example of an extraction method in accordance with the invention.

This extraction method is for example implemented by the cryptographic processing server 3 of the cryptographic system 1. Generally speaking, the extraction method is implemented by computer.

As shown in Figure 3, the extraction process begins at step E10. During this step, the cryptographic system 1 (and more particularly the cryptographic processing server 3) determines a polynomial . The notation corresponds to the modulo operator.

The extraction method then comprises step E12. During this step, the cryptographic system 1 determines the zero-order coefficient of the polynomial . The homomorphic encrypted element c _β is related to this zeroth order coefficient of the polynomial .

Then, the extraction process continues to step E14 during which the cryptographic system 1 compares the quantity to the quantity . In particular, cryptographic system 1 evaluates whether the quantity is greater than or equal to the quantity .

If, at step E14, the cryptographic system 1 identifies that the quantity is greater than or equal to the quantity , the method continues in step E16. In this step E16, the cryptographic system 1 determines the homomorphic encrypted element c _β as corresponding to a linear combination of coefficients of the message µ(X). In other words, the zero-order coefficient determined (in step E12) corresponds to the result obtained by encryption of a linear combination of several coefficients of the message µ(X).

Thus, during this step E16, the cryptographic system 1 extracts, as a homomorphic encrypted element c _β , this linear combination (via the zero-order coefficient of the polynomial ).

If at step E14, the cryptographic system 1 identifies that the quantity is less than the quantity , the method continues at step E18. Here, the cryptographic system 1 identifies more particularly that the quantity verifies the following inequality: .

In step E18, the cryptographic system 1 then determines the homomorphic encrypted element c _β as corresponding to an encrypted element of the coefficient of order β of the plaintext message µ(X) on the basis of the coefficient of order zero of the polynomial determined in step E12. In other words, the zero-order coefficient determined corresponds to the result obtained by encryption of the β-order coefficient of the plaintext message µ(X). In other words, the cryptographic system 1 extracts, from the encrypted message c(X) (via the zero-order coefficient of the polynomial ), the homomorphic encrypted element c _β corresponding to the result obtained by encryption of the order coefficient β of the plaintext message µ(X).

Alternatively, in the case of any number β, the extraction method provides, as output, an encrypted element of the linear combination : .

Operation d 'aggregation (Or " packing »)

This aggregation operation aims to group together different scalar encrypted elements obtained by a known method of homomorphic encryption in the torus T (or TLWE encryption for " Torus Learning With Errors ") into an encrypted element in polynomial form (associated with a TRLWE encryption).

The present invention then relates to an aggregation method implementing the targeted application. represents, in the form of a flowchart, an example of an aggregation method in accordance with the invention.

This aggregation process is for example implemented by the cryptographic processing server 3 of the cryptographic system 1. Generally speaking, the aggregation process is implemented by computer.

As shown in Figure 4, the method begins at step E20 during which the cryptographic system 1 (and more particularly the cryptographic processing server 3) receives a plurality of encrypted messages c ⁽ⁱ⁾ , with i a natural integer defined such that And .

Each encrypted message c ⁽ⁱ⁾ belongs to the set T ⁿ⁺¹ , n being a non-zero natural integer (i.e. ).

In practice, each encrypted message c ⁽ⁱ⁾ corresponds to the result of the homomorphic encryption in the torus T , of a corresponding scalar plaintext message µ ⁽ⁱ⁾ . This encryption is implemented by means of a private encryption key s defined in the space (that is to say that ).

In other words, each encrypted message c ⁽ⁱ⁾ corresponds to a TLWE encryption of the corresponding scalar plaintext message µ ⁽ⁱ⁾ , using the private encryption key s.

The method then continues to step E22. In this step, the private encryption key s is homomorphically encrypted using a key . The key is presented in the form of a polynomial of degree less than or equal to N-1 belonging to the space (with the cyclotomic polynomial of order M). This key allows the aggregation of the different encrypted messages c ⁽ⁱ⁾ obtained using a TLWE encryption into an encrypted element in polynomial form. In other words, this key in polynomial form allows the implementation of TRLWE encryption.

As shown in Figure 4, the method then comprises step E24 during which a plurality of encrypted messages c ⁽ⁱ⁾ are grouped in the form of a polynomial of degree less than or equal to N-1 so as to obtain an encrypted message appearing in the form of a polynomial. This encrypted polynomial of polynomial form is constructed in such a way as to correspond to a polynomial encryption with coefficients in the torus T (TRLWE encryption) of a message in plaintext appearing in polynomial form. This TRLWE encryption is implemented using the encrypted key determined in step E22. In other words, .

The coefficients are defined in the set {0, …, N-1}. The quantity L is a matrix intended to modify the scalar µ ⁽ⁱ⁾ plaintext messages such that if an extraction operation (as described above) is implemented after the aggregation operation, the result obtained corresponds to an encrypted element of the corresponding scalar µ ⁽ⁱ⁾ plaintext message.

In case , this matrix L is for example a linear operator which, at the elements associates the elements with : , with And .

In practice, we define each encrypted message c ⁽ⁱ⁾ as follows: . We also define with , , And .

For the aggregation operation, an aggregation key KPac is also defined: , with , , . This KPac aggregation key is constructed in such a way that it allows obtaining the encrypted polynomial with the desired properties (described previously).

We use the following notation: .

Thus, the decomposition of the components of the element is written: with a usual remainder associated with this decomposition in base B. This remainder verifies .

We then obtain the following relationship: .

Furthermore, by construction of the aggregation key, the following relation can be written: with the notation A ^T designating the transpose of any matrix A (here the transpose operator is applied to the vector ), And corresponding to an encryption error of .

So : .

By identification, it can then be deduced: And .

Thus, the aggregation operation proposed according to the invention is such that it allows, if an extraction operation is subsequently applied, to directly arrive at the result of an encrypted element corresponding to the result of the encryption of a coefficient of the clear message.

Alternatively, it is possible to omit the L matrix in the message definition . In this case, the aggregation operation allows to obtain, if an extraction operation is subsequently applied, an encrypted element of .

Operation aggregation (“packing”) using the operators " traces »

This other aggregation operation aims to transform a scalar encrypted element obtained by a known method of homomorphic encryption in the torus T (or TLWE encryption for " Torus Learning With Errors ") into an encrypted element in polynomial form (associated with a TRLWE encryption), using the trace operators.

A trace operator (also called "trace" in this description) is a linear transformation on polynomials, of the form:

, with a polynomial defined in space , G a subset of the integers between 0 and M-1 and predefined weights. The notation corresponds, in the present description, to the trace operator. Alternatively, the subset G can be defined on the basis of integers between 0 and M-1 and prime with M.

The weights and the subset G depend on the desired transformation of the polynomial P. Here, we want to obtain an encryption of the transformed polynomial P obtained. The encryption of this result obtained by the transformation of the polynomial P is done homomorphically, from the expression of the trace previously indicated.

In practice, these traces are used to “clean” certain polynomials, that is, to obtain a numerical element of the polynomial in which only certain terms are preserved (namely, the terms useful for the intended application).

To this end, the present invention then relates to a method of transforming an encrypted message. obtained according to the determination method described above. This transformation method aims to transform the encrypted message into a transformed message Advantageously, this method is implemented without noise amplification, despite the presence of a multiplicative factor in the trace (as defined above).

This transformation process then includes a step of determining the transformed element by applying a linear application applied to the message µ(X). Advantageously according to the invention, this linear application is the trace operator as defined previously and with µ(X) as a polynomial P.

The transformation process then makes it possible to obtain the transformed element which is a transformed version of the encrypted message . The transformed element belongs to space .

This transformation process then allows, via the set G of values of d (therefore the elements chosen in the sum), to select only certain terms of the polynomial defining the encrypted message. .

Traces are generally expressed in the framework of Galois theory concerning field extensions. The sets G correspond in this case to groups called "Galois groups". These traces have several applications: they allow in particular, as aimed at in the present invention, to implement a TRLWE encryption of a scalar message. from a TLWE encrypted element of .

Here, we consider that , with t a prime number strictly greater than 3. Furthermore, .

The present invention then relates to a variant of the aggregation method, based on the determination of traces. An example of this variant of the aggregation method (also called another aggregation method in the following) is described below.

This other aggregation method is for example implemented by the cryptographic processing server 3 of the cryptographic system 1. Generally speaking, the other aggregation method is implemented by computer.

This other aggregation process begins with a first step during which the cryptographic system 1 (and more particularly the cryptographic processing server 3) receives an encrypted message . This encrypted message is obtained by encrypting a clear message. using a key , with .

By definition, we write .

We also define: , And .

It is observed that does not correspond to a polynomially encrypted element (associated with a TRLWE cipher) of the element (in space previously defined).

However, it is observed that: , with .

The second step of this other aggregation process therefore aims to evaluate an encrypted element (according to the encryption process introduced previously) of the zeroth order coefficient of the polynomial in space . Here, the goal is to successfully encrypt the zeroth order coefficient using polynomials (i.e. with a TRLWE encryption). Traces are a suitable tool for doing this.

This second step is therefore implemented using traces. More specifically, the following relation is given:

.

In this equality, the subset G is the set of integers d between 0 and M-1 and which are prime with M. And, making the link to the definition of the trace introduced above, here, the weights are equal to: . Use this equality to allows to obtain a TRLWE encryption of the coefficient of order 0, that is to say of the coefficient .

Advantageously thanks to Galois theory, the previous trace can be decomposed into partial traces in the following manner, with corresponding to a subset of the set G: . For example, it is possible to choose And And and where is a generator of the group (the notation denoting the group of invertible elements for multiplication, that is, of integers prime to M).

In practice, this decomposition is as fine as possible so as to be carried out to the maximum. Advantageously, the use of this decomposition into partial traces makes it possible to reduce the computational cost associated with the aggregation operation, to accelerate the aggregation operation and to reduce the error obtained at the end of the operation.

The postman present in the equation indicated in paragraph [00149] can be distributed on each of the partial traces so as to obtain a numerical element of the coefficient of order 0, that is to say of the coefficient . For example, in the given expression of the partial trace decomposition introduced, the factor involved in each of the partial traces is . Advantageously, the encryption error is thus not increased.

Refresh operation î chissement (or " bootstrapping »)

The refresh operation (generally called " bootstrapping ") aims to prevent the increase of a noise term during the processing of encrypted messages. The present invention therefore relates here to a method for refreshing an encrypted message c. This encrypted message c is here an encrypted message obtained by encryption of the plaintext message µ (scalar). More particularly, the plaintext message µ is defined in the torus T _p , while the encrypted message c is defined in the space T ⁿ⁺¹ .

As is known, the encrypted message c is defined by . This encrypted message is derived from the plaintext message µ by the following formula: b=μ+e+as, where e is the noise (random) component associated with the encrypted message c and s is the private encryption key.

In practice, the encrypted message c is obtained by a known method of homomorphic encryption in the torus T (or TLWE encryption for " Torus Learning With Errors ") applied to the plaintext message µ and by means of the private encryption key s. It is important to note that the cryptographic processing server 3 does not have the private encryption key s (and is therefore not able to decrypt the encrypted message c).

The refresh method therefore aims to produce a refreshed version of the encrypted message c, i.e. another encrypted message c’ (hereinafter called “refreshed encrypted message c’”). This refreshed encrypted message c’ is also decrypted as a plaintext message µ (when decrypted using the private encryption key s), but whose associated noise component is smaller than the noise component e of the encrypted message c.

Furthermore, if we first introduce a function acting on the message space defined in the torus T _p , then the refresh operation can also provide a refreshed encrypted element c' of .

There represents, in the form of a flowchart, an example of the refreshing method according to the invention.

This refresh method is for example implemented by the cryptographic processing server 3 of the cryptographic system 1. Generally speaking, the refresh method is implemented by computer.

As shown in the , the refresh method begins at step E30 during which the cryptographic system 1 (and more particularly the cryptographic processing server 3) receives the encrypted message c. As indicated previously, the encrypted message c was obtained, prior to the implementation of the refresh method, by encrypting the plaintext message µ, using the private encryption key s.

During this step E30, the cryptographic processing server 3 also receives an encrypted public version BK (“Bootstrap key” according to the commonly used Anglo-Saxon terminology) of the private encryption key s (using another encryption key). More particularly, the encrypted public version BK is obtained by encrypting the private encryption key s according to the encryption method described above.

Then, the method continues at step E32. During this step, the cryptographic processing server 3 determines a polynomial defined by the following expression . The polynomial is here a functional refresh polynomial which belongs to the space , with . In this expression, µ corresponds to the plaintext message (and therefore belongs to the torus T ). In the present description, the notation corresponding to the integer closest to the number x and the notation corresponding to the modulo operator. is the cyclotomic polynomial of order M (as introduced previously).

In practice, this functional refresh polynomial is determined according to a specific algorithm (described below). In practice, this algorithm allows to determine the coefficients of the functional refresh polynomial based on values of a function (introduced below). The algorithm according to the invention covers the cases And .

In practice, the determination of the functional refresh polynomial is equivalent to the determination of a function g(µ) called the refresh function defined by the following expression: , if the refresh function g(µ) satisfies the two properties described in the following paragraphs ([00167] and [00168]).

By construction, this refresh function g(µ) is a piecewise function: , with , i=0, …, M-1.

Furthermore, the refresh function satisfies the following relationship (called the “compatibility condition): .The functional refresh polynomial is then determined based on the refresh function g.

The values of the refresh function g(µ) must coincide with the values of the function defined in the space T _p . In other words, the following relation must be verified: .

Two cases can then be distinguished.

If , the compatibility condition verified by g imposes constraints on the quantities , with F a function defined in the space ℤ and with values in the space ℤ. This is then written in the following form: . In practice, this latter relation is satisfied by a wide class of functions but is not satisfied for all functions. . To satisfy it automatically, simply replace the function by function with .

In this case ( ), an optimal choice for the functional refresh polynomial is given, as a function of the values taken by the function , by the following expression: .

The refresh function g is in this case a staircase function with the width of each step around messages East .

If p and t are coprime, there are no special constraints on the quantities . It is then a question of finding a refresh function g which satisfies the following expression: . More precisely, it is then a question of determining all the values from the following relationships , while allowing the staircase function g to have the widest possible landings.

The described step E32 aims to determine the functional refresh polynomial .

According to one embodiment of the invention, the determination of this functional refresh polynomial amounts to determining, in an optimal manner, the coefficients of the functional refresh polynomial (involved in the definition of the refresh function g) such that:

, with , positive values as large as possible.

This then amounts to determining the values of the refresh function g at the points .

If , the optimal solution is obtained for .

If p and t are coprime, the determination of the coefficients of the functional refresh polynomial is broken down into the following sub-steps.

The first sub-step aims to express the previously introduced compatibility condition in the form of M compatibility relations obtained for . The system formed by these M compatibility relations satisfied by the refresh function g is equivalent to the following relationships: , For .

The second sub-step aims to use the relations determined in the previous step to determine the function g. In other words, it is a question of solving the system of equations in such a way as to determine the values taken by the refresh function g at all points .

For each fixed index j, with , the algorithm determines the index i between 0 and M-1, among the set of indices i which verify the relation and which is the furthest from the message the closest. We note this index. In other words, the index achieves the following maximum: .

The values of the refresh function g taken at all points are then given by the following relations:

For And And

.

This second substep is repeated for the set of equivalent relations j, with . This then makes it possible to obtain the values taken by the refresh function g at all points .

Then, in a third sub-step, the cryptographic system 3 determines the coefficients of the polynomial functional refresh according to the following expression: , with And .

Advantageously, this implementation allows to determine the functional refresh polynomial optimal satisfying the conditions stated above.

The refreshed encrypted message c' is then derived (step E34). This refreshed encrypted message c' is obtained by a known method of homomorphic encryption in the torus T (or TLWE encryption) of the coefficient of order 0 of this polynomial . This homomorphic encryption is implemented using the encrypted public version BK of the private encryption key s.

The use of the cyclotomic polynomial of order M in this refreshing method is particularly advantageous because it allows to considerably improve the performance of the processing processes (in particular homomorphic calculations) involving longer messages (and not processed in binary format). Indeed, the known refreshing process does not allow to process messages in the form of long integers without using the binary format. Here, thanks to the use of cyclotomic polynomials, it is possible to carry out this processing for messages in the form of long integers. In particular, the use of the cyclotomic polynomial of order M allows to perform the homomorphic calculation and the refreshing of the encrypted message c during the same operation, on these messages in the form of long integers.

The refresh process ends with step E36. During this step, the cryptographic processing server 3 extracts the refreshed encrypted message c’.

Advantageously, the refreshed encrypted message c' has a noise component e' smaller than the noise component e associated with the encrypted message c.

Claims (12)

Method for determining an encrypted message c(X) corresponding to an encrypted version of a message µ(X), the message µ(X) being in the form of a polynomial of degree less than or equal to N-1 whose coefficients have values in a space with p a non-zero integer, N being a non-zero integer,
said method comprising a step of encrypting the message µ(X) by totally homomorphic encryption, from a private key s(X) in the form of a polynomial of degree less than or equal to N-1, in the encrypted message c(X) in the form of a polynomial belonging to a space , with T _q [X] a space of polynomials of degree less than or equal to N-1 whose coefficients have values in with q a non-zero integer greater than p and a cyclotomic polynomial of order M, with , t a prime number strictly greater than 3 and α a non-zero integer or , with t _i prime numbers and α _i non-zero integers, at least one of the prime numbers t _i being strictly greater than 3. A determination method according to claim 1, wherein the fully homomorphic encryption is implemented by a polynomial encryption function with coefficients in a space defined by a torus T. Method for transforming an encrypted message c(X) determined according to claim 1 or 2 into an encrypted element , said encrypted element belonging to a subspace of space , comprising a step of determining said encrypted element by applying a linear application to the message µ(X), said linear application being a trace operator defined as follows: , with G a subset of the integers between 0 and M-1 and prime to M and predefined weights. Method for refreshing the encrypted message c corresponding to an encrypted version of a message ρ, said message ρ being defined in the torus T , said refreshing method comprising a step of determining a refreshed encrypted message c', the refreshed encrypted message c' comprising a noise component e' smaller than a noise component e of the encrypted message c, the refreshed encrypted message c' being determined on the basis of a polynomial obtained according to the determination method according to claim 1 or 2. A refreshing method according to claim 4, wherein the step of determining the refreshed encrypted message c' comprises a step of calculating a zero-order coefficient of the polynomial with a functional refresh polynomial belonging to the space , with , the notation corresponding to the integer closest to the number x and the notation corresponding to the modulo operator. Method for extracting a homomorphic encrypted element c _β from an encrypted message c(X) in the form of a polynomial belonging to the space , the encrypted message c(X) being determined by a determination method according to claim 1 or 2, the homomorphic encrypted element c _β being obtained by determining the coefficient of order 0 of a polynomial , being a cyclotomic polynomial of order M, with , t being a prime number strictly greater than 3 and α a non-zero integer, being a non-zero integer, said homomorphic encrypted element c _β corresponding to an encrypted element of a linear combination of coefficients of the message µ(X). Extraction method according to claim 6, comprising a step of determining the non-zero integer β so as to verify the following inequality: , said homomorphic encrypted element c _β corresponding to an encrypted element of a coefficient of order β of the message µ(X). Method for aggregating a plurality of encrypted messages c ⁽ⁱ⁾ , i being a natural integer, each encrypted message c ⁽ⁱ⁾ belonging to a space T ⁿ⁺¹ , n being a non-zero natural integer, each encrypted message c ⁽ⁱ⁾ corresponding to an encrypted version of an associated message µ ⁽ⁱ⁾ , this encryption being implemented by means of a private encryption key s, the aggregation method comprising steps of:
- determination of an encrypted key according to the determination method according to claims 1 or 2, and
- aggregating said plurality of encrypted messages c ⁽ⁱ⁾ so as to obtain an encrypted message appearing in the form of a polynomial. The aggregation method of claim 8, wherein the encrypted message appearing in the form of a polynomial is determined on the basis of a polynomial encryption with coefficients in the space defined by the torus T . Device (2A) for determining an encrypted message c(X) corresponding to an encrypted version of a message µ(X), the message µ(X) being in the form of a polynomial of degree less than or equal to N-1 whose coefficients have values in a space with p a non-zero integer, N being a non-zero integer,
the determination device (2A) comprising at least one processor and a storage device, the processor comprising:
- a module for encrypting the message µ(X) by totally homomorphic encryption, from a private key s(X) in the form of a polynomial of degree less than or equal to N-1, in the encrypted message c(X) in the form of a polynomial belonging to a space , withT _q[X] a space of polynomials of degree less than or equal to N-1 whose coefficients have values in with q a non-zero integer greater than p and a cyclotomic polynomial of order M, with , t a prime number strictly greater than 3 and α a non-zero integer or , with t_iprime numbers and α_i non-zero integers, at least one of the prime numbers t_ibeing strictly greater than 3. Cryptographic system (1) comprising:
- a device (2A) for determining an encrypted message c(X) according to claim 11, and
- a cryptographic processing server (3) configured to implement at least one cryptographic processing operation on the encrypted message c(X). Computer program comprising instructions executable by a processor and designed to implement a method according to any one of claims 1 to 9 when these instructions are executed by said processor.