8
$\begingroup$

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.).

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

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