Brevet FR3047373A1 — publié le 20170804

DOMAINE DE L'INVENTION L'invention concerne un procédé de traitement de données mis en oeuvre conjointement par deux parties, dans lequel une fonction de deux variables est évaluée de manière sécurisée par les deux parties, en ayant pour entrées des vecteurs détenus respectivement par chaque partie. L'invention s'applique notamment à la protection de la confidentialité des vecteurs détenus par les parties, dans un contexte ou au moins l'une des parties est malicieuse, ou malveillante. ETAT DE LA TECHNIQUE On connaît du brevet FR 2 992 124 un procédé de calcul sécurisé multipartite d'une fonction de plusieurs variables, évalué en des données détenues respectivement par les différentes parties intervenant dans le calcul. Le terme « sécurisé » signifie qu'à l'issue du procédé de calcul de la fonction, le résultat est connu d'au moins l'une des parties, mais aucune partie n'a appris d'information sur les données détenues par la ou les autres parties. Le procédé décrit dans ce brevet s'applique au calcul de fonctions F s'écrivant comme somme de sous-fonctions f, de deux variables : F = fi, et à valeurs dans l'ensemble Zm des entiers compris entre 0 et m-1 où m est un nombre entier, n est un nombre entier positif correspondant au nombre de sous-fonctions, et i est un indice muet à valeurs de 1 à n. Le procédé est par exemple applicable au calcul d'une distance de Hamming entre deux données biométriques X,Y comprenant chacune n composantes x' y, Y=(Yi ,yr,), les données étant détenues par deux parties. Le calcul de la fonction est mis en oeuvre comme suit. Une première partie génère un ensemble de n valeurs aléatoires r, choisies dans l'ensemble Zrn, et génère un ensemble comprenant les éléments r,+f,(0,x,) et r,+f,(1,x,), pour chaque i de 1 à n. Les deux parties exécutent ensuite un protocole dit de « transfert inconscient » (également appelé oblivious transfer en anglais) pour que la deuxième partie récupère, pour chaque i de 1 à n, en fonction de la valeur des composantes y, de sa donnée Y, l'un des deux éléments générés par la première partie et qui correspond à r, + f,(y'x,). 3047373 2 De façon générale, un transfert inconscient est une opération de calcul entre deux parties P1 et P2. Dans ce type d'opération, P1 dispose d'une liste de N éléments indexés où N est un nombre entier positif, et P2 connaît le nombre N d'éléments de la liste et choisit un indice compris entre 0 et N-1. Par transfert 5 inconscient, P2 recupère le ième élément de P1, c'est-à-dire l'élément de P1 indexé par i. P1 n'apprend aucune information sur l'indice de l'élément récupéré par P2, et P2 ne récupère aucune information sur les autres éléments de la liste détenus par Pi. 10 Il existe plusieurs protocoles de transfert inconscient, qui sont par exemple décrits dans les publications suivantes : - Naor et al., Efficient oblivious transfer protocols, In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9 2001, Washington, DC, USA, pages 448-457, 2001. 15 - Asharov et al., More efficient oblivious transfer and extensions for faster secure computation, In 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS'13, Berlin, Germany, November 4-8 2013, pages 535-548, 2013. 20 Le transfert inconscient appliqué au protocole décrit ci-avant implique que la première partie n'apprend aucune information sur la composante y, de la deuxième partie, et la deuxième partie n'apprend aucune information sur ri + fi (1 - yi, xi). Ensuite, la deuxième partie somme les données qu'elle a obtenues pour chaque i et obtient un T = Ei(ri + (yi, xi)) = R + F(X,Y). La première partie 25 somme les valeurs aléatoires r, qu'elle a générées pour obtenir R. Ensuite l'une des parties envoie son résultat à l'autre pour obtenir par un simple calcul la valeur de F(X,Y). Pour évaluer la sécurité d'un procédé en cryptographie, on modélise le 30 comportement des parties. En particulier, on définit un comportement « semi- honnète » et un comportement « malicieux » des parties au procédé. Une partie semi-honnête est une partie qui, même si elle cherche à obtenir des informations sur les données détenues par l'autre partie, va suivre exactement les étapes du procédé. Une partie malicieuse est une partie qui ne respecte pas 3047373 3 forcément les étapes du procédé, ceci afin de tenter d'obtenir des informations sur les données détenues par l'autre partie. Par exemple, une partie malicieuse peut fausser les valeurs des x, dans les éléments r,+f,(0,x,) et r,+f,(1,x,). 5 Le procédé décrit ci-avant est sécurisé dans le cas d'une partie adverse semi-honnête si le protocole mis en oeuvre pour le transfert inconscient est lui-même sécurisé contre ce type d'adversaire. En effet, d'une part la première partie n'apprend rien sur les entrées de l'autre partie car elle joue le rôle de l'envoyeur dans le protocole de transfert inconscient et n'obtient donc aucune sortie. D'autre 10 part, la deuxième partie reçoit t= r, + f,(y'x,) mais cela ne révèle aucune information sur les f,(y'x,) car les t et les f,(y'x,) appartiennent à Zm et r, choisi aléatoirement par l'autre partie dans Zrn. Par conséquent, t, est uniformément aléatoire dans Zm et ne révèle donc aucune information sur f,(y'x,). En revanche, dans le cas où la première partie est malicieuse, elle peut 15 apprendre des informations sur la donnée détenue par l'autre partie, par exemple en modifiant la fonction calculée de sorte que f(X,Y)=x,. Par ailleurs, dans le cas où la deuxième partie est malicieuse, elle ne peut normalement pas obtenir d'informations sur la donnée détenue par la première partie grâce aux valeurs aléatoires r,. Cependant si la sélection des valeurs r, n'est 20 pas réellement aléatoire et que la deuxième partie parvient à obtenir des informations sur la façon dont les r, sont générés, alors il peut en déduire des informations sur la donnée détenue par la première partie. Ainsi, dans le cas où les parties intervenant dans le calcul sont malicieuses, le procédé de calcul n'est pas sécurisé, même si le protocole de transfert 25 inconscient l'est. PRESENTATION DE L'INVENTION L'invention a pour but de remédier au problème présenté ci-avant. En particulier, un but de l'invention est de proposer un procédé de calcul 30 multipartite d'une fonction de données détenues par plusieurs parties qui soit sécurisé même dans le cas où les parties sont malicieuses. Un autre but de l'invention est de proposer un procédé dont le temps d'exécution n'est pas considérablement accru par rapport à la version non sécurisée dans le cas de parties malicieuses. 3047373 4 Un autre but de l'invention est de proposer un procédé d'authentification d'un individu par calcul sécurisé multipartite même dans le cas où l'une des unités de traitement intervenant dans le procédé est malicieuse. 5 A cet égard, l'invention a pour objet un procédé d'exécution d'un calcul cryptographique mis en oeuvre par deux unités de traitement comprenant chacune des moyens de traitement, et possédant chacune un vecteur comprenant un nombre n de composantes indexées, le procédé comprenant l'évaluation sécurisée d'une fonction F obtenue par 10 l'application à n sous-fonctions f, de plusieurs variables d'une opération dite première opération, avec les vecteurs de chaque unité de traitement comme entrées de la fonction, le procédé étant caractérisé en ce qu'il comprend : - la mise en oeuvre d'une série d'étapes de calcul sécurisé dans lequel une unité 15 de traitement prend un rôle de client et l'autre unité de traitement prend un rôle de serveur, et - la répétition de la série d'étapes de calcul sécurisé dans laquelle les rôles de client et de serveur sont échangés entre les deux unités de traitement, chaque série d'étapes comprenant : 20 a) génération aléatoire, par le serveur, de n premières données de masquage, dans l'ensemble Zm avec m premier, inversibles pour la première opération, et d'une deuxième donnée de masquage dans l'ensemble Zrn, inversible pour une deuxième opération, différente de la première opération, et distributive par rapport à celle-ci, 25 b) pour chaque sous-fonction f' génération par le serveur d'un ensemble d'éléments, chaque élément étant formé par : o un résultat possible de la sous-fonction f, évaluée en la donnée du client et la donnée du serveur, o masqué par une première donnée de masquage, le masquage étant 30 obtenu par application de la première opération entre le résultat et la première donnée de masquage, et o masqué par la deuxième donnée de masquage, le masquage étant mis en oeuvre par application entre le résultat masqué par la 3047373 5 première donnée de masquage et la deuxième donnée de masquage de la deuxième opération, c) récupération par transfert inconscient, par le client, pour chaque composante de son vecteur, d'une donnée intermédiaire correspondant à l'un des 5 éléments générés par le serveur et indexé par la valeur de ladite composante, d) génération, par le serveur, d'une première partie de résultat, par : - le masquage de chaque première donnée de masquage par la deuxième donnée de masquage, et 10 - l'application à toutes lesdites premières données masquées de la première opération, et e) génération, par le client, d'une deuxième partie de résultat, par application à toutes les données intermédiaires de la première opération, ladite deuxième partie de résultat comprenant une évaluation masquée de la fonction F avec 15 les vecteurs des deux unités de traitement comme entrées, - la mise en oeuvre, par les deux unités de traitement, d'un test d'égalité sur les évaluations masquées de la fonction F obtenues à l'issue de chaque série d'étape, et - si le test d'égalité est satisfait, le calcul, par l'une des deux unités de traitement, 20 de la fonction évaluée avec les données des deux unités de traitement F(A,B) à partir des premières et deuxièmes parties de résultat, et - l'utilisation de la fonction évaluée avec les données des deux unités de traitement dans au moins une application parmi le groupe comprenant une application cryptographique, une application d'identification, et une application 25 d'authentification. Avantageusement, mais facultativement, le procédé selon l'invention peut en outre comprendre au moins l'une des caractéristiques suivantes : - la mise en oeuvre des deux séries d'étapes est réalisée simultanément. 30 - l'étape de calcul par l'une des deux unités de traitement de F(A,B) comprend l'obtention par une partie, de la partie de résultat détenue par l'autre unité de traitement, et la déduction de F(A,B) à partir des deux parties de résultat. 3047373 6 - la fonction à évaluer est une fraction de fonctions, et les étapes de mise en oeuvre et de répétition de la série d'étapes sont effectuées une fois pour le numérateur de la fraction, et une fois pour le dénominateur. - la première opération est une addition ou une multiplication, et la deuxième 5 opération est respectivement une multiplication ou une mise à la puissance. - la fonction F est une somme des n sous-fonctions f' et la mise en oeuvre de chaque série d'étapes comprend : o lors de l'étape b), chaque élément est formé par la somme d'un résultat possible de la sous-fonction f, évaluée en la donnée du client 10 et la donnée du serveur et d'une première donnée de masquage, et multipliée par la deuxième donnée de masquage, o lors de l'étape d), la première partie du résultat est générée par le serveur par sommation de toutes les premières données de masquage et multiplication par la deuxième donnée de masquage, et 15 o lors de l'étape e), la deuxième partie du résultat est générée par le client par sommation de toutes les données intermédiaires. - la fonction à évaluer est l'une parmi le groupe suivant : o distance de Hamming entre les vecteurs des parties, o distance de Hamming normalisée entre les vecteurs des parties, 20 o produit scalaire entre les vecteurs des parties. - les vecteurs des unités de traitement sont des données d'identité d'individus, et l'utilisation de la fonction évaluée comprend : o la comparaison de la valeur F(X,Y) à un seuil préétabli en fonction de la nature de la fonction évaluée, et 25 o à partir du résultat de ladite comparaison, la détermination (500) du fait que les données d'identité correspondent ou non à un même individu. - les données d'identité d'individus sont des données encodées sur des traits biométriques d'individus. 30 - chaque sous-fonction f, est une fonction de deux variables, les composantes des données détenues par les unités de traitement sont des entiers compris entre 0 et q-1, et : o l'étape b) comprend la génération par le serveur d'un ensemble comprenant les éléments : 3047373 7 (a(ri + fi(0,11)), , a(ri + fi (1, Y))) où Y est le vecteur possédé par le serveur, et o la donnée intermédiaire récupérée lors de l'étape c) est : a(ri + fi (xi, Y)) - la fonction à évaluer est un produit des n sous-fonctions f' et la mise en oeuvre de chaque série d'étapes comprend : 5 o lors de l'étape b), chaque élément est formé par le produit d'un résultat possible de la sous-fonction f, évaluée en la donnée du client et la donnée du serveur et d'une première donnée de masquage, et mise à la puissance de la deuxième donnée de masquage, o lors de l'étape d), la première partie du résultat est générée par le 10 serveur par produit de toutes les premières données de masquage et mise à la puissance à la deuxième donnée de masquage, et o lors de l'étape e), la deuxième partie du résultat est générée par le client par produit de toutes les données intermédiaires. - chaque sous-fonction f, est une fonction de deux variables, les composantes 15 des données détenues par les unités de traitement sont des entiers compris entre 0 et q-1, et : o l'étape b) comprend la génération par le serveur d'un ensemble comprenant les éléments : ((ri. fi(0,Y))a , fi(1,Y)r) où Y est le vecteur possédé par le serveur, et 20 o la donnée intermédiaire récupérée lors de l'étape c) est : (ri. fi(xi,n)a L'invention a également pour objet un produit programme d'ordinateur, comprenant des instructions de code pour l'exécution, par un processeur d'une unité de traitement, d'un procédé comprenant la mise en oeuvre d'une série d'étapes 25 comprenant : - génération aléatoire de n premières données dans l'ensemble de Zm avec m premier, et inversibles pour une première opération, et d'une deuxième donnée appartenant à l'ensemble des éléments inversibles de Zm pour une 3047373 8 deuxième opération, différente de la première opération et distributive par rapport à celle-ci, - pour chaque i de 1 à n, génération d'un ensemble d'éléments, chaque élément étant formé par : 5 o un résultat possible d'une fonction f, évaluée en une donnée inconnue et une donnée connue, o masqué par une première donnée de masquage, le masquage étant obtenu par l'application de la première opération entre la première donnée et le résultat, et 10 o masqué par la deuxième donnée de masquage, le masquage étant mis en oeuvre par application, entre le résultat masqué par la première donnée de masquage et la deuxième donnée de masquage de la deuxième opération, - participation à un protocole de transfert inconscient avec une unité de 15 traitement distincte pour communiquer, pour chaque i de 1 à n, un élément parmi les éléments générés. Selon un autre objet, l'invention propose un procédé d'authentification d'un individu, mis en oeuvre par un système d'authentification comportant une première unité de 20 traitement détenant une donnée d'identité de l'individu, et une deuxième unité de traitement détenant une donnée d'identité d'un individu de référence, le procédé comprenant la mise en oeuvre du procédé de traitement de données selon la description qui précède par les unités de traitement à partir des deux données d'identité, la fonction à évaluer étant choisie parmi le groupe comprenant : 25 - distance de Hamming entre les vecteurs des parties, - distance de Hamming normalisée entre les vecteurs des parties, - produit scalaire entre les vecteurs des parties. L'invention a également pour objet un système d'authentification d'un individu, 30 comprenant une première unité de traitement et une deuxième unité de traitement, chaque unité de traitement comprenant un processeur et une interface de communication, le système étant caractérisé en ce que la première et la deuxième unité de traitement sont adaptées pour mettre en oeuvre le procédé de traitement de 3047373 9 données selon la description qui précède, la fonction à évaluer étant choisie parmi le groupe comprenant : - distance de Hamming entre les vecteurs des parties, - distance de Hamming normalisée entre les vecteurs des parties, 5 - produit scalaire entre les vecteurs des parties. Selon un mode de réalisation, l'invention concerne un procédé d'exécution d'un calcul cryptographique mis en oeuvre par deux unités de traitement comprenant chacune des moyens de traitement, et possédant chacune un vecteur comprenant 10 un nombre n de composantes indexées, le procédé comprenant l'évaluation sécurisée d'une fonction F s'écrivant comme une somme de n sous-fonctions f, de plusieurs variables, l'évaluation étant mise en oeuvre avec les vecteurs de chaque unité de traitement comme entrées de la fonction, 15 le procédé étant caractérisé en ce qu'il comprend : - la mise en oeuvre d'une série d'étapes de calcul sécurisé dans lequel une unité de traitement prend un rôle de client et l'autre unité de traitement prend un rôle de serveur, - la répétition de la série d'étapes de calcul sécurisé dans laquelle les rôles de 20 client et de serveur sont échangés entre les deux unités de traitement, la série d'étapes comprenant : a) génération aléatoire, par le serveur, de n premières données de masquage appartenant à l'ensemble Zm avec m premier et d'une deuxième donnée de masquage appartenant à l'ensemble des éléments inversibles pour la 25 multiplication de Zrn, b) pour chaque sous-fonction f' génération par le serveur d'un ensemble d'éléments, chaque élément étant formé par : o un résultat possible de la sous-fonction f, évaluée en la donnée du client et la donnée du serveur, 30 o additionné d'une première donnée de masquage, et o multiplié par la deuxième donnée de masquage, c) récupération par transfert inconscient, par le client, pour chaque composante de son vecteur, d'une donnée intermédiaire correspondant à l'un des 3047373 10 éléments générés par le serveur et indexé par la valeur de ladite composante, d) génération, par le serveur, d'une première partie de résultat, par la sommation de toutes les premières données de masquage multipliées par la 5 seconde donnée de masquage, et e) génération, par le client, d'une deuxième partie de résultat, par sommation de toutes les données intermédiaires, ladite deuxième partie de résultat comprenant une évaluation masquée de la fonction F avec les vecteurs des deux unités de traitement comme entrées, 10 - la mise en oeuvre, par les deux unités de traitement, d'un test d'égalité sur les évaluations masquées de la fonction F obtenues à l'issue de chaque série d'étape, - si le test d'égalité est satisfait, le calcul par l'une des deux unités de traitement de la fonction évaluée sur les données des deux unités de 15 traitement F(A,B), et - l'utilisation de la fonction évaluée sur les données des deux unités de traitement dans une application cryptographique. Selon un deuxième mode de réalisation, l'invention concerne un procédé 20 d'exécution d'un calcul cryptographique mis en oeuvre par deux unités de traitement comprenant chacune des moyens de traitement, et possédant chacune un vecteur comprenant un nombre n de composantes indexées, le procédé comprenant l'évaluation sécurisée d'une fonction F s'écrivant comme un produit de n sous-fonctions f, de plusieurs variables, l'évaluation étant mise en 25 oeuvre avec les vecteurs de chaque partie comme entrées de la fonction, le procédé étant caractérisé en ce qu'il comprend : - la mise en oeuvre d'une série d'étapes de calcul sécurisé dans lequel une partie prend un rôle de client et l'autre partie prend un rôle de serveur, - la répétition de la série d'étapes de calcul sécurisé dans laquelle les rôles de 30 client et de serveur sont échangés entre les deux parties, la série d'étapes comprenant : a) génération aléatoire, par le serveur, de n premières données de masquage et d'une deuxième donnée de masquage appartenant à l'ensemble des éléments inversibles de Zmavec m premier, 3047373 11 b) pour chaque sous-fonction f' génération par le serveur d'un ensemble d'éléments, chaque élément étant formé par : o un résultat possible de la sous-fonction f, évaluée en la donnée du client et la donnée du serveur, 5 o multiplié par une première donnée de masquage, et o mis à la puissance de la deuxième donnée de masquage, c) récupération par transfert inconscient, par le client, pour chaque composante de son vecteur, d'une donnée intermédiaire correspondant à l'un des éléments générés par le serveur et indexé par la valeur de ladite 10 composante, d) génération, par le serveur, d'une première partie de résultat, par la multiplication de toutes les premières données de masquage à la puissance de la deuxième donnée de masquage, et e) génération, par le client, d'une deuxième partie de résultat, par multiplication 15 de toutes les données intermédiaires, ladite deuxième partie de résultat comprenant une évaluation masquée de la fonction F avec les vecteurs des deux unités de traitement comme entrées, - la mise en oeuvre par les deux parties d'un test d'égalité sur les évaluations masquées de la fonction F obtenues à l'issue de chaque série d'étape, 20 - si le test d'égalité est satisfait, le calcul par l'une des deux parties de la fonction évaluée en les données des deux parties F(A,B), et - l'utilisation de la fonction évaluée sur les données des deux unités de traitement dans une application cryptographique. 25 Le procédé proposé est sécurisé même dans le cas où les parties au calcul, c'est-à-dire les unités de traitement, sont malicieuses, en supposant que le protocole de transfert inconscient soit lui-même sécurisé. En effet, en premier lieu le fait de proposer une exécution double de la série d'étapes du calcul de la fonction, en inversant les rôles entre les deux parties, 30 permet que chaque partie obtienne une partie du résultat. Le test d'égalité permet ensuite de comparer si les deux résultats sont identiques sans révéler leurs valeurs afin de pouvoir arrêter le protocole sans révéler la sortie en cas de triche. En second lieu, le procédé permet de se prémunir d'un cas où une partie malicieuse fausserait le résultat du test d'égalité ou le résultat de la fonction F(X,Y) 3047373 12 en modifiant les valeurs des parties de résultat T et de R obtenues à l'issue d'une série d'étapes. En effet, le procédé comprend un double masquage qui comprend la génération aléatoire par chaque partie d'une donnée inversible qui protège ces valeurs de T et R. Il est ainsi beaucoup plus difficile, pour une partie malicieuse, de 5 fausser le test d'égalité de F(X,Y) car elle ne connaît pas la valeur de la donnée inversible de l'autre partie et ne peut donc pas adapter ses valeurs de T, R, ou de sa deuxième donnée de masquage, pour tromper le test d'égalité. Comme les deux séries d'étapes peuvent être exécutées en parallèle, ce procédé ne requiert qu'une augmentation très limitée du temps d'exécution par 10 rapport à la version du procédé non sécurisée contre des parties malicieuses. L'application du procédé présenté à des fonctions de types distance de Hamming, ou produit scalaire, sur des données d'identité d'individus telles que des données biométriques, permet une authentification sécurisée d'individus. 15 DESCRIPTION DES FIGURES D'autres caractéristiques, buts et avantages de la présente invention apparaîtront à la lecture de la description détaillée qui va suivre, au regard des figures annexées, données à titre d'exemples non limitatifs et sur lesquelles : - La figure la représente un premier exemple d'exécution répétée d'une série 20 d'étapes d'un procédé d'exécution d'un calcul cryptographique, - La figure 1 b représente un deuxième exemple d'exécution répétée d'une série d'étapes d'un procédé d'exécution d'un calcul cryptographique avec un masquage différent, - La figure 2a représente un exemple de test d'égalité applicable à l'exemple 25 d'exécution de la figure I a, - La figure 2b représente un exemple de test d'égalité applicable à l'exemple d'exécution de la figure 1 b, - La figure 3a représente schématiquement les principales étapes d'un exemple de procédé d'exécution d'un calcul cryptographique, 30 - La figure 3b représente schématiquement les principales étapes d'un exemple de procédé d'authentification, - La figure 4 représente schématiquement un de système de traitement de données adapté pour la mise en oeuvre du procédé, dans un exemple d'application à une authentification d'individu. 3047373 13 DESCRIPTION DETAILLEE D'AU MOINS UN MODE DE MISE EN OEUVRE DE L'INVENTION Système de traitement de données 5 En référence à la figure 4, on a représenté deux parties P1 et P2 disposant respectivement d'un vecteur A et B, chaque vecteur comprenant un même nombre n de composantes indexées (a1,...,an), ,bn). Chaque vecteur est exprimé en base q, où q est un nombre entier strictement supérieur à 1, c'est-à-dire que les composantes aiet bi sont des entiers 10 à valeurs comprises entre 0 et q-1. Les données A et B ne sont pas nécessairement exprimées dans la même base de sorte que A peut être en base q et B en base q' avec q' un entier strictement supérieur à 1 et différent de de q. Selon un mode de réalisation particulier et non limitatif, chaque vecteur est binaire, et ses composantes sont à valeurs égales à 0 ou 1. 15 Les vecteurs A et B respectivement détenus par les parties P1 et P2 sont secrets, c'est-à-dire que le vecteur A n'est connu que de P1 et le vecteur B n'est connu que de P2. Chaque partie est une unité de traitement, et dispose de moyens de traitement, par exemple un processeur 101,102, adapté pour mettre en oeuvre des 20 calculs, et pour exécuter un programme comprenant des instructions de code installées sur le processeur. Chaque partie dispose également d'une mémoire 111, 112 et d'une interface de communication 121, 122 avec l'autre partie. Les deux parties P1 et P2 peuvent s'engager dans un procédé d'exécution d'un calcul cryptographique comprenant le calcul d'une fonction F qui est obtenue 25 par l'application à un ensemble de n sous-fonctions f, d'une même opération mathématique, dite première opération, où les sous-fonctions f, sont à plusieurs variables, n est un nombre entier positif correspondant au nombre de sous-fonctions dans la fonction f, et i est un indice muet à valeurs de 1 à n. On peut noter F=fiopf2op... opfn, où op est la première opération. 30 La première opération est par exemple une somme ou un produit, c'est-à- dire que la fonction F s'écrit respectivement soit comme une somme, soit comme un produit, des n sous-fonctions f,. En particulier, chaque sous-fonction f, est une fonction de deux variables X et Y à n composantes x' y,. Dans le cas où F s'écrit comme une somme de sous-fonctions f' on note : 3047373 14 F (X ,Y) fi(xi,Y) fi(yi, X) i=t i=i avec xi, yi, les composantes entières des variables X et Y. Dans le cas où F s'écrit comme un produit de sous-fonctions fi, on note : n n F (X ,Y) = fi(xi,Y) = fi(yi, X) i=t i=i avec xi, yi, les composantes entières des variables X et Y. Les sous-fonctions de xi, Y et de yi, X peuvent être différentes de sorte que 5 l'on pourrait avoir une expression de F telle que : F (X, Y) = fi(xi,Y) = FI g i(yi, X) i=t i=t De même le nombre de composantes de x, et y' et donc de sous-fonctions f, et g, pourraient être deux nombres différents. Le procédé s'applique dans ce cas de la même manière moyennant une prise en compte des différences de sous-fonctions et de nombre de composantes. 10 Cependant, dans la suite on prendra le cas simplifié ou les sous-fonctions sont identiques, et les nombres de composantes des données sont identiques aussi. La fonction F peut également être une fraction dont le numérateur et le dénominateur sont chacun obtenus par l'application de la première opération à n 15 sous-fonctions. Dans ce cas, et comme on le voit ci-après, le procédé est mis en oeuvre deux fois, une fois pour le calcul du numérateur, et une fois pour le calcul du dénominateur. La fonction F est à valeurs dans l'ensemble Zm des entiers compris entre 0 et m-1, où m est un nombre entier positif, et est en outre premier, pour des raisons 20 explicitées ci-après. De plus, la fonction F est à valeurs dans le sous-ensemble de Zm des éléments inversibles pour la première opération. Ceci signifie que, dans le cas où la fonction F s'écrit comme un produit de n sous-fonctions f' cette fonction est à valeurs dans l'ensemble Zm* des entiers compris entre 1 et m-1, avec m également premier. En d'autres termes, les fi(xi,Y) 25 et les fi(yi,X) sont avantageusement tous différents de O. Ceci permet d'améliorer la sécurité du procédé pour les raisons détaillées ci-après. 3047373 15 Le procédé de traitement de données qui va être décrit ci-après peut notamment s'appliquer à un contexte d'authentification d'individus, notamment d'authentification biométrique, lorsque la fonction F s'écrit comme une somme des sous-fonctions f,. Le système d'authentification de la figure 4 est représenté dans un 5 tel contexte et à titre d'exemple non limitatif. Un procédé d'authentification comprend une comparaison d'une donnée d'identité d'un individu candidat à une donnée d'un individu de référence pour détecter une correspondance entre les données et déterminer que l'individu est l'individu de référence. 10 Dans ce contexte, une partie P1 peut être une unité de contrôle d'un individu candidat, comprenant par exemple un moyen d'acquisition 13 d'une donnée d'identité de l'individu. Cette donnée d'identité est avantageusement une donnée biométrique, c'est-à-dire une donnée numérique encodée sur un trait biométrique d'un individu. 15 Les traits biométriques concernés peuvent typiquement comprendre des empreintes digitales, images d'iris, forme du visage, etc. Dans ce cas, le moyen d'acquisition de donnée d'identité du serveur de contrôle est avantageusement un capteur de donnée biométrique (par exemple, mais non limitativement, un capteur d'empreinte digitale) ou un lecteur de document 20 d'identité dans lequel une donnée biométrique a été préalablement enregistrée, par exemple en étant mémorisée dans une puce électronique intégrée au document ou en étant imprimée sur le document. L'autre partie P2 peut être une unité comprenant au moins une donnée d'identité d'un individu de référence, stockée par exemple dans sa mémoire 112. 25 La fonction F peut alors être une fonction de comparaison de données d'identité d'individus, et en particulier peut être choisie parmi le groupe suivant : - Distance de Hamming, définie par F(X,Y) = xieyi, - , Distance de Hamming normalisée, définie par F(X,Y)= En lfmomri(x/EDY/)) où M=(111,... mn) et M'(m'i,...,m'n) sont des vecteurs de masquage 30 respectivement associés aux vecteurs X et Y, dont les bits à 1 indiquent les bits de même index des vecteurs X et Y à prendre en compte pour le calcul de la distance de Hamming, et - Le produit scalaire, défini par F(X,Y) = yi. 3047373 16 Lors d'un procédé d'authentification d'un individu, les parties P1 et P2 s'engagent dans le calcul de la fonction F choisie parmi ce groupe en suivant le procédé décrit ci-après pour évaluer un taux de similarité entre une donnée d'identité de l'individu et une donnée d'identité de l'individu de référence. 5 Si le taux de similarité est inférieur à un seuil prédéterminé, les données d'identité de l'individu candidat et de l'individu de référence sont considérées comme provenant de la même personne et l'individu candidat est authentifié. Procédé de traitement de données 10 En référence aux figures la à 3a, on va décrire un procédé de calcul de la fonction F pouvant être mis en oeuvre par un système tel que présenté ci-avant, et qui permet qu'une des parties obtienne l'évaluation de la fonction F(A,B) avec pour entrées les vecteurs A et B détenues par les parties, sans qu'aucune partie n'obtienne d'informations sur le vecteur de l'autre partie, même si elle présente un 15 comportement malicieux. Pour ce faire, le procédé comprend une première phase 100, illustrée en figures la et 1b, comprenant la mise en oeuvre d'une série d'étapes déterminées 1001 dans laquelle la première partie P1 a un rôle de client et la deuxième partie P2 a un rôle de serveur, et la répétition de cette série d'étapes 1002 en inversant les 20 rôles, c'est-à-dire que la première partie P1 a un rôle de serveur et la deuxième partie P2 a un rôle de client. De préférence, mais non limitativement, la mise en oeuvre des deux séries d'étapes peut être réalisée simultanément par les deux parties, ceci afin de raccourcir la durée d'exécution du procédé. Alternativement, les séries d'étapes 25 peuvent être mises en oeuvre successivement. Première phase du procédé Dans la suite, et par esprit de concision, on va décrire la série d'étapes par rapport aux rôles du serveur et du client sans détailler la première phase puis la 30 deuxième phase, puisqu'elles sont symétriques. On note X le vecteur détenu par la partie ayant le rôle de client et Y le vecteur détenu par la partie ayant le rôle de serveur. On comprend donc que lors de la mise en oeuvre de la première série d'étapes 1001, X=A et Y=B, et lors de la mise en oeuvre de la deuxième série d'étapes 1002, X=B et Y=A. On note également par 3047373 17 les indices 1 et 2 les étapes mises en oeuvre ou les données générées respectivement lors de la première ou la deuxième série d'étapes. L'implémentation de chaque série d'étapes avec les notations propres à chaque partie et chaque mise en oeuvre de la série d'étapes est néanmoins 5 détaillée sur les figures la et 1b. Chaque série d'étapes 1001, 1002 comporte une première étape 1101, 1102 au cours de laquelle le serveur génère aléatoirement un ensemble de n premières données de masquage indexées r, dans l'ensemble Zrn. Les données r, sont en 10 outre choisies parmi les éléments inversibles dans l'ensemble Zrn, pour la première opération. En d'autres termes, si F est une somme des sous-fonctions f' alors les données r, sont inversibles pour l'addition, et elles sont donc choisies parmi l'ensemble Zrn. 15 On note : Vi E [1, TL], rl E RZm En revanche, si la fonction F Est un produit des sous-fonctions f' alors les données r, sont inversibles pour la multiplication, et elles sont donc choisies parmi l'ensemble Zm* (soit Zm privé de l'élément 0). On note : Vi E [1, TL], rl E RZm 20 Le serveur génère également aléatoirement une deuxième donnée de masquage a inversible pour une deuxième opération, qui est différente de la première et distributive par rapport à celle-ci. Par exemple, si la première opération est l'addition, F est une somme de f' et la deuxième opération est avantageusement 25 la multiplication. Si la première opération est la multiplication, F est un produit de f' la deuxième opération est avantageusement la mise à la puissance. Dans ces deux exemples, la deuxième donnée de masquage a doit être inversible pour la multiplication dans l'ensemble Zm (car les mêmes critères d'inversibilité s'appliquent pour la multiplication et la mise à la puissance). On note 30 a E RZIn* - 3047373 18 Sur les figures la et 1 b, on a en outre ajouté l'indice 1 ou 2 aux données r, et a pour indiquer que ces données sont générées respectivement lors de la première ou de la deuxième mise en oeuvre de la série d'étapes 100 et ne sont donc pas identiques (par exemple ai# a2 et pour chaque i de 1 à n ro# r,2). Les indices 1 et 2 5 sont néanmoins omis dans la plupart des notations ci-après pour ne pas alourdir le texte. Le fait que m soit premier implique que tous les éléments de l'ensemble Zm* sont inversibles pour la multiplication. Par conséquent, lorsque la deuxième donnée a est choisie aléatoirement, on ne peut déduire aucune information sur la valeur de 10 cette donnée. Comme on l'a dit, dans le cas d'une fonction F sous la forme d'une fraction de fonctions, comme c'est le cas par exemple de la distance de Hamming normalisée (cas non représenté sur la figure la), alors à chaque implémentation de 15 l'étape 100, des données r, et a sont générées pour le numérateur, et des données r', et a' (présentant les mêmes propriétés que les données r, et a) pour le dénominateur . Lors d'une étape 1201, 1202, le serveur génère, à partir de ces données, et 20 pour chaque sous-fonction f' c'est-à-dire pour tout i de 1 à n, un ensemble d'éléments, tel que chaque élément est formé par un résultat possible de la fonction f, évaluée en la donnée du client (qui lui est donc inconnue) et la donnée du serveur f,(x'Y), masquée par une première donnée de masquage r, et par la deuxième donnée de masquage a. 25 Le masquage par la première donnée de masquage r, est mis en oeuvre en appliquant entre cette donnée et le résultat possible de la fonction f, la première opération, c'est-à-dire par exemple sommation ou multiplication, si F est obtenue respectivement par sommation ou multiplication des sous-fonctions f,. Dans le cas où F est une somme de f' chaque résultat possible de la 30 fonction f, évaluée en la donnée du client et la donnée du serveur est additionné d'une première donnée de masquage r,. Dans le cas où F est un produit de f' chaque résultat possible de la fonction f, évaluée en la donnée du client et la donnée du serveur est multiplié par une première donnée de masquage r,. 3047373 19 Le masquage par la deuxième donnée de masquage a est mis en oeuvre par application, entre le résultat de la fonction f, masqué par une première donnée de masquage r, et la deuxième donnée de masquage a, de la deuxième opération. 5 En particulier, dans le cas où la première opération est une sommation, chaque élément de l'ensemble généré par le serveur est un résultat possible de la fonction f, évaluée en la donnée du client et la donnée du serveur, additionné d'une première donnée de masquage r' et multiplié par la deuxième donnée de masquage a: a(ri + fi (x Y)) 10 Par exemple, si la fonction est une somme de sous-fonctions f, à deux variables et que les données X et Y sont binaires, le serveur génère donc un doublet comme suit : (a(r, f, (0, Y)), a(r, f,(1, Y))) 15 Dans le cas où la première opération est une multiplication, la deuxième opération est une mise à la puissance à la deuxième donnée de masquage a. Alors, chaque élément de l'ensemble généré par le serveur est un résultat possible de la fonction f, évaluée en la donnée du client et la donnée du serveur, multiplié par une première donnée de masquage r' et mis à la puissance a : fi(xi,Y))a 20 Par exemple, lorsque la fonction est un produit de sous-fonctions f, à deux variables, et que les données X et Y sont binaires, le serveur génère un doublet comme suit : ((ri. fi(0,Y))a , (ri. fi(1,Y))a) 25 Lorsque la fonction F est une fraction, un ensemble conforme à la description qui précède est généré par le serveur pour le numérateur, et un autre pour le dénominateur. Selon un exemple particulier, dans le cas où la fonction à évaluer est la distance de Hamming normalisée, chaque partie détient, en plus de sa donnée 3047373 20 respective A, B, binaire une donnée de masquage respective de taille n, également binaire, et dont les bits à 1 indiquent respectivement les bits des vecteurs A et B à prendre en compte pour le calcul de la distance de Hamming. On note M=(mi,... mn) la donnée de masquage détenue par l'unité ayant le rôle de serveur et 5 m'n) la donnée de masquage détenue par l'unité ayant le rôle de client. Sur la figure 4, on a indiqué par AM et BM les données de masquage correspondant respectivement aux vecteurs A et B. On a donc, lors de la première mise en oeuvre de la série d'étapes 1001, AM=M' et BM=M, et lors de la seconde mise en oeuvre de la série d'étapes 1002, AM=M et BM=M'. 10 Dans ce cas, on peut se ramener pour chaque partie à une donnée de longueur 2n en considérant qu'un bit de la donnée associée à un bit correspondant du masque à 0 est nul. On pose ainsi X' une donnée obtenue à partir de X et M', de longueur 2n, et telle que x',=x, pour i =1 à n et x',=m',, pour i compris entre n+1 et 2n. La même 15 chose s'applique mutatis mutandis pour obtenir Y' à partir de Y et M. Lors de l'étape 120, le serveur génère, pour ce qui concerne le numérateur, pour tous les i de 1 à 2n, un ensemble de doublets : (a(ri fi num (0, y)), cr(r, fi num (1, Y'))) Où finumdésigne le numérateur de la distance de Hamming normalisée, dont les valeurs sont détaillées au paragraphe 4.2 de la publication de J. Bringer et al., 20 « GSHADE : Faster Privacy-Preserving Distance Computation and Biometric Identification », In Proceedings of the 2nd ACM workshop on Information hiding and multipedia security, 187-198, 2014. Le serveur génère également, pour le dénominateur, pour tous les i de 1 à n, un ensemble de doublets : 25 (a' r ri, a' (r' + mi)). Au cours de l'étape 120, le serveur génère ainsi une combinatoire des résultats possibles de la fonction F évaluée en la donnée du serveur et du client, en masquant les résultats par les r, et a, (et les cas échéant r', et a',). 30 La série d'étapes comprend ensuite une étape 1301, 1302 lors de laquelle le client et le serveur s'engagent dans un protocole de transfert inconscient, où le client récupère, pour chaque i de 1 à n, l'un des éléments de l'ensemble généré par 3047373 21 le serveur à l'étape 120, indexé de la valeur de x,. Le type de transfert inconscient qui est utilisé pour cette étape est de préférence un protocole qui est sécurisé contre les parties malicieuses. C'est le cas des protocoles de transfert inconscient qui sont décrits dans ces deux publications : 5 - Asharov et al., More efficient oblivious transfer and extensions for faster secure computation, In 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS'13, Berlin, Germany, November 4-8 2013, pages 535-548, 2013. - Asharov et al., More efficient oblivious transfer extensions with security for 10 malicious adversaries. In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographie Techniques, Sofia, Bulgaria, April 26-30 2015, Proceedings, Part I, pages 673-701, 2015 15 Le transfert inconscient est schématisé sur les figures 1 a et 1 b par le sigle « OT ». En particulier, dans le cas où le serveur a généré un doublet pour chaque i, si x, est égal à 0, le client récupère par un transfert inconscient de type 1 parmi 2 le premier élément du doublet, et si x, est égal à 1, il récupère le deuxième élément du doublet. Dans un cas plus général où la donnée du client est exprimée en base q, le serveur 20 aura généré un q-uplet pour chaque i, et le client récupère par un transfert inconscient de type 1 parmi q l'élément du doublet correspondant à la valeur de x, entre 0 et q-1. Ainsi le client peut récupérer une donnée t nommée donnée intermédiaire. La donnée intermédiaire t s'écrit, dans le cas où la fonction F est une somme de 25 sous-fonctions f,: ti = a(ri + fi(xi,n) Dans le cas où la fonction F est un produit de sous-fonctions fi, elle s'écrit : ti,(ri. fi(xi,n)a Dans l'exemple introduit précédemment où la fonction F est la distance de Hamming normalisée, le client récupère une donnée intermédiaire ti pour le numérateur, en fonction de la valeur de x'i tel que défini ci-avant, et une donnée 30 intermédiaire fi pour le dénominateur, en fonction de la valeur de m'i. 3047373 22 Sur les figures la et 1 b, on a également ajouté un indice 1 ou 2 aux données intermédiaires t, selon qu'elles sont obtenues lors de la première ou la deuxième implémentation de la phase 100. 5 Lors d'une étape 1401, 1402, le serveur génère à partir de toutes les premières données de masquage r, et de la deuxième donnée de masquage une première partie de résultat notée R. Cette partie R est obtenue en appliquant la première opération - c'est-à-dire par exemple addition ou multiplication - à toutes les premières données de 10 masquage, et en les masquant par la deuxième donnée a, c'est-à-dire en leur appliquant la deuxième opération avec a, par exemple respectivement en les multipliant par a ou les mettant à la puissance a. En résumé, dans le cas où la fonction F est une somme des sous-fonctions f' le serveur génère une partie de résultat R telle que : R= 15 Dans le cas où la fonction F est un produit des sous-fonctions f' le serveur génère une partie de résultat R telle que : R = (H ri)a i=t Dans le cas du calcul d'une fonction sous forme de fraction, le serveur effectue cette opération pour le numérateur à partir des données r, et a pour obtenir une donnée R et pour le dénominateur à partir des données r', et a' pour obtenir une donnée R'. 20 L'étape 140 peut être mise en oeuvre à n'importe quel moment après l'étape 110, et pas nécessairement après l'étape 130. Bien entendu, et comme visible sur les figures la et 1 b, une partie de résultat R (et le cas échéant R') est calculée lors de chaque implémentation de la phase 100. On note R1 la partie de résultat calculée lors de la première 25 implémentation de la phase 100, et R2 la partie de résultat calculée lors de la deuxième implémentation de la phase 100. R1 et R2 sont différentes. Lors d'une étape 1501, 1502, le client applique la première opération - c'est-à-dire par exemple addition ou multiplication - à toutes les données intermédiaires t, 30 de manière à obtenir une partie de résultat T telle que : 3047373 23 - Si la fonction F est une somme de sous-fonctions f, : n T = ti -/n. a(r1 + f1(x1,Y)) = R + aF ,Y) 1=1 i=t - Si la fonction F est un produit de sous-fonctions fi : T = ti = fi(xi,n)a = R. F , i=i i=i Comme précédemment, une partie de résultat T est calculée lors de chaque implémentation de la phase 100, et sur les figures la et 1 b on a noté 5 respectivement T1 et T2 les parties de résultats obtenues respectivement lors de la première et la deuxième implémentation, T1 et T2 étant différentes. Dans le cas où la fonction f est une fraction, cette étape est mise en oeuvre pour le numérateur (obtention d'une donnée T) et pour le dénominateur (obtention d'une donnée T') avec les données intermédiaires respectives. 10 En reprenant les indices 1 et 2 liés à la première ou deuxième implémentation de la phase 100, à l'issue de la première mise en oeuvre de la série d'étapes, la partie P1 dans le rôle du client dispose d'une donnée T1 et la partie P2 dans le rôle du serveur dispose d'une donnée R1 permettant ensemble d'obtenir une 15 première évaluation de la fonction F en les données du client et du serveur, masquée par la deuxième donnée de masquage al, qui a été générée aléatoirement par la partie P2 en tant que serveur, et est donc inconnue de la partie P1. Dans le cas où F est une somme de sous-fonctions, on a T1 -R1 = aifi(X,Y) Dans le cas où F est un produit de sous-fonctions, on a R1-1 = Fi_ (X, Y) ai 20 A l'issue de la deuxième mise en oeuvre de la série d'étapes 1002, la partie P1 dans le rôle du serveur dispose d'une donnée R2, et la partie P2 dans le rôle du client dispose d'une donnée T2 permettant d'obtenir une deuxième évaluation de la fonction F en les données du client et du serveur, masquée par la deuxième donnée 25 de masquage a2, qui a été générée aléatoirement par la partie P1 en tant que serveur, et est donc inconnue de la partie P2. Dans le cas où F est une somme de sous-fonctions, on a: 3047373 24 T2 - R2 = a2F2 (X, Y) Dans le cas où F est un produit de sous-fonctions, on a : T2 . R2 = F2 (X, Y)Ce2 Les résultats Fi(X,Y) et F2(X,Y) sont égaux et valent F(A,B) en l'absence de fraude. Dans le cas où l'une des parties est malicieuse, par exemple P1, elle ne peut 5 donc pas, en modifiant les valeurs des données qu'elle détient, par exemple T1, R2 et a2, faire en sorte que : a2 (Ti - R1) = a2 (X, Y) = (T2 - R2) = a1a2F2 (X, Y) Ou que : (T1. R1-1)a2 = Fl (X, nala2 = (T2. R2 -1)al = F2(X,Y)a2ai De retour à l'étape 150, pour le cas de la distance de Hamming généralisée, 10 le client somme séparément les données intermédiaires ti et fi obtenues pour le numérateur et le dénominateur, pour obtenir (indices 1 et 2 omis) : T =1ti= R + aIKX yAmnmill T' =le 1 = + i=i On obtient donc, à la suite des deux implémentations de la phase 100, les relations suivantes : T1 R1 a1(ai)-1Fi(X,Y) = el T2 R2 a2 (a)-1-F2 (X, Y) = 15 Comme précédemment, grâce à la multiplication lors de chaque série d'étapes par une valeur al, a'1, a2 ou a'2 aléatoire et propre à une partie, une partie malicieuse, par exemple P1, ne peut pas modifier les éléments qu'elle détient, soit T1, T'1, R2, R'2 et a2 et a'2, pour faire en sorte que : a1 T2 R2 (ai)-1a2 (aD-1F2 (X, = T, -R'2 ai 2 - a2 T1 - (ai)-1a2 (aD -1-Fi (X, = T, R, 1 1 20 Test d'égalité 3047373 25 A l'issue de la phase 100, le procédé comprend un test d'égalité 200 des valeurs de F1(X,Y) et F2(X,Y) pouvant être déduites de chaque série d'étapes de la phase 100. Pour que ce test d'égalité 200 ne révèle pas d'information sur la valeur de F (X,Y) avant d'avoir vérifié l'égalité, il comprend les deux étapes suivantes : 5 - Une première étape 210 consiste à « mettre en gage » ou réaliser un « commitment » de l'ensemble des sorties des deux séries d'étapes de la phase 100, à savoir T1, R1, al, et T2, R2, a 2. Une mise en gage est une opération classique en cryptographie consistant à générer, à partir d'une donnée, d'une fonction de chiffrement et d'une clé, une 10 valeur ne fournissant aucune information sur la donnée initiale. De plus, elle garantit que lors de l'opération de « désengagement » ou « decommitment », qui consiste à retrouver la donnée initiale à partir de la valeur, de la clé et d'une fonction de déchiffrement adaptée, la donnée initiale obtenue à l'issue du désengagement n'a pas été altérée. L'étape 210 permet donc d'assurer que, lors du test d'égalité, 15 aucune sortie des séries d'étapes de la phase 100 n'est altérée. - Une deuxième étape 220 est une vérification de l'égalité des valeurs de F1(X,Y) et F2(X,Y) sans qu'une partie n'obtienne d'information sur le résultat F(X,Y). 20 A titre d'exemple non limitatif, on décrit ci-après et en référence à la figure 2 un protocole de test d'égalité possible pour cette phase 200. Lors de ce protocole, la partie P1 a pour entrées les données T1, R2 et a2 et la partie P2 a pour entrées les données R1, T2 et al issues de la première phase 25 100. Le protocole comprend une première étape de mise en gage 210 au cours de laquelle la partie P1 met en gage, au moyen de clés aléatoires K1, K2, K3 respectivement ses données T1, R2 et a2 pour obtenir trois jetons cl, c2, c3 définis respectivement par : = Com(T1, K1) C2 = COM(R2, 1(2) c3 = Com(a2, K3) 30 La partie P1 envoie les jetons à la partie P2. Dans le cas où la fonction calculée est la distance de Hamming généralisée, les données T'1, R'2 et a'2sont 3047373 26 mises en gage avec d'autres clés aléatoires, et les jetons obtenus sont aussi envoyés à l'autre partie. De son côté, la partie P2 met en gage, au moyen de clés aléatoires K4, K5, 5 K6, respectivement ses données R1, T2 et al pour obtenir trois jetons c4, c5, c6 définis respectivement par : c4 = Com(Ri, K4) c5 = Com(T2, K5) c6 = Com(a1, K6) La partie P2 envoie les jetons à la partie P1. Dans le cas où la fonction calculée est la distance de Hamming généralisée, les données T'2, R'1 et a'1 sont mises en gage avec d'autres clés aléatoires, et les jetons obtenus sont aussi 10 envoyés à la première partie P1. L'étape 220 de vérification de l'égalité des valeurs de F1(X,Y) et F2(X,Y) obtenues lors de la phase 1 peut ensuite être mise en oeuvre comme suit, selon un exemple non limitatif. 15 La première partie P1 envoie à la deuxième partie P2 la donnée R2 et la clé K2. La partie P2 peut donc réaliser le désengagement de la donnée R2, DeCOM(C2, K2), et vérifier qu'elle correspond à la donnée transmise, et donc que la partie P1 ne l'a pas modifiée. S'il existe une différence entre la donnée R2 transmise par P1 et son désengagement à partir de K2, le protocole s'arrête, une fraude est 20 détectée. Ensuite, la deuxième partie P2 envoie à la première partie P1 la donnée R1 et la clé K4. La partie P1 peut réaliser le désengagement de la donnée R1, Decom(c4, K4), et vérifier qu'elle correspond à la donnée transmise. S'il existe une différence entre la donnée R1 transmise par P2 et son désengagement à partir de 25 K4, le protocole s'arrête, une fraude est détectée. Dans le cas d'une fonction F sous forme de fraction de fonctions, la vérification de l'égalité est réalisée en vérifiant séparément l'égalité des numérateurs et des dénominateurs. 3047373 27 Sur la figure 2a, dans le cas où la fonction F est une somme de sous-fonctions f' la partie P1 et la partie P2 sont alors en mesure de calculer respectivement les valeurs ot1a2F1 (X, Y) et a1a2F2 (X, Y) (par a2(T1-R1) et a1(T2-R2)). On note H1 = Hash(a1a2MX,Y)) et H2 = Hash(a1a2F2(X,Y)) où Hash est 5 une fonction de hachage. Une partie envoie d'abord l'un de H1 ou H2 à l'autre partie, qui compare l'un de H1 ou H2 reçu à l'autre qu'elle détenait auparavant. Si H141-12, la partie ayant effectué la comparaison arrête le protocole. Sinon, cette partie ne disposant que de hachés elle ne peut pas en déduire la valeur de la fonction F évaluée en X et Y. 10 Alors cette partie envoie à l'autre celui qu'elle détient parmi a1a2F2(X,Y) et a1a2MX, Y). La partie ayant reçu par exemple a1a2F2(X,Y) le compare à a1a2F1(X,Y) qu'elle détenait déjà (ou vice-versa) pour vérifier l'égalité entre les deux termes. Si ce n'est pas le cas, la partie arrête le protocole. Sinon, les deux parties ont pu vérifier si F1(X,Y)=F2(X,Y) tout en s'assurant 15 que l'autre partie n'a pas altéré l'intégrité des données. Sur la figure 2b, dans le cas où la fonction F est un produit de sous-fonctions f' la partie P1 et la partie P2 sont en mesure de calculer (MX, Y))aia2 et (F2 (X, Y))aia2 (par (T1R11)a2 et (T2R21)"1) 20 On note H'1 = Hashee,nr1a2) et H'2 = HashOEF2(X,Y)r1a2) où Hash est une fonction de hashage. Une partie envoie l'un de H'1 ou H'2 à l'autre partie, qui compare H'1 et H'2, et arrête le protocole s'il existe une différence. Sinon, elle renvoie ensuite à l'autre partie l'un de (F2(X, Y))aia2 et 25 (Fi (X, Y))"1"2. La partie possédant (F2(X, Y))aia2 et (MX, Y))aia2 les compare, et s'il existe une différence, elle arrête le protocole. Ainsi les deux parties peuvent vérifier si (X,Y)=F2(X,Y) tout en garantissant l'intégrité des données. 30 Si une partie constate que Fi (X,Y)4F2(X,Y), alors le protocole s'arrête, et une fraude est détectée. 3047373 28 A l'issue du test d'égalité, si l'égalité des valeurs de Fi (X,Y) et F2(X,Y) a été vérifiée et confirmée, alors l'une des deux parties peut calculer F(X,Y) lors d'une étape 300. Par exemple, une partie peut soit utiliser sa donnée T1 (resp T2) et récupérer R1 (resp R2) et al (resp a2) auprès de l'autre partie, soit utiliser ses données R1 (resp 5 R2) et al (resp a2) et récupérer la donnée T1 (resp T2) détenue par l'autre partie, pour déduire F(A,B). Selon une variante avantageuse en termes de sécurité, la partie peut utiliser une donnée de l'autre partie qu'elle a déjà reçue lors du procédé (en l'occurrence, R1 ou R2), et utiliser également les deux autres paramètres T1, al ou T2, a2 détenus 10 par l'autre partie et qu'elle n'a pas récupérés. En effet, la partie peut également récupérer les jetons de mise en gage des paramètres correspondants et vérifier l'intégrité à partir des jetons. La déduction de F(A,B) se fait, quand F est une somme de sous-fonctions, par l'opération : F (A, B) = - R1) 15 Ou F (A, B) = ail (T2 - R2) La déduction de F(A,B) se fait, quand F est un produit de sous-fonctions, par l'opération : 20 ou 1 F(A, B) = (Ut 1)al 1 F(A, B) = (T2R2 1)2 Dans le cas où la fonction calculée est une fraction de fonctions, le calcul de F(A,B) est réalisé en calculant d'abord le numérateur, puis le dénominateur de la fonction. 25 Le résultat de la fonction évaluée en A et B est donc détenu par l'une des parties sans qu'aucune partie n'ait révélé d'information à l'autre partie sur la donnée qu'elle détient. Sur la figure 3b, dans le cas où le calcul de la fonction F est mis en oeuvre lors d'un procédé d'authentification d'un individu, le résultat F(A,B) peut être 3047373 29 comparé à un seuil prédéterminé lors d'une étape 400. Par exemple, dans le cas où la fonction est une distance de Hamming, le résultat doit être inférieur à un seuil déterminé pour que les données soient considérées comme provenant de la même personne. 5 Si le résultat de la comparaison indique que les données A et B proviennent de la même personne, l'individu est authentifié comme l'individu de référence lors d'une étape 500. Sinon, des mesures d'avertissement peuvent être mises en oeuvre par l'une des parties, par exemples au moyen par exemple de l'affichage d'un message, de la génération d'une alerte sonore, etc. 10 REVENDICATIONS1. Procédé d'exécution d'un calcul cryptographique mis en oeuvre par deux unités de traitement (P1,P2) comprenant chacune des moyens de traitement, et possédant chacune un vecteur (A,B) comprenant un nombre n de composantes indexées, le procédé comprenant l'évaluation sécurisée d'une fonction F obtenue par l'application à n sous-fonctions f, de plusieurs variables d'une opération dite première opération, avec les vecteurs de chaque unité de traitement comme entrées de la fonction, le procédé étant caractérisé en ce qu'il comprend : - la mise en oeuvre d'une série d'étapes (1001) de calcul sécurisé dans lequel une unité de traitement prend un rôle de client et l'autre unité de traitement prend un rôle de serveur, et - la répétition de la série d'étapes (1002) de calcul sécurisé dans laquelle les rôles de client et de serveur sont échangés entre les deux unités de traitement, chaque série d'étapes (100) comprenant : a) génération aléatoire (110), par le serveur, de n premières données de masquage (r,), dans l'ensemble Zm avec m premier, inversibles pour la première opération, et d'une deuxième donnée de masquage (a) dans l'ensemble Zrn, inversible pour une deuxième opération, différente de la première opération, et distributive par rapport à celle-ci, b) pour chaque sous-fonction f' génération (120) par le serveur d'un ensemble d'éléments, chaque élément étant formé par : o un résultat possible de la sous-fonction f, évaluée en la donnée du client et la donnée du serveur, o masqué par une première donnée de masquage (r,), le masquage étant obtenu par application de la première opération entre le résultat et la première donnée de masquage, et o masqué par la deuxième donnée de masquage (a), le masquage étant mis en oeuvre par application entre le résultat masqué par la première donnée de masquage et la deuxième donnée de masquage de la deuxième opération, c) récupération par transfert inconscient (130), par le client, pour chaque composante de son vecteur, d'une donnée intermédiaire correspondant à 3047373 31 l'un des éléments générés par le serveur et indexé par la valeur de ladite composante, d) génération (140), par le serveur, d'une première partie de résultat (R), par : - le masquage de chaque première donnée de masquage (r,) par la 5 deuxième donnée de masquage (a), et - l'application à toutes lesdites premières données masquées de la première opération, et e) génération (150), par le client, d'une deuxième partie de résultat (T), par application à toutes les données intermédiaires de la première opération, 10 ladite deuxième partie de résultat comprenant une évaluation masquée de la fonction F avec les vecteurs des deux unités de traitement comme entrées, - la mise en oeuvre, par les deux unités de traitement, d'un test d'égalité (200) sur les évaluations masquées de la fonction F obtenues à l'issue de chaque série d'étapes, et 15 - si le test d'égalité est satisfait, le calcul (300), par l'une des deux unités de traitement, de la fonction évaluée avec les données des deux unités de traitement F(A,B) à partir des premières et deuxièmes parties de résultat, et - l'utilisation de la fonction évaluée avec les données des deux unités de traitement dans au moins une application parmi le groupe comprenant une 20 application cryptographique, une application d'identification, et une application d'authentification. 2. Procédé selon la revendication 1, dans lequel la mise en oeuvre des deux séries d'étapes est réalisée simultanément. 3. Procédé selon l'une des revendications précédentes, dans lequel l'étape de calcul (300) par l'une des deux unités de traitement de F(A,B) comprend l'obtention par une partie, de la partie de résultat détenue par l'autre unité de traitement, et la déduction de F(A,B) à partir des deux parties de résultat. 4. Procédé selon l'une des revendications précédentes, dans lequel la fonction à évaluer est une fraction de fonctions, et les étapes de mise en oeuvre et de répétition de la série d'étapes sont effectuées une fois pour le numérateur de la fraction, et une fois pour le dénominateur. 25 30 3047373 32 5. Procédé selon l'une des revendications précédentes, dans lequel la première opération est une addition ou une multiplication, et la deuxième opération est respectivement une multiplication ou une mise à la puissance. 5 6. Procédé selon la revendication 5, dans lequel la fonction F est une somme des n sous-fonctions f' et la mise en oeuvre de chaque série d'étapes comprend : - lors de l'étape b), chaque élément est formé par la somme d'un résultat possible de la sous-fonction f, évaluée en la donnée du client et la donnée du 10 serveur et d'une première donnée de masquage, et multipliée par la deuxième donnée de masquage, - lors de l'étape d), la première partie du résultat est générée par le serveur par sommation de toutes les premières données de masquage et multiplication par la deuxième donnée de masquage, et 15 - lors de l'étape e), la deuxième partie du résultat est générée par le client par sommation de toutes les données intermédiaires. 7. Procédé selon l'une des revendications 5 ou 6, dans lequel la fonction à évaluer est l'une parmi le groupe suivant : 20 - distance de Hamming entre les vecteurs des parties, - distance de Hamming normalisée entre les vecteurs des parties, - produit scalaire entre les vecteurs des parties. 8. Procédé selon la revendication 7, dans lequel les vecteurs des unités de 25 traitement sont des données d'identité d'individus, et l'utilisation de la fonction évaluée comprend : - la comparaison (400) de la valeur F(X,Y) à un seuil préétabli en fonction de la nature de la fonction évaluée, et - à partir du résultat de ladite comparaison, la détermination (500) du fait que 30 les données d'identité correspondent ou non à un même individu. 9. Procédé selon la revendication 8, dans lequel les données d'identité d'individus sont des données encodées sur des traits biométriques d'individus. 3047373 33 10. Procédé selon l'une des revendications 7 à 9, dans lequel chaque sous-fonction f, est une fonction de deux variables, les composantes des données détenues par les unités de traitement sont des entiers compris entre 0 et q-1, et : - l'étape b) comprend la génération par le serveur d'un ensemble comprenant 5 les éléments : (a(ri + fi(0, Y), , a(ri + fi(q - 1,Y))) où Y est le vecteur possédé par le serveur, et - la donnée intermédiaire récupérée lors de l'étape c) est : a(ri + fi (xi, Y)) 11. Procédé selon l'une des revendications 1 à 5, dans lequel la fonction à évaluer 10 est un produit des n sous-fonctions f' et la mise en oeuvre de chaque série d'étapes comprend : - lors de l'étape b), chaque élément est formé par le produit d'un résultat possible de la sous-fonction f, évaluée en la donnée du client et la donnée du serveur et d'une première donnée de masquage, et mise à la puissance de 15 la deuxième donnée de masquage, - lors de l'étape d), la première partie du résultat est générée par le serveur par produit de toutes les premières données de masquage et mise à la puissance à la deuxième donnée de masquage, et - lors de l'étape e), la deuxième partie du résultat est générée par le client par 20 produit de toutes les données intermédiaires. 12. Procédé selon la revendication 11, dans lequel chaque sous-fonction f, est une fonction de deux variables, les composantes des données détenues par les unités de traitement sont des entiers compris entre 0 et q-1, et : 25 - l'étape b) comprend la génération par le serveur d'un ensemble comprenant les éléments : ((ri. fi(0,Y))a , , (ri. fi(q - 1,Y))a) où Y est le vecteur possédé par le serveur, et - la donnée intermédiaire récupérée lors de l'étape c) est : (ri. fi(xi,Y))" 3047373 34 13. Produit programme d'ordinateur, comprenant des instructions de code pour l'exécution, par un processeur (10) d'une unité de traitement, d'un procédé comprenant la mise en oeuvre d'une série d'étapes comprenant : - génération aléatoire (110) de n premières données ri dans l'ensemble de Zm 5 avec m premier, et inversibles pour une première opération, et d'une deuxième donnée appartenant à l'ensemble des éléments inversibles de Zm pour une deuxième opération, différente de la première opération et distributive par rapport à celle-ci, - pour chaque i de 1 à n, génération (120) d'un ensemble d'éléments, chaque 10 élément étant formé par : o un résultat possible d'une fonction f, évaluée en une donnée inconnue et une donnée connue, o masqué par une première donnée de masquage (r,), le masquage étant obtenu par l'application de la première opération entre la 15 première donnée et le résultat, et o masqué par la deuxième donnée de masquage (a), le masquage étant mis en oeuvre par application, entre le résultat masqué par la première donnée de masquage et la deuxième donnée de masquage de la deuxième opération, 20 - participation à un protocole de transfert inconscient (130) avec une unité de traitement distincte pour communiquer, pour chaque i de 1 à n, un élément parmi les éléments générés. 14. Procédé d'authentification d'un individu, mis en oeuvre par un système 25 d'authentification comportant une première unité de traitement détenant une donnée d'identité de l'individu, et une deuxième unité de traitement détenant une donnée d'identité d'un individu de référence, le procédé comprenant la mise en oeuvre du procédé de traitement de données selon l'une des revendications 1 à 10 par les unités de traitement à partir des deux 30 données d'identité, la fonction à évaluer étant choisie parmi le groupe comprenant : - distance de Hamming entre les vecteurs des parties, - distance de Hamming normalisée entre les vecteurs des parties, - produit scalaire entre les vecteurs des parties. 3047373 15. Système d'authentification d'un individu, comprenant une première unité de traitement et une deuxième unité de traitement, chaque unité de traitement comprenant un processeur (10) et une interface de communication (12), le système étant caractérisé en ce que la première et la deuxième unité de 5 traitement sont adaptées pour mettre en oeuvre le procédé de traitement de données selon l'une des revendications 1 à 10, la fonction à évaluer étant choisie parmi le groupe comprenant : - distance de Hamming entre les vecteurs des parties, - distance de Hamming normalisée entre les vecteurs des parties, 10 - produit scalaire entre les vecteurs des parties.