Forgot your password?
typodupeerror
Security Encryption Supercomputing Science

Time Running Out for Public Key Encryption 300

Posted by Zonk
from the interesting-times-are-upon-us dept.
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.'"
This discussion has been archived. No new comments can be posted.

Time Running Out for Public Key Encryption

Comments Filter:
  • by MyLongNickName (822545) on Thursday September 13, 2007 @02:07PM (#20591569) Journal
    I have developed an algorithm to efficiently decrypt ROT-26. You will need to use it to read this encrypted message.
  • 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)

      by jellomizer (103300) *
      Well Students of colleges (Perhaps undgrads, or people pretending to be an actual student) can have access to such systems. 10-20 years down the line when such systems become obsolete they get in the hands of the public. Or engineering Quantum Computers becomes more feasable then everyone may have one.
    • Re: (Score:3, Funny)

      "In other news, man with quantum computer reported missing...."
    • Well-funded governments or criminal organizations could take advantage of this...

      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)

      by brunascle (994197)

      Nobody is going to spend millions of dollars to build a working quantum computer just so they can steal your credit card number.
      with a universal cryptography-breaking-device, there are much bigger targets than individuals. if you find the right target, it could be very profitable.
    • Re: (Score:3, Insightful)

      by Vellmont (569020)

      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".
    • by Maximum Prophet (716608) on Thursday September 13, 2007 @02:41PM (#20592253)
      Governments still use one-time pads for the really sensitive stuff.

      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.
  • Well... (Score:4, Insightful)

    by morgan_greywolf (835522) on Thursday September 13, 2007 @02:08PM (#20591601) Homepage Journal
    It doesn't necessarily mean the end of public key cryptography, it just means we'll have to come up with something other than prime factoring to compute the keys.

    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.
    • Well, the problem is that Shor's algorithm can solve discreet logs in any group. This makes ECC unsafe as currently implemented. No one has come up with secure methods that will not fall to Shor's algorithm.
      • by 0ptix (649734) on Thursday September 13, 2007 @04:05PM (#20593859)
        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 [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. :-) i'm down with that.
  • by Anonymous Coward on Thursday September 13, 2007 @02:12PM (#20591675)
    http://www.huliq.com/34160/qubits-poised-to-reveal-our-secrets [huliq.com] seems to be a copypasta of the article.
  • Yeah, but who filed the patent first. That's all that matters.
  • Hmmm, guess I'd better start using a 1024 septendecillion or larger bit key.
  • Not the end (Score:5, Insightful)

    by drabgah (1150633) on Thursday September 13, 2007 @02:17PM (#20591801)
    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.
    • by Anonymous Coward on Thursday September 13, 2007 @02:38PM (#20592185)

      The quantum computer referenced in the summary managed the immense feat of finding the factors of the number 15.
      ...well come on then, tell us, what are they?
    • Re:Not the end (Score:4, Insightful)

      by blueg3 (192743) on Thursday September 13, 2007 @03:33PM (#20593195)
      Factoring a four-bit number on a quantum computer requires quite a lot of qbits. You require 20 qbits just to store a four-bit number, and more just to execute the algorithm. This is a big improvement on the few-qbit machines previously made. At this point, while decoherence is still a large barrier, it's solely an engineering barrier, and one should expect it to last for too long. (Where "too long" is in physics terms. You'll probably be okay for 20 years or so.)
      • Re: (Score:3, Interesting)

        by StikyPad (445176)
        So, just like with classic attacks, can't we just increase the keyspace to stay ahead of the quantum curve indefinately? The only real problem I see is that passwords will eventually be obsolete, but that's essentially the case already. Passphrases will help to some extent, but again, it's just a matter of time before the computational ability outstrips the capacity to remember (and patience to enter) a sufficiently long and/or incoherent passphrase.
  • The first article linked to in the summary requires a subscription to read anything more than the synopsis.
  • by Spy der Mann (805235) <spydermann.slash ... Hl.com minus cat> on Thursday September 13, 2007 @02:18PM (#20591821) Homepage Journal
    I googled (surprise!) and found this result:

    "PQCrypto 2006: International Workshop on Post-Quantum Cryptography"
    http://postquantum.cr.yp.to/ [cr.yp.to]

    From The link:

    Will large quantum computers be built? If so, what will they do to the cryptographic landscape?

    Anyone who can build a large quantum computer can break today's most popular public-key cryptosystems: e.g., RSA, DSA, and ECDSA. But there are several other cryptosystems that are conjectured to resist quantum computers: e.g., the Diffie-Lamport-Merkle signature system, the NTRU encryption system, the McEliece encryption system, and the HFE signature system. Exactly which of these systems are secure? How efficient are they, in theory and in practice?

    PQCrypto 2006, the International Workshop on Post-Quantum Cryptography, will look ahead to a possible future of quantum computers, and will begin preparing the cryptographic world for that future.
    • by Kythe (4779)
      Very interesting to know there are other algorithms which might resist quantum computing attacks.

      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)

      by Intron (870560)
      They have also left out the One Time Pad system - still unbreakable.

      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.
  • by 4of11 (714557) on Thursday September 13, 2007 @02:19PM (#20591843)
    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: (Score:2, Informative)

      by Anonymous Coward
      Elliptic Curve encryption relies on the hardness of the discrete logarithm in an elliptic curve group. Unfortunately, I believe Shor's algorithm can also be used to solve discrete logarithms in arbitrary groups, so this method is no better than RSA when quantum computing becomes sufficiently advanced.
    • by elandqui (880910) on Thursday September 13, 2007 @03:09PM (#20592691)
      Actually, quantum computing attacks do exist for elliptic curve crypto, which relies on the elliptic curve discrete log problem (ECDLP), as Bernstein mentioned in the Post-Quantum Crypto conference list. As that blog post noted, Shor's Algorithm essentially boils down to finding the order of a subgroup of the multiplicative group (Z/(nZ))^*, where n is the number to factor, and the rest is easy. That is precisely what you need to do in the ECDLP: find the order of the subgroup generated by a point on the curve. It's a little different in practice of course, since you need to implement elliptic curve arithmetic, but the idea is the same.
  • This means that people will come up with new encryption methods that I couldn't possibly imagine (not much of a stretch). Based off these newly powerful methods people will find new impregnable methods. Sort of like how when people came up with the idea of wooden shields, someone came up with a way to pierce them so someone came up with metallic armor and then someone came up with the idea of a combustion-powered missile (gun) and someone came up with Kevlar and so on...
    • So what you're saying is...

      Necessity is the mother of invention.

      Right?

      I think we all already knew this.
    • That's true. However, in the cases you mention, the exploit of the armor came out several centuries before the improvement in armor that made that exploit less dangerous. (And the newer armor is only _resistant_ to the attack, not truly attack-proof.)

      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

  • Is to just use quantum encryption whenever transmitting encrypted data... supposedly, that's unbreakable (or at least not breakable without alerting the sender or receiver that you broke it), right?
  • No big deal (Score:4, Insightful)

    by jd (1658) <imipak&yahoo,com> on Thursday September 13, 2007 @02:24PM (#20591961) Homepage Journal
    RSA uses primes. This leaves the ones that don't: HFE, NTRU, ECC, XTR, Paillier, ElGamal, ....
  • by ishmalius (153450) on Thursday September 13, 2007 @02:25PM (#20591969)
    The general handshaking mechanism itself is not in danger. It is the prime factor-based RSA algorithm. There might be other key algorithms in danger as well, but this doesn't reflect on the PK framework.
  • by drolli (522659) on Thursday September 13, 2007 @02:27PM (#20591991) Journal
    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.
  • ...and quantum physics taketh away. Looks like it'll be a race between quantum computing and quantum cryptography to see whether we're all left with a gap where everyone's vulnerable...
  • sigh (Score:5, Funny)

    by Ant P. (974313) on Thursday September 13, 2007 @02:32PM (#20592091) Homepage
    I finally went and figured out gpg just this week and it's already about to be obsoleted...
  • What Codes? (Score:3, Insightful)

    by segedunum (883035) on Thursday September 13, 2007 @02:33PM (#20592095)

    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.
    It might just show how sadly cynical I am regarding many companies' attitudes towards security, but I looked at that sentence and and thought "This would actually make a difference?"
  • I'm skeptical (Score:5, Informative)

    by Fnkmaster (89084) on Thursday September 13, 2007 @02:33PM (#20592101)
    This sounds like some serious breathless bullshit to me.

    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.
  • So can I guess an American university has not been able to do this because they would be put in jail (DMCA). "I'm sorry we can't cure your cancer because the technology used to do this could circumvent digital property rights and encryption algorithms."
  • the inverse? (Score:3, Interesting)

    by j00r0m4nc3r (959816) on Thursday September 13, 2007 @02:48PM (#20592359)
    Can quantum computers be used to create encryption keys that other quantum computers cannot solve in linear time? Perhaps computers will someday each include a QPU (quantum processing unit) that would be dedicated to performing such tasks.
  • Just RSA, actually (Score:5, Interesting)

    by geekgirlandrea (1148779) <andrea+slashdot@persephoneslair.org> on Thursday September 13, 2007 @02:50PM (#20592399) Homepage

    *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.

    • by rjh (40933) <rjh@sixdemonbag.org> on Thursday September 13, 2007 @04:52PM (#20594747)
      Superpositional computation works very nicely against ECC and the discrete logarithm problem.

      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.
  • I'm going to use my brain's Alzheimer disease algorithm to encrypt everything since in a few years I won't able to remember anything and therefore no one would be able to get it, ever. Now where the heck I put my car keys at...
  • Pretty soon, even if I make sure the cute little lock (ah! there it is!) is on on my browser, someone will be able to klaJADf llkqjwer wlkertuidf hjaidf adfy ajsdf yadsfhjm, werl sdfi iughj ajkajhsdfdk ?

    Thssag!

  • How the quantum computer solves the public key encryption:

    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
  • Not all PKK is based on prime numbers. Take for example ElGamal, which is proovablu hard to break. Also these demo "quantum computers" may just not scale up far enough to break any real keys based on prime numbers. In fact that is quite likely.
  • I'm back in 1999 again... oy.
  • by DanielMarkham (765899) * on Thursday September 13, 2007 @04:09PM (#20593931) Homepage
    Cheap storage will eventually destroy any kind of crypto/anti-crypto technology.

    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.
  • by cpeikert (9457) <cpeikert@NOSpAm.alum.mit.edu> on Thursday September 13, 2007 @10:16PM (#20598391) Homepage
    I am a professional research cryptographer. There are many misstatements in the comments so far (what else should one expect, it's Slashdot.....)

    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.

Somebody ought to cross ball point pens with coat hangers so that the pens will multiply instead of disappear.

Working...