-3

It is generally known that we choose our key-lengths, so they are unbreakable in a specific time frame. For example we choose 112 bit keys (=2048-bit RSA) to protect data for the next few years and we choose 128-bit keys for protection of data for the next decade and 256-bit keys for anything else.

Those estimates heavily depend on the availability of ressources to an attacker, for example the amount of computing power. But as we continue innovation, quantum computers become more likely every day. Obviously it's quite unlikely that we'll face fully ready-to-use quantum computers next year, but there may be in the future.

Now my question:
For which timeframe is it reasonable to assume quantum computers, being ready to perform cryptographically relevant operations (Grover and Shor)?
Some examples of such timeframes: 5 years? 10 years? 20 years?...

This information has a huge impact on choosing the right key-lengths, as one needs to double symmetric key-lengths (128 -> 256 bit or 256 -> 512 bit) and to drop "classic" encryption methods (ECC, factoring based, discrete-log based).

SEJPM
  • 9,500
  • 5
  • 35
  • 66
  • 1
    I'm not fully sure if InfoSec is the right place for this. I assumed this to be risk-management related and hence fitting for InfoSec, but if it doesn't fit, please tell me and I'll try and migrate to Crypto.SE. – SEJPM Jul 10 '15 at 19:54
  • Now. Look up D-Wave Quantum processors. I don't know how stable they are though – dylan7 Jul 10 '15 at 20:01
  • @dylan7. They can't do crypto-related operations (like Short and Grover). They don't work in the required way. And it's even questionnable if they even show a speed-up against any classic computer. – SEJPM Jul 10 '15 at 20:07
  • Well you also have to consider the NSA they have started quantum computing projects and even with the snowden documents, how far they have come could still be a mystery. – dylan7 Jul 10 '15 at 20:25
  • @dylan7, I think quantum computers aren't yet ready for crypto-related operations. The Snowden documents suggested that the NSA doesn't have a significant advantage (other then money) over the "free research". They'd also drop ECC very fast as soon as they realize a quantum computer as they'd have to assume other nations to have similar capabilities (esp. China and Russia), making ECC unsuitable for secret and top-secret. – SEJPM Jul 10 '15 at 20:29

1 Answers1

1

Assuming quantum computing at the caliber necessary for cryptographic functions is even possible (we're not certain of this!), it is reasonable to also assume that a quantum processor can crack any non-quantum cypher (quantum computers examine all possibilities simultaneously), so it basically doesn't matter (we're screwed if it comes, there'd be no way to upgrade fast enough).

If you're trying to get a date for when quantum cracking arrives and then use Moore's Law to determine what key size is still uncrackable by non-quantum computers around that time, I suppose that's admirable ... but there's no way to forecast that as it's essentially waiting for a series of scientific and/or mathematical breakthroughs.

 

Our one saving grace may be that the number of possibilities a quantum cracker can examine is limited to a certain key size; iirc, the proof-of-concept quantum computers we have can only examine a dozen or so possibilities. This is convenient because it means you want a larger key size, which is the same kind of future-proofing we already employ in order to combat Moore's Law.

Just make large keys according to your performance requirements (larger is better, but too large can be too slow). This is the best you can do. If you're lucky, quantum computing will either never arrive or else never be able to handle the kind of entropy dictated by your large keys. That's also assuming we don't suffer an independent mathematical breakthrough that trivializes decryption speeds with or without a quantum computer.

But first things first:  Where's my flying car?

 

Edit: Okay, we're closer than I thought (I answered that off the top of my head and I was not fully up to date), though I still stand by what I said earlier. The NSA is actively pursuing this but doesn't appear to have made much progress. D-Wave has even made "real" quantum computers, albeit without the ability to crack RSA beyond a key size of 128 bits; GCN reported about two years ago on this:

Ladizinsky says much of the government’s interest in quantum computing has to do with code breaking. To break 128-bit RSA encryption the traditional way would take 2,000 workstations and supercomputers about eight months. For 256-bit encryption, it’s a million years. And for 600-bit encryption, it would take the age of the universe. But with quantum computing, the size of the problem doesn't matter so much, because a powerful enough quantum machine could look at all the possibilities at once. Although Ladizinsky says the D-wave machine is not specifically designed to break encryption, he knows others are experimenting heavily in that field.

See also this crypto.SE question on why D-Wave can't crack RSA.

Adam Katz
  • 9,718
  • 2
  • 22
  • 44