Time Running Out for Public Key Encryption 300
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.'"
That is nothing (Score:4, Funny)
Comment removed (Score:5, Funny)
Re:That is nothing (Score:5, Funny)
Re: (Score:2)
I'm not sure how big of a deal this is. (Score:2)
Well-funded governments or criminal organizations could take advantage of this, but I guarantee you that J-random-cracker in his basement is NOT going to be able to build a quantum computer.
This poses a big threat to governments, and possibly financial institutions, but not individuals. Nobody is going to spend millions of dollars to build a working quantum computer just so they can steal your credit card number. If I had a quantum computer I would use it to blackmail entire governments, not harass the li
Re: (Score:3, Insightful)
Re: (Score:3, Funny)
Re:I'm not sure how big of a deal this is. (Score:5, Funny)
Re: (Score:3, Funny)
From the account of witnesses, Police believe the man may be traveling inside a box and there is a possibility he is now dead, and alive.
Re: (Score:2)
Most governments will have the "funds" for this, should they have the interest, I'm not sure "well funded" has anything to do with it. The knowledge for building monster computers from PC hardware ("imagine a Beowulf cluster of those...") is public these days, and a team of mercenary computer scientists is a financial drop in the bucket. Our "enemies" such as Russia, China, and Iran have almost certainly already been working h
Re: (Score:3, Interesting)
Re: (Score:3, Insightful)
This poses a big threat to governments, and possibly financial institutions, but not individuals.
As an individual, I consider threats to governments and financial institutions "a big deal".
Re:I'm not sure how big of a deal this is. (Score:5, Informative)
See http://en.wikipedia.org/wiki/Numbers_station [wikipedia.org]
The one-time pad is in no danger of being broken by quantum computers or anything else because it's provably unbreakable. (Unless there is operator error, and sometimes that's the case)
The Good Guys(tm) want to have this so that they know what The Bad Guys(tm) might have, and that way they can change their systems before they are cracked. I could imagine some crime syndicate paying the millions for a working quantum computer and the PhD talent to run it so that they could break into international banking systems.
On the flip side, pressing exactly two HD-DVDs with random data, and distributing these to your bankings sites for the most sensitive information is getting more and more cost effective.
Meet Guido (Score:2)
Well... (Score:4, Insightful)
What this does mean is that there's going to be a lot of money to be made replacing public-key cryptograhy in custom code ala Y2K.
Re: (Score:2)
trapdoor one-way permutation candidates (Score:5, Informative)
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 [acm.org] of basing PKE on worst-case hardness of the shortest vector problem (SVP) or Micciancio's work [psu.edu]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 [uci.edu] and generalized Jacobian groups [uwaterloo.ca]). 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.
Non-subscription link (Score:4, Informative)
Yeah, but... (Score:2)
Re:Yeah, but... (Score:5, Funny)
Big numbers (Score:2)
Not the end (Score:5, Insightful)
Re:Not the end (Score:4, Funny)
Re:Not the end (Score:4, Insightful)
Re: (Score:3, Interesting)
What does the article actually say? (Score:2)
post-quantum cryptography (Score:5, Informative)
"PQCrypto 2006: International Workshop on Post-Quantum Cryptography"
http://postquantum.cr.yp.to/ [cr.yp.to]
From The link:
Very cool (Score:2)
It's also very good that the cutting edge of this technology is (presumably) being done and reported on publicly, so people will know if and when they can no longer protect their communications using certain methods.
Re: (Score:3, Funny)
I will be passing all my public keys through two slits and keeping one of them under observation at all times from now on. That should keep me safe from quantum computers.
Elliptic curve cryptography (Score:5, Informative)
Re: (Score:2, Informative)
Re:Elliptic curve cryptography (Score:4, Informative)
new decryption methods == new encryption methods (Score:2, Insightful)
Re: (Score:2)
Necessity is the mother of invention.
Right?
I think we all already knew this.
Re:new decryption methods == new encryption method (Score:2)
I don't think our current economy would do well if it had to go several centuries before finding a new method of encryption. Fortunately for us, there are several well-known encryption schemes that do not rely on the difficulty of product-of-large-primes fa
Of course the obvious solution... (Score:2)
No big deal (Score:4, Insightful)
Not PK encryption per se, the RSA implementation (Score:4, Insightful)
I work in the field and i have to comment, (Score:5, Informative)
-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.
Quantum physics giveth... (Score:2)
sigh (Score:5, Funny)
What Codes? (Score:3, Insightful)
I'm skeptical (Score:5, Informative)
There have been quite a few different methods of quantum computing developed that take advantage of several types of quantum processes in nature. I worked on bulk-spin-resonance QC as a research assistant at MIT.
To the best of my knowledge, every method so far developed runs into coherence and noise limitations that make it very difficult to scale them up. It's usually not too hard to build a 3- or 4- qubit quantum computer, but scaling up the size seems to itself have an exponential characteristic to the problem. Basically, it's very hard to build a practical quantum computer that works on the scale necessary to factor even modest sized numbers. The engineering challenges to make any of these methods at all practical are bafflingly hard - the underlying science and math are pretty straightforward on the other hand, and the algorithms are undoubtedly cool as hell.
I understand these days the interesting work is on trapped-ion approaches and semi-conductor approaches.
Anyway, Shor's algorithm has been around for years. The theory behind QCs is fairly well understood, the experimental difficulties are huge.
Basically, unless this represents a real breakthrough, i.e. a technique that is not just scalable in theory but can be demonstrated practically to be linearly more difficult to scale up the number of qubits, then it's not a breakthrough that anybody needs to worry about yet.
Without seeing this article's full text though, it's hard to really know, but I gather optical approaches have been tried before and haven't gotten any further than anybody else has.
Therefore... Quantum Computing Illegal in US? (Score:2, Insightful)
the inverse? (Score:3, Interesting)
Yes but, (Score:2)
Just RSA, actually (Score:5, Interesting)
*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 [caltech.edu] but with inverses not in BQP [caltech.edu]. 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. [caltech.edu]
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 (Score:4, Insightful)
SC doesn't work against things in class NP-COMPLETE, but it's quite effective against many problems that are in NP but less than NP-COMPLETE. In fact, I'm scratching my head trying to find one that SC doesn't work against.
Also, the total number of qubits required is twice the number of bits in the key. While nontrivial, it is not as ridiculous as you're making it out to be. It's possible we'll have this in twenty years. Less, if engineering breakthroughs go our way; more, if they don't.
Re:Just RSA, actually (Score:5, Informative)
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
Brain's Alzheimer disease algorithm. (Score:2, Funny)
So you're saying that... (Score:2)
Thssag!
Workings of the system (Score:2)
1. Put box on computer
2. Let it randomly generate and test primes
In this state the computer virtually exists in an infinite number of states of which some will have randomly generated the secret primes.
The problem however lies within the observer;
3. Take off the box and the infinite number of states collapse in only one observed state; which is very unlikely to be the computer-state that hit the secret primes
The solution to this problem is found to b
Nonsense Story Title (Score:2)
Y2K!! (Score:2)
Storage will beat Crypto (Score:5, Interesting)
What are the new DVD formats getting? 50GB of data RW? Will options up to 250GB or so of RW storage?
How much information do you really, really need to hide, anyway? Maybe a couple of megabytes of financial-related data per day? A one-time pad on a DVD should provide you with centuries of totally secure communications.
So you sign up for your bank account. The bank snail mails you a 10GB random noise memory stick. You add it to your 10TB secure random storage system and you and the bank can talk for the rest of your life without anybody else being able to listen in.
FACTS about quantum and public-key crypto (Score:5, Informative)
Here are some facts to fix the clutter:
1. Shor's algorithm works on quantum computers and can factor integers in polynomial time. This breaks all public-key systems that depend on the hardness of factoring, including RSA, Rabin, Paillier, and XTR.
2. A different version of Shor's algorithm also computes discrete logarithms (again, in poly time). This breaks all public-key systems that depend on the hardness of discrete log, over *any* cyclic group. This includes ElGamal, even over "exotic" groups like those associated with elliptic curves.
3. Nevertheless, factoring and discrete log are different beasts and are not known to be equivalent to each other. Still, Shor's algorithm (in different versions) solves them both.
4. Shor's algorithm does not yet break all known public-key cryptosystems. Systems based on lattices, for example, do not appear to be affected as of yet. These include Ajtai-Dwork and a couple systems by Regev. NTRU is based on lattices, but is based on some not-so-natural assumptions (i.e, the assumption that "NTRU is secure").
5. Public key encryption is (probably) *not* equivalent to trapdoor permutations (or even trapdoor one-way functions). TDPs are a much stronger notion and are not strictly needed to do secure public-key encryption. For example, ElGamal and lattice-based systems are not based on trapdoor primitives per se.
Re: (Score:2)
Re:bigger keys? (Score:5, Informative)
For the best known classical factoring algorithms, doubling the key length will basically multiply the number of operations required to factor by itself. For Shor's algorithm, doubling the key length might multiply the time to factor by four, but given how quickly computers get faster, that's basically worthless.
Re:bigger keys? (Score:5, Interesting)
Re: (Score:3, Informative)
I was trying to address the specific point of the parent poster (that quantum computers gave instant results), not the difficulties of using Shor's algorithm in a practical setting to break cryptography.
There seems to be a general belief that quantum computing can try an algorithm against all possible inputs and give you the best/correct input in one iteration, which is just absolutely not true.
Re:bigger keys? (Score:4, Insightful)
plus, cryptography is very resource-intensive, growing exponentially with key size. there comes a point when it's just not practical to use a key that large, as it will take too long to encrypt/decrypt/generate the key.
not quite... (Score:2, Informative)
Re: (Score:3, Informative)
Fortunately, symetric keys are still fine, Quantum Computers can calculation square roots faster, but this only halves the execution time, which is easily accounted for by double the key size. Even with a Quantum Computer cracking AES 512, or 2048 is intractable.
Re:not quite... (Score:5, Informative)
No. With classical algorithms, RSA encryption and signature verification are O(n^2), while RSA decryption and signing are O(n^3).
and cracking is [considered] exponential in the length of the key
No. All modern factorization algorithms are subexponential; this is why a 1024 bit RSA key is roughly as secure as an 80 bit symmetric encryption key.
Re: (Score:2)
you are correct; i was thinking of the faster multiplication algorithms (the standard one would be O(n^2) indeed) and didn't consider speed of decryption.
s/linear/polynomial/g
s/exponential/non-polynomial/g
there
Re:not quite... (Score:5, Informative)
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
Re: (Score:3, Interesting)
Factoring and discrete logs are codependent on each other being hard problems. Either one can solve the other. I'm not familiar enough with ECC to know if being able to solve regular discrete logs necessary breaks it; but if so, then factoring breaks it too.
Re: (Score:3, Informative)
ECC with correctly chosen parameters cannot be mapped/isomorphic/whatever to the appropriate finite field. However that doesn't mean that someone might develop a technique to do so with currently s
Shor also has a quantum discrete log algorithm (Score:3, Interesting)
Shor also describes a quantum algorithm for solving the discrete log problem in polynomial time, although I don't see any references for anyone having implemented it in a physical experiment like this one with quantum factorization.
See Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarit [arxiv.org]
Re: (Score:3, Interesting)
Re: (Score:2)
The only catch might exist if there is an algorithm for a quantum computer to find a [secret, shared] key that produces a plaintext in a human language. That's probably the only way to break the OTP (aside from stealing the key.) However this is also easy to obscure - roughly speaking, create a ZIP file and apply a OTP to it. If the OTP's plaintext is not recognizable as such there is no way to accept the key and start working on the second layer
Re:bigger keys? (Score:5, Informative)
The whole point of a One time Pad is that there is no such thing as an algorithm to crack it without quite some information in addition to the ciphertext. The beauty of a One Time Pad is that you can crank through every possible key, but that doesn't get you anything. Sure, you may wind up with some keys that take the ciphertext and make perfectly intelligible English out of it, but there are an enourmous number of messages of a given length, and any of them could be an equally valid. So, cracking a message properly encrypted with a OTP basically amounts to creanking through every possible bit combination the same length as the message, and then guessing arbitrarily which one is the "solution."
In practice, the only time OTP's get broken is when they are used wrong. For example, a message is enciphered with a particular pad, transmitted, and then through a beaurocratic fuckup, the same message also gets transmitted as plaintext. Then, somebody fucks up and uses the same OTP (now a TTP!) on another message. the cryptanalyst gives the old captured OTP a whirl and gets lucky. The OTP is only vulnerable to the CHF algorithm. (Cascading Human Fuckups.)
Re: (Score:2)
Re: (Score:3, Insightful)
Properly applied, one-time pad encryption is not crackable. Ever. Using any amount of technology or resources.
Unless you already know the key, any message of the proper length could be the plaintext you're looking for. Even a huge quantum computer wouldn't be able to tell that the ciphertext "VPx\PztI-H&jAL" decrypts to "attack at dawn" and not "attack at dusk" or "retreating now". (or even "yay ice cream!") It might seem like this would break down with degenerate plaintext (such as signed messages), b
Re: (Score:3, Insightful)
Anywho, it is said that AES-256 should be strong enough to withstand attacks by quantum computing. Of course, by definition, one time pads are resistant against every attack, as long as the keys are really kept safe. The reason why they are not commonly used is the size of the keys (as long as the plain text) and key di
Re: (Score:2, Insightful)
Re: (Score:3, Insightful)
Re: (Score:3, Interesting)
it's a bit like nuclear weapons, in that you can pretty much "know" how a bomb works, but even if you had detailed plans, it's pretty much only governments who can build them.
I'm actually somewhat surprised that governments haven't passed laws banning the construction of quantum computers except under very tightly controlled circumstances. Kind of like how the ciphers themselves used to be classified as "munitions" in the United States.
Re: (Score:2, Insightful)
by the way, I'm just making this up, but I bet you believed me. Sad state of affairs we're in.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
down with the fearless inevitability of a pack of ravenous velociraptors.
Re:More like the Chinese gov (Score:5, Insightful)
Yeah, the Chinese government is the only government that would like to do that.
Re:More like the Chinese gov (Score:5, Funny)
Think of it Marty. No more rich people, no more poor people, everybody's the same
Re:More like the Chinese gov (Score:4, Interesting)
Re: (Score:2)
Re:More like the Chinese gov (Score:5, Funny)
Re: (Score:2)
The name of the Chinese secret service is so secret you can't even pronounce it.
Umm, well, you probably can't pronounce most Chinese words...
Re: (Score:3, Funny)
Re: (Score:2)
SO what if they break the encryption? (Score:3, Interesting)
Take this example. Person A sends a message to person B. Every tenth character person A switches to a new key. Person B, who knows what keys are in use, but not the order for today, collects the message, and runs their key 'recipes' on it until one makes sense of the first ten blocks, being enough to identify which sequence of keys is in use. Person B then d
Re:SO what if they break the encryption? (Score:5, Insightful)
Example, vising gmail and checking out the certificate Google (which is pretty security conscious) has a key valid from 05/03/2007 through 05/14/2008 (over a year).
In order to trivially look at EVERY session encrypted over gmail an attack would need to crack that key ONCE. Google is pretty good by the way, there are certs in existence for far longer than 1 year out on the intraweb.
It is true that every session uses a symmetric cypher with a different session key... but how do you think the keys are exchanged? Once the PKI encryption is broken, the attacker will be able to read the session key in plaintext and decrypt the entire session. And this is for every single person using Google's certificate. That is why cracking PKI is so profitable, the long-term nature of the keys means once it is cracked, you have free reign for a long time.
Re:SO what if they break the encryption? (Score:5, Insightful)
Re:why? (Score:4, Funny)
Hmm. I see what you mean.
Re:More like the Chinese gov (Score:5, Funny)
Jet Li.
Re:Tor like oatmeals! (Score:5, Interesting)
Re:Tor like oatmeals! (Score:4, Informative)
Re: (Score:2)
Anyone who modded this up as "Informative" needs to think about what the word means.
Re: (Score:3, Interesting)
Someone you need a shared secret to be passed the first time. If there is alway someone listening it will not work.
But I am assuming your moving around and no one can intercept all conversation, but more like the case of a Credit card wh