Procédé de conversion d'un premier chiffré en un deuxième chiffré

La présente invention concerne le domaine de la cryptographie à clé secrète. Plus précisément, l'invention porte sur un procédé de conversion par une entité de conversion d'un premier chiffré en un deuxième chiffré

L'invention trouve une application intéressante dans des services dits de transchiffrement adaptés pour recevoir un contenu chiffré d'une première entité et pour le transmettre chiffré à l'attention d'une deuxième entité.

En cryptographie symétrique, l'émetteur et le destinataire d'un message partagent la connaissance d'une même clé secrète K. Celle-ci permet à l'émetteur de transformer un message en clair en un cryptogramme, ou message chiffré, et au destinataire de recouvrer le message en clair à partir du message chiffré

Certaines applications nécessitent qu'une entité intermédiaire entre l'émetteur et le destinataire, convertisse un premier chiffré Cl d'un message en clair M, obtenu par une première entité Ul au moyen d'une première clé secrète Kl, en un deuxième chiffré C2 du même message en clair M au moyen d'une deuxième clé secrète K2 pour une deuxième entité U2. La deuxième entité U2 qui détient la deuxième clé secrète K2 est capable d'obtenir le message en clair par déchiffrement du deuxième chiffré C2. Un exemple d'un tel service consiste en un service de stockage distant de contenus. La première entité transmet à un serveur distant de stockage des données chiffrées au moyen de sa clé secrète Kl. Par la suite la première entité Ul souhaite donner accès à ses données à une deuxième entité U2 sans lui révéler sa clé secrète. Une façon évidente de procéder consiste à transmettre à l'entité intermédiaire, en l'espèce le serveur distant les clés secrètes Kl et K2 des deux entités afin que l'entité intermédiaire déchiffre au moyen de la clé Kl le premier chiffré C 1 pour obtenir le message en clair M, puis chiffre au moyen de la clé secrète K2 de la deuxième entité le message M obtenu à l'attention de la deuxième entité U2. Cependant, en procédant ainsi, l'entité intermédiaire prend connaissance du message en clair M. En outre, l'entité intermédiaire détient les clés secrètes respectives des entités. On comprend cependant que des utilisateurs désireux de mettre en œuvre un tel service puissent ne pas avoir confiance en l'entité intermédiaire Ainsi, on comprend que des utilisateurs souhaitent, pour des raisons de confiance avoir la garantie que l'entité intermédiaire n'accède pas au message en clair et que d'autre part, ils ne souhaitent pas, pour des raisons de sécunté transmettre leur clé secrète à l'entité intermédiaire.

La façon évidente de procéder peut donc ne pas convenir Or il n'existe pas de procédé permettant de rechiffrer pour un autre utilisateur dans le cadre de la cryptographie à clé secrète Afin de remédier aux problèmes identifiés ci-dessus, l'invention propose un procédé de conversion par une entité de conversion d'un premier chiffre en un deuxième chiffre, le premier chiffré correspondant au résultat d'un chiffrement probabiliste symétrique d'un élément de message en clair au moyen d'une première matrice secrète paramétrée par un vecteur aléatoire, le deuxième chiffré correspondant au résultat d'un chiffrement probabiliste symétrique de l'élément de message en clair au moyen d'une deuxième matrice secrète paramétrée par le vecteur aléatoire, caractérisé par le fait que le procédé comprend une étape de calcul du deuxième chiffré par chiffrement du premier chiffré au moyen d'une matrice secrète de conversion fonction de la première et deuxième matrices secrètes, et paramétrée par le vecteur aléatoire.

D'emblée, on notera que, par définition, un "élément de message" comprend tout ou partie d'un message.

Avec le procédé de l'invention, il devient possible dans un contexte de cryptographie symétrique de convertir un premier chiffré d'un message en clair obtenu au moyen d'une première clé secrète en un deuxième chiffré du même message en clair adapté pour être déchiffré au moyen d'une deuxième clé secrète. Cette conversion est réalisée sans que l'entité en charge de la conversion ne puisse prendre connaissance du message en clair associé correspondant à ces deux chiffrés. En effet, l'entité de conversion traite le premier chiffré qui résulte d'un chiffrement probabiliste symétrique au moyen d'une première matrice secrète, mais elle ne dispose pas de la première matrice secrète qui lui permettrait de déchiffrer le premier chiffré pour obtenir le message en clair. De même, l'entité de conversion calcule le deuxième chiffré, destiné à être déchiffré conformément à un déchiffrement probabiliste symétrique au moyen d'une deuxième matrice secrète, mais elle ne dispose pas de la deuxième matrice secrète qui lui permettrait de déchiffrer le deuxième chiffré pour obtenir le message en clair. En effet, l'entité de conversion utilise pour effectuer la conversion du premier chiffré en le deuxième chiffré une matrice de conversion qui ne fournit aucune information sur les matrices secrètes. Ainsi, il n'est pas possible à partir de la matrice de conversion de trouver la première ou la deuxième matrices secrètes.

On remarque en outre que le procédé de conversion est symétrique en ce sens que l'entité de conversion est également adaptée pour convertir le deuxième chiffré associé obtenu par chiffrement symétrique probabiliste au moyen de la deuxième matrice secrète en le premier chiffré associé à la première matrice secrète en utilisant la même matrice de conversion que pour une conversion du premier chiffré en le deuxième chiffré.

Dans un mode de réalisation de l'invention, le procédé comprend une étape de :

- réception du premier chiffré couplé au vecteur aléatoire en provenance d'une première entité,

- envoi du deuxième chiffré couplé au vecteur aléatoire à destination d'une deuxième entité. Ce mode de réalisation correspond à une utilisation du procédé de conversion par deux entités pour transmettre des données chiffrées de la première entité à la deuxième entité. Des entités, par exemple des utilisateurs qui utiliseraient cette entité de conversion dans le cadre d'un service d'échange de données chiffrées, seraient ainsi rassurées sur la sécurité mise en œuvre par le service, et confiantes quant au caractère confidentiel des données transmises

De façon avantageuse, la matπce secrète de conversion est calculée par une opération de OU EXCLUSIF entre la première et la deuxième matrices secrètes.

La matrice de conversion, bien que calculée à partir des matrices secrètes des première et deuxième entités ne fournit pas d'information qui permettrait de retrouver la première ou la deuxième matπce secrète. Ainsi, il n'est pas possible à partir de la matπce de conversion d'obtenir le message en clair qui est associé au premier et au deuxième chiffré.

L'invention est décπte ici avec une seule matπce de conversion calculée à partir de deux matπces secrètes, chaque matπce étant associée à une entité On comprend que l'entité de conversion peut mettre en œuvre le procédé de conversion pour n entités, avec n > 2. Les entités sont notées 1, 2, . , n. Dans ce cas, l'entité de conversion n'a besoin de ne stocker dans sa mémoire que (n - 1) matπces de conversion II est alors calculé (n-1) matπces de conversion M _u ,M _2i ,M _u ,...,M _n _ _hι qm sont transmises à l'entité de conversion On remarque en effet qu'il n'est pas nécessaire de calculer toutes les matrices de conversion propres à tous les couples d'entités (î, j). En effet, il est possible d'obtenir une matπce de conversion pour un couple (î, j) avec j>i+l , à partir des matrices calculées. En effet, on remarque que M — M _I(ι+X) θ ... θ M _{(ι+(j M))y} .

Avantageusement, la matπce de conversion est une matnce de Toeplitz II est connu qu'avec une matπce de Toeplitz, les coefficients sur une diagonale descendant de gauche à droite sont les mêmes. Ainsi, l'ensemble des coefficients de la matπce de conversion Mi ₂ peuvent se déduire des seuls coefficients de la première ligne et de la première colonne de la matrice. Aussi, il suffit de stocker les seuls coefficients de la première ligne et de la première colonne de la matπce de conversion pour disposer de l'ensemble des coefficients de la matπce de conversion. Cela est intéressant lorsque l'entité de conversion dispose de peu de mémoire de stockage

Selon un mode de réalisation de l'invention, la matπce de conversion est obtenue par l'entité de conversion auprès d'une entité de confiance qui calcule la matrice de conversion au moyen des première et deuxième matπces secrètes transmises respectivement par la première et la deuxième entité

Dans ce mode de réalisation, la matπce de conversion est calculée par une entité de confiance à partir des première et deuxième matπces secrètes que lui ont transmis les première et deuxième entités La matπce de conversion, une fois calculée, est mise à disposition de l'entité de conversion On constate que l'opération délicate en termes de sécurité qui consiste à manipuler les première et deuxième matπces secrètes pour calculer la matπce de conversion est effectuée avec une sécurité maximale par une entité dediee en laquelle les premières et deuxièmes entités ont confiance L'mvention concerne également un procédé de transmission d'un élément de message en clair sous forme chiffrée entre une première et une deuxième entité, comprenant une étape de :

- chiffrement par la première entité au moyen d'un chiffrement probabihste symétπque du message en clair au moyen d'une première matrice secrète, paramétrée par un vecteur aléatoire, afin d'obtenir un premier chiffré,

- envoi du premier chiffré couplé au vecteur aléatoire à une entité de conversion,

- conversion par l'entité de conversion du premier chiffré en un deuxième chiffré selon le procédé de conversion,

- envoi par l'entité de conversion à la deuxième entité du deuxième chiffré couplé au vecteur aléatoire,

- réception par la deuxième entité du deuxième chiffré couplé au vecteur aléatoire,

- déchiffrement par la deuxième entité du deuxième chiffré au moyen d'une deuxième matrice secrète par déchiffrement probabihste symétπque.

Le procédé correspond ici à un procédé de transmission de bout en bout qui intègre une conversion d'un premier chiffré en un deuxième chiffré.

L'mvention concerne aussi une entité de conversion adaptée pour convertir un premier chiffré en un deuxième chiffré, le premier chiffré correspondant au résultat d'un chiffrement probabihste symétπque d'un élément de message en clair au moyen d'une première matπce secrète paramétrée par un vecteur aléatoire, le deuxième chiffré correspondant au résultat d'un chiffrement probabihste symétrique de l'élément de message en clair au moyen d'une deuxième matπce secrète paramétrée par le vecteur aléatoire, l'entité de conversion comprenant :

- des moyens de calcul du deuxième chiffré, adaptés pour calculer le deuxième chiffré par chiffrement du premier chiffré reçu au moyen d'une matπce secrète de conversion fonction de la première et deuxième matπces secrètes, et paramétrée par le vecteur aléatoire.

Dans un mode de réalisation de l'mvention, l'entité de conversion comprend en outre ^•

- des moyens de réception adaptés pour recevoir le premier chiffré couplé à un vecteur aléatoire,

- des moyens d'envoi adaptés pour envoyer le deuxième chiffré couplé au vecteur aléatoire. L'invention concerne également un système de conversion adapté pour convertir un premier chiffre en un deuxième chiffré, le premier chiffré correspondant au résultat d'un chiffrement probabihste symétπque d'un élément de message en clair au moyen d'une première matπce secrète paramétrée par un vecteur aléatoire, le deuxième chiffré correspondant au résultat d'un chiffrement probabihste symétπque de l'élément de message en clair au moyen d'une deuxième matπce secrète paramétrée par le vecteur aléatoire, le système comprenant

- une entité de conversion selon l'invention,

- une entité de confiance adaptée pour calculer la matnce de conversion à partir des matπces secrètes L'invention concerne aussi un programme d'ordinateur destiné à être installé dans une mémoire d'une entité intermédiaire, comprenant des instructions pour la mise en œuvre des étapes du procédé de conversion selon l'invention, lorsque le programme est exécuté par un processeur.

L'invention porte également sur un support de données sur lequel est enregistré le programme d'ordinateur selon l'invention.

D'autres caractéristiques et avantages de la présente invention seront mieux compris de la descπption et des dessins annexés parmi lesquels ^•

- les figures la et Ib représentent un organigramme des étapes d'un procédé de chiffrement symétπque probabiliste, respectivement un organigramme des étapes d'un procédé de déchiffrement symétrique selon l'état antérieur de la technique ;

- la figure 2 représente un organigramme des étapes du procédé de conversion d'un premier chiffré en un deuxième chiffré selon un mode de réalisation particulier décπt ;

- la figure 3 représente un schéma bloc fonctionnel d'une forme particulière d'une entité de conversion adaptée pour mettre en œuvre le procédé de la figure 2.

Le procédé de conversion selon l'invention repose sur un chiffrement/déchiffrement probabiliste symétrique tel que décπt dans [GRS08] (H. Gilbert, M. Robshaw, and Y. Seuπn. How to Encrypt with the LPN Problem? In ICALP'08, Lectures Notes m Computer Science, volume 5126, p.679-690, Spπnger Verlag, 2008). Un chiffrement est dit "probabiliste" lorsqu'il fait intervenir un aléa dans le chiffrement. Ainsi, lorsque l'on chiffre deux fois le même message clair, on obtient deux messages chiffrés différents avec une forte probabilité. Le chiffrement probabiliste utilisé dans le cadre de la présente invention repose sur la combinaison d'un encodage par code correcteur d'erreurs et de l'ajout d'un bruit. Cette combinaison a pour effet de rendre plus difficile le déchiffrement du chiffré par un adversaire tout en étant adapté pour être naturellement supprimé par le décodage du code correcteur d'erreurs Avec ce chiffrement, il est possible de prouver la sécunté par une approche réductionmste consistant à traduire la sécuπté en une hypothèse sur la difficulté de résoudre un problème connu. En d'autres termes, il est possible de prouver que, pour casser la secuπté de cette méthode de chiffrement, un attaquant doit être capable de résoudre un problème connu, présumé difficile Dans le cadre du présent chiffrement, le problème bien défini et bien connu est le problème "LPN" (pour "Learnmg Paπty with Noise")

Les étapes des procédés de chiffrement et de déchiffrement selon un mode particulier de réalisation vont être décπtes en relation avec les figures la et Ib Selon l'état antéπeur de la technique, le procédé de chiffrement probabiliste symétπque utilise une clé secrète partagée par une première et une deuxième entité, l'une de chiffrement, et l'autre de déchiffrement, référencées respectivement 1 et 2. L'entité de déchiffrement 2 est apte à mettre en œuvre un procédé de déchiffrement, ou de restitution d'un message en clair x à partir du message chiffré fourni par la première entité 1 La clé secrète peut être représentée sous forme d'une matrice M à k lignes et n colonnes, avec 1 < k et 1 < n

L'entité de chiffrement 1 et l'entité de déchiffrement 2 sont ici respectivement intégrées dans un équipement de communication émetteur et dans un équipement de communication récepteur, non représentés, aptes à communiquer entre eux, par exemple par voie radio Par exemple l'équipement émetteur peut être une étiquette RFID et l'équipement récepteur un lecteur associé

Le chiffrement est dit probabihste du fait qu'il utilise un aléa pour calculer un message chiffré à partir d'un message clair

Le message clair x est représenté par un vecteur binaire à R bits.

La procédé comprend une étape El d'encodage du message clair x à l'aide d'un code correcteur d'erreur, noté C

Un code correcteur d'erreurs est une technique bien connue de l'homme du métier, basé sur la redondance Elle a usuellement pour vocation de corriger des erreurs de transmission d'un message a travers un canal de communication peu fiable Des informations du message transmis à travers ce canal πsquent en effet d'être altérées. Le code correcteur d'erreurs a pour rôle d'ajouter des informations redondantes dans le message avant sa transmission Ces informations redondantes permettent de corriger les informations du message tel que reçu, qui ont été altérées lors de la transmission

En l'espèce, le code correcteur d'erreurs est un code linéaire en blocs, noté C Ce code correcteur C est de longueur n, de dimension r et de capacité de correction t Autrement dit, le code correcteur C est une fonction de l'espace binaire de dimension r {θ,l}' dans l'espace binaire de dimension n |θ,lj" Cette fonction est adaptée pour transformer un message de r bits en un mot de code de n bits, avec n > r, par ajout de bits de redondance En outre, le code correcteur C est adapté pour garantir que, si un nombre d'erreurs inférieur à la capacité de correction t est ajouté au mot de code, le décodage permet de restituer le message d'origine

Dans l'exemple particulier décrit ici, on suppose que le nombre de bits R du message x est égal à la dimension r du code correcteur C

L'étape El d'encodage du message x fournit donc un mot de code représente par un vecteur a n bits note C(x)

Le procédé comprend une étape E2 de génération d'un aléa a. Dans l'exemple de cette descπption, l'alea a est un vecteur binaire de k bits produit par une source pseudo-aleatoire de bits S

L'étape E2 est suivie par une étape E3 de calcul du produit entre le vecteur aléatoire a, sous forme de vecteur ligne, et la matrice M représentant la cle secrète Le résultat du produit a - M est représenté par un vecteur a n bits Une fois les étapes El à E3 réalisées, le procédé met en œuvre une étape de calcul E4 au cours de laquelle le résultat du produit a• M est ajouté au mot de code C(x). Autrement dit, l'étape E4 réalise l'opération C(x) θ a - M . Le rôle de l'étape E4 est de chiffrer le mot de code C(x).

Le procédé comprend également une étape E5 de génération d'un vecteur de bruit binaire ε à n bits à partir d'une source de bruit bernouillien B. Celle-ci est adaptée pour produire des bits indépendants valant 1 avec une probabilité η et des bits indépendants valant 0 avec une probabilité

1 - η , avec η e o, .-— . En outre, la source de bruit B est adaptée pour que la probabilité δ pour le poids de Hamming du vecteur de bruit ε d'être supérieur à la capacité de correction t du code correcteur soit très faible, inférieur à un seuil Σ prédéfini. A titre d'exemple, ce seuil peut être égal à 10 ^~ . Suivant le cadre d'utilisation, il pourrait être inférieur à cette valeur. Par définition, le poids de Hamming d'un vecteur binaire est le nombre de bits différents de 0, autrement dit valant 1 , de ce vecteur. Ainsi, pour la plupart des vecteurs de bruit ε générés par la source B, le poids de Hamming du vecteur ε , noté Hwt( ε ) est inférieur ou égal à la capacité de correction t du code correcteur C. Dans l'exemple particulier décrit ici, pour satisfaire la condition relative à la probabilité δ , les paramètres t, η et n vérifient la relation suivante : t > η * n .

Une fois les étapes E4 et E5 réalisées, le procédé met en œuvre une étape de calcul E6, dans laquelle le vecteur de bruit ε est ajouté au résultat de l'opération E4, C(x) θ a - M . Le résultat de cette opération E6 est un vecteur à n bits, noté y, correspondant au message x chiffré. Celui-ci est en définitive le mot de code C(x), c'est-à-dire le message x encodé, chiffré et bruité.

Enfin, le procédé comprend une étape E7 d'envoi de la paire (a, y), c'est-à-dire

(a, C(x) θ a• M ® ε ), h partir de l'équipement de communication émetteur vers l'équipement de communication récepteur.

La paire (a, y) circule à travers un canal de communication ici radio jusqu'à réception par l'équipement récepteur, lors d'une étape E8. représentée sur la figure Ib. Pour rappel, l'équipement récepteur intègre une entité de déchiffrement apte à déchiffrer le message chiffré y reçu afin de retrouver le message clair x.

Dans un cas où le message en clair x est de taille R bits avec R > r, alors le message en clair est découpé en blocs de r bits, avec éventuellement ajout de valeurs prédéterminées pour compléter un bloc à r bits (on parle habituellement de padding) si la valeur R n'est pas un multiple de la valeur r. Le procédé de chiffrement décrit est alors appliqué à chaque bloc.

Sur la figure Ib, on a représenté les différentes étapes du procédé de restitution, ou de déchiffrement, pour retrouver le message en clair x à partir de la paire (a, y), mises en œuvre par l'entité de déchiffrement 2. Pour rappel, l'entité de déchiffrement 2 a la connaissance de la clé secrète représentée par la matnce secrète M

Le procédé de restitution comprend d'abord une phase de calcul comprenant deux étapes de calcul E9 et ElO

Lors de la première étape de calcul E9, le vecteur aléatoire a est extrait de la paire (a, y) reçue et le produit a - M est calculé, a étant représenté sous la forme d'un vecteur ligne de k bits

Lors de l'étape de calcul ElO, le vecteur à n bits résultant du produit a - M est ajouté au vecteur y reçu, autrement dit l'opération de calcul y θ a - M est réalisée En binaire, cette opération correspond à soustraire le résultat du produit a - M du vecteur y reçu

On notera que y étant égal au mot de code chiffré et bruité, à savoir C(x) θ a• M θ ε , le résultat de l'étape de calcul ElO correspond au mot de code uniquement bruité, a savoir

Le procédé comprend ensuite une phase de décodage EI l, lors de laquelle le résultat de l'étape ElO est décodé à l'aide du code correcteur d'erreurs utilisé lors du chiffrement Le poids de Hamming du vecteur de bruit ε étant inférieur ou égal à la capacité de correction t du code correcteur d'erreurs, le décodage fournit directement le message en clair x

A titre d'exemple, nous allons fournir maintenant quelques exemples de réalisation de ce procédé de chiffrement avec des paramètres concrets. On rappelle que la sécunté du système de chiffrement dépend de la difficulté de résolution du problème LPN Or, cette difficulté repose sur les paramètres k et η , correspondant au nombre de bits du vecteur aléatoire a et a la probabilité pour un bit du vecteur de bruit ε de valoir 1 respectivement II convient donc de choisir des valeurs convenables pour ces paramètres, permettant de garantir une bonne sécunté du système Deux exemples de valeurs convenables pour ces paramètres k et η sont les suivants

- k = 512, η = 0 125

- k = 768, η = 0 05

On notera par ailleurs que si le message en clair x est de taille r bits, la taille totale du message chiffré transmis, correspondant à la paire (a, y) est de (n+k) bits, puisque le vecteur aléatoire a comprend k bits et le chiffre y n bits On constate donc que le chiffrement s'accompagne d'une certaine expansion du message On note σ - le facteur d'expansion Afin de limiter r

cette expansion, il convient donc, à k fixé, de prendre une valeur de r la plus grande possible et une valeur de n la plus faible possible On rappelle en outre que la capacité de correction t du code correcteur et la longueur n du code correcteur doivent véπfier la condition suivante t > η * n afin de garantir un déchiffrement correct du message dans la plupart des cas On note [n, r, d] un tπplet de paramètres d'un code correcteur d'erreurs Ces paramètres n, r et d correspondent respectivement à la longueur, la dimension et la distance minimale du code. La distance minimale d du code est fonction de la capacité de correction t, par la relation suivante ^•

[ ₌ d - \

2

On va maintenant donner quatre exemples de réalisation avec des paramètres concrets pour l'encodage et le chiffrement proprement dits .

- pour les paramètres k = 512, η = 0 125, on peut utiliser .

un code linéaire paramétré par le tπplet [80, 27, 21] capable de corriger 10 erreurs, le paramètre d'expansion σ valant alors 21 ,

- un code hnaire paramétré par le tπplet [160, 42, 42], capable de corπger 20 erreurs, le facteur d'expansion σ valant alors 16.

- pour les paramètres k = 768, η = 0.05, on peut utiliser :

un code hnaire paramétré par le tπplet [80, 53, 9] capable de corπger 4 erreurs, le paramètre d'expansion σ valant alors 16 ;

- un code linéaire paramétré par le tπplet [160, 99, 17] capable de corπger 8 erreurs, le facteur d'expansion σ valant alors 8,8

Pour optimiser le facteur d'expansion σ , il est donc souhaitable d'utiliser une taille k grande pour le vecteur aléatoire, une probabilité η pour chaque bit du vecteur de bruit ε de valoir

1 faible et un code de grande longueur n et de grande dimension r. On peut également diminuer le facteur d'expansion σ en augmentant la taille de la matrice M. En effet, en prenant une matπce à k lignes et N * n colonnes, avec N entier stπctement supéπeur à 2, on peut chiffrer N blocs de r bits en même temps, avec le même vecteur aléatoire de k bits. Le facteur d'expansion n'est alors que de

N * n + k

σ≈

N * r Le procédé de conversion selon un mode de réalisation de l'invention va maintenant être décrit en relation avec la figure 2

Une entité de conversion référencée 3 est apte à mettre en œuvre le procédé de conversion selon l'invention. L'entité 3 communique avec au moins une première entité, référencée 1 et une deuxième entité, référencée 2 L'entité de conversion 3 communique avec les entités 1 et 2 par exemple par l'intermédiaire d'un réseau. La première entité 1 est comparable à une entité de chiffrement adaptée pour mettre en œuvre le procédé de chiffrement probabiliste symétπque décπt en relation avec la figure 1 a Elle possède une clé secrète qui peut être représentée sous forme d'une matπce Mi de k lignes et n colonnes, avec 1≤ k et 1 < n La deuxième entité 2 est adaptée pour mettre en œuvre le procédé de déchiffrement décrit en relation avec la figure Ib La deuxième entité 2 possède une deuxième clé secrète qui peut être représentée sous forme d'une deuxième matnce M ₂ de k lignes et n colonnes. L'invention décrite ici a un intérêt dans un cas où les matπces secrètes Mi et M ₂ des première et deuxième entités 1, 2 sont différentes, c'est-à-dire dans un cas où les entités 1 et 2 ne partagent pas une matrice secrète. Dans un cas où la première et la deuxième entités partagent la connaissance d'une même clé secrète représentée par une matnce M, alors les procédés de chiffrement et déchiffrement décπts en relation avec les figures la et Ib sont mis en œuvre par la première entité en tant qu'entité de chiffrement, et par la deuxième entité en tant qu'entité de déchiffrement Les deux entités utilisent alors la même matnce secrète.

On suppose que l'on veut procéder à une conversion d'un message en clair x de r bits chiffré par la première entité 1 par chiffrement probabiliste symétrique au moyen de sa matnce secrète Mi en un deuxième message chiffré à l'attention de la deuxième entité 2. En d'autres termes, on veut que le deuxième message chiffré puisse être déchiffré par la deuxième entité 2 au moyen de sa matnce secrète M ₂ et que le déchiffrement du deuxième message chiffré permette à la deuxième entité 2 d'obtenir le message en clair x.

Dans une étape préalable El 9 de calcul du premier chiffré, la première entité 1 procède au chiffrement du message en clair x de r bits, conformément au procédé de chiffrement probabiliste symétnque décnt en relation avec la figure 1 a. A cette fin, l'entité 1 encode le message x au moyen d'un code correcteur d'erreurs C de longueur m, de dimension r et de capacité de correction t. On rappelle que si un nombre d'erreurs mféneur à t est ajouté a C(x), la procédure de décodage retrouve le message en clair x. L'entité 1 obtient également un vecteur aléatoire a de k bits d'une source S non représentée sur la figure 2, et un vecteur de bruit ε de n bits produite par une source B non représentée sur la figure 2 L'entité 1 calcule alors le premier chiffré yi par chiffrement du mot de code C(x) au moyen de la matnce secrète Mi paramétrée par le vecteur aléatoire a, et en ajoutant le bruit ε à la valeur obtenue. En d'autres termes, la première entité calcule y _x = C(x) θ a - M^ Φ ε

Dans une étape E20 d'envoi du premier chiffré, la première entité 1 envoie à l'entité de conversion 3 le premier chiffré yi, couplé au vecteur aléatoire a.

Dans une étape de réception E21 , l'entité de conversion 3 reçoit de la première entité 1 le premier message chiffré couplé au vecteur aléatoire (y _ls a)

Dans une étape E22 de calcul du deuxième chiffré, l'entité de conversion 3 calcule un deuxième chiffré y ₂ destiné à être déchiffré par la deuxième entité 2 au moyen de sa matnce secrète M ₂ L'entité de conversion 3 extrait le vecteur aléatoire a de la paire reçue. Le deuxième chiffré y ₂ est calculé en ajoutant au premier chiffré yj le produit entre le vecteur aléatoire a, sous forme de vecteur ligne de k bits, avec une matnce de conversion M] ₂ représentant une clé secrète propre à l'entité de conversion 3 En d'autres termes, y _y — y _} Θ a - M _n Le rôle de cette étape E21 est de chiffrer le premier chiffré yl On parle habituellement, pour cette opération consistant à chiffrer une valeur déjà chiffrée de transchiffrement. La matπce de conversion Mi ₂ est mémoπsée par l'entité de conversion 3 dans une mémoire non représentée sur la figure 2. La matrice de conversion M) ₂ a été préalablement calculée par exemple par une entité de confiance non représentée sur la figure 2 à laquelle les première et deuxième entités ont transmis leur clé secrète respective. La matπce de conversion M ₁₂ est calculée par l'entité de confiance en ajoutant la matπce M, de la première entité 1 à la matπce M ₂ de la deuxième entité 2. Ainsi, M ₁₂ = M ₁ Θ M ₂ , où ® représente une addition bit à bit, ou une opération de OU EXCLUSIF

Dans une étape E23 d'envoi, l'entité de conversion 3 envoie à la deuxième entité 2 le deuxième chiffré couplé au vecteur aléatoire a (y ₂ , a).

Ainsi, la deuxième entité 2 reçoit dans une étape E24 de réception la paire (y ₂ , a), où le deuxième chiffré y ₂ correspond au chiffré de yi au moyen de la matπce de conversion paramétrée par le vecteur aléatoire a. En d'autres termes, yi = y\ ® a - M _n . Or, le premier chiffré yi a été obtenu par chiffrement probabiliste symétπque du message en clair x au moyen de la première matnce secrète Mi paramétrée par le vecteur aléatoire a. Ainsi, y\ = C(x) Φ a.M _λ θ ε . Sachant en outre que la matnce de conversion M ₁₂ a été obtenue à partir des première et deuxième matnces secrètes M) et M ₂ par une opération de OU EXCLUSIF, alors on véπfie que :

y ₂ = y _x θ a• M ₁₂ = C(x) Φ a• Af , θ s θ a.M _{ ® a - M ₂ = C(x) ® a - M ₂ ® ε , si bien que y ₂ correspond bien au chiffrement probabiliste symétπque du message clair x au moyen de la deuxième matπce secrète M ₂ paramétrée par le vecteur aléatoire a La deuxième entité 2 est donc apte à déchiffrer le deuxième chiffré y ₂ au moyen de sa matπce secrète M ₂ conformément au procédé de déchiffrement décπt en relation avec la figure Ib, et à obtenir le message en clair x

Dans une étape E25 de déchiffrement, la deuxième entité 2 extrait le vecteur aléatoire a de la paire reçue, puis ajoute au deuxième chiffré y ₂ le résultat du produit entre le vecteur aléatoire a et la deuxième matπce secrète M ₂ . En binaire, cette opération correspond à soustraire le résultat du produit a - M ₂ du vecteur y ₂ reçu On notera que y ₂ étant égal au mot de code chiffré et bruité, à savoir C(x) θ a - M ₂ θ ε , le résultat de cette opération correspond au mot de code uniquement bruité, à savoir C(x) θ ε Le résultat obtenu est ensuite décodé à l'aide du code correcteur d'erreurs C utilisé par l'entité 1 lors de l'étape El 9 de chiffrement Le poids de Hamming du vecteur de bruit ε étant mféπeur ou égal à la capacité de correction t du code correcteur d'erreurs, le décodage fournit directement le message en clair x.

Dans un autre mode de réalisation de l'invention, la matπce de conversion Mj ₂ est calculée par la première entité 1 , ou la deuxième entité 2 Par exemple, les première et deuxième entités 1 , 2 se mettent d'accord pour que l'entité 1 calcule la matrice de conversion M _]2 à partir de la première matrice secrète Mi qu'elle détient et de la deuxième matrice secrète M ₂ que lui transmet la deuxième entité 2.

Le procédé de conversion est décrit ici avec une entité de conversion 3 et deux entités que l'on qualifie de terminales : une première entité 1 qui chiffre un message en clair x et une deuxième entité 2 qui déchiffre le deuxième chiffré y ₂ calculé par l'entité de conversion 3 pour obtenir le message en clair x. Le procédé peut bien sûr être mis en œuvre pour n entités terminales, avec n > 2. Dans ce cas, soit n entités notées 1, 2, ..., n. Il est alors calculé (n-1) matrices de conversion M ₁₂ ,M ₂₃ ,M ₃₄ ,...,M _;ι _ _|/1 qui sont transmises à l'entité de conversion 3. On remarque en effet qu'il n'est pas nécessaire de calculer toutes les matrices de conversion propres à tous les couples d'entités (i, j). D'une part, on note le caractère symétrique des matrices de conversion. En effet, pour une paire d'entités (i, j), la matrice de conversion associée M _u est égale à la matrice de conversion M _j1 associée à la paire d'entités (j, i). D'autre part, il est possible d'obtenir une matrice de conversion pour un couple (i, j) avec j>i+l, à partir des matrices calculées. En effet, on remarque que M _tJ = M, ₍ , ₊₁₎ Θ ... Θ M _MH))/ . Par exemple, M ₁₃ = M ₁₂ θ M ₂₃ .

L'entité de conversion 3 va maintenant être décrite en relation avec la figure 3.

L'entité de conversion 3 comprend une mémoire 31 de stockage d'une clé secrète de conversion sous la forme d'une matrice secrète M ₎₂ , un module de calcul 32 d'un deuxième chiffré à partir d'un premier chiffré. Le module de calcul 32 accède à la mémoire 31.

L'entité de conversion comprend en outre :

- une unité de traitement 33, ou "CPU" (de l'anglais "Control Processing Unit"),

- une mémoire volatile 34 ou "RAM" (pour "Random Access memory") utilisée pour charger des instructions de code, les exécuter, stocker des variables, etc.

En fonctionnement, un premier chiffré yl (non représenté sur le figure 3) est fourni en entrée du module de calcul 32 qui produit en sortie un deuxième chiffré y2 (non représenté sur la figure 3).

La mémoire 31 est destinée à stocker la matrice secrète M ₁₂ utilisée pour calculer le deuxième chiffré y ₂ à partir du premier chiffré yi. La matrice secrète M ₎₂ , est calculée au préalable à partir des matrices secrètes M| et M ₂ des entités. Les matrices M ₁ et M ₂ sont par exemple des matrices de Toeplitz. Par définition, il s'agit de matrices dont les coefficients sur une diagonale descendant de gauche à droite sont les mêmes. Ainsi, la matrice de conversion M] ₂ obtenue à partir des deux matrices secrètes des entités par un OU EXCLUSIF entre ces deux matrices est également une matrice de Toeplitz. Ainsi, l'ensemble des coefficients de la matrice de conversion M _i2 peuvent se déduire des seuls coefficients de la première ligne et de la première colonne de la matrice. Aussi, il suffit de stocker les seuls coefficients de la première ligne et de la première colonne de la matrice de conversion pour disposer de l'ensemble des coefficients de la matrice de conversion. La mémoire 31 peut donc ne stocker que les coefficients de la première ligne et les coefficients de la première colonne de la matrice de conversion Mi ₂ L'utilisation d'une matπce de Toeplitz permet de limiter la capacité de stockage nécessaire pour stocker les coefficients de la matπce de conversion Mi ₂

Le module de calcul 32 est adapté pour

- calculer le produit du vecteur aléatoire a pπs sous la forme d'un vecteur ligne de k bits, avec la matπce secrète Mi ₂ , soit le produit a M _n ,

- ajouter le premier chiffré yi reçu en entrée du module au résultat du produit a• M ₁₂

Le module de calcul fournit donc en sortie le chiffré de yι au moyen de la matnce de conversion Mi ₂ , soit y _x ® a - M _n

Les différents modules communiquent grâce à un bus de communication

Le module de calcul 32 met en œuvre l'étape E22 de calcul du deuxième chiffré

Dans un mode particulier de réalisation de l'invention, l'entité de conversion 3 comprend également

- un module 35 de réception (en pointillés sur la figure 3), adapté pour recevoir d'une première entité le premier chiffré V ₁ ,

- un module 36 d'émission (en pointillés sur la figure 3), adapté pour envoyer à une deuxième entité le deuxième chiffré y ₂ obtenu en sortie du module de calcul 32

Dans cet exemple de réalisation le module 35 de réception est connecté en entrée au module de calcul 32, lequel est connecté en sortie au module 36 d'émission.

Le module 35 de réception met en œuvre l'étape E21 de réception

Le module 36 d'émission met en œuvre l'étape E23 d'émission

Dans un exemple de réalisation, dans lequel l'entité de conversion 3 reçoit la matπce de conversion M ₁₂ , le module 35 de réception est également adapté pour recevoir d'une entité tiers la matπce de conversion Mj ₂ et la mémoπser dans la mémoire 31

Les modules 32, 34 et 35 sont de préférence de modules logiciels comprenant des instructions logicielles pour faire exécuter les étapes du procède selon l'invention

Ils peuvent être stockés sur un même ordinateur d'un reseau ou sur des ordinateurs différents qui assurent les fonctions de l'entité de conversion

L'invention concerne donc aussi

- des programmes d'ordinateur comportant des instructions pour la mise en œuvre du procédé de conversion, lorsque ces programmes sont exécutés par un processeur ,

- un support d'enregistrement lisible par un ordinateur sur lequel est enregistre le programme d'ordinateur decπt ci-dessus

Les modules logiciels peuvent être stockes dans, ou transmis par un support de données

Celui-ci peut être un support matenel de stockage, par exemple un CD-ROM, une disquette magnétique ou un disque dur, ou bien un support de transmission tel qu'un signal, ou un réseau de télécommunication.