Time Running Out for Public Key Encryption

holy_calamity writes "Two research teams have independently made quantum computers that run the prime-number-factorising Shor's algorithm — a significant step towards breaking public key cryptography. Most of the article is sadly behind a pay-wall, but a blog post at the New Scientist site nicely explains how the algorithm works. From the blurb: 'The advent of quantum computers that can run a routine called Shor's algorithm could have profound consequences. It means the most dangerous threat posed by quantum computing - the ability to break the codes that protect our banking, business and e-commerce data - is now a step nearer reality. Adding to the worry is the fact that this feat has been performed by not one but two research groups, independently of each other. One team is led by Andrew White at the University of Queensland in Brisbane, Australia, and the other by Chao-Yang Lu of the University of Science and Technology of China, in Hefei.'"

Comments

Not the end

[drabgah]

The quantum computer referenced in the summary managed the immense feat of finding the factors of the number 15. While it is true that factoring numbers of the magnitude used in cryptography is now a "matter of engineering", there are profound difficulties involved in scaling quantum computing. The fundamental problem is called "decoherence" and describes the tendency of quantum systems to become entangled with their environment, and the consequent loss of pure quantum states. The issues involved in quantum computation connect to deep issues of thermodynamics and entropy, and research on quantum computation has potentially great significance for fundamental physics. Cryptography may have to develop and implement new, extended standards as computational techniques evolve, but the encryption sky is not yet falling.

Re:I'm not sure how big of a deal this is.

[zippthorne]

...His velocity, however, is known precisely.

Elliptic curve cryptography

[4of11]

Elliptic curve public crypto does not rely on the difficulty of factorization, so this specific attack wouldn't affect it, but I don't know if there are applicable quantum computing attacks. Too bad software patents are such an issue for it in the US.

Re:Tor like oatmeals!

[Anonymous Coward]

The Magic Words are Squeamish Ossifrage

Re:Yeah, but...

[Selfbain]

Depends on the observer.

I work in the field and i have to comment,

[drolli]

that it will be a really long time before QC are cheaper in terms of factorizing numbers than the equivalent classical machine. If they work at all. The common beliefs about the different QC other implementations in the field usually are said to be

-NMR: Most advanced no decoherence, but severe scalability problems. Nobody knows if they can ever put more than 10 qubits (
-Quantum Dots: Nice but Semiconductors have a hell of excitaions and decoherence
-Spintronics: Interesting, but it will take a time until it is under control
-Ions: well advanced, good control, some scalability problem (not necessarily IMHO)
-Atoms: advancing (-> Atom Chip), could be fine
-Superconducting qubits: Right now decoherence problems, which may be solved.

Re:More like the Chinese gov

[Anonymous Coward]

Does anyone know the name of the Chinese equivalent of the CIA, KGB and MI6?

Jet Li.

Just RSA, actually

[geekgirlandrea]

*sigh*

This doesn't break "public-key cryptography". Even if you could build a Shor-factorization machine big enough to use against real-world keys (and that's a *big* if), it's only good against RSA. Elliptic-curve cryptosystems, for example, would be entirely unaffected. In general, the question of whether general-purpose quantum computers would break all public-key cryptography is a really hard one. It's equivalent to whether there are any trapdoor one-way functions which are in P but with inverses not in BQP. Even the existence of non-trapdoor one-way functions is still an open question; they would have to have inverses in , and proving that would also imply P != NP. All the existence of Shor's algorithm really shows about that problem is that there is at least one problem, integer factorization, which is in BQP but (probably) not in P.

Anyway, it's a long way from running Shor's algorithm to factor 15 to being able to factor a 4096-bit RSA key. Remember that because of the no-cloning theorem you can't build a flip-flop for qubits, so quantum circuits are all combinatorial logic. Applying Shor's algorithm to real-world RSA keys would require building a complete modular exponentiator combinatorially out of quantum logic gates, wide enough to deal with the biggest key sizes practical for anyone to use (and the cost of RSA encryption/decryption only scales linearly with the key size). We couldn't even build that out of regular non-quantum logic.

Re:Just RSA, actually

[geekgirlandrea]

Well, put briefly, the existence of secure public-key cryptography is equivalent to the existence of trap-door one-way functions. Suppose we have a public-key cryptosystem consisting of an encryption function E and a decryption function D, with a secret key Ks and a public key Kp. Let p be the plaintext and c be the ciphertext. Then, c=E(p,Kp) (we encrypt the plaintext with the public key to get the ciphertext), and p=D(c,Ks) (we decrypt the ciphertext with the secret key to get the plaintext back). Now, the public key Kp is known to an attacker, and so are the functions E and D, so in principle the attacker could do a brute-force search of the keyspace to find the secret key Ks corresponding to a given Kp using them. Thus, there exists another decryption function Dp using the public key rather than the secret key: p=Dp(c,Kp). To prove the cryptosystem is secure, we have to prove there's no way to compute Dp efficiently.

Now, a one-way function is exactly what we need. A one-way function o is a function that is easy to compute (can be done in polynomial time), but its inverse is hard (can't be done in polynomial time). It's fairly easy to prove that if a function is in P, then it's inverse must be at most NP. Well, strictly speaking P and NP are for decision problems, so we should refer to FP and FNP. If it's in FP, then the output can be at most polynomially large in the input length, so we can invert by doing a brute-force search of all possible inputs shorter than that bound, and a nondeterministic Turing machine can check them all in parallel. Thus, one-way functions exist only if P != NP (which is equivalent to FP != FNP). Otherwise anything we could compute efficiently we could also invert efficiently. Actually, it turns out that the inverses of one-way functions must be UP (unambiguous polynomial time). That is, there exists a nondeterministic Turing machine to compute them such that for any accepting input, exactly one path accepts (general NP problems can have more than one accepting path). It's believed, but not proven, that UP is smaller than NP; no NP-complete problems are known to be in UP. Thus, the existence of one-way functions is stronger than P != NP, since it also implies UP is strictly larger than P.

Of course, we need to be able to decrypt efficiently if we know the secret key, so we need something more specific than a one-way function: a trap-door one-way function, for which there is an algorithm to compute the inverse in FP if we have some additional piece of information, the trap-door. In complexity-theoretic terms, what we need for public-key cryptography is a family of trap-door one-way functions (functions in P with inverses in UP) parametrized by the public keys, and the secret keys are the corresponding trap doors (inverses in P if we also have the secret key as an input). A few functions, like RSA or discrete logarithms, really look like what we want, but none have ever been proved to be, and a proof that they are would necessarily include P vs. NP as a special case as describe above.

Anyway, BQP is the complexity class of problems tractable on quantum computers, analogous to P for Turing machines. It's a bounded error probability class, like BPP. BQP is the set of all decision problems which have an algorithm on a quantum computer that computes them in polynomial time with an error probability less than one-third (this bound is an arbitrary choice, we can reduce the error probability exponentially with a linear number of repetitions, and the class would be identical for any probability less than one-half). BQP is necessarily at least as large as P, and the existence of Shor's algorithm shows that factorization is in BQP, so BQP is probably strictly larger than P (although it hasn't been proven that you can't factor in P). NP probably contains problems that are not in BQP (no NP-complete problem is known to be in BQP), but proving this is equivalent to proving P != NP. So, if we assume quantum computers are feasible to build on a practical scale

Re:not quite...

[smallfries]

Although you are theoretically correct what you have said is wrong in practice. If I want to run a classical algorithm on a larger piece of data then I can just simulate a larger computer (to the extent that I page things in or out of memory, implement 64bit operations in 32bit etc). For a quantum computer I need a bigger computer. I can't simulate a 8-qubit machine on a 4-qubit machine with just a polynomial slowdown.

I can't read the actual article at home so I don't know how large their machine is. Shor's algorithm has actually been run on a 4-qubit machine before so the summary is incorrect. I believe that the number they factored was 15. The point being that I need a quantum machine large enough to factor the RSA number. As building a 8-qubit machine is not as simple as slapping two 4-qubit machines together (because of problems with quantum coherence) there will always be a state-of-the-art for how large a Quantum Computer can be, and public crypto with keys significantly larger than that will be safe until a larger machine is developed. Sort of a faster version of the battle between cryptographers and cryptoanalysts that we see at the moment.

You'll notice that nobody made the same claims when EPFL sieved a 1024-bit number recently - instead everyone said use larger keys. The situation is likely to be the same as Quantum Computers increase in size. Lastly, not all public key crypto is shafted, only things that rely on factorisation as a problem. ECC will be quite safe until (if?) somebody develops a quantum algorithm for discrete logs.

Disclaimer: I don't do research in quantum - I work in cryptography, but the quantum guys have an office down the corridor and occasionally I understand what they are talking about. Ashley, don't beat me around the head for getting the details wrong :)

trapdoor one-way permutation candidates

[0ptix]

There seems to me some (a lot?) of FUD mixed up in this article. (surprise surprise...)

It starts out with the fact that public key encryption relies on the existence of one trapdoor one-way functions. Now in practice we mainly instantiate these functions with the RSA function (f_e(x):=x^e mod n with trapdoor p,q such that pq=n). But there is no reason to believe this is the only possible example of trapdoor OWF! Admitedly in the 80s when this concept was first being explored there were quite a few failures when trying to base implementations on NP-Complete and/or NP-Hard problems (think knapsack for example). But since we already had RSA with all it's nice properties (efficiency, elegance and simplicity) the research community was not overly motivated to find others.

There have been and to this day still are other lines of research. Take Ajtai and Dwork's work in the direction of basing PKE on worst-case hardness of the shortest vector problem (SVP) or Micciancio's work on generalizing the knapsack problem such that average-case hardness of approximating the answer can be reduced to worst-case hardness of certain lattice based problems.

Another general direction has been to come up with groups and fields over which solving the DLP is difficult. (For example torus-based crypto and generalized Jacobian groups). AFAIK for most of these candidates there are no (known efficient) reductions from the DLP problem over Z_p or elliptic curves to the DLP in these new groups. Thus it is not immediately clear how or if Schorr's algorithm would break such systems.

In any case there is reason to believe that there can not be (or that we can't find) good candidates for trapdoor OWFs in the quantum computational model. After all there is such a thing as Quantum P and Quantum NP. Though the inequality of these set's of problems doesn't directly imply the existence of quantum trapdoor OWFs it is a good indication there of.

So basically the message is : Relax! The PKE world is by no means on the brink of an apocalypse. At most (and best in my opinion) we're in for a bout of some serious foundations research. to me that just sounds like more funding for applied mathematicians and complexity theorists from various corners and a WHOLE bunch of new candidates and interesting results. :-) i'm down with that.