Are the encryptions "broken" with great computing power?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.