These days I'm reading about quantum computing and quantum cryptography which I've found extremely interesting. Well, I also read some blog posts of Bruce Schneier talking about how quantum computers threaten our current asymmetric crypto-systems. However, I don't know whether quantum computers also threaten symmetric crypto-systems (AES, Vernam cipher, etc.).
2 Answers
$\begingroup$
$\endgroup$
With Grover's algorithm, quantum computers can brute-force a block cipher with $n$-bit keys using $2^{n/2}$ steps, which is much smaller than the regular effort ($2^n$). This means, for example, that AES-128 could be broken with $2^{64}$ steps, and that AES-256 would offer the same security that AES-128 offers currently.
In short, key sizes would need to be doubled.
$\begingroup$
$\endgroup$
Not really. Grover's algorithm is serial and the $2^{64}$ steps that people talk about to break AES-128 have to happen in series. If we had an amazing classical implementation of AES that evaluated 1 round per clock cycle and a top end clock rate of 8Ghz, we could evaluate about 800,000,000 ~ $2^{29.6}$ AES-128 encryptions per second. Thus current top end classical computers would take around 700 years to evaluate $2^{64}$ AES-128 encryptions in series.
Even if we could produce quantum computers that evaluate instructions at the same speed as today's classical computers and get arbitrarily long-lived cubits, it still doesn't feel like a realistic threat.
