Est-il possible qu'il existe une méthode de chiffrement impossible à résoudre, même en utilisant des ordinateurs quantiques?

On sait que les ordinateurs quantiques sont capables de déchiffrer en temps polynomial un large éventail d’algorithmes cryptographiques que l’on pensait auparavant ne pouvant être résolus que par des ressources augmentant de façon exponentielle avec la taille en bits de la clé. L'algorithme de Shor en est un exemple .

Mais, autant que je sache, tous les problèmes ne relèvent pas de cette catégorie. Sur les problèmes difficiles pour les ordinateurs Quantum , on peut lire

Les chercheurs ont développé un algorithme informatique qui ne résout pas les problèmes mais les crée dans le but d'évaluer les ordinateurs quantiques.

Pouvons-nous toujours espérer un nouvel algorithme cryptographique difficile à déchiffrer même avec un ordinateur quantique ? Pour plus de clarté: la question concerne spécifiquement la conception de nouveaux algorithmes .

Le titre de votre question demande des techniques impossibles à intégrer, auxquelles One Time Pad (OTP) est la réponse correcte, comme indiqué dans les autres réponses. L'OTP est théoriquement sûr de l'information, ce qui signifie que les capacités de calcul d'un adversaire sont inapplicables lorsqu'il s'agit de trouver le message.

Cependant, bien qu’elle soit parfaitement sécurisée en théorie , le protocole OTP n’a qu’une utilité limitée dans la cryptographie moderne. Il est extrêmement difficile à utiliser avec succès dans la pratique .

La question importante est vraiment:

Pouvons-nous toujours espérer un nouvel algorithme cryptographique difficile à déchiffrer même avec un ordinateur quantique?

Cryptographie asymétrique

La cryptographie asymétrique comprend les schémas de chiffrement à clé publique (PKE), de signatures numériques et d’accords de clé. Ces techniques sont essentielles pour résoudre les problèmes de distribution et de gestion des clés. La distribution et la gestion des clés sont des problèmes non négligeables, c’est en grande partie ce qui empêche le bon fonctionnement du logiciel OTP. Internet tel que nous le connaissons aujourd’hui ne fonctionnerait pas sans la possibilité de créer un canal de communication sécurisé à partir d’un canal de communication non sécurisé, ce qui est l’une des caractéristiques offertes par les algorithmes asymétriques.

Algorithme de Shor

L'algorithme de Shor est utile pour résoudre les problèmes de factorisation d'entiers et de logarithmes discrets. Ces deux problèmes constituent la base de la sécurité de systèmes largement utilisés tels que RSA et Diffie-Hellman .

Le NIST évalue actuellement les soumissions pour les algorithmes Post-Quantum, des algorithmes basés sur des problèmes réputés résistants aux ordinateurs quantiques. Ces problèmes incluent:

• Problèmes liés au réseau
  • Problème de vecteur le plus court (SVP)
  • Problème de vecteur le plus proche (CVP)
• Équations multivariées
  • Équations polynomiales multivariées
• Schémas basés sur des codes
  • Basé sur la dureté du décodage des codes linéaires
• Isogénie Supersingulaire Diffie-Hellman (SIDH)

Il convient de noter que des algorithmes classiques permettant de résoudre les problèmes ci-dessus peuvent exister , mais que leur exécution et leur précision sont prohibitives pour la résolution de grandes instances dans la pratique. Ces problèmes ne semblent pas pouvoir être résolus par la capacité de résoudre le problème de la prise de commande , ce que fait la partie quantique de l'algorithme de Shor.

Cryptographie Symétrique

Algorithme de Grover fournit une accélération quadratique lors de la recherche dans une liste non triée. C’est effectivement le problème qui force une clé de chiffrement symétrique.

Utiliser l'algorithme de Grover est relativement facile comparé à l'algorithme de Shor: doublez simplement la taille de votre clé symétrique . Une clé de 256 bits offre à un adversaire qui utilise l'algorithme de Grover une résistance à la force brute de 128 bits.

L'algorithme de Grover est également utilisable contre les fonctions de hachage . La solution est simple: doublez la taille de votre sortie de hachage (et de votre capacité si vous utilisez un hachage basé sur une construction en éponge ).

Je suppose qu’il existe un type de chiffrement qui ne peut pas être craqué avec des ordinateurs quantiques: un tampon unique tel que le chiffrement Vigenère. . Il s'agit d'un chiffre avec un clavier qui a au moins la longueur de la chaîne codée et ne sera utilisé qu'une seule fois. Ce chiffre est impossible à craquer même avec un ordinateur quantique.

Je vais expliquer pourquoi:

Supposons que notre texte en clair est ABCD. La clé correspondante pourrait être 1234. Si vous l'encodez, alors vous obtenez XYZW. Maintenant, vous pouvez utiliser 1234pour obtenir ABCDou 4678pour obtenir EFGHce qui pourrait être une phrase valide aussi.

Le problème est donc que personne ne peut décider si vous voulez dire ABCDou EFGHsans connaître votre clé.

La seule raison pour laquelle ce type de chiffrement peut être déchiffré est que les utilisateurs sont paresseux et utilisent une clé deux fois. Et alors vous pouvez essayer de le casser. @Peterh a déclaré que les tampons uniques nécessitaient le partage d’un canal secret

Oui, il existe de nombreuses propositions d' algorithmes cryptographiques post-quantiques qui fournissent les primitives cryptographiques auxquelles nous sommes habitués (notamment le cryptage asymétrique avec des clés privées et publiques).

Pour donner suite à la réponse d'Ella Rose: la plupart des systèmes de chiffrement pratiques utilisés aujourd'hui (par exemple, Diffie-Hellman, RSA, courbe elliptique, réseau), sont centrés sur la difficulté de résoudre le problème du sous-groupe caché (HSP). Cependant, les trois premiers sont centrés sur le PSH pour les groupes abéliens . Le HSP pour les groupes abéliens peut être efficacement résolu par la transformée de Fourier quantique , qui est implémentée par exemple par l'algorithme de Shor. Ils sont donc vulnérables aux attaques d'un ordinateur quantique. La plupart des méthodes basées sur le réseau, d’autre part, tournent autour du HSP pour le dièdre.groupes, qui sont non-labéliens. On ne pense pas que les ordinateurs quantiques soient capables de résoudre efficacement le HSP non labélien; ces algorithmes devraient donc être capables de mettre en œuvre une cryptographie post-quantique.