I've recently read a number of (layman's) articles on quantum mechanics and quantum computing, and keep seeing examples along the lines of "Quantum computing can crack passwords quickly by trying all combinations at once". The example goes on to show that rather than passing in an N-bit value, an N-qubit value is passed in which is effectively all combinations due to its superposition state. The value is then collapsed to the state which was successful; i.e. giving the correct password.
The problem I have with this example, is it assumes that our ValidatePassword function accepts a qubit array as an input; which I suspect people would know better than to do.
Is this example just an oversimplification to demonstrate something which tries many possibilities at once; or is there a real potential security concern with the advent of quantum computers?
Best Answer
It's primarily just an oversimplification, but there's a real security concern there, too.
For web servers across the Internet, this is spot on. You can't send qubits over the Internet, so there's no way to send this "quantum superposition of passwords" to the server.
The problem arises when I have an algorithm that somehow lets me test whether or not any given password is correct. Suppose, for example, that I've broken into the website's database and found a salted password hash. Now I can check whether or not a password is correct by salting and hashing it and comparing it against the hash I found.
Suppose that it takes 1 millisecond to test a password, and there are 1,000,000,000,000,000,000 possible passwords. With classical computing, if I wanted to try out every possible password, it would take me 1,000,000,000,000,000,000 milliseconds, which is over 30 million years.
With quantum computing, things are different. Can I just try all of the passwords at once, and then "collapse to the successful value", thereby figuring out the password in mere seconds? No, it's not that simple.
What I can do is use Grover's algorithm. Now, Grover's algorithm is complicated and I don't know how it works. But I do know what it does.
With Grover's algorithm, you start with a quantum superposition. Then you do "the Grover iteration" a bunch of times. Doing one Grover iteration involves performing the password testing algorithm once, along with a little bit of other stuff. The number of times that you have to do the Grover iteration is approximately equal to the square root of the number of possible passwords, or 1,000,000,000. Why do you have to do it that many times? I don't know. Then you do some more stuff, and somehow, Grover's algorithm tells you what the answer is.
So how fast can we crack the password? Well, suppose that our quantum computer can perform the password testing algorithm in 1 millisecond, just like a classical computer can. (In reality, it will probably be slower, because making a fast quantum computer is harder than making a fast classical computer.) Then the amount of time it will take you to crack the password is about 1,000,000,000 milliseconds, or about 12 days. Not bad.
What's the upshot of all this? Quantum computing doesn't simply allow you to "try everything at once", but it does make brute-force searching a whole lot faster.