Cryptage déterministe

Un schéma de chiffrement déterministe (par opposition à un schéma de chiffrement probabiliste ) est un système de chiffrement qui produit toujours le même texte chiffré pour un texte en clair et une clé donnés , même après des exécutions séparées de l'algorithme de chiffrement. Les exemples d'algorithmes de chiffrement déterministes incluent le système de chiffrement RSA (sans remplissage de chiffrement) et de nombreux chiffrements par blocs lorsqu'ils sont utilisés en mode ECB ou avec un vecteur d'initialisation constant .

Le chiffrement déterministe peut divulguer des informations à un espion, qui peut reconnaître des textes chiffrés connus. Par exemple, lorsqu'un adversaire apprend qu'un texte chiffré donné correspond à un message intéressant, il peut en apprendre quelque chose à chaque fois que ce texte chiffré est transmis. Pour obtenir des informations sur la signification de divers textes chiffrés, un adversaire peut effectuer une analyse statistique des messages transmis sur un canal chiffré ou tenter de corréler les textes chiffrés avec les actions observées (par exemple, en notant qu'un texte chiffré donné est toujours reçu immédiatement avant une plongée sous-marine). Ce problème est particulièrement grave dans le cas de la cryptographie à clé publique , où n'importe quelle partie peut chiffrer des messages choisis à l'aide d'une clé de chiffrement publique. Dans ce cas, l'adversaire peut créer un grand « dictionnaire » de paires texte clair/texte chiffré utiles, puis observer le canal chiffré pour trouver des textes chiffrés correspondants.

Bien que les schémas de chiffrement déterministes ne puissent jamais être sémantiquement sécurisés , ils présentent certains avantages par rapport aux schémas probabilistes.

L'une des principales motivations de l'utilisation du chiffrement déterministe est la recherche efficace de données chiffrées. Supposons qu'un client souhaite confier une base de données à un fournisseur de services de base de données potentiellement peu fiable. Si chaque entrée est chiffrée à l'aide d'un système de chiffrement à clé publique, n'importe qui peut ajouter des données à la base de données et seul le « récepteur » distingué qui possède la clé privée peut déchiffrer les entrées de la base de données. Si, toutefois, le récepteur souhaite rechercher un enregistrement spécifique dans la base de données, cela devient très difficile. Il existe certains schémas de chiffrement à clé publique qui permettent la recherche par mot-clé, mais ces schémas nécessitent tous un temps de recherche linéaire par rapport à la taille de la base de données. Si les entrées de la base de données étaient chiffrées avec un schéma déterministe et triées, un champ spécifique de la base de données pourrait être récupéré en temps logarithmique.

En supposant qu’un schéma de cryptage déterministe soit utilisé, il est important de comprendre quel est le niveau de sécurité maximal qui peut être garanti.

Plusieurs travaux se sont concentrés sur ce problème précis. Le premier travail visant à définir rigoureusement la sécurité pour un schéma déterministe a été publié dans CRYPTO 2007. [ Ce travail a fourni des définitions de sécurité assez solides (bien que plus faibles que la sécurité sémantique) et a donné des constructions dans le modèle d'oracle aléatoire . Deux travaux de suivi sont apparus l'année suivante dans CRYPTO 2008, donnant des équivalences définitionnelles et des constructions sans oracles aléatoires.

Pour contrer ce problème, les cryptographes ont proposé la notion de chiffrement « aléatoire » ou probabiliste . Dans ces schémas, un texte en clair donné peut être chiffré dans un très grand ensemble de textes chiffrés possibles, choisis au hasard au cours du processus de chiffrement. Avec des garanties de sécurité suffisamment fortes, les attaques proposées ci-dessus deviennent irréalisables, car l'adversaire sera incapable de corréler deux chiffrements du même message, ou de corréler un message à son texte chiffré, même s'il a accès à la clé de chiffrement publique. Cette garantie est connue sous le nom de sécurité sémantique ou indiscernabilité du texte chiffré , et a plusieurs définitions en fonction des capacités supposées de l'attaquant (voir sécurité sémantique ).