Het zoeken naar een sleutel van n bits voor symmetrische cryptografie met het algoritme van Grover op een kwantumcomputer kost naar verluidt ongeveer 2^(n/2) berekeningen. Welke waarde ligt bij deze eenvoudige vuistregel het dichtst bij de veiligheid van AES-128 tegen kwantumcomputers?

Antwoord: A. Ongeveer 64 bits veiligheid

Het algoritme van Grover verlaagt het aantal pogingen bij brute force van 2ⁿ tot ongeveer 2^(n/2), de vierkantswortel. Voor AES-128 is dat 2^(128/2) = 2⁶⁴ pogingen, dus de veiligheid komt overeen met ongeveer 64 bits. Anders dan het algoritme van Shor, dat publieke-sleutelcryptografie in polynomiale tijd breekt, kan dit met langere sleutels worden opgevangen, en AES-256 behoudt ongeveer 128 bits veiligheid. Het algoritme van Grover profiteert echter weinig van parallellisatie en moet ook een lange berekening zonder fouten uitvoeren, dus dit is slechts een eenvoudige vuistregel; ook in de beoordeling van post-kwantumcryptografie door NIST geldt als maatstaf voor de laagste veiligheidscategorie dat iets even moeilijk is als het zoeken naar een AES-128-sleutel.