Si P = NP, y a-t-il des cryptosystèmes qui nécessiteraient n ^ 2 temps pour se casser?

Si P est égal à NP, sera-t-il encore possible de concevoir un cryptosystème où l'algorithme de cryptanalyse optimal prend, disons, le carré du temps occupé par les algorithmes de chiffrement et de déchiffrement légitimes? Existe-t-il déjà de tels algorithmes?

Oui - en fait, le tout premier algorithme à clé publique qui a été inventé en dehors d'une agence de renseignement a fonctionné comme ça! La première publication qui proposait la cryptographie à clé publique était "Secure Communications over Insecure Channels" de Ralph Merkle , où il proposait d'utiliser des "puzzles" . Il s'agit d'un protocole d'accord clé.

1. Alice envoie messages cryptés (appelés puzzles) contenant chacun un identifiant unique I i et une clé de session K i , les clés de chaque message étant choisies parmi un ensemble de $n$$I_i$$K_i$$n$ clés. Cela prend fois ( O ( 1 ) par message).$O(n)$$O(1)$
2. Bob déchiffre l'un des messages par force brute et renvoie chiffré avec K i . Cela prend O ( $I_i$$K_i$ fois ( O ( 1 ) par touche, fois n touches possibles).$O(n)$$O(1)$$n$
3. $O(n)$

Chaque partie ne nécessite que le calcul , mais une écoute indiscrète qui souhaite trouver $O(n)$$K_i$$\Theta(n^2)$

Après que Merkle ait inventé ses puzzles, Diffie et Hellman ont publié un protocole d'accord clé basé sur le problème du logarithme discret . Ce protocole est encore utilisé aujourd'hui.

Le problème avec les puzzles Merkle, ou quoi que ce soit où la quantité de travail à faire par l'attaquant n'augmente qu'au fur et à mesure que le carré de la partie légitime, est qu'il faut d'énormes tailles de clés et des quantités de calcul pour atteindre une marge de sécurité décente.

Dans tous les cas, il n'est pas clair que le simple fait de prouver que P = NP invalidera les algorithmes cryptographiques existants. Si l'augmentation polynomiale est une puissance suffisamment élevée, cela peut ne pas avoir autant d'importance dans la pratique. Voir Comment la sécurité devra-t-elle être modifiée si P = NP? , Peut-on dire que si P = NPP = NP il n'y a pas de cryptage sécurisé par clé publique CPA? , P = NP et systèmes cryptographiques actuels ,…

https://en.m.wikipedia.org/wiki/One-time_pad

Un One Time Pad est sécurisé quelle que soit la complexité, tant que vos numéros sont vraiment aléatoires.

Même si vous pouvez essayer toutes les touches rapidement, cela ne sert à rien car cela révélera tous les messages possibles, et il n'y a aucun moyen de savoir lequel était le souhaité.

Pour ce que vous décrivez, si l'analyse ne prenait que le carré du temps de cryptage, elle serait considérée comme non sécurisée par les normes modernes. Le cryptage doit se produire en quelques secondes ou même moins, donc une augmentation quadratique permettrait aux messages d'être décodés en quelques heures.