Algorithme de Simon
Un algorithme quantique qui trouve une période XOR cachée dans une fonction exponentiellement plus vite que toute méthode classique.
Le problème paraît artificiel : une fonction vérifie f(x) = f(x ⊕ s) pour un secret s ; trouver s. Classiquement, il faut environ 2n/2 requêtes avant de tomber sur une collision. Daniel Simon a montré en 1994 qu'un ordinateur quantique y parvient avec un nombre de requêtes linéaire en n. C'était la première séparation exponentielle entre quantique et classique pour un problème bien défini, et Peter Shor a dit que c'est l'article de Simon qui l'a lancé à l'assaut de la factorisation.
Pendant vingt ans, l'algorithme est resté surtout une note historique. Puis on a découvert que de nombreuses constructions Even–Mansour et modes de MAC contiennent précisément ce genre de période XOR, ce qui en fait le cheval de bataille de la cryptanalyse quantique contre les schémas symétriques.