3

http://www.dwavesys.com/en/pressreleases.html#lm_2011

Lockheed Martin Corporation (NYSE: LMT) has entered into an agreement to purchase a quantum computing system from D-Wave Systems Inc.

I'm just asking that if computing power would be "infinite" (not really, but the quantum computers could bring dimensional difference against the modern supercomputer-clusters in a medium term(? fixme) ).

So are there any symetric/asymetric encryptions that can be still good when computing power is "infinite"?

Or the whole "encryption thing" in information technology will be DEAD in about 10-20 years because of these quantum computers (brute force)?

Thank you for any opinion.

3
  • 1
    This question contains some faulty premises. Quantum computers don't mean that computing power is infinite. Please revise the question and try asking what you really want to know, without the faulty premises. If you want to know if there are any encryption schemes that are secure against quantum computers, ask that. That's very different from asking whether something is secure against "infinite computing power".
    – D.W.
    Jun 3, 2011 at 0:39
  • 2
    (Can't resist.) Perhaps the answer is yes, but with great computing power comes great computing responsibility.
    – Iszi
    Jun 4, 2011 at 16:48
  • 1
    Quantum computers don't have infinite computing power at all. They can just parallelize computations. But as soon as there are dependencies in the computations, quatum computer cannot do anything to really speed it up. i.e. parallelism != infinite computing power
    – Henri
    Jun 7, 2011 at 18:06

3 Answers 3

9

Public-key cryptosystems base their security on certain assumptions, one of these being that certain mathematical problems, while theoretically solvable, are computationally infeasible to solve. Typical examples are integer factorisation and the reverse logarithm problem which are used in cryptosystems such as RSA, DSA and Elgamal. For example, an attacker that had infinite processing power, memory and time, could derive a private key only by having a public key.

Quantum computers work with qubits instead of bits, which means that each bit could be in either 0, 1 or a superposition of these states simultaneously, in contrast to classical computers where each bit can only be in one state at a time. This leads to what is called quantum parallelism.

The real issue is to find how to utilise this parallelism to solve mathematical problems faster. Certain tasks, such as multiplication, cannot be performed much quicker by this kind of computer, while others, such as integer factorisation can. Algorithms such as Shor’s algorithm exploit the power of quantum parallelism to perform integer factorisation in exponentially less time than normal computers. For example factorising a 1024-digit number which would take billions of billions of years, with a quantum computer it could take 20 minutes. This means that cryptosystems such as RSA that rely on the computational infeasibility of breaking an integer into two primes will be considered obsolete if a quantum computer (that can handle such computation) is built.

For this reason, cryptographers are already researching what would happen in a post-quantum era and have been trying to find how to build public-key cryptosystems that rely on problems that cannot be solved by quantum computers any quicker that classical computers.

Finally, it should be stated that symmetric cryptography is thought not be affected so much by quantum computers. By using a quantum computer, Grover’s algorithm can make the search for a key quicker by needing the square root of the time of a normal brute-force search. This is significant, but it is suggested that simply doubling the key length is enough to mitigate the attack.

1
  • John, although I largely agree I would like to see a (reliable) source that 1024bit rsa can be broken in 20 minutes. As far as I know (from classes on this topic) factoring a 4096 bit integer using quatum computers is as fast as the best attacks on DES these days.
    – Henri
    Jun 7, 2011 at 18:02
7

Some cryptographic algorithms, in particular most asymmetric algorithms (asymmetric encryption, signatures), suffer quite a lot in the presence of a true quantum computer. Note that the McEliece asymmetric encryption and its digital signature counterpart (Niederreiter scheme) are, for the moment, immune to quantum computing (there is no proof of immunity, but no quantum-powered attack is known for those).

A true quantum computer would also give a boost to attacks on symmetric algorithms, but not a deadly one. At best, it would make AES with a 256-bit key no stronger than what AES with a 128-bit key does today (i.e. still unbreakable).

The machine announced by D-Wave appears not to be a true quantum computer. It seems to be designed for finding approximations to optimization problems which behave "smoothly" (i.e. you can have an "almost good" solution and recognize it as such). Cryptographic algorithms are exactly the opposite of such problems.

A true quantum computer is nowhere near "infinite" computing power. Nevertheless, there are a few cryptographic algorithms which resist infinite computing power, e.g. One-Time Pad and Shamir's Secret Sharing. These algorithms have extremely specific and constrained application range, but they fear no computer, be it traditional, quantum or divine.

1
  • I don't like ever calling something unbreakable, but very good answer (+1). It seems that when it comes to encryption the "infinite processing power" question always comes into play. It's comparable to asking if brute-forcing will work. With time, it is going to work, but that's assuming there has been no change to the subject. Implementation is what is key.
    – Ormis
    Jun 3, 2011 at 14:20
4

Infinite is really the wrong word here - infinite compute power wins, obviously. So scaling it back to what you really mean - massive increases in compute power - yes it will obviously have an effect. @John has mentioned the direct effect of quantum computing, and examples of where it will significantly speed things up and where it won't.

In general though, dramatic increases in compute power generally lead to needs for an increase in key length, and step changes in how crypto is broken leads to a need for new and improved algorithms.

So in summary, no I don't expect the need for encryption to go - I just expect longer keys, better algorithms, and potentially algorithms which are more resistant to quantum computers.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .