How exactly does Grovers algorithm "crack" symmetric key encryption? I searched around on the internet, and found that it could make the key length effectively half as long, meaning you only needed to double the lenth of your key for the encryption to be viable again. But how exactly could it brute force the password?

  • 2
    $\begingroup$ I think it would be incorrect to say that Grover can "crack" any particular cryptosystem. Grover merely provides a quadratic speedup over classical search algorithms. For instance if you have to search for a key in say $n$-bit strings there are $2^n$ keys to brute force check. Grover search can effectively square root the search space but this means there are still $2^{n/2}$ keys to brute force... still an exponential number of keys (with respect to $n$) to check. $\endgroup$
    – Condo
    Oct 16 '20 at 14:07

Grover's algorithm is a Circuit SAT solver that finds a satisfying assignment in around $2^{n/2}$ evaluations of the circuit, where $n$ is the number of inputs. You can build a circuit that takes a key as input and checks whether it can successfully decrypt a ciphertext with that key (perhaps by verifying an authenticator), returning 1 if it can. Grover's algorithm then gives you a working key in around $2^{n/2}$ decryptions where $n$ is the key length.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.