Algoritme van Simon
Een kwantumalgoritme dat een verborgen xor-periode van een functie exponentieel sneller vindt dan elke klassieke methode.
Het probleem lijkt gezocht: een functie voldoet aan f(x) = f(x ⊕ s) voor een geheime s; vind s. Klassiek zijn ongeveer 2n/2 queries nodig voordat er een botsing opduikt. Daniel Simon liet in 1994 zien dat een kwantumcomputer het met een aantal queries lineair in n af kan. Het was de eerste exponentiële scheiding tussen kwantum en klassiek voor een goed gedefinieerd probleem, en volgens Peter Shor was het Simons artikel dat hem op het spoor van het factoriseren zette.
Twintig jaar lang was het algoritme vooral een historische voetnoot. Toen bleek dat veel Even-Mansour-constructies en MAC-modi precies zo’n xor-periode bevatten, waardoor het het werkpaard werd van de kwantumcryptanalyse van symmetrische schema’s.