EP4540956A1 - Procédé de détermination homomorphe du signe d'un message par dilatation, procédés et dispositifs associés - Google Patents

Procédé de détermination homomorphe du signe d'un message par dilatation, procédés et dispositifs associés

Info

Publication number
EP4540956A1
EP4540956A1 EP23734502.0A EP23734502A EP4540956A1 EP 4540956 A1 EP4540956 A1 EP 4540956A1 EP 23734502 A EP23734502 A EP 23734502A EP 4540956 A1 EP4540956 A1 EP 4540956A1
Authority
EP
European Patent Office
Prior art keywords
message
encrypted
homomorphic
messages
calculation
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
EP23734502.0A
Other languages
German (de)
English (en)
Inventor
Philippe CHARTIER
Michel Koskas
Mohammed LEMOU
Florian MEHATS
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Ravel Technologies SAS
Original Assignee
Ravel Technologies SAS
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Ravel Technologies SAS filed Critical Ravel Technologies SAS
Publication of EP4540956A1 publication Critical patent/EP4540956A1/fr
Pending legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/008—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols involving homomorphic encryption
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
    • H04L9/3033—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters details relating to pseudo-prime or prime number generation, e.g. primality test

Definitions

  • DESCRIPTION TITLE Method for homomorphic determination of the sign of a message by dilation, associated methods and devices TECHNICAL FIELD [0001] The technical field is that of homomorphic cryptography methods, devices and systems. TECHNOLOGICAL BACKGROUND [0002] Homomorphic cryptography, which makes it possible to perform calculations or data processing on encrypted data, without first decrypting them, has attracted a lot of attention recently. [0003] 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, because this personal data tends to circulate more and more in the digital systems environments that we use on a daily basis.
  • Encryptid and homomorphic processing techniques appear to be a very promising solution, because they make it possible to process data while preserving the anonymity and private nature of this data in a particularly secure manner; not being decrypted during processing.
  • Homomorphic cryptography methods therefore respond, among other things, to the technical challenge of allowing: - an external, generally remote services and processing server to perform “blind” operations on data encrypted, without decrypting them, this server not having the necessary key to decrypt the data, - the data, encrypted, being provided by another, distinct entity (a client, in the IT sense), which, in turn, has the encryption key.
  • These data processing operations may consist of carrying out individual operations, data by data, to format them or filter them by example.
  • LWE learning with errors
  • b ⁇ +e+as
  • - s is a secret key
  • - a is a vector chosen at random, to project the secret key s
  • - e is a random noise component, added to ⁇ +as
  • ba.s equal to ⁇ +e
  • the noise term e must be and remain sufficiently small if we want to be able to recover the message ⁇ .
  • each binary message is decomposed into binary messages (classic binary decomposition), each binary message is encrypted separately, and the operation is then carried out, homomorphically, bit by bit. But in this process, it is necessary to take into account the (encrypted) carry resulting from each addition or binary operation, and propagate this carry to the next binary operation. It is therefore a serial process, very consuming, in terms of calculation time.
  • each binary operation is performed in a homomorphic manner, which multiplies the number of homomorphic (and therefore time-consuming) operations.
  • the coefficients att[0] and att[1] are for example such that (att[0] + att[1]).g ⁇ remains between -1/2 and 1/2.
  • the decomposition of the encrypted message c into these q independent components ci, and the recomposition of the message c from these components ci is carried out by applying the Chinese remainder theorem.
  • the corresponding plaintext message, ⁇ can also be broken down into q components ⁇ i (and recomposed from these), in the same way. Numerous operations on the encrypted message c, for example a homomorphic addition (FIG. 6), a homomorphic multiplication (FIG.
  • the two messages both have a positive sign; Their The signs of components of the message are therefore (-1,1) for message 2/15, and (1,1) for message 7/15 while these messages are both positive, which clearly illustrates that the sign of the complete message cannot be deduced from the sign of its components.
  • the different elements of the discrete torus T p are much closer to each other than the elements of the discrete torus T p1 , or T pi (in addition to being affected by a larger noise component).
  • the first technique makes it possible to scale the message u, more precisely to expand it, by operating directly on its encrypted version c, without expanding the noise e.
  • This expansion operation possibly carried out for several increasingly large expansion coefficients, allows (if necessary) to take the message out of the vicinity of 0 to bring it into a zone where its sign can be determined from weak way, with a very low probability of error, as illustrated schematically in Figure 8.
  • a second technique, implemented in this process then consists of adding: - the sign (in its encrypted version) of the non-expanded message p, knowing that 0 is assigned if the message p is located in a zone of uncertainty, including in particular a central interval, centered on 0, of width e, with - the sign (in its encrypted version) of the dilated message pm, this sign being assigned an attenuation coefficient att[i] which reduces its contribution , compared to the sign of the initial message p.
  • This procedure of sum weighted by increasingly small coefficients, can be generalized in the case where several successive expansions are necessary to exit the zone of uncertainty.
  • ge is a step function: - which is zero on a central interval ]-e/2, e /2[, which has two distinct values, for example -1 and +1 (case of figure 9), on - either side of this central interval, and - which is zero near the ends of the torus, on the intervals ]1/2-e/2, 1/2[ and [-1/2, -1/2+e/2[.
  • the present technology also relates to a method for homomorphically applying the Heaviside function H, which is zero for negative values and equal to 1 otherwise, the method comprising the execution of the method for determining the positive or negative character of the message ⁇ as described above, the function g ⁇ being chosen to be zero for negative values and equal to 1 for positive values.
  • the present technology also relates to a method for homomorphically applying a constant function f piecewise to a message ⁇ , the function f having t distinct pieces, the method comprising: - a decomposition of the function f in the form of a linear combination of translated Heaviside functions, i.e. where the coefficients ⁇ j are integers and where the abscissa points of discontinuity belong to the interval [-1/4, 1/4], - a calculation of the quantity each term being determined, in a homomorphic manner, in accordance with the method for homomorphically applying the Heaviside function H which has just been presented.
  • the present technology also relates to a method of sorting a database, the database comprising at least, in a first location of the database, a first encrypted message ca, and in a second location of the database, a second encrypted message cb, the method comprising at least one writing, in the first location, of the quantity Maxh determined in accordance with the method presented above, or of the quantity Minh, determined in accordance with the method presented above .
  • any of the processes presented above is executed by a computer (programmed or otherwise arranged to execute the process in question), that is to say a device or a electronic system (optionally distributed among several remote, remote devices) comprising at least one processor for executing logical operations, and a memory device for storing data.
  • a computer programmed or otherwise arranged to execute the process in question
  • a device or a electronic system comprising at least one processor for executing logical operations, and a memory device for storing data.
  • the encryption step is optional. Furthermore, the transmission step or the emission step could be omitted in this method.
  • the communication module can be configured to also transmit the result of said homomorphic processing.
  • the present technology also relates to a cryptographic system comprising: - the cryptographic processing server as described above, - a client, configured to encrypt at least the message ⁇ , in the form of the encrypted message c, and to communicate the encrypted message c, or an encrypted database containing the encrypted message c, to the server via a communication channel.
  • a cryptographic system comprising: - the cryptographic processing server as described above, - a client, configured to encrypt at least the message ⁇ , in the form of the encrypted message c, and to communicate the encrypted message c, or an encrypted database containing the encrypted message c, to the server via a communication channel.
  • FIG. 2 schematically represents an exemplary embodiment of a cryptographic processing server that can be used in the system of Figure 1.
  • FIG.3 schematically represents another exemplary embodiment of a cryptographic processing server that can be used in the system of Figure 1.
  • FIG. 4 schematically represents yet another embodiment of a cryptographic processing server that can be used in the system of Figure 1, in particular to carry out encrypted database processing operations.
  • [Fig.5] schematically represents an encryption operation implemented in such a system.
  • FIG. 6 schematically represents a homomorphic addition operation, component by component, for two messages which have been encrypted using the encryption operation of Figure 5.
  • FIG. 7 schematically represents a homomorphic multiplication operation, component by component, between two messages which have been encrypted using the encryption operation of Figure 5.
  • FIG. 8 schematically represents the effect of a scaling operation on a message whose sign we seek to determine.
  • FIG. 9 schematically represents a function used to determine, in a homomorphic manner, the positive or negative character of such a message.
  • FIG.10 schematically represents a packet fusion method, used to determine, in a homomorphic manner, the positive or negative character of such a message.
  • FIG. 11 shows an algorithm (in pseudocode) implementing this packet fusion method.
  • FIG.12 groups together, in the form of a table, values of Bézout coefficients, and “dilated” Bézout coefficients used to determine, in a homomorphic manner, the positive or negative character of such a message , for an example of implementation.
  • Figure 1 represents, synoptically, a cryptographic system 1 comprising: - a cryptographic processing server, 3, and - an entity 2, distinct from the server 3, configured to transmit one or more messages to the server 3 , in encrypted form, for example in the form of an encrypted database DB.
  • the server 3 is configured to perform processing operations (function application, comparison, sorting) on the encrypted message(s) received, and this in a homomorphic manner, that is to say without decryption of the messages. Server 3 does not have the private encryption key used to produce the encrypted message(s), from one or more unencrypted clear messages.
  • the entity in question, 2 distinct from the processing server, perhaps an external database, or a client (in the IT sense), configured to encrypt one or more messages (and, possibly, to collect at these messages), with a private key s, before transmitting the encrypted message(s) corresponding to the server 3, the message(s) being for example accompanied by a processing request.
  • a communication channel 5 connects the entity 2 and the server 3.
  • the cryptographic system 1 can also include a recipient entity 4, distinct from the server 3, the result of the homomorphic processing carried out by the server 3 (result which is itself encrypted) being transmitted to this recipient entity 4, via a channel communication channel 6.
  • the recipient entity 4 can be the entity 2 itself, and the communication channels 5 and 6 can form the same bidirectional communication channel.
  • the server 3 comprises a communication module, for receiving and/or transmitting data (in practice one or more encrypted messages, grouped for example in the form of the encrypted database DB), and a calculation module, to carry out the homomorphic processing operations mentioned above.
  • the modules in question can take 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 a programmable circuit, and a memory (for the calculation module).
  • the server itself can thus take the form of its own electronic device.
  • the modules in question can 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 reception and/or transmission of data (for the communication module), or data processing (for the cryptographic calculation module).
  • the server 3 can 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 (structure delocalized on several distinct electronic support devices, and distant from each other, networked).
  • the server 3 can be programmed to carry out different processing operations in a homomorphic manner. [0081] It can for example be programmed to apply a function piecewise to a message.
  • the piecewise function in question can for example be the sign function Sign (which is worth +1 if the message is positive, -1 if it is negative, and 0 if the message is zero), or the Heaviside function H (which is worth 0 if the message is zero or negative, and +1 otherwise), or a piecewise function f with more than two pieces.
  • the server can also be programmed to compare two encrypted messages ca and cb, by determining the maximum or minimum of these two messages. This is the case for the server 31 corresponding to the exemplary embodiment of FIG. 3.
  • the server can also be programmed to sort (classify) such messages, in order to sort an encrypted database DB (without deciphering it), to produce a fully or partially sorted DB' database, for example. This is the case for the server 32 corresponding to the exemplary embodiment of FIG. 4.
  • a common tool which is a method for homomorphic determination of the positive or negative character of a message (for example via the homomorphic calculation of the sign function, or the heaviside function), or, more generally, determination of the position of this message in relation to a discontinuity of a piecewise function.
  • Encryption scheme As indicated above, the encryption scheme used is based on a decomposition into components, or in other words into sub-messages, based on the Chinese remainder theorem. [0089] In this diagram, each initial message x, unencrypted, belongs to with the integers pi being first among them.
  • This decomposition is carried out during step D, in Figure 5.
  • a reduced component ⁇ i xi/pi belonging to the discrete torus Tpi is then calculated, here.
  • the complete encrypted message can also be explicitly reconstructed, from these components, in the form which directly corresponds to an encrypted version of ⁇ (encryption by learning with error, with the same key s).
  • each component ci is decrypted (to obtain the plain component ⁇ i), before recomposing the complete message in plain text ⁇ .
  • Each component ci is decrypted, by a decryption module having the private key s, by calculating the quantity bi-ai.s (which is equal to ⁇ i+ei), and rounding the result to the nearest value of the discrete torus Tpi, thus removing the noise component ei to finally obtain ⁇ i.
  • the encrypted component ci obtained by thus encrypting the component ⁇ i can also be noted [0100]
  • the encryption scheme is presented above in the case where the message ⁇ belongs to the discrete torus Tp.
  • This encryption scheme can however also be applied when the message ⁇ belongs to a discrete set in bijection with Tp, for example when the message belongs to [00101]
  • a “refreshed” version C' of the encrypted message C can be determined by calculating, component by component, the following quantity where G designates a bootstrapping operation for messages belonging to Tpi (and which at the same time applies a function g to clear message).
  • This boostrapping operation is described in more detail in the aforementioned patent application PCT/IB2020/001147, in paragraphs 85 to 117, and in initial claim 3 of this earlier application.
  • Homomorphic determination of the positive or negative character of a message [00108] As explained in the “summary” section, unlike the operations of addition, subtraction, multiplication and boostrapping, the sign of the message ⁇ cannot be determined, from the respective signs of the components of this message.
  • a scaling operation more precisely dilation, which, remarkably, does not increase the noise affecting the message, can then make it possible to bring the value of the message out of this zone of uncertainty ( figure 8).
  • the uncertainty zone in question corresponds to the intervals: ]-e/2,e/2[, ]1/2-e/2, 1/2[ and [- 1/2, -1/2+e/2 [ (where e is a parameter, presented later).
  • This scaling operation consists of calculating a dilated encrypted message c [1] , from the message c (more precisely, from its components Ci), in accordance with the following formula where the expansion coefficient p is an odd number greater than or equal to 3, and less than p.
  • K can thus be chosen as follows: or even as follows.
  • the quantity Fk(c [k] ) is evaluated during a bootstrapping operation (during which the noise is refreshed, and, in addition, the function considered is evaluated).
  • the attenuation coefficients a(k) are preferably chosen such that their sum att[o ],+...+ att[kj+... att[Ki] is less than 1/2.
  • the result of this sum calculation then belongs to the torus T (which facilitates its subsequent use, in the encryption scheme used here).
  • This condition as well as the particular decay condition mentioned above, can be obtained for example by choosing, for the coefficients att[k], the value AR k , where the ratio R of this geometric sequence is less than 1/2, and where A is less than (1 -R)/2.
  • each packet can, for example, include 2 to 5 terms.
  • this merger by packets can be carried out by executing the following steps: - S1: mergers by packets, each packet grouping m terms, each merger of a packet corresponding to the calculation of the intermediate result i being the packet number, - S2: packet mergers of intermediate results resi, each merger of a packet of m' intermediate results corresponding to the calculation of a new intermediate result j being the packet number, designating a homomorphic calculation operation of a quantity - step S2 being repeated until only one result is obtained, to which the operation is applied which provides a final result which is an encrypted version of the message sign p.
  • each arrow represents a boostrapping operation, with evaluation of the quantity att[k].ge for terms of type Fk(), or with evaluation of the quantity for terms of type
  • s is another uncertainty width, used to merge the intermediate results mentioned above (the function is defined in the same way than ge, but replacing ⁇ by is for example equal to 1/(2N), where N-1 is the degree of the specific bootstrapping polynomial W g [X] (see claim 3 of application PCT/IB2020/001147,), also denoted v[X] .
  • step S2 is executed r-1 times.
  • Figure 12 is a table which, for this example, groups together the values of the Bézout coefficients Vj, the values of the “dilated” Bézout coefficients (which also illustrates that these values remain advantageously small, although allowing an expansion of the message), and values of the quantity which intervenes in the calculation of the noise affecting the encrypted messages dilated.
  • the function is a piecewise constant function with possible discontinuities at points such that either [00171]
  • the function g ⁇ being odd with right-hand discontinuities in ⁇ /2 and in 1/2- ⁇ /2, a natural choice for the parameter ⁇ is under duress either
  • the server 3 will for example be programmed so as to execute the following operations: - decomposition of the function f in the form of a linear combination of translated Heaviside functions, i.e. where the coefficients ⁇ j are integers and where the abscissa of the points of discontinuity belong to the interval [-1/4, 1/4], - calculation of the quantity each term being determined, homomorphically, as indicated above for the Heaviside H function.
  • the server 31 of the exemplary embodiment of Figure 3 is programmed to perform these operations.
  • the module 310 of this server performs the homomorphic subtraction Then the module 30 determines the quantity h from Cd.
  • the module 311 then carries out the operations and delivers the corresponding results, Maxh and Minh.
  • the quantities Maxh and Minh could be determined by - homomorphically determining an encrypted version of denoted h', then - by calculating the quantity h'.c b +(1 -h').c a (for the maximum) and h'.c a +(1 -h').c b (for the minimum ).
  • the quantities Maxh and Minh could each be determined from a numerical version of the sign of the difference
  • the server 32 of the exemplary embodiment of Figure 4 is programmed to execute a process for sorting an encrypted database DB.
  • This database includes at least, in a first location of the database, a first encrypted message c a , and in a second location of the database, a second encrypted message c b .
  • This sorting method comprises at least: - a writing, in the first location, of the quantity Maxh presented above, determined from c a and c b , or, respectively, of the quantity Minh presented above above (determined from c a and c b ), and - a writing, in the second location, of the quantity Minh, or, respectively, of the quantity Maxh.
  • the first and second locations in question can for example each be identified, in the database, by an indexing number associated with the location considered (for example a line number, in a form database matrix).

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Financial Or Insurance-Related Operations Such As Payment And Settlement (AREA)
  • User Interface Of Digital Computer (AREA)
  • Storage Device Security (AREA)

Abstract

Procédé de détermination homomorphe du caractère positif ou négatif d'un message μ à partir d'un message chiffré c correspondant, chiffré par une méthode de type apprentissage avec erreur, le message μ appartenant au tore discret Tp ou à un espace en bijection avec Tp, avec Formula (p) les entiers pi étant premiers entre eux, le message chiffré c étant formé de q composantes Ci, avec Formula (c), vi étant le coefficient de Bézout associé à l'entier pi. Le procédé comprend au moins une dilatation du message chiffé c conformément à la formule (c[1]), où p est un nombre impair supérieur ou égal à 3. Le procédé comprend aussi une fusion de quantités représentatives du signe de c et du signe de c[1].

Description

DESCRIPTION TITRE : Procédé de détermination homomorphe du signe d’un message par dilatation, procédés et dispositifs associés DOMAINE TECHNIQUE [0001] Le domaine technique est celui des méthodes, dispositifs et systèmes de cryptographie homomorphe. ARRIERE-PLAN TECHNOLOGIQUE [0002] La cryptographie homomorphe, qui permet d'effectuer des calculs ou des traitements de données sur des données chiffrées, sans les déchiffrer au préalable, a suscité beaucoup d'attention dernièrement. [0003] En effet, le traitement numérique de données personnelles est devenu omniprésent dans notre vie quotidienne. La protection de la confidentialité de ces données, et de la vie privée des individus concernés est donc devenue critique, car ces données personnelles ont tendance à circuler de plus en plus dans les environnements en systèmes digitaux que nous utilisons au quotidien. [0004] Dans ce contexte, les techniques de chiffrement et traitement homomorphe apparaissent comme une solution très prometteuse, car elles permettent de traiter des données tout en préservant de manière particulièrement sûre l'anonymat et le caractère privé de ces données, ces dernières n'étant pas déchiffrées pendant leur traitement. [0005] Les méthodes de cryptographie homomorphe répondent donc, entre autres, à l’enjeu technique qui consiste à permettre : - à 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. [0006] Ces opérations de traitement de données peuvent consister à effectuer des opérations individuelles, donnée par donnée, pour les mettre en forme ou les filtrer par exemple. Mais les applications les plus notables concernent des opérations de comparaison entre données, de tri ou de regroupement. Il est donc très utile de disposer d’outil permettant de réaliser de manière efficace des comparaisons entre données chiffrées, et cela de manière homomorphe. [0007] La cryptographie homomorphe peut être basée sur le schéma de cryptage dit "apprentissage avec erreur" (« learning with errors » ou LWE, en anglais), dans lequel le message crypté c=(a,b) est dérivé du message non crypté µ selon la formule suivante : b=µ+e+a.s, où : - 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. [0008] Pour décrypter le message, une personne possédant la clé secrète s peut calculer la quantité b-a.s (égale à µ+e), puis arrondir le résultat pour supprimer la composante de bruit e et retrouver le message µ. Bien entendu, le terme de bruit e doit être et rester suffisamment petit si l'on veut pouvoir récupérer le message µ. [0009] Lorsque l'on additionne deux messages cryptés, on obtient un message crypté, qui est une version cryptée de la somme (des deux messages initiaux non cryptés, dont la composante de bruit est plus élevée que pour les deux messages cryptés initiaux. [0010] Ainsi, pour empêcher le terme de bruit d'augmenter et de croître au cours du traitement des données, une procédure de rafraîchissement, généralement appelée "bootstrapping", est exécutée de manière répétée. Cette procédure produit une version rafraîchie de c, c'est-à-dire un message crypté c' qui est décrypté lui aussi en tant µ (lorsqu'il est décrypté en utilisant s), mais dont la composante de bruit est plus petite que celle de c. Cette procédure de boostrapping est extrêmement utile et ingénieuse, mais elle est aussi très consommatrice, en termes de ressources de calcul (en particulier parce que les opérations impliquées doivent être effectuées de manière homomorphique), d'autant plus qu'elle doit être exécutée très régulièrement. [0011] Le schéma de chiffrement homomorphe décrit ci-dessus, qui combine "apprentissage avec erreur" et bootstrapping a ainsi l’inconvénient d’être généralement très lourd à mettre en oeuvre, nécessitant une puissance ou un temps de calcul très importants.
[0012] Pour faciliter les opérations en question, il est alors choisi, en général, de d’opérer sur des messages binaires (c'est-à-dire des messages dont la valeur est soit 0 soit 1 ). Les outils, complexes (notamment pour le boostrapping), qui ont été développés pour mettre en oeuvre ce type de schéma cryptographique, sont ainsi des outils adaptés à des messages binaires.
[0013] Pour effectuer des opérations homomorphes sur un message plus long, le message est décomposé en messages binaires (décomposition binaire classique), chaque message binaire est crypté séparément, et l'opération est ensuite effectuée, de manière homomorphe, bit par bit. Mais dans ce processus, il faut tenir compte de la retenue (chiffrée) résultant de chaque addition ou opération binaire, et propager cette retenue à l'opération binaire suivante. Il s'agit donc d'un processus série, très consommateur, en termes de temps de calcul. De plus, chaque opération binaire est effectuée de manière homomorphe, ce qui multiplie le nombre d'opérations homomorphes (et donc coûteuses en temps).
[0014] Dans ce contexte, il serait donc utile de disposer d’une technique de cryptographie homomorphe plus efficace sur le plan calculatoire, et adaptée notamment à des opérations de traitement de base de données, par exemple de type comparaison ou tri.
RESUME
[0015] La présente technologie concerne alors un procédé de détermination homomorphe du caractère positif ou négatif d’un message μ à partir d’un message chiffré c correspondant, sans déchiffrement du message chiffré c, le message chiffré c correspondant au message μ chiffré par une méthode de type apprentissage avec erreur, - le message μ appartenant au tore discret ou à un espace en bijection avec Tp, avec Ies entiers pi étant premiers entre eux, le message chiffré c étant formé de q composantes ci, avec vi étant le coefficient de Bézout associé à l’entier pi, défini par ui pi + vi p/pi = 1 , - le procédé comprenant : - une étape de mise à l’échelle, comprenant une détermination d’un message chiffré dilaté c[1] conformément à la formule suivante est un nombre impair supérieur ou égal à 3, et - une étape de fusion, comprenant un calcul de la somme F0(c) + F1(c[1]) où F0 et F1 désignent respectivement une opération de calcul homomorphe d’une quantité att[0].gε, et d’une quantité att[1].gε, gε étant une fonction en escalier qui est nulle sur un intervalle central ]-ε/2, ε/2[ et qui a deux valeurs distinctes de part et d’autre de cet intervalle central, le coefficient att[1] étant inférieur au coefficient att[0]. [0016] Les coefficients att[0] et att[1] sont par exemple tels que (att[0] + att[1]).gε reste compris entre -1/2 et 1/2. [0017] La décomposition du message chiffré c en ces q composantes indépendantes ci, et la recomposition du message c à parti de ces composantes ci est réalisée en appliquant le théorème des restes chinois. [0018] Le message en clair correspondant, µ, peut d’ailleurs être décomposé en q composantes µi (et recomposé à partir de celles-ci), de la même manière. [0019] De nombreuses opérations sur le message chiffré c, par exemple une addition homomorphe (figure 6), une multiplication homomorphe (figure 7), ou une opération de bootstraping, peuvent être réalisées composante par composante, en traitant les q composantes ci du message c, indépendamment les uns des autres, sans avoir à propager aucune retenue entre eux. [0020] On tire ainsi partie de la décomposition particulière du théorème chinois, pour traiter en parallèle, indépendamment, les différentes composantes ci du message chiffré c, ce qui permet un traitement accéléré, par rapport à une décomposition binaire avec propagation de retenues (chiffrées). [0021] Il est noté que les différentes composantes ci correspondent à des « sous- messages » chiffrés, associés chacun (par chiffrement) à l’un des « sous-messages » µi composant le message en clair total µ (figure 5). [0022] Prévoir d’utiliser une telle décomposition, pour développer une technique de cryptographie homomorphe plus efficace, est très loin d’être immédiat. En effet, comme mentionné ci-dessus, la plupart des outils de cryptographie homomorphique actuellement disponibles sont adaptés spécifiquement aux messages binaires. Ainsi, pour mettre au point une telle technique, il a fallu aller à l'encontre des pratiques et préjugés habituels et développer des outils spécifiques (et élaborés) destinés à des messages plus longs que juste binaire (i.e. : pour traiter les sous-messages µi, qui ne sont pas seulement binaire, à deux valeurs, puisqu’ils peuvent prendre pi valeurs, avec pi = 3, 7, 11 ou encore 17, par exemple), sans même savoir si un traitement homomorphique direct de « longs » messages était réellement possible ou non, ou s'il pouvait être exécuté efficacement ou non. En particulier, la mise en place d’un tel schéma de chiffrement a nécessité d’élaborer un nouveau schéma de multiplication homomorphe et une nouvelle méthode de boostrapping. Ce n'est qu'une fois ces nouveaux outils mis au point que les inventeurs ont pu être sûrs de la faisabilité et de l’intérêt d’un tel schéma, à décomposition via the théorème des restes chinois. [0023] Ces nouveaux outils (nouveau boostrapping, et nouvelle multiplication homomorphe pour sous-messages « longs » non-binaires) sont décrits en détail dans la demande de brevet PCT/IB2020/001147, non encore publiée, et qui a été déposée par le même déposant. [0024] Cette avancée, basée sur ces nouveaux outils de calcul homomorphe, et sur cette utilisation du théorème des restes chinois, permet de traiter des messages longs (pouvant prendre par exemple 7×11×13×17×19 = 323323 valeurs différentes). [0025] Néanmoins, comme indiqué en préambule, une opération très utile dans le domaine du traitement de données (en particulier pour le traitement de bases de données à caractère personnel ou privé) est la comparaison de deux messages (de deux données) l’un avec l’autre, par exemple pour trier une base de données ou pour réaliser des extractions dans celle-ci. [0026] Une manière de comparer deux messages (pour déterminer lequel est le plus grand) est de calculer leur différence, puis de déterminer le signe de la différence. [0027] Le calcul homomorphe de la différence de deux messages, construits comme indiqué ci-dessus (à partir de sous-messages indépendants, via le théorème des restes chinois), ne pose pas de difficulté particulière, et peut être réalisée composante par composante. En revanche, la détermination homomorphe du signe d’un tel message présente des difficultés.
[0028] En effet, le signe du message « complet » μ n’a pas de lien avec les signes respectifs des différentes composantes μi qui le compose. Le signe du message p ne peut donc pas être déterminé composante par composante.
[0029] Cela est illustré par l’exemple numérique suivant, où
Les deux messages ont tous deux un signe positif ; Leurs Les signes des composantes du message sont donc (-1 ,1 ) pour le message 2/15, et (1 ,1 ) pour le message 7/15 alors que ces messages sont tous les deux positifs, ce qui illustre bien que le signe du message complet ne peut pas être déduit du signe de ses composantes.
[0030] Or la détermination du signe du message complet p, directement à partir du message chiffré complet c (et sans déchiffrement de ses composantes), pose des difficultés, à cause de la discontinuité de la fonction signe en 0 et à cause de la composante de bruit e présente dans le message chiffré complet c (avec e = Err(μ ) = composante qui est nettement plus importante que pour les messages individuels pi. Ainsi, lorsque μ est assez proche 0, du fait de cette composante de bruit importante pour c, une détermination (homomorphe) fiable du caractère positif ou négatif de μ, directement à partir du message chiffré c, n’est plus possible.
[0031] Cette difficulté est d’autant plus marquée que les valeurs de p, qui appartiennent à Tp, p=p1x...xpq, peuvent être nettement plus proches de 0 que les valeurs des messages individuels μ1 ... μq, qui appartiennent, elles à Tpi, ou TPi. Autrement dit, les différents éléments du tore discret Tp sont beaucoup plus proches les uns des autres que les éléments du tore discret Tp1, ou Tpi (en plus d’être affectés par une composante de bruit plus importante).
[0032] On notera que les difficultés en question se posent lorsque la valeur de p est proche de 0 ou des extrémités 1/2 et -1/2 du tore. En revanche, pour les valeurs éloignées de ces points (par exemple pour les valeurs proches de 1 /4, ou de -1/4), une détermination fiable du signe du message p est possible directement, à partir de son chiffré c, via une opération de bootstrapping incluant l’évaluation de la fonction signe. [0033] Pour surmonter la difficulté mentionnée ci-dessus, deux techniques ingénieuses ont été mises au point par les inventeurs.
[0034] La première technique permet de mettre à l’échelle le message u, plus précisément de le dilater, en opérant directement sur sa version chiffrée c, sans dilater en ne dilatant la de bruit e. Cette opération de dilatation, réalisée éventuellement pour plusieurs coefficients de dilatation de plus en plus grands, permet (s’il y a lieu) de faire sortir le message du voisinage de 0 pour l’amener dans une zone où son signe peut être déterminé de manière faible, avec une probabilité d’erreur très faible, comme illustré schématiquement sur la figure 8.
[0035] Cette dilatation de la valeur du message, mais pas du bruit associé, est réalisée en calculant le message chiffré dilaté C[1] comme suit : c[1] = où le coefficient de dilatation p est un nombre impair, supérieur ou égal à 3.
[0036] Ainsi, dans la somme plutôt que de multiplier le sous-message chiffré Ci par (ce qui augmenterait sa composante de bruit), c’est le coefficient vi que l’on multiplie par
[0037] Et comme les coefficients de Bézout sont définis à chacun à pi près (i.e. : modulo pi), on peut conserver une valeur réduite pour le ‘coefficient’ qui multiplie Ci, dans cette somme, ce qui permet de dilater c (plus précisément : dilater p), en ne dilatant quasiment pas sa composante de bruit e.
[0038] Cette opération de dilatation sans bruit est très utile si la valeur du message p est proche de 0, comme expliqué ci-dessus. En revanche, si la valeur de p est déjà suffisamment grande avant dilatation (par exemple proche de 1/4), l’opération de dilatation, en augmentant la valeur de p, va modifier son signe (du fait de la cyclicité du tore), conduisant ainsi à un résultat erroné. Il faudrait donc ne dilater le message que si nécessaire.
[0039] Mais justement, dans un protocole de cryptographie homomorphe, la valeur initiale du message n’est pas connue, et les opérations sont exécutées en quelque sorte en aveugle, toujours sous forme chiffrée. Ainsi, on ne peut pas savoir, a priori, s’il est nécessaire de dilater le message, ou s’il faut, au contraire s’abstenir de le dilater. [0040] Une deuxième technique, mise en œuvre dans ce procédé, consiste alors à sommer : - le signe (dans sa version chiffrée) du message non dilaté p, sachant que 0 est attribué si le message p est située dans une zone d’incertitude, comprenant notamment un intervalle central, centré sur 0, de largeur e, avec - le signe (dans sa version chiffrée) du message dilaté pm, ce signe étant affecté d’un coefficient d’atténuation att[i] qui réduit sa contribution, par rapport au signe du message initial p.
[0041] Ainsi, si le message initial p a une valeur assez grande pour déterminer son signe sans erreur, c’est le premier terme qui dominera, dans cette somme (grâce au coefficient d’atténuation att[i]), et qui fixera le signe de l’ensemble de la somme (tandis que le signe du dilaté, qui est « faux », verra sa contribution écrasée).
[0042] Au contraire, si le message initial est dans la zone d’incertitude en question (avec un signe ne pouvant être déterminé de manière fiable), alors, dans cette somme, le premier terme est nul, et le signe de la somme est fixé par le signe du dilaté, qui, cette fois-ci, a au contraire une valeur correcte, correspondant au signe de c lui-même.
[0043] Cette procédure, de somme pondérée par des coefficients de plus en plus petits, peut être généralisée au cas où plusieurs dilatations successives sont nécessaires pour sortir de la zone d’incertitude.
[0044] Pour déterminer de manière homomorphe le signe du message p à partir de son chiffré c, mais en affectant la valeur 0 à ce résultat lorsque le message se trouve dans la zone d’incertitude en question, on applique de manière homomorphe une fonction ge ou att[o].ge à p (cette fonction étant appliquée lors d’un boostrapping avec calcul de fonction intégré), où ge est une fonction en escalier : - qui est nulle sur un intervalle central ]-e/2, e/2[, qui a deux valeurs distinctes, par exemple -1 et +1 (cas de la figure 9), de - part et d’autre de cet intervalle central, et - qui est nulle près des extrémités du tore, sur les intervalles ]1/2-e/2, 1/2[ et [-1/2, -1/2+e/2[. [0045] Les deux techniques mentionnées ci-dessus permettent une détermination homomorphe du signe d’un message, décomposé en sous-messages sur la base du théorème des restes chinois. Elles permettent plus généralement d’appliquer n’importe quelle fonction constante par morceau à un tel message (par exemple la fonction de Heaviside, ou une autre fonction ayant plus de deux morceaux distincts, sur l’intervalle [-1/2, 1/2[.
[0046] Outre les caractéristiques mentionnées ci-dessus, le procédé qui vient d’être présenté peut comporter une ou plusieurs des caractéristiques optionnelles suivantes, considérées individuellement ou selon toutes les combinaisons techniquement envisageables : - l’étape de mise à l’échelle comprend des déterminations de plusieurs messages chiffrés dilatés c[k], l’entier k variant de 1 à K-1 , chaque message chiffré dilaté étant déterminé conformément à la formule suivante c[k] = , et dans lequel le caractère positif ou négatif du message p est déterminé en fonction de c et en fonction des différents messages chiffrés dilatés - l’étape de fusion comprend une étape de fusion d’un paquet au cours de laquelle la somme suivante est calculée : Fm(c[m]), où Fk désigne une opération de calcul homomorphe de la quantité att[k].ge, où att[k] est un coefficient d’atténuation inférieur à 1 , la suite de coefficients att[k], k=0..m étant décroissante et telle : que la somme des coefficients d’atténuation, successifs à l’un des coefficients d’atténuation donné de la suite, est inférieure audit coefficient d’atténuation donné ; il s’agit par exemple d’une suite géométrique de raison inférieure à - m est inférieur à K ; - l'étape de fusion comprend les étapes suivantes
S1 : fusions par paquets, chaque paquet regroupant m termes, chaque fusion d'un paquet correspondant au calcul du résultat intermédiaire i étant le numéro du paquet, - S2 : fusions par paquets des résultats intermédiaires resi, chaque fusion d'un paquet de m’ résultats intermédiaires correspondant au calcul d’un nouveau résultat intermédiaire res'j = étant le numéro du paquet, désignant une opération de calcul homomorphe d’une quantité - l'étape S2 étant répétée jusqu'à n'obtenir qu'un seul résultat, auquel est appliqué l’opération , qui fournit un résultat final qui est une version chiffrée du signe du message μ. - le nombre K-1 de messages chiffrés dilatés pris en compte est tel que - lequel la largeur ε de l’intervalle central est inférieure à
[0047] La présente technologie concerne également un procédé pour appliquer de manière homomorphe la fonction de Heaviside H, qui est nulle pour les valeurs négatives et égale à 1 sinon, le procédé comprenant l’exécution du procédé de détermination du caractère positif ou négatif du message μ tel que décrit ci-dessus, la fonction gε étant choisie nulle pour les valeurs négatives et égale à 1 pour les valeurs positives.
[0048] La présente technologie concerne aussi un procédé pour appliquer de manière homomorphe une fonction f constante par morceaux à un message μ, la fonction f ayant t morceaux distincts, le procédé comprenant : - une décomposition de la fonction f sous la forme d’une combinaison linéaire de fonctions de Heaviside translatées, soit où les coefficients αj sont des entiers et où les abscisses des points de discontinuité appartiennent à l’intervalle [-1/4, 1/4], - un calcul de la quantité chaque terme étant déterminé, de manière homomorphe, conformément au procédé pour appliquer de manière homomorphe la fonction de Heaviside H qui vient d’être présenté. [0049] La présente technologie concerne aussi un procédé pour déterminer de manière homomorphe le maximum de deux messages µa et µb, à partir des messages chiffrés correspondants ca et cb, sans déchiffrement des messages chiffrés ca et cb, le procédé comprenant : - une détermination homomorphe de la quantité H(µa - µb), la fonction de Heaviside H étant appliquée comme indiqué ci-dessus, la version chiffrée de H(µa - µb) ainsi déterminée étant notée h, et - le calcul de la quantité Maxh=h.ca+(1-h).cb - ou, une détermination homomorphe de la quantité H(µb - µa), la fonction de Heaviside H étant appliquée comme indiqué ci-dessus, la version chiffrée de H(µb - µa) ainsi déterminée étant notée h’, et le calcul de la quantité h’.cb+(1-h’).ca . [0050] La présente technologie concerne aussi un procédé pour déterminer de manière homomorphe le minimum de deux messages µa et µb, à partir des messages chiffrés correspondants ca et cb, sans déchiffrement des messages chiffrés ca et cb, le procédé comprenant : - une détermination homomorphe de la quantité H(µa - µb), la fonction de Heaviside H étant appliquée comme indiqué ci-dessus, la version chiffrée de H(µa - µb) ainsi déterminée étant notée h, et - le calcul de la quantité Minh=h.cb+(1-h).ca - ou, une détermination homomorphe de la quantité H(µb - µa), la fonction de Heaviside H étant appliquée comme indiqué ci-dessus, la version chiffrée de H(µb - µa) ainsi déterminée étant notée h’, et le calcul de la quantité h’.ca+(1-h’).cb . [0051] La présente technologie concerne aussi un procédé de tri d’une base de données, la base de données comprenant au moins, dans un premier emplacement de la base de données, un premier message chiffré ca, et dans un deuxième emplacement de la base de données, un deuxième message chiffré cb, le procédé comprenant au moins une écriture, dans le premier emplacement, de la quantité Maxh déterminée conformément au procédé présenté ci-dessus, ou de la quantité Minh, déterminée conformément au procédé présenté ci-dessus. [0052] Selon un aspect de la présent technologie, l'un quelconque des procédé présentées ci-dessus est exécuté par un ordinateur (programmé ou autrement agencé pour exécuter le procédé en question), c'est-à-dire un dispositif ou un système électronique (éventuellement réparti entre plusieurs dispositifs distants, à distance) comprenant au moins un processeur pour exécuter des opérations logiques, et un dispositif de mémoire pour stocker des données. [0053] La présente technologie concerne aussi une méthode de communication et traitement chiffrés, comprenant les étapes suivantes : - chiffrement d’au moins un message µ, avec une clef privée s, par un client, sous la forme d’un message chiffré c, par une méthode de type apprentissage avec erreur, le message µ appartenant au tore discret ou à un espace en bijection avec avec , les entiers pi étant premiers entre eux, le message chiffré c=(c1,...ci,...cq) étant formé de q composantes ci, avec étant le coefficient de Bézout associé à l’entier pi , défini par - transmission du message chiffré c, ou d’une base de données chiffrée contenant le message chiffré c, par le client, à un serveur distinct du client et ne disposant pas de la clef privée s, via un canal de communication, - traitement du message chiffré c, ou d’une différence entre le message chiffré c et un autre message chiffré, ou de la base de données chiffrées contenant le message chiffré c, par le serveur, de manière homomorphe, conformément à l’un quelconque des procédé décrits ci-dessus, - émission du résultat dudit traitement homomorphe, par le serveur. [0054] Dans cette méthode, l’étape de chiffrement est optionnelle. Par ailleurs, l’étape de transmission ou celle d’émission pourrait être omise, dans cette méthode. [0055] La présente technologie concerne aussi un serveur de traitement cryptographique, comprenant au moins un module de communication et un module de calcul : - le module de communication étant configuré pour recevoir, de la part d’une entité externe au serveur, un message chiffré c ou une base de données chiffrée contenant le message chiffré c, le message chiffré c correspondant à un message µ chiffré par une méthode de type apprentissage avec erreur, le message µappartenant au tore discret p ou à un espace en bijection avec les entiers pi étant premiers entre eux, le message chiffré c=(c1,...ci,...cq) étant formé de q composantes ci, avec étant le coefficient de Bézout associé à l’entier pi, défini par - le module de calcul étant programmé pour traiter le message chiffré c, ou une différence entre le message chiffré c et un autre message chiffré, ou la base de données chiffrée contenant le message chiffré c, de manière homomorphe, sans déchiffrement du message c, conformément à l’un quelconque des procédés (de traitement) décrits ci-dessus. [0056] Le module de communication peut être configuré pour émettre aussi le résultat dudit traitement homomorphe. [0057] La présente technologie concerne aussi un système cryptographique comprenant : - le serveur de traitement cryptographique tel que décrit ci-dessus, - un client, configuré pour chiffrer au moins le message µ, sous la forme du message chiffré c, et pour communiquer le message chiffré c, ou une base de données chiffrée contenant le message chiffré c, au serveur via un canal de communication. [0058] La présente technologie et ses différentes applications seront mieux comprises à la lecture de la description qui suit et à l’examen des figures qui l’accompagnent. BREVE DESCRIPTION DES FIGURES [0059] Les figures sont présentées à titre indicatif et nullement limitatif. [0060] [Fig. 1] représente schématiquement un système cryptographique mettant en œuvre la présente technologie. [0061] [Fig. 2] représente schématiquement un exemple de réalisation d’un serveur de traitement cryptographique pouvant être employé dans le système de la figure 1. [0062] [Fig.3] représente schématiquement un autre exemple de réalisation d’un serveur de traitement cryptographique pouvant être employé dans le système de la figure 1. [0063] [Fig. 4] représente schématiquement encore un autre exemple de réalisation d’un serveur de traitement cryptographique pouvant être employé dans le système de la figure 1, notamment pour réaliser des opérations de traitement de bases de données chiffrées. [0064] [Fig.5] représente schématiquement une opération de chiffrement mise en œuvre dans un tel système. [0065] [Fig. 6] représente schématiquement une opération d’addition homomorphe, composante pas composante, pour deux messages qui ont été chiffrés en employant l’opération de chiffrement de la figure 5. [0066] [Fig. 7] représente schématiquement une opération de multiplication homomorphe, composante pas composante, entre deux messages qui ont été chiffrés en employant l’opération de chiffrement de la figure 5. [0067] [Fig. 8] représente schématiquement l’effet d’une opération de mise à l’échelle sur un message dont on cherche à déterminer le signe. [0068] [Fig. 9] représente schématiquement une fonction employée pour déterminer, de manière homomorphe, le caractère positif ou négatif d’un tel message. [0069] [Fig.10] représente schématiquement une méthode de fusion par paquets, employée pour déterminer, de manière homomorphe, le caractère positif ou négatif d’un tel message. [0070] [Fig. 11] montre un algorithme (en pseudocode) mettant en œuvre cette méthode de fusion par paquets. [0071] [Fig.12] regroupe, sous forme d’un tableau, des valeurs de coefficients de Bézout, et de coefficients de Bézout « dilatés » employée pour déterminer, de manière homomorphe, le caractère positif ou négatif d’un tel message, pour un exemple de réalisation. DESCRIPTION DETAILLEE [0072] La figure 1 représente, de manière synoptique, un système cryptographique 1 comprenant : - un serveur de traitement cryptographique, 3, et - une entité 2, distincte du serveur 3, configurée pour transmettre au serveur 3 un ou des messages, sous forme chiffrée, par exemple sous la forme d’une base de données chiffrée DB. [0073] Le serveur 3 est configuré pour effectuer des opérations de traitement (application de fonction, comparaison, trie) sur le ou les messages chiffrés reçus, et cela de manière homomorphe, c’est-à-dire sans déchiffrement des messages. Le serveur 3 ne dispose d’ailleurs pas de la clef de chiffrement privé ayant servi à produire le ou les messages chiffrés, à partir d’un ou plusieurs messages en clair non chiffrés. [0074] L’entité en question, 2, distincte du serveur de traitement, peut-être une base de données externe, ou un client (au sens informatique), configuré pour chiffrer un ou des messages (et, éventuellement, pour collecter au préalable ces messages), avec une clef privé s, avant de transmettre le ou les messages chiffrés correspondant au serveur 3, le ou les messages étant par exemple accompagnés d’une requête de traitement. [0075] Un canal de communication 5 relie l’entité 2 et le serveur 3. Il s’agit par exemple d’un canal de communication pour lequel les données transmisses sont susceptibles d’être interceptées. Il peut s’agit s’agir d’un canal de communication sans fil, ou de communication filaire. L’entité 2 et le serveur 3 peuvent être distants l’un de l’autre, par exemple être situés dans des bâtiments différents. Mais il peut aussi s’agir d’entités appartenant à un même système informatique, par exemple au sein d’un même dispositif électronique (par exemple au sein d’un même ordinateur, ou d’un même dispositif électronique portatif). [0076] Le système cryptographique 1 peut aussi comprendre une entité destinataire 4, distincte du serveur 3, le résultat du traitement homomorphe réalisé par le serveur 3 (résultat qui est lui-même chiffré) étant transmis à cette entité destinataire 4, via un canal de communication 6. L’entité destinataire 4 peut être l’entité 2 elle- même, et les canaux de communication 5 et 6 peuvent former un même canal de communication bidirectionnel. [0077] Le serveur 3 comprend un module de communication, pour recevoir et/ou émettre des données (en pratique un ou des messages chiffrés, regroupés par exemple sous la forme de la base de données chiffrée DB), et un module de calcul, pour réaliser les opérations de traitement homomorphe mentionnées plus haut. [0078] Les modules en question peuvent prendre la forme d’un circuit électronique dédié, tel qu’une carte de communication (pour le module de communication), ou un circuit de calcul cryptographique comprenant au moins un processeur ou un circuit programmable, et une mémoire (pour le module de calcul). Le serveur lui-même peut ainsi prendre la forme d’un dispositif électronique propre. [0079] Les modules en question peuvent aussi prendre chacun la forme d’un ensemble d’instructions dont l’exécution par un système informatique (par exemple par un ordinateur) conduit à la réalisation d’étapes de réception et/ou émission de données (pour le module de communication), ou de traitement de données (pour le module de calcul cryptographique). Le serveur 3 peut en particulier prendre la forme de services informatiques délocalisés, disponibles, via un réseau de communication (par exemple via internet, ou via un intranet), dans une structure informatique délocalisée, par exemple de type « cloud » (structure délocalisée sur plusieurs dispositifs électroniques supports distincts, et distants les uns des autres, mis en réseau). [0080] Le serveur 3 peut être programmé pour réaliser de manière homomorphe différentes opérations de traitement. [0081] Il peut par exemple être programmé pour appliquer une fonction par morceaux à un message. C’est le cas pour le serveur 30 correspondant à l’exemple de réalisation de la figure 2. La fonction par morceaux en question peut par exemple être la fonction signe Sign (qui vaut +1 si le message est positif, -1 s’il est négatif, et 0 si le message est nul), ou la fonction de Heaviside H (qui vaut 0 si le message est nul ou négatif, et +1 sinon), ou une fonction par morceaux f à plus de deux morceaux. [0082] Le serveur peut aussi être programmé pour comparer deux messages chiffrés ca et cb, en déterminant le maximum ou le minimum de ces deux messages. C’est le cas pour le serveur 31 correspondant à l’exemple de réalisation de la figure 3. [0083] Le serveur peut aussi être programmé pour effectuer un tri (classement) de tels messages, afin de trier une base de données chiffrée DB (sans la déchiffrer), pour produire une base de données DB’ totalement ou partiellement triée, par exemple. C’est le cas pour le serveur 32 correspondant à l’exemple de réalisation de la figure 4. [0084] Ces différentes applications s’appuient sur un outil commun, qui est un procédé de détermination homomorphe du caractère positif ou négatif d’un message (par exemple via le calcul homomorphe de la fonction signe, ou de la fonction de heaviside), ou, plus généralement, de détermination de la position de ce message par rapport à une discontinuité d’une fonction par morceaux. [0085] Dans la suite, on décrit : - le schéma de chiffrement employé, basé sur la méthode de chiffrement dite « apprentissage avec erreur », et sur une décomposition basée sur le théorème des restes chinois, puis - le procédé de détermination homomorphe du caractère positif ou négatif d’un message. [0086] Enfin, on donne des détails supplémentaires concernant les applications en question. [0087] Schéma de chiffrement [0088] Comme indiqué plus haut, le schéma de chiffrement employé s’appuie sur une décomposition en composantes, ou autrement dit en sous-messages, basée sur le théorème des restes chinois. [0089] Dans ce schéma, chaque message initial x, non chiffré, appartient à avec les entiers pi étant premiers entre eux. [0090] Ce message peut donc être décomposé en q composantes xi, appartenant chacune à avec xi=x mod(pi) (c’est-à-dire modulo(pi)), pour i=1…q. Cette décomposition est réalisée lors de l’étape D, sur la figure 5. [0091] Pour chaque composante xi, une composante réduite µi = xi/pi appartenant au tore discret Tpi est ensuite calculée, ici. [0092] Le message (en clair) µ=x/p, associé à x, et qui appartient au Tore discret Tp, peut ainsi être décomposé en ces q composantes µi, avec [0093] Inversement, il est possible de reconstruire le message complet µ à partir de ses composantes µi, en calculant la quantité suivante : étant le coefficient de Bézout associé à l’entier pi, défini par [0094] Chaque composante µi est ensuite chiffrée, lors de l’étape E, selon la méthode dite apprentissage avec erreur, avec une clef privée s, pour déterminer une composante chiffrée ci. La composante chiffrée ci=(ai,bi) est déterminée comme suit: - sélection aléatoire d’un vecteur ai, et - calcul de la quantité bi=µi+ei+ai.s où ei est une composante de bruit, ajoutée à µi+ai.s. [0095] Lorsque µi appartient, comme ici, à Tpi, la composante de bruit ei appartient au tore T=[-1/2,1/2[. [0096] Le message chiffré complet peut être représenté par ses q composantes ci, i=1…q, sous la forme C=(c1,...ci,...cq). Le message chiffré complet peut aussi être reconstruit explicitement, à partir de ces composantes, sous la forme ce qui correspond directement à une version chiffrée de µ (chiffrement par apprentissage avec erreur, avec la même clef s). Le terme b du message chiffré c=(a,b) appartient au tore T=[-1/2, 1/2[, de même que les termes bi de ses différentes composantes ci=(ai,bi). [0097] Pour déchiffrer c (ou, de manière équivalente, C) chaque composante ci est déchiffrée (pour obtenir la composante en clair µi), avant de recomposer le message complet en clair µ. [0098] Chaque composante ci est déchiffrée, par un module de déchiffrement disposant de la clef privée s, en calculant la quantité bi-ai.s (qui est égales à µi+ei), et en arrondissant le résultat à la plus proche valeur du tore discret Tpi, retirant ainsi la composante de bruit ei pour obtenir finalement µi. [0099] La composante chiffrée ci, obtenue en chiffrant ainsi la composante µi peut aussi être notée [0100] Le schéma de chiffrement est présenté ci-dessus dans le cas où le message µ appartient au tore discret Tp. Ce schéma de chiffrement peut toutefois être appliqué aussi lorsque le message µ appartient à un ensemble discret en bijection avec Tp, par exemple lorsque le message appartient à [00101] Quoi qu’il en soit, comme indiqué dans la partie « résumé », ce schéma de chiffrement, basé sur une décomposition selon le théorème des restes chinois, permet de réaliser de manière très efficace des opérations sur le message µ (ou, de manière équivalente, sur le message x), de manière homomorphe, directement à partir du message chiffré C=(c1,...ci,...cq), sans déchiffrer C. En effet, plusieurs opérations, dont l’addition, la soustraction, la multiplication, et le boostrapping (ou « rafraichissement ») peuvent être réalisée directement à partir du message C, en traitant les composantes ci de c indépendamment les unes des autres (et donc, possiblement, en parallèle les unes des autres), et sans avoir à propager de retenue. [00102] L’addition homomorphe de deux messages C1 et C2 tels que décrits ci- dessus, chacun sous forme cryptée, est ainsi réalisée comme suit (figure 6) : la quantité étant égale à la somme terme à terme de [00103] De même, la multiplication homomorphe de tels messages C1 et C2 tels que décrits ci-dessus, chacun sous forme cryptée, est réalisé comme suit (figure 7): [00104] [00105] où désigne une opération de multiplication homomorphe de deux messages appartenant à Tpi×Tpi, décrite en détail dans la demande de brevet PCT/IB2020/001147, non encore publiée, et qui a été déposée par le même déposant (paragraphes 118 à 134, et revendication initiale 6 de cette demande antérieure ; dans cette demande antérieure, les notations sont généralement identiques aux notations employées ici, mais la notation µ remplace la notation m, et la notation q remplace la notation r). [00106] De la même manière, une version « rafraichie » C’ du message chiffré C peut être déterminée en calculant, composante par composante, la quantité suivante où G désigne une opération de bootstrapping pour messages appartenant à Tpi (et qui applique en même temps une fonction g au message en clair). Cette opération de boostrapping est décrite plus en détail dans la demande de brevet PCT/IB2020/001147 précitée, aux paragraphes 85 à 117, et dans la revendication initiale 3 de cette demande antérieure. [00107] Détermination homomorphe du caractère positif ou négatif d’un message [00108] Comme expliqué dans la partie « résumé », contrairement aux opérations d’addition, soustraction, multiplication et boostrapping, le signe du message µ ne peut pas être déterminé, à partir des signes respectifs des composantes de ce message. [00109] Et déterminer directement le signe du message µ, à partir de sa version chiffrée c présente des difficultés (expliquées en détail dans la partie « résumé »), car le message chiffré c est affecté d’une composante de bruit importante , qui empêche une détermination fiable du signe lorsque µ est proche de 0. [00110] D’ailleurs, plus généralement, comme les éléments de Tp sont proches (plus proches les uns des autres que ceux de Tpi), et comme la composante de bruit e est importante (plus grande que la composante de bruit ei affectant la composante ci), il n’est généralement pas possible de déchiffrer directement, de manière fiable, le message chiffré c (le déchiffrement passant par un déchiffrement de chaque composante ci, puis une recomposition de µ). [00111] A titre d’exemple, - pour 23, - et pour des composantes de bruit individuelles ei dont l’amplitude est choisie de manière à obtenir un déchiffrement correct pour chaque composantes ci, avec une probabilité de 1-10-10, - on peut démontrer que la probabilité d’un déchiffrement erroné d’un message µ appartenant à Tp est supérieure à 0,65, ce qui montre bien qu’un déchiffrement direct et fiable de c (ou une détermination directe et fiable de son signe) n’est pas possible en pratique. [00112] Comme expliqué dans la partie « résumé », deux techniques originales sont proposées pour surmonter cette difficulté, et afin de déterminer de manière homomorphe la caractère positif ou négatif du message μ, de manière fiable, à partir directement de sa version chiffrée complète c. Il s’agit en l’occurrence d’une technique de mise à l’échelle sans bruit (ou avec peu de bruit) ajouté, et d’une technique de fusion de signes, présentées plus en détail ci-dessous.
[00113] Mise à l’échelle sans bruit
[00114] Lorsque le message p est proche 0, ou des bords 1/2 et -1/2 du tore T, il se trouve dans une zone d’incertitude, où son signe ne peut pas être déterminé de manière fiable.
[00115] Une opération de mise à l’échelle, plus précisément de dilatation, qui, de manière remarquable, n’augmente pas le bruit affectant le message, peut alors permettre de faire sortir la valeur du message de cette zone d’incertitude (figure 8). La zone d’incertitude en question correspond aux intervalles : ]-e/2,e/2[, ]1/2-e/2, 1/2[ et [- 1/2, -1/2+e/2[ (où e est un paramètre, présenté plus loin).
[00116] Cette opération de mise à l’échelle consiste à calculer un message chiffré dilaté c[1], à partir du message c (plus précisément, à partir de ses composantes Ci), conformément à la formule suivante où le coefficient de dilatation p est un nombre impair supérieur ou égal à 3, et inférieur à p.
[00117] Comme expliqué plus haut, cette opération permet de dilater le message μ, mais sans augmenter (ou n’en augmentant que peu) la composante de bruit associée.
[00118] On comprend qu’une telle dilatation permet, pour certaines valeurs de p, de faire sortir la valeur en question de la zone d’incertitude. Mais, pour d’autres valeurs plus petites, une dilatation plus importante peut être nécessaire pour sortir de cette zone d’incertitude.
[00119] De manière remarquable, en considérant la suite on montre que, pour - Si alors il existe un entier tel que pour tout on a tandis que autrement dit, dans la suite il existe bien un coefficient de dilatation pour lequel le message dilaté est hors de la zone d’incertitude (i.e. : de signe déterminable) et de même signe que µ (dans la suite il s’agit du premier coefficient de dilatation pour lequel sort de la zone d’incertitude), et - Si alors il existe un entier tel que pour tout on a tandis que [00120] Démonstration de l’existence de k* et encadrement de sa valeur [00121] Ce résultat peut être démontré comme suit. [00122] Toute d’abord, on note que : [00123] Par ailleurs, si / ∈ 1/2 ^ a′, 1/2 , alors 1/2 ^ / ∈!0, a′!, et, de même que ci- dessus, on a : [00124] En prenant le symétrique modulo 1, on obtient alors que si alors mod [00125] Supposons maintenant que , Soit le plus grand entier tel que p"0/ ∈!0, a′ pour tout k=1..k*-1. Un tel entier existe puisque ∞ si k → ∞. Alors, comme p"0/ ` a′, on a [00126] Ainsi, en utilisant que on obient que existe, et vaut où désigne la valeur entière immédiatement supérieure. [00127] Une démonstration symétrique montre que, lorsque existe aussi et vaut [00128] En considérant la plus petite valeur de µ sur Tp, à savoir 1/(2p), ainsi que la valeur la plus proche de 1/2, à savoir 1/2 – 1/(2p), on obtient par ailleurs l’encadrement suivant pour k* : [00129] Et, plus particulièrement, en considérant la plus grande valeur de e’ adaptée à ce protocole, à savoir on a aussi :
[00130] Comme la valeur du message p n’est pas connue (puisque chiffrée), il est prévu, lors de l’étape de mise à l’échelle, de calculer plusieurs messages chiffrés dilatés c[k], avec un coefficient de dilatation de plus en plus grand, jusqu’à être sûr que la valeur du message dilaté soit sortie de la zone d’incertitude.
[00131] Autrement dit, on calcule plusieurs messages chiffrés dilatés c[k], avec un coefficient de dilatation pour k=1 ...K-1 , avec K choisi suffisamment grand pour que K-1 soit supérieur ou égal à l’entier k* présenté ci-dessus (i.e. : de manière à être sûr, que, dans la suite k=1 ...K-1 , on sorte à un moment de la zone d’incertitude).
[00132] Pour cela, vu l’encadrement de la valeur de k* établit ci-dessus, on choisit ici K de sorte que
[00133] K peut ainsi être choisi comme suit : voire comme suit .
[00134] Lors de l’étape de mise à l’échelle, chaque message chiffré dilaté est déterminé conformément à la formule suivante k=1 ...K-1 .
[00135] Comme expliqué dans la partie « résumé », dans la suite pour k<k*, le signe de ne peut généralement pas être déterminé de manière fiable à partir de sa version chiffrée c[k], pour k=k*, le signe de peut être déterminé de manière fiable à partir de sa version chiffrée c[k], et il est égal au signe du message μ, et pour k > k*, le signe de peut être faux, c’est-à-dire ne plus être égal au signe de p.
[00136] Le différents messages chiffrés dilatés c[k], k=1..K-1 sont alors pris en compte d’une particulière, lors de l’étape de fusion, pour déduire de ces messages chiffrés le signe du message p (signe qui est d’ailleurs obtenu lui aussi sous forme chiffrée, puisqu’il s’agit d’un procédé de calcul homomorphe).
[00137] Fusion
[00138] Dans la suite c[k], k=0..K-1 (où c[0]=c), on ne sait pas quel message chiffré dilaté est celui permettant une détermination de signe fiable (i.e.: correspond à un message dilaté situé hors de la zone d'incertitude), et identique au signe de p. Aussi, l'ensemble de ces messages est pris en compte, ici, pour déterminer le signe de p : - a) en affectant la valeur 0 au signe (ou une fonction représentative du signe) de chaque message dilaté, s'il est dans la zone d'incertitude, et - b) en pondérant le signe (ou une fonction représentative du signe) de chaque message dilaté avec un coefficient de pondération att[k] qui décroit lorsque k augmente, pour donner plus de poids au signe du premier message chiffré dilaté de "signe" est non nul (i.e. : premier message dilaté qui est hors de la zone d'incertitude), par rapport aux signes de messages chiffrés dilatés suivants (dont le signe peut être "faux", c'est à dire différent de celui de p).
[00139] Le calcul d'une somme pondérée de ces signes (ou de valeurs représentatives de ces signes) permet alors d'obtenir, de manière homomorphe, un résultat qui est positif, négatif ou nul (par exemple de valeur +1/4, -1/4, 0 ; ou +1/3, - 1/3, 0), selon que le message μ est positif, négatif ou nul.
[00140] En effet, dans cette somme : - les termes correspondant à k<k* sont nuis ; - le premier terme non nul, associé au message dilaté (en pratique, un terme Fk*(c[k*]), présenté ci-dessous), a un signe qui est celui de μ, et - les termes suivants, correspondant à k>k*, ont possiblement des signes arbitraires, mais ne modifient pas le signe de la somme, du fait du caractère décroissant des coefficients d'atténuation att[k] (plus précisément, du fait que la suite de coefficients att[k] est telle que : la somme des coefficients d’atténuation, successifs à l’un quelconque des coefficients d’atténuation de la suite, est inférieur audit coefficient d’atténuation, ce qui peut être obtenu par exemple avec une suite géométrique de raison inférieure à 1/2). [00141] En pratique, pour mettre en oeuvre cette technique de fusion, on calcule, pour chaque message chiffré dilaté c[k] une quantité Fk(c[k]), où Fk désigne une opération de calcul homomorphe de la quantité ge, où même directement, comme ici, une opération de calcul homomorphe de la quantité att[k].ge, où ge est une fonction en escalier : - qui est nulle sur un intervalle central ]-e/2, e/2[, - qui a deux valeurs distinctes, par exemple -1 et +1 (cas de la figure 9), de part et d’autre de cet intervalle central, et - qui est nulle près des extrémités du tore, sur les intervalles ]1/2-e/2, 1/2[ et [-1/2, -1/2+e/2[.
[00142] Le choix de cette fonction ge (plutôt que de la fonction signe Sign) permet d'attribuer la valeur 0 à un message dilaté situé dans la zone d'incertitude, dans la somme mentionnée ci-dessus.
[00143] En pratique, la quantité Fk(c[k]) est évaluée lors d'une opération de bootstrapping (au cours de laquelle on rafraîchit le bruit, et, en plus, on évalue la fonction considérée).
[00144] Pour ce qui est maintenant du calcul de la somme, c'est à dire de la fusion en elle-même, elle pourrait éventuellement être réalisée directement, en calculant la quantité F0(c) + F1(c[1])+...+ Fk(c[k])+...+ FK-I (C[K-1 ]), notamment lorsque K est petit.
[00145] Dans ce cas, lorsque les deux valeurs distinctes de ge (pour un message respectivement positif et négatif) sont -1 et +1 , les coefficients d'atténuation a(k) sont choisis de préférence tels que leur somme att[o],+...+ att[kj+... att[K-i] soit inférieur à 1/2. Le résultat de ce calcul de somme appartient alors au tore T (ce qui facilite son utilisation ultérieure, dans le schéma de chiffrement employé ici). Cette condition, ainsi que la condition de décroissance particulière mentionnée plus haut, peut être obtenue par exemple en choisissant, pour les coefficients att[k], la valeur A.Rk, où la raison R de cette suite géométrique est inférieure à 1/2, et où A est inférieur à (1 -R)/2.
[00146] Ainsi, à titre d'exemple, on pourrait choisir R=1/2, et A=1/4, soit att[k]=1/22+k.
On pourrait aussi choisir R=1/3, et A=1/3, soit att[kj=1 /31+k.
[00147] Néanmoins, une difficulté se présente lors du calcul d'une telle somme (en particulier si K est grand). Lorsque le premier terme non nul de la suite Fk(c[k]), k=0...K- 1 correspond à une valeur de k assez grande, il est multiplié par un coefficient d'atténuation att[k] petit, et a donc lui-même une valeur petite qui est alors noyée dans le bruit (bruit qui, de manière inhérente, affecte cette somme, puisqu'il s'agit du résultat d'un calcul homomorphe, et qu'il est donc fourni sous forme chiffrée, et donc bruitée). Cet effet peut empêcher une détermination correcte du signe de la somme, et donc du signe du message μ.
[00148] Pour résoudre cette difficulté, on peut, comme ici, fusionner les termes par paquets de quelques termes seulement (pour que, dans chaque paquet, les coefficients d’atténuation restent relativement grands), et cela plusieurs fois de suite pour réaliser cette fusion de manière progressive. Chaque paquet peut, à titre d’exemple, comprendre de 2 à 5 termes.
[00149] Plus précisément, cette fusion par paquets peut être réalisée en exécutant les étapes suivantes : - S1 : fusions par paquets, chaque paquet regroupant m termes, chaque fusion d'un paquet correspondant au calcul du résultat intermédiaire i étant le numéro du paquet, - S2 : fusions par paquets des résultats intermédiaires resi, chaque fusion d'un paquet de m’ résultats intermédiaires correspondant au calcul d’un nouveau résultat intermédiaire j étant le numéro du paquet, désignant une opération de calcul homomorphe d’une quantité - l'étape S2 étant répétée jusqu'à n'obtenir qu'un seul résultat, auquel est appliqué l’opération qui fournit un résultat final qui est une version chiffrée du signe du message p.
[00150] On peut par exemple avoir m’=m.
[00151] Cette méthode de fusion progressive par paquets est représentée de manière schématique sur la figure 10 pour un cas où K=8 et où chaque paquet comprend deux termes, soit m=m’=2 (l'étape S2 étant alors exécutée deux fois). [00152] Sur cette figure, chaque flèche représente une opération de boostrapping, avec évaluation de la quantité att[k].ge pour les termes de type Fk(), ou avec évaluation de la quantité pour les termes de type
[00153] s est une autre largeur d'incertitude, employée pour fusionner les résultats intermédiaires mentionnés plus haut (la fonction est définie de la même manière que ge, mais en remplaçant ε par est par exemple égal à 1/(2N), où N-1 est le degrés du polynôme spécifique de bootstrapping Wg[X] (voir la revendication 3 de la demande PCT/IB2020/001147,), aussi noté v[X].
[00154] La structure de ce calcul de fusion par paquets reste la même que celle de la figure 10 lorsque K a une valeur différente (différente de 8), et lorsque le nombre m de termes par paquets est différent (différent de 2).
[00155] Ainsi, à titre d’exemple, un algorithme en pseudo-code pour réaliser cette fusion par paquet, pour un exemple de réalisation dans lequel K=27 et m=3 (l’étape S2 étant aussi exécutée deux fois, et l’étape S1 une fois) est représenté sur la figure 1 1.
[00156] Quoiqu’il en soit, lors d’une telle fusion par paquets, pour chaque paquet de m termes, les coefficient atténuation de la somme pondérée, att[k], k=0..m-1 satisfont les mêmes conditions que précédemment (décroissante avec k, somme des coefficients suivants un coefficient donné inférieure à ce coefficient donné, somme complète, de 0 à m-1 , inférieure à 1/2).
[00157] Par commodité, on peut supposer que K=mr (dans l'exemple de la figure
10, m=2 et r = 3, par exemple), et m’=m. Dans ce cas, l’étape S2 est exécutée r-1 fois.
[00158] Dans ce cas, le résultat de l'ensemble de l'opération de fusion progressive par paquets (résultat qui est le signe de μ, chiffré) peut s'exprimer directement comme :
[00159] Considérations sur le bruit [00160] Une démonstration détaillée permet de prouver que le procédé présenté ci- dessus permet effectivement une détermination homomorphe du signe d’un message p, directement à partir du message chiffré c correspondant, avec une probabilité d’erreur très faible.
[00161] A titre d’exemple, dans un cas où : - le message μ appartient à Tp, avec p8 = 7 x 11 x 13 x 17 x 19 x 23 x 25 x 27 (soit p=5 019 589 575 > 232), en choisissant les valeurs suivantes pour les paramètres du procédé de détermination du signe : on montre que la probabilité d’erreur dans la détermination homomorphe du signe de μ est inférieure à 1 ,03 .10-9 (ce qui est très faible), - les paramètres du schéma de chiffrement étant quant à eux : n=412 (n est le nombre de composantes de la clef secrète s, qui appartient à Bn, où B={0,1 }, un paramètre de collapsing I valant quant à lui l=4) , N=1024, et un écart-type σ(ei) de la composante de bruit affectant chaque composante Ci qui vaut (ce qui correspond à un niveau de bruit permettant 200 additions homomorphes sans boostrapping entre elles).
[00162] La figure 12 est un tableau qui, pour cet exemple, regroupe les valeurs des coefficients de Bézout Vj, les valeurs des coefficients de Bézout « dilatés » (ce qui illustre d’ailleurs que ces valeurs restent avantageusement petites, bien que permettant une dilatation du message), et des valeurs de la quantité qui intervient dans le calcul du bruit affectant les messages chiffrés dilatés.
[00163] Détails concernant la fonction qε, et son émulation par boostrappinq
[00164] Les détails ci-dessous sont présentés pour un exemple de réalisation pour lequel les coefficients d’atténuation valent att[kj=1 /(22+k). Ils peuvent être transposés à d’autres valeurs des coefficients d’atténuation.
[00165] Tout d’abord, on suppose que : où les δ[k] de sont définis par [00166] Les inventeurs ont alors démontré qu’il existe alors k* tel que [00167] Emulation de la fonction gε [00168] Comme détaillé dans la demande de brevet PCT/IB2020/001147, le but est de construire un polynôme v[X] tel que, pour émuler la fonction gε sous forme chiffrée lors d’une opération de boostrapping. [00169] Choix du paramètre ε [00170] Par construction, la fonction est une fonction constante par morceaux avec de possibles discontinuités aux points tels que soit [00171] La fonction gε étant impaire avec des discontinuités à droite en ε/2 et en 1/2-ε/2, un choix naturel pour le paramètre ε est sous la contrainte soit [00172] Construction du polynôme v[X] Pour toute fonction F de Z dans T, 2N-périodique, et telle que il existe un unique polynôme v de Les coefficients vj de ce polynôme sont donnés par 3 , Pour un k donné, i est donc suffisant de définir F sur {0,…,N-1}, comme suit : de sorte que soit Pour ce choix de polynôme et du paramètre ε, la relation (2) ci-dessus est effectivement satisfaite, sans erreur. Arrondis Lors d’une opération de boostrapping, la valeur prise par µ dans la relation (2) est obtenue à partir de pour en arrondissant les valeurs de et dans comme suit et en remplaçant par On notera que d’autres variantes sont envisageables pour réaliser ces arrondis. Le processus d’arrondi en question introduit des erreurs, dont on tient compte via les termes δ[k], dans la formule (1). On a ainsi, en tenant compte de la relation (2) et de la définition des δ[k] : [00179] La fonction boostrappée complète, qui fournit une valeur chiffrée de est
[00180] On remarquera que la définition des δ[k] peut être changée comme suit de sorte que la relation (3) reste valable.
[00181] Boostrapping de la fonction signe
[00182] Dans un cas où 1/2k+2 n’est pas trop petit (coefficients d’atténuation pas trop petits), le signe de p peut être obtenu par exemple en calculant la quantité suivante (ce qui correspond à une fusion directe, et non progressive par paquets) :
[00183] Exemples d’applications
[00184] Calcul homomorphe de la fonction de Heaviside
[00185] Pour appliquer de manière homomorphe la fonction de Heaviside H au message p, on applique le procédé de détermination homomorphe du signe présenté ci-dessus, mais en choisissant, pour la fonction gε, les valeurs 0 sur [-1/2+e/2, -e/2], et +1 sur [e/2,1/2-e/2] (au lieu de -1 et +1 ).
[00186] Calcul homomorphe d’une fonction constante par morceaux quelconque
[00187] Pour appliquer une fonction f constante par morceaux quelconque au message p, la fonction f ayant t morceaux distincts, le serveur 3 sera par exemple programmé de manière à exécuter les opérations suivantes : - décomposition de la fonction f sous la forme d’une combinaison linéaire de fonctions de Heaviside translatées, soit où les coefficients αj sont des entiers et où les abscisses des points de discontinuité appartiennent à l’intervalle [-1/4, 1/4], - calcul de la quantité chaque terme étant déterminé, de manière homomorphe, comme indiqué ci-dessus pour la fonction de Heaviside H.
[00188] Comparaison : détermination homomorphe du maximum et du minimum
[00189] Soit μa et μb deux messages, avec ca et cb les messages chiffrés correspondants, obtenus avec le schéma de chiffrement présenté plus haut.
[00190] On note h la version chiffrée de déterminée comme expliqué ci- dessus (calcul de la fonction de Heaviside).
[00191] Du fait de la linéarité des opérations de chiffrement employées ici, la quantité h.ca+(1 -h).cb est une version chiffrée de qui n’est autre que le maximum max
[00192] Calculer ainsi la quantité Maxh=h.ca+(1 -h). cb permet donc d’obtenir, de manière homomorphe, une version chiffrée de
[00193] De même, calculer la quantité Minh=h.cb+(1 -h).ca permet d’obtenir, de manière homomorphe, une version chiffrée de minimum de
[00194] Le serveur 31 de l’exemple de réalisation de la figure 3 est programmé pour effectuer ces opérations. Le module 310 de ce serveur effectue la soustraction homomorphe Puis le module 30 détermine la quantité h à partir de Cd. Le module 311 effectue ensuite les opérations et délivre les résultats correspondants, Maxh et Minh.
[00195] En variante, les quantités Maxh et Minh pourraient être déterminées en - déterminant de manière homomorphe une version chiffrée de notée h’ , puis - en calculant la quantité h’.cb+(1 -h’).ca (pour le maximum) et h’.ca+(1 -h’).cb (pour le minimum). [00196] En variante encore, les quantités Maxh et Minh pourraient être déterminées chacune à partir d’une version chiffrée du signe de la différence
[00197] Tri d’une base de données
[00198] Pouvoir déterminer de manière homomorphe le maximum et/ou minimum de deux messages est particulièrement intéressant car cela permet de réaliser, de manière homomorphe aussi, un tri (un classement, par exemple par ordre croissant ou décroissant) d’un ensemble de messages chiffrés.
[00199] De nombreux algorithmes de tri sont en effet basés sur une étape élémentaire (réitérée) de comparaison message par message, c’est-à-dire entre deux messages, parmi ceux à trier. L’un des deux messages est alors remplacé par le maximum des deux messages, tandis que l’autre message est remplacé par le minimum de ces deux messages.
[00200] Le serveur 32 de l’exemple de réalisation de la figure 4 est programmé pour exécuter un procédé de tri d’une basse de données chiffrée DB.
[00201] Cette base de données comprend au moins, dans un premier emplacement de la base de données, un premier message chiffré ca, et dans un deuxième emplacement de la base de données, un deuxième message chiffré cb.
[00202] Ce procédé de tri comprend au moins : - une écriture, dans le premier emplacement, de la quantité Maxh présentée ci-dessus, déterminée à partir de ca et cb, ou, respectivement, de la quantité Minh présentée ci-dessus (déterminée à partir de ca et cb), et - une écriture, dans le deuxième emplacement, de la quantité Minh, ou, respectivement, de la quantité Maxh.
[00203] Les premier et deuxième emplacements en question peuvent par exemple être repérés chacun, dans la base de données, par un numéro d’indexation associé à l’emplacement considéré (par exemple un numéro de ligne, dans une base de données de forme matricielle).

Claims

REVENDICATIONS [Revendication 1] Procédé de détermination homomorphe du caractère positif ou négatif d’un message µ à partir d’un message chiffré c correspondant, sans déchiffrement du message chiffré c, le message chiffré c correspondant au message µ étant chiffré par une méthode de type apprentissage avec erreur, le message µ appartenant au tore discret p ou à un espace en bijection avec Tp, avec les entiers pi étant premiers entre eux, le message chiffré c étant formé de q composantes ci, avec étant le coefficient de Bézout associé à l’entier pi, défini par le procédé comprenant : - une étape de mise à l’échelle, comprenant une détermination d’un message chiffré dilaté c[1] conformément à la formule suivante est un nombre impair supérieur ou égal à 3, et - une étape de fusion, comprenant un calcul de la somme F0(c) + F1(c[1]) où F0 et F1 désignent respectivement une opération de calcul homomorphe d’une quantité att[0].gε, et d’une quantité att[1].gε, gε étant une fonction en escalier qui est nulle sur un intervalle central ]-ε/2, ε/2[ et qui a deux valeurs distinctes de part et d’autre de cet intervalle central, le coefficient att[1] étant inférieur au coefficient att[0]. [Revendication 2] Procédé selon la revendication précédente, dans lequel l’étape de mise à l’échelle comprend des déterminations de plusieurs messages chiffrés dilatés c[k], l’entier k variant de 1 à K-1, chaque message chiffré dilaté étant déterminé conformément à la formule suivante et dans lequel le caractère positif ou négatif du message µ est déterminé en fonction de c et en fonction des différents messages chiffrés dilatés c[k], k=1..K-1. [Revendication 3] Procédé selon la revendication précédente, dans lequel l’étape de fusion comprend une étape de fusion d’un paquet au cours de laquelle la somme suivante est calculée : F0(c) + F1(c[1])+…+ Fk(c[k])+…+ Fm(c[m]), où Fk désigne une opération de calcul homomorphe de la quantité att[k].gε, où att[k] est un coefficient d’atténuation inférieur à 1, la suite de coefficients att[k], k=0..m étant décroissante et telle : que la somme des coefficients d’atténuation, successifs à l’un des coefficients d’atténuation donné de la suite, est inférieure audit coefficient d’atténuation donné. [Revendication 4] Procédé selon la revendication précédente, dans lequel m est inférieur à K, et dans lequel l'étape de fusion comprend les étapes suivantes : - S1 : fusions par paquets, chaque paquet regroupant m termes, chaque fusion d'un paquet correspondant au calcul du résultat intermédiaire resi=F0(c[(i-1).m]) + F1(c[(i-1).m+1])+…+ Fk(c[(i-1).m+k])+…+ Fm-1(c[i.m-1]), i étant le numéro du paquet, - S2 : fusions par paquets des résultats intermédiaires resi, chaque fusion d'un paquet de m’ résultats intermédiaires correspondant au calcul d’un nouveau résultat intermédiaire j étant le numéro du paquet, désignant une opération de calcul homomorphe d’une quantité - l'étape S2 étant répétée jusqu'à n'obtenir qu'un seul résultat, auquel est appliqué l’opération qui fournit un résultat final qui est une version chiffrée du signe du message µ. [Revendication 5] Procédé selon l’une des revendications 2 à 4, dans lequel le nombre K-1 de messages chiffrés dilatés pris en compte est tel que [Revendication 6] Procédé selon l’une des revendications précédentes, dans lequel la largeur ε de l’intervalle central est inférieure à [Revendication 7] Procédé pour appliquer de manière homomorphe la fonction de Heaviside H, qui est nulle pour les valeurs négatives et égale à 1 sinon, le procédé comprenant l’exécution du procédé de détermination du caractère positif ou négatif du message µ selon l’une quelconque des revendications précédentes, la fonction gε étant choisie nulle pour les valeurs négatives et égale à 1 pour les valeurs positives. [Revendication 8] Procédé pour appliquer de manière homomorphe une fonction f constante par morceaux à un message µ, la fonction f ayant t morceaux distincts, le procédé comprenant : - une décomposition de la fonction f sous la forme d’une combinaison linéaire de fonctions de Heaviside translatées, soit où les coefficients αj sont des entiers et où les abscisses βj des points de discontinuité appartiennent à l’intervalle [-1/4, 1/4], - un calcul de la quantité chaque terme étant déterminé, de manière homomorphe, conformément au procédé de la revendication précédente. [Revendication 9] Procédé pour déterminer de manière homomorphe le maximum de deux messages µa et µb, à partir des messages chiffrés correspondants ca et cb, sans déchiffrement des messages chiffrés ca et cb, le procédé comprenant : - une détermination homomorphe de la quantité H(µa - µb), conformément au procédé selon la revendication 7, la version chiffrée de H(µa - µb) ainsi déterminée étant notée h, et le calcul de la quantité Maxh=h.ca+(1-h).cb, - ou, une détermination homomorphe de la quantité H(µb - µa), conformément au procédé selon la revendication 7, la version chiffrée de H(µb - µa) ainsi déterminée étant notée h’, et le calcul de la quantité h’.cb+(1-h’).ca . [Revendication 10] Procédé pour déterminer de manière homomorphe le minimum de deux messages µa et µb, à partir des messages chiffrés correspondants ca et cb, sans déchiffrement des messages chiffrés ca et cb, le procédé comprenant : - une détermination homomorphe de la quantité H(µa - µb), conformément au procédé selon la revendication 7, la version chiffrée de H(µa - µb) ainsi déterminée étant notée h, et le calcul de la quantité Minh=h.cb+(1-h).ca, - ou, une détermination homomorphe de la quantité H(µb - µa), conformément au procédé selon la revendication 7, la version chiffrée de H(µb - µa) ainsi déterminée étant notée h’, et le calcul de la quantité h’.ca+(1-h’).cb . [Revendication 11] Procédé de tri d’une base de données, la base de données comprenant au moins, dans un premier emplacement de la base de données, un premier message chiffré ca, et dans un deuxième emplacement de la base de données, un deuxième message chiffré cb, le procédé comprenant au moins une écriture, dans le premier emplacement, de la quantité Maxh déterminée conformément au procédé de la revendication 9, ou de la quantité Minh, déterminée conformément au procédé de la revendication 10. [Revendication 12] Méthode de communication et traitement chiffrés, comprenant les étapes suivantes : - Chiffrement d’au moins un message µ, avec une clef privée s, par un client (2), sous la forme d’un message chiffré c, par une méthode de type apprentissage avec erreur, le message µ appartenant au tore discret ou à un espace en bijection avec Tp, avec les entiers pi étant premiers entre eux, le message chiffré c=(c1,...ci,...cq) étant formé de q composantes ci, avec étant le coefficient de Bézout associé à l’entier pi, défini par - Transmission du message chiffré c, ou d’une base de données chiffrée contenant le message chiffré c, par le client (2), à un serveur (3 ; 30 ; 31 ; 32) distinct du client (2) et ne disposant pas de la clef privée s, via un canal de communication (5), - Traitement du message chiffré c, ou d’une différence entre le message chiffré c et un autre message chiffré, ou de la base de données chiffrées (DB) contenant le message chiffré c, par le serveur (3 ; 30 ; 31 ; 32), de manière homomorphe, conformément au procédé selon l’une quelconque des revendications précédentes, - Emission du résultat (res, DB’) dudit traitement homomorphe, par le serveur (3 ; 30 ; 31 ; 32). [Revendication 13] Serveur (3 ; 30 ; 31 ; 32) de traitement cryptographique, comprenant au moins un module de communication et un module de calcul : - Le module de communication étant configuré pour recevoir, de la part d’une entité externe au serveur, un message chiffré c ou une base de données chiffrée (DB) contenant le message chiffré c, le message chiffré c correspondant à un message µ chiffré par une méthode de type apprentissage avec erreur, le message µ appartenant au tore discret ou à un espace en bijection avec Tp, avec les entiers pi étant premiers entre eux, le message chiffré c=(c1,...ci,...cq) étant formé de q composantes ci, avec étant le coefficient de Bézout associé à l’entier pi, défini par - Le module de calcul étant programmé pour traiter le message chiffré c, ou une différence entre le message chiffré c et un autre message chiffré, ou la base de données chiffrée (DB) contenant le message chiffré c, de manière homomorphe, sans déchiffrement du message c, conformément au procédé selon l’une quelconque des revendications 1 à 11, - Le module de communication étant configuré aussi pour émettre le résultat (res, DB’) dudit traitement homomorphe. [Revendication 14] Système cryptographique (1) comprenant : - le serveur (3 ; 30 ; 31 ; 32) de traitement cryptographique selon la revendication précédente, - un client (2), configuré pour chiffrer au moins le message µ, sous la forme du message chiffré c, et pour communiquer le message chiffré c, ou une base de données chiffrée (DB) contenant le message chiffré c, au serveur (3 ; 30 ; 31 ; 32) via un canal de communication (5).
EP23734502.0A 2022-06-17 2023-06-16 Procédé de détermination homomorphe du signe d'un message par dilatation, procédés et dispositifs associés Pending EP4540956A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR2205957A FR3136920B1 (fr) 2022-06-17 2022-06-17 Procédé de détermination homomorphe du signe d’un message par dilatation, procédés et dispositifs associés
PCT/EP2023/066324 WO2023242429A1 (fr) 2022-06-17 2023-06-16 Procédé de détermination homomorphe du signe d'un message par dilatation, procédés et dispositifs associés

Publications (1)

Publication Number Publication Date
EP4540956A1 true EP4540956A1 (fr) 2025-04-23

Family

ID=83438742

Family Applications (1)

Application Number Title Priority Date Filing Date
EP23734502.0A Pending EP4540956A1 (fr) 2022-06-17 2023-06-16 Procédé de détermination homomorphe du signe d'un message par dilatation, procédés et dispositifs associés

Country Status (4)

Country Link
EP (1) EP4540956A1 (fr)
CN (1) CN119731987A (fr)
FR (1) FR3136920B1 (fr)
WO (1) WO2023242429A1 (fr)

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110649375B (zh) 2018-06-26 2021-01-01 中兴通讯股份有限公司 一种移动终端天线和移动终端

Also Published As

Publication number Publication date
FR3136920B1 (fr) 2024-05-31
FR3136920A1 (fr) 2023-12-22
WO2023242429A1 (fr) 2023-12-21
CN119731987A (zh) 2025-03-28

Similar Documents

Publication Publication Date Title
EP3751468B1 (fr) Méthode d&#39;apprentissage collaboratif d&#39;un réseau de neurones artificiels sans divulgation des données d&#39;apprentissage
EP3535923B1 (fr) Méthode de classification sécurisée utilisant une opération de transchiffrement
EP3345175B1 (fr) Méthode d&#39;interrogation confidentielle d&#39;un service géodépendant par cryptographie homomorphe
WO2009095574A2 (fr) Procede et entite de chiffrement symetrique probabiliste
EP4262141A1 (fr) Methode d&#39;interrogation confidentielle multi-utilsateur de la présence d&#39;un enregistrement dans une base de données
FR2808948A1 (fr) Systeme et methode pour authentifier de maniere unique chaque reproduction d&#39;un groupe de documents electroniques
EP1959572B1 (fr) Procédé de décodage à passage de messages et à convergence forcée
EP1783659B1 (fr) Identification d&#39;etiquette radiofrequence
EP3545641B1 (fr) Procédé de chiffrement cherchable
WO2000045549A1 (fr) Procede d&#39;authentification ou de signature a nombre de calculs reduit
EP1869823B1 (fr) Procédé de communication entre un lecteur et un marqueur d&#39;identification sans fil, lecteur et marqueur associés
EP4540956A1 (fr) Procédé de détermination homomorphe du signe d&#39;un message par dilatation, procédés et dispositifs associés
EP1523823A2 (fr) Procede de generation de cles electroniques pour procede de cryptographie a cle publique et objet portatif securise mettant en oeuvre le procede
EP3857810B1 (fr) Procédé cryptographique de comparaison sécurisée de deux données secrètes x et y
EP3008851B1 (fr) Procédé et système de délégation d&#39;un calcul d&#39;une valeur de couplage bilinéaire à un serveur de calcul
WO2018104557A1 (fr) Procédé d&#39;émission d&#39;un message, procédé de réception, dispositif d&#39;émission, dispositif de réception et système de communication associés
EP1989820B1 (fr) Dispositif et procédé de hachage cryptographique
EP1829279A2 (fr) Procede et dispositif d&#39;execution d&#39;un calcul cryptographique
WO2024261248A1 (fr) Procédé de détermination d&#39;un message chiffré, procédé de rafraîchissement, d&#39;extraction et d&#39;agrégation associés
EP3869368A1 (fr) Procede et dispositif de detection d&#39;anomalie
FR2734435A1 (fr) Procede de signature numerique a connaissance nulle, permettant d&#39;elaborer une signature resistant aux collisions
EP1642413A1 (fr) Procede de chiffrement/dechiffrement d un message et disposi tif associe
WO2024261250A1 (fr) Procédé d&#39;extraction d&#39;un élément chiffré homomorphe d&#39;une liste chiffrée homomorphe et procédé d&#39;insertion d&#39;un élément chiffré homomorphe dans une liste chiffré homomorphe
WO2009030857A2 (fr) Generateur et procede de generation de fonction pseudo-aleatoire a cle secrete
WO2004084485A1 (fr) Procede cryptographique mettant en oeuvre des courbes hyperelliptiques de genre 2

Legal Events

Date Code Title Description
STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: UNKNOWN

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE INTERNATIONAL PUBLICATION HAS BEEN MADE

PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: REQUEST FOR EXAMINATION WAS MADE

17P Request for examination filed

Effective date: 20250115

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AL AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LI LT LU LV MC ME MK MT NL NO PL PT RO RS SE SI SK SM TR

GRAP Despatch of communication of intention to grant a patent

Free format text: ORIGINAL CODE: EPIDOSNIGR1

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: GRANT OF PATENT IS INTENDED

DAV Request for validation of the european patent (deleted)
DAX Request for extension of the european patent (deleted)
INTG Intention to grant announced

Effective date: 20250904

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN