Brevet FR3136920A1 — publié le 20231222

Procédé de détermination homomorphe du signe d’un message par dilatation, procédés et dispositifs associés 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 ou à un espace en bijection avec T p , avec , les entiers p i étant premiers entre eux, le message chiffré c étant formé de q composantes c i , avec , v i étant le coefficient de Bézout associé à l’entier p i . Le procédé comprend au moins une dilatation du message chiffé c conformément à la formule suivante , où 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] . Figure à publier avec l’abrégé : Figure 8 Procédé de détermination homomorphe du signe d’un message par dilatation, procédés et dispositifs associés Le domaine technique est celui des méthodes, dispositifs et systèmes de cryptographie homomorphe. ARRIERE-PLAN TECHNOLOGIQUE 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. 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. 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. 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. 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. 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. 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 μ. 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. 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. 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 œuvre, nécessitant une puissance ou un temps de calcul très importants. 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 œuvre ce type de schéma cryptographique, sont ainsi des outils adaptés à des messages binaires. 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). 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 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 T p , avec , les entiers p i étant premiers entre eux, le message chiffré c étant formé de q composantes c i , avec , v i étant le coefficient de Bézout associé à l’entier p i , 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 , où est un nombre impair supérieur ou égal à 3, et une étape de fusion, comprenant un calcul de la somme F 0 (c) + F 1 (c [1] ) où F 0 et F 1 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] . 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. La décomposition du message chiffré c en ces q composantes indépendantes c i , et la recomposition du message c à parti de ces composantes c i est réalisée en appliquant le théorème des restes chinois. 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. De nombreuses opérations sur le message chiffré c, par exemple une addition homomorphe ( ), une multiplication homomorphe ( ), ou une opération de bootstraping, peuvent être réalisées composante par composante, en traitant les q composantes c i du message c, indépendamment les uns des autres, sans avoir à propager aucune retenue entre eux . 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 c i du message chiffré c, ce qui permet un traitement accéléré, par rapport à une décomposition binaire avec propagation de retenues (chiffrées). Il est noté que les différentes composantes c i correspondent à des « sous-messages » chiffrés, associés chacun (par chiffrement) à l’un des « sous-messages » μ i composant le message en clair total μ ( ). 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 p i valeurs, avec p i = 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. 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. 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). 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. 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. 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. 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 μ ne peut donc pas être déterminé composante par composante. Cela est illustré par l’exemple numérique suivant, où . Les deux messages et ont tous deux un signe positif ; Leurs composantes respectives sont et . 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. Or la détermination du signe du message complet μ, 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 ), composante qui est nettement plus importante que pour les messages individuels μ i . 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. Cette difficulté est d’autant plus marquée que les valeurs de μ, qui appartiennent à T p , p=p 1 ×…×p q , peuvent être nettement plus proches de 0 que les valeurs des messages individuels μ 1 … μ q , qui appartiennent, elles à T p 1 , ou T pi . Autrement dit, les différents éléments du tore discret T p sont beaucoup plus proches les uns des autres que les éléments du tore discret T p1 , ou T pi (en plus d’être affectés par une composante de bruit plus importante). On notera que les difficultés en question se posent lorsque la valeur de μ 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 μ est possible directement, à partir de son chiffré c, via une opération de bootstrapping incluant l’évaluation de la fonction signe. Pour surmonter la difficulté mentionnée ci-dessus, deux techniques ingénieuses ont été mises au point par les inventeurs. La première technique permet de mettre à l’échelle le message μ, plus précisément de le dilater, en opérant directement sur sa version chiffrée c, sans dilater (ou en ne dilatant que peu) la composante 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 . 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 : , où le coefficient de dilatation est un nombre impair, supérieur ou égal à 3. Ainsi, dans la somme , plutôt que de multiplier le sous-message chiffré c i par (ce qui augmenterait sa composante de bruit), c’est le coefficient v i que l’on multiplie par . Et comme les coefficients de Bézout sont définis à chacun à p i près (i.e. : modulo p i ), on peut conserver une valeur réduite pour le ‘coefficient’ qui multiplie c i , dans cette somme, ce qui permet de dilater c (plus précisément : dilater μ), en ne dilatant quasiment pas sa composante de bruit e. Cette opération de dilatation sans bruit est très utile si la valeur du message μ est proche de 0, comme expliqué ci-dessus. En revanche, si la valeur de μ est déjà suffisamment grande avant dilatation (par exemple proche de 1/4), l’opération de dilatation, en augmentant la valeur de μ, 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. 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. 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é μ, sachant que 0 est attribué si le message μ est située dans une zone d’incertitude, comprenant notamment un intervalle central, centré sur 0, de largeur ε, avec le signe (dans sa version chiffrée) du message dilaté μ [1] , ce signe étant affecté d’un coefficient d’atténuation att [1] qui réduit sa contribution, par rapport au signe du message initial μ. Ainsi, si le message initial μ 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 [ 1] ), 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). 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. 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. Pour déterminer de manière homomorphe le signe du message μ à 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 gε ou att [ 0 ] .gε à μ (cette fonction étant appliquée lors d’un boostrapping avec calcul de fonction intégré), où gε est une fonction en escalier : qui est nulle sur un intervalle central ]-ε/2, ε/2[, qui a deux valeurs distinctes, par exemple -1 et +1 (cas de la ), 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-ε/2, 1/2[ et [-1/2, -1/2+ε/2[. 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[. 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 , 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, l’étape de fusion comprend une étape de fusion d’un paquet au cours de laquelle la somme suivante est calculée : F 0 (c) + F 1 (c [1] )+…+ F k (c [k] )+…+ F m (c [m] ), où F k 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é ; 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 res i =F 0 (c [(i-1).m] ) + F 1 (c [(i-1).m+1 ] )+…+ F k (c [(i-1).m+k] )+…+ F m-1 (c [i.m-1] ), i étant le numéro du paquet, S2 : fusions par paquets des résultats intermédiaires res i , 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 μ. 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 à . 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. 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 β 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é pour appliquer de manière homomorphe la fonction de Heaviside H qui vient d’être présenté. 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 c a et c b , sans déchiffrement des messages chiffrés c a et c b , 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.c a +(1-h).c b 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’.c b +(1-h’).c a . 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 c a et c b , sans déchiffrement des messages chiffrés c a et c b , 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.c b +(1-h).c a 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’.c a +(1-h’).c b . 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é c a , et dans un deuxième emplacement de la base de données, un deuxième message chiffré c b , 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. 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. 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 T p , avec , les entiers p i étant premiers entre eux, le message chiffré c=(c 1 ,...c i ,...c q ) étant formé de q composantes c i , avec , v i étant le coefficient de Bézout associé à l’entier p i , 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. 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. 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 ou à un espace en bijection avec T p , avec , les entiers p i étant premiers entre eux, le message chiffré c=(c 1 ,...c i ,...c q ) étant formé de q composantes c i , avec , v i étant le coefficient de Bézout associé à l’entier p i , 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. Le module de communication peut être configuré pour émettre aussi le résultat dudit traitement homomorphe. 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. 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 Les figures sont présentées à titre indicatif et nullement limitatif. représente schématiquement un système cryptographique mettant en œuvre la présente technologie. représente schématiquement un exemple de réalisation d’un serveur de traitement cryptographique pouvant être employé dans le système de la . 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 . 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 , notamment pour réaliser des opérations de traitement de bases de données chiffrées. représente schématiquement une opération de chiffrement mise en œuvre dans un tel système. 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 . 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 . représente schématiquement l’effet d’une opération de mise à l’échelle sur un message dont on cherche à déterminer le signe. 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. 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. montre un algorithme (en pseudocode) mettant en œuvre cette méthode de fusion par paquets. 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 La 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. 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. 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. 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). 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. 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. 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. 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). Le serveur 3 peut être programmé pour réaliser de manière homomorphe différentes opérations de traitement. 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 . 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. Le serveur peut aussi être programmé pour comparer deux messages chiffrés c a et c b , 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 . 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 . 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. 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. Enfin, on donne des détails supplémentaires concernant les applications en question. S chéma de chiffrement 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. Dans ce schéma, chaque message initial x, non chiffré, appartient à , avec , les entiers p i étant premiers entre eux. Ce message peut donc être décomposé en q composantes x i , appartenant chacune à , avec x i =x mod(p i ) (c’est-à-dire modulo(p i )), pour i=1…q. Cette décomposition est réalisée lors de l’étape D, sur la . Pour chaque composante x i , une composante réduite μ i = x i /p i appartenant au tore discret T pi est ensuite calculée, ici. Le message (en clair) μ=x/p, associé à x, et qui appartient au Tore discret T p , peut ainsi être décomposé en ces q composantes μ i , avec . Inversement, il est possible de reconstruire le message complet μ à partir de ses composantes μ i , en calculant la quantité suivante : , v i étant le coefficient de Bézout associé à l’entier p i , défini par . 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 c i . La composante chiffrée c i =(a i ,b i ) est déterminée comme suit: sélection aléatoire d’un vecteur a i , et calcul de la quantité b i =μ i +e i +a i .s où e i est une composante de bruit, ajoutée à μ i +a i .s. Lorsque μ i appartient, comme ici, à T pi , la composante de bruit e i appartient au tore T =[-1/2,1/2[. Le message chiffré complet peut être représenté par ses q composantes c i , i=1…q, sous la forme C=(c 1 ,...c i ,...c q ). 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 b i de ses différentes composantes c i =(a i ,b i ). Pour déchiffrer c (ou, de manière équivalente, C) chaque composante c i est déchiffrée (pour obtenir la composante en clair μ i ), avant de recomposer le message complet en clair μ. Chaque composante c i est déchiffrée, par un module de déchiffrement disposant de la clef privée s, en calculant la quantité b i -a i .s (qui est égales à μ i +e i ), et en arrondissant le résultat à la plus proche valeur du tore discret T pi , retirant ainsi la composante de bruit e i pour obtenir finalement μ i . La composante chiffrée c i , obtenue en chiffrant ainsi la composante μ i peut aussi être notée . Le schéma de chiffrement est présenté ci-dessus dans le cas où le message μ appartient au tore discret T p . Ce schéma de chiffrement peut toutefois être appliqué aussi lorsque le message μ appartient à un ensemble discret en bijection avec T p , par exemple lorsque le message appartient à . 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=(c 1 ,...c i ,...c q ), 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 c i de c indépendamment les unes des autres (et donc, possiblement, en parallèle les unes des autres), et sans avoir à propager de retenue. 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 ( ) : la quantité étant égale à la somme terme à terme de c1 i et c2 i : . 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 ( ): où désigne une opération de multiplication homomorphe de deux messages appartenant à T pi × T pi , 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). 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 à T pi (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. D étermination homomorphe du caractère positif ou négatif d’un message 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. 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. D’ailleurs, plus généralement, comme les éléments de T p sont proches (plus proches les uns des autres que ceux de T pi ), et comme la composante de bruit e est importante (plus grande que la composante de bruit e i affectant la composante c i ), 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 c i , puis une recomposition de μ). A titre d’exemple, pour , et pour des composantes de bruit individuelles e i dont l’amplitude est choisie de manière à obtenir un déchiffrement correct pour chaque composantes c i , avec une probabilité de 1-10 -10 , on peut démontrer que la probabilité d’un déchiffrement erroné d’un message μ appartenant à T p 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. 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. Mise à l’échelle sans bruit Lorsque le message μ 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. 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 ( ). La zone d’incertitude en question correspond aux intervalles : ]-ε/2,ε/2[, ]1/2-ε/2, 1/2[ et [-1/2, -1/2+ε/2[ (où ε est un paramètre, présenté plus loin). 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 c i ), conformément à la formule suivante , où le coefficient de dilatation est un nombre impair supérieur ou égal à 3, et inférieur à p. 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. On comprend qu’une telle dilatation permet, pour certaines valeurs de μ, 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. 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 . Démonstration de l’existence de k* et encadrement de sa valeur Ce résultat peut être démontré comme suit. Toute d’abord, on note que : Par ailleurs, si , alors , et, de même que ci-dessus, on a : En prenant le symétrique modulo 1, on obtient alors que si , alors . Supposons maintenant que . Soit k* le plus grand entier tel que pour tout k=1..k*-1. Un tel entier existe puisque et . Alors, comme , on a Ainsi, en utilisant que , on obient que k* existe, et vaut où désigne la valeur entière immédiatement supérieure. Une démonstration symétrique montre que, lorsque , k* existe aussi et vaut . En considérant la plus petite valeur de μ sur T p , à 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* : Et, plus particulièrement, en considérant la plus grande valeur de ε’ adaptée à ce protocole, à savoir , on a aussi : Comme la valeur du message μ 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. 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). Pour cela, vu l’encadrement de la valeur de k* établit ci-dessus, on choisit ici K de sorte que . K peut ainsi être choisi comme suit : , voire comme suit : . Lors de l’étape de mise à l’échelle, chaque message chiffré dilaté est déterminé conformément à la formule suivante , k=1...K-1. Comme expliqué dans la partie « résumé », dans la suite , k=1…K-1, pour k 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 μ. 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 μ (signe qui est d’ailleurs obtenu lui aussi sous forme chiffrée, puisqu’il s’agit d’un procédé de calcul homomorphe). F usion 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 μ. Aussi, l'ensemble de ces messages est pris en compte, ici, pour déterminer le signe de μ : 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 μ). 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. En effet, dans cette somme : les termes correspondant à k le premier terme non nul, associé au message dilaté (en pratique, un terme F k* (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). En pratique, pour mettre en œuvre cette technique de fusion, on calcule, pour chaque message chiffré dilaté c [ k ] une quantité F k (c [ k ] ), où F k désigne une opération de calcul homomorphe de la quantité gε, où même directement, comme ici, une opération de calcul homomorphe de la quantité att [ k ] .gε, où gε est une fonction en escalier : qui est nulle sur un intervalle central ]-ε/2, ε/2[, qui a deux valeurs distinctes, par exemple -1 et +1 (cas de la ), 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-ε/2, 1/2[ et [-1/2, -1/2+ε/2[. Le choix de cette fonction gε (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. En pratique, la quantité F k (c [ k ] ) est évaluée lors d'une opération de bootstrapping (au cours de laquelle on rafraichit le bruit, et, en plus, on évalue la fonction considérée). 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é F 0 (c) + F 1 (c [ 1] )+…+ F k (c [ k ] )+…+ F K-1 (c [ K-1 ] ), notamment lorsque K est petit. Dans ce cas, lorsque les deux valeurs distinctes de gε (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 [ 0], +...+ att [k] +... att [K-1] 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.R k , où la raison R de cette suite géométrique est inférieure à 1/2, et où A est inférieur à (1-R)/2. Ainsi, à titre d'exemple, on pourrait choisir R=1/2, et A=1/4, soit att [k] =1/2 2+k . On pourrait aussi choisir R=1/3, et A=1/3, soit att [k] =1/3 1 +k . 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 F k (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 μ. 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. 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 res i =F 0 (c [ ( i -1) .m] ) + F 1 (c [ ( i -1) .m+1 ] )+…+ F k (c [ ( i -1) .m+k] )+…+ F m-1 (c [i.m-1] ), i étant le numéro du paquet, S2 : fusions par paquets des résultats intermédiaires res i , 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 μ. On peut par exemple avoir m’=m. Cette méthode de fusion progressive par paquets est représentée de manière schématique sur la 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). Sur cette figure, chaque flèche représente une opération de boostrapping, avec évaluation de la quantité att [ k ] .gε pour les termes de type F k (), ou avec évaluation de la quantité pour les termes de type . 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 gε, 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 W g [X] (voir la revendication 3 de la demande PCT/IB2020/001147,), aussi noté v[X]. La structure de ce calcul de fusion par paquets reste la même que celle de la 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). 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 . 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). Par commodité, on peut supposer que K=m r (dans l'exemple de la , m=2 et r = 3, par exemple), et m’=m. Dans ce cas, l’étape S2 est exécutée r-1 fois. 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 : où . Considérations sur le bruit 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 μ, directement à partir du message chiffré c correspondant, avec une probabilité d’erreur très faible. A titre d’exemple, dans un cas où : le message μ appartient à T p , avec (soit p=5 019 589 575 > 2 32 ), en choisissant les valeurs suivantes pour les paramètres du procédé de détermination du signe : , K=21 et , 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 à B n , où B={0,1}, un paramètre de collapsing l valant quant à lui l=4), N=1024, et un écart-type σ(e i ) de la composante de bruit affectant chaque composante c i qui vaut (ce qui correspond à un niveau de bruit permettant 200 additions homomorphes sans boostrapping entre elles). La figure 12 est un tableau qui, pour cet exemple, regroupe les valeurs des coefficients de Bézout v j , 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. Détails concernant la fonction g ε , et son émulation par boostrapping Les détails ci-dessous sont présentés pour un exemple de réalisation pour lequel les coefficients d’atténuation valent att [k] =1/(2 2+k ). Ils peuvent être transposés à d’autres valeurs des coefficients d’atténuation. Tout d’abord, on suppose que : où les δ [k] de sont définis par . Les inventeurs ont alors démontré qu’il existe alors k* tel que 1. Si μ>0, alors et pour tout , ; 2. Si μ et pour tout , ; 3. Si μ=0, alors pour tout . Emulation de la fonction g ε 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. Choix du paramètre ε Par construction, la fonction est une fonction constante par morceaux avec de possibles discontinuités aux points tels que soit 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 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 T N [X] tel que . Les coefficients v j de ce polynôme sont donnés par . 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] : La fonction boostrappée complète, qui fournit une valeur chiffrée de est On remarquera que la définition des δ [k] peut être changée comme suit de sorte que la relation (3) reste valable. Boostrapping de la fonction signe Dans un cas où 1/2 k+2 n’est pas trop petit (coefficients d’atténuation pas trop petits), le signe de μ peut être obtenu par exemple en calculant la quantité suivante (ce qui correspond à une fusion directe, et non progressive par paquets) : E xemples d’ applications Calcul homomorphe de la fonction de Heaviside Pour appliquer de manière homomorphe la fonction de Heaviside H au message μ, 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+ε/2, -ε/2], et +1 sur [ε/2,1/2-ε/2] (au lieu de -1 et +1). Calcul homomorphe d’une f onction constante par morceaux quelconque Pour appliquer une fonction f constante par morceaux quelconque au message μ, 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 β j 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. Comparaison : détermination homomorphe du maximum et du minimum Soit μ a et μ b deux messages, avec c a et c b les messages chiffrés correspondants, obtenus avec le schéma de chiffrement présenté plus haut. On note h la version chiffrée de H(μ a - μ b ), déterminée comme expliqué ci-dessus (calcul de la fonction de Heaviside). Du fait de la linéarité des opérations de chiffrement employées ici, la quantité h.c a +(1-h).c b est une version chiffrée de μ a .H(μ a - μ b ) + μ b .[1- H(μ a - μ b )], qui n’est autre que le maximum max(μ a ,μ b ) de μ a et μ b . Calculer ainsi la quantité Maxh=h.c a +(1-h).c b permet donc d’obtenir, de manière homomorphe, une version chiffrée de max(μ a ,μ b ). De même, calculer la quantité Minh=h.c b +(1-h).c a permet d’obtenir, de manière homomorphe, une version chiffrée de minimum min(μ a ,μ b ) de μ a et μ b . 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 c d . Le module 311 effectue ensuite les opérations h.c a +(1-h).c b et h.c b +(1-h).c a et délivre les résultats correspondants, Maxh et Minh. 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 H(μ b - μ a ), notée h’ , puis en calculant la quantité h’.c b +(1-h’).c a (pour le maximum) et h’.c a +(1-h’).c b (pour le minimum). 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 μ a - μ b . Tri d’une base de données 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. 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. Le serveur 32 de l’exemple de réalisation de la est programmé pour exécuter un procédé de tri d’une basse de données chiffrée DB. Cette base de données comprend au moins, dans un premier emplacement de la base de données, un premier message chiffré c a , et dans un deuxième emplacement de la base de données, un deuxième message chiffré c b . 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 c a et c b , ou, respectivement, de la quantité Minh présentée ci-dessus (déterminée à partir de c a et c b ), et une écriture, dans le deuxième emplacement, de la quantité Minh, ou, respectivement, de la quantité Maxh. 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). 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 ou à un espace en bijection avec T p , avec , les entiers p i étant premiers entre eux, le message chiffré c étant formé de q composantes c i , avec , v i étant le coefficient de Bézout associé à l’entier p i , 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 , où est un nombre impair supérieur ou égal à 3, et une étape de fusion, comprenant un calcul de la somme F 0 (c) + F 1 (c [1] ) où F 0 et F 1 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 ] . 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. 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 : F 0 (c) + F 1 (c [1] )+…+ F k (c [ k ] )+…+ F m (c [ m ] ), où F k 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é. 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 res i =F 0 (c [ ( i -1) .m] ) + F 1 (c [ ( i -1) .m+1 ] )+…+ F k (c [ ( i -1) .m+k] )+…+ F m-1 (c [i.m-1] ), i étant le numéro du paquet, S2 : fusions par paquets des résultats intermédiaires res i , 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 μ. 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 . Procédé selon l’une des revendications précédentes, dans lequel la largeur ε de l’intervalle central est inférieure à . 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. 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. Procédé pour déterminer de manière homomorphe le maximum de deux messages μ a et μ b , à partir des messages chiffrés correspondants c a et c b , sans déchiffrement des messages chiffrés c a et c b , 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.c a +(1-h).c b , 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’.c b +(1-h’).c a . Procédé pour déterminer de manière homomorphe le minimum de deux messages μ a et μ b , à partir des messages chiffrés correspondants c a et c b , sans déchiffrement des messages chiffrés c a et c b , 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.c b +(1-h).c a , 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’.c a +(1-h’).c b . 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é c a , et dans un deuxième emplacement de la base de données, un deuxième message chiffré c b , 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. 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 T p , avec , les entiers p i étant premiers entre eux, le message chiffré c=(c 1 ,...c i ,...c q ) étant formé de q composantes c i , avec , v i étant le coefficient de Bézout associé à l’entier p i , 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). 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 T p , avec , les entiers p i étant premiers entre eux, le message chiffré c=(c 1 ,...c i ,...c q ) étant formé de q composantes c i , avec , v i étant le coefficient de Bézout associé à l’entier p i , 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. 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).