8
$\begingroup$

I understand that using Grover's algorithm it only requires $2^{64}$ lookups for a 128 bit AES encryption, leading people to say we need to increase to 256 bit keys. But how long would it actually take a quantum computer to do $2^{64}$ lookups?

I can't say I fully understand quantum computers, but aren't people making the assumption that 128 bit is only unsafe to quantum computers because 64 bit (which 128 bit becomes using a quantum computer) can be broken through brute force on our current computers...? Even if a quantum computer only needs to do $2^{64}$ lookups, presumably it doesn't do them at the exact speed of current computers.

When people have asked in the past how long a quantum computer would take to break AES 128 bit, people always answer that it would take $2^{64}$ lookups (which some people take to mean the amount of time we currently take to break 64 bit), but there's never any indication of an actual time.

I understand that quantum computers are highly theoretical at this stage in terms of large scale implementation, but can anyone offer any ideas?

Improve this question
$\endgroup$
3
  • $\begingroup$ Take a look at this $\endgroup$
    – rath
    Commented Oct 13, 2013 at 4:48
  • $\begingroup$ the biggest number factored so far by a quantum algorithm is something like 64. That's six four. Don't hold your breath. $\endgroup$
    – ddyer
    Commented Oct 15, 2013 at 0:41
  • $\begingroup$ If it's a Microsoft Core-Q, it'll be 30 seconds...4379 years...53 minutes $\endgroup$
    – Leo
    Commented Jul 1, 2016 at 8:41

1 Answer 1

Reset to default
7
$\begingroup$

I'm not going to exactly answer your question, because I have no idea. I simply do not know how fast the quantum computer is that NSA is building in secret.

However I could explain why people recommend 256-bit security in the face of quantum computing using some numbers. If you feel that $2^{128}$ is a comfortable security against bruteforcing, remember that a $2^{64}$ security level is $18446744073709551616$ times faster to bruteforce.

That means a ~0.000000000162630 GHz quantum processor bruteforces a 128 bit key faster than a 3GHz regular processor, assuming one lookup per cycle.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ NSA? I think they subcontracted that via Google and NASA… "Google and NASA buy D-Wave quantum computer - SlashGear" and for a whopping 10 million US$, we can get one too. ;) $\endgroup$
    – e-sushi
    Commented Oct 13, 2013 at 0:13
  • 1
    $\begingroup$ @e-sushi If NSA isn't far ahead of D-Wave, then we'll be safe for decades. $\endgroup$
    – CodesInChaos
    Commented Oct 13, 2013 at 8:28
  • $\begingroup$ @e-sushi from that article: "Google will co-invest in a quantum supercomputer lab near its Mountain View campus, exploring the potential for incredibly-fast processing tipped to run 11,000x faster at some tasks compared to a standard Intel chip." 11,000x is much less than 18,446,744,073,709,551,616x, what Grover's algorithm would suggest. If it is mere 11,000x, it would be more cost effective to use standard intel hardware in parallel, or maybe FPGAs. $\endgroup$
    – user4982
    Commented Oct 13, 2013 at 10:09
  • $\begingroup$ @nightcracker the reason you have no idea is that open academic research has not been able to provide device that used Grover's algorithm to brute-force AES or some other well-known cipher, such as DES. Lack of earlier results makes it very hard to estimate how long single lookup would take. For things like brute-forcing DES or brute-forcing RSA earlier results exist and it is possible to calculate costs (both time and investment) from that. For Quantum computers no materials exist. Given that the recent NSA leaks do not already tell details of the speed of NSA's Quantum thing I doubt it is. $\endgroup$
    – user4982
    Commented Oct 13, 2013 at 10:17
  • 3
    $\begingroup$ @e-sushi According to existing public sources, the Kryptos solving capabilities of NSA have been several years ahead of the first successful public analysis. I bet they've broken it already. $\endgroup$
    – user4982
    Commented Oct 13, 2013 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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