Hacker News Reader

Comment by dsacco | Hacker News Reader

Two reminders, for anyone reading this and wondering about the implications for cryptography:

1. Grover's algorithm is applicable to symmetric cryptosystems, like AES. It searches for secret keys in a quantum-optimal manner. Shor's algorithm is the much more serious threat which endangers asymmetric (public-key) cryptosystems like RSA. It uses the quantum Fourier transform to attack integer factorization and discrete logarithm problems.

2. This 3-qubit implementation corresponds to 2^3 items; it is still extremely far off from being practically usable against AES-128. Moreover, Grover's algorithm can't be credibly used to break AES-256, as it improves the search time by approximately halving the number of items to be searched (i.e. AES-256 is reduced to 128 bits of security, AES-128 is reduced to 64, etc).

View on HN

> it improves the search time by approximately halving the number of items to be searched (i.e. AES-256 is reduced to 128 bits of security, AES-128 is reduced to 64, etc).

No, "halving the number of items to be searched" would be a constant factor (1/2) change, which would be trivial. Computers get that much faster in a year.

Rather, using Grover brute search to crack a hash reduces the effective number of items to try by a square root. Each bit of AES increases cracking time by a factor of 2, which is why decreasing the cracking time by a square root is equivalent to halving the number of bits of security: sqrt(2^N) = 2^(N/2)

I’m confused by your comment, because it doesn’t seem like we’re disagreeing. The end result of Grover’s algorithm is that a 2^N keyspace can be searched in a worst case of 2^N/2 steps instead of 2^N steps. So yes, it does halve the number of items to be searched.

2^10 = 1024

2^20 = 1048576

O(2^(N/2)) is a quadratic speedup over O(2^N). Halving the search space, on the other hand, would only give you a linear speedup.

Edit: just to be clear: one half of 2^N is just 2^(N-1).

Yes, I see the issue now. I wasn’t referring to bits being halved. I was referring to bit-security (i.e. 128-bit versus 64-bit).

Maybe you've just used "items" in a non-standard way? The number of bits (N) is indeed being halved, but the standard way of talking about Grover's search is that you're searching for an item in the "database" of bit configurations (i.e., keyspace), which is 2^N. No one would refer to the bits as "items".

Ah, I see what you mean. Yes, I didn’t intend to refer to the bits themselves as items; rather I was referring to the bit-security.

Reply on news.ycombinator.com