L'informatique quantique pourrait-elle éventuellement être utilisée pour rendre le hachage moderne trivial à briser?

En termes simples, si l'on devait construire un appareil informatique quantique d'une puissance de, disons, 20 qubits, un tel ordinateur pourrait-il être utilisé pour rendre inutile tout type d'algorithme de hachage moderne?

Serait-il même possible d'exploiter la puissance de l'informatique quantique dans une application informatique traditionnelle?

Les ordinateurs quantiques peuvent avoir un certain avantage sur les ordinateurs classiques dans certains cas. L'exemple le plus remarquable est l'algorithme de Shor qui peut prendre en compte un grand nombre de temps polynomiaux (alors que classiquement, l' algorithme le plus connu prend un temps exponentiel). Cela casse complètement les schémas comme RSA, basés sur la dureté de la factorisation.

Ce n'est pas nécessairement le cas pour les fonctions de hachage. Tout d'abord, nous devons définir ce que signifie rompre une fonction de hachage. Une façon de le casser est appelée attaque pré-image : vous me donnez une valeur de hachage $v$ , et j'ai besoin de trouver un message tel que hachage ( m ) = v . Une autre attaque est l' attaque par collision , dans laquelle vous ne me donnez rien, et je dois trouver deux messages différents m 1 , m 2 qui ont le même hachage hachage ( m 1 ) = hachage ( m 2$m$$\operatorname{hash}(m)=v$$m_1, m_2$$\operatorname{hash}(m_1)=\operatorname{hash}(m_2)$. C'est plus facile que de trouver une pré-image, car je ne suis pas lié au spécifique .$v$

Que peuvent faire les ordinateurs Quantum? Le résultat principal est l'algorithme de recherche de Grover : une méthode permettant à un ordinateur quantique de rechercher dans une base de données non triée de taille avec le temps O ( $N$(alors que classiquement cela prendra un temps prévu deN/2).$O(\sqrt{N})$$N/2$

Avec l'algorithme de Grover, trouver une pré-image d'une fonction de hachage dont la sortie est bits prend O ( 2 k / 2 ) de temps, plutôt que O ( 2 k ) .$k$$O(2^{k/2})$$O(2^k)$

Est-ce un problème ? Pas nécessairement. Les fonctions de hachage sont conçues de telle sorte que le temps soit considéré comme "sûr" (en d'autres termes, les concepteurs de hachage doublent toujours k ). Cela est dû au paradoxe d'anniversaire avec lequel il est possible de trouver une collision avec le temps O ( 2 k / 2 ) par un ordinateur classique.$2^{k/2}$$k$$O(2^{k/2})$

La bonne chose à propos de l'algorithme de Grover est qu'il est optimal - tous les autres algorithmes quantiques pour trouver un élément dans une base de données non triée s'exécuteront dans le temps .$\Omega(\sqrt{N})$

Les ordinateurs quantiques peuvent-ils effectuer de meilleures attaques par collision ? En fait, je n'en suis pas sûr. L'algorithme de Grover peut être étendu, de sorte que s'il y a éléments (c'est-à-dire des pré-images), le temps pour en trouver un est réduit à O ( $t$. Mais cela ne donne aucune collision - une nouvelle exécution de l'algorithme pourrait renvoyer la même pré-image. En revanche, si nous choisissonsm1au hasard, puis utilisons l'algorithme de Grover, il est probable qu'il renverra un message différent. Je ne sais pas si cela donne de meilleures attaques.$O(\sqrt{N/t})$$m_1$

_{(cela répond à la question plus générale, sans restreindre l'ordinateur à 20 qubits, ce qui ne sera pas suffisant pour casser les hachages actuels de 1024 bits).}

D'après ce que je comprends, l'informatique quantique a le pouvoir de casser facilement les algorithmes de hachage d'aujourd'hui. Cependant, à long terme, nous pourrons également utiliser des algorithmes de hachage plus complexes, et il est généralement plus facile de chiffrer que de déchiffrer quelque chose. Je pense que les plus grands problèmes à prendre en compte sont lorsque l'informatique quantique n'est disponible que pour quelques privilégiés, ce qui leur donne un accès facile à des éléments protégés par les algorithmes d'aujourd'hui bien avant que les algorithmes plus avancés ou même la conscience de la menace ne soient répandus.

Voir ici pour une réponse réellement technique à la question sur Stack Overflow.