Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
Security Science

1978 Cryptosystem Resists Quantum Attack 185

Posted by samzenpus from the built-to-last dept.
KentuckyFC writes "In 1978, the CalTech mathematician Robert McEliece developed a cryptosystem based on the (then) new idea of using asymmetric mathematical functions to create different keys for encrypting and decrypting information. The security of these systems relies on mathematical steps that are easy to make in one direction but hard to do in the other. Today, popular encryption systems such as the RSA algorithm use exactly this idea. But in 1994, the mathematician Peter Shor dreamt up a quantum algorithm that could factorise much faster than any classical counterpart and so can break these codes. As soon as the first decent-sized quantum computer is switched on, these codes will become breakable. Since then, cryptographers have been hunting for encryption systems that will be safe in the post quantum world. Now a group of mathematicians have shown that the McEliece encryption system is safe against attack by Shor's algorithm and all other known quantum algorithms. That's because it does not depend on factorisation but gets its security from another asymmetric conundrum known as the hidden subgroup problem which they show is immune to all known quantum attacks."
This discussion has been archived. No new comments can be posted.

1978 Cryptosystem Resists Quantum Attack More

1978 Cryptosystem Resists Quantum Attack

Comments Filter:

  • Hidden subgroup problem is under active research (Score:5, Informative)

    by da cog ( 531643 ) on Wednesday August 18, 2010 @03:50PM (#33293834)

    It is worth noting that solving hidden subgroup problem is a subfield of quantum computing that has been active for a while. Although we can't figure out how to solve it in general, we can solve specific instances of it; for example, I think that factorizing is one such instance.

    Thus, I suspect that we will eventually figure out a way to break this encryption. Even if we do, though, these mathematicians still get credit for giving us a new instance of the hidden subgroup problem to try and solve, which may give us additional insight into the extent to which the general problem can be solved by a quantum computer.

  • ElGamal?? (Score:4, Interesting)

    by neiko ( 846668 ) on Wednesday August 18, 2010 @03:51PM (#33293846)
    Would ElGamal also be immune since it's based on Discrete Logarithms?

  • conspiracy theory (Score:4, Interesting)

    by craftycoder ( 1851452 ) on Wednesday August 18, 2010 @03:51PM (#33293850)

    I wonder if "THEY" already have one of these quantum computers and are keeping a lid on it so they can snoop on the PGP of our enemies. Would it be possible to develop one of these in secrecy?

    • Re: (Score:2, Funny)

      by Anonymous Coward

      No. Nothing to see here.

    • If you want to test it (Score:5, Funny)

      by Atmchicago ( 555403 ) on Wednesday August 18, 2010 @03:57PM (#33293932)
      Send a bunch of encrypted e-mails containing questionable content and see if anyone comes knocking at your door. And be sure to not send any questionable content unencrypted, or to give any other reasons for them to show up.

      • Re:If you want to test it (Score:4, Funny)

        by fishexe ( 168879 ) on Wednesday August 18, 2010 @04:04PM (#33294050) Homepage

        Send a bunch of encrypted e-mails containing questionable content and see if anyone comes knocking at your door. And be sure to not send any questionable content unencrypted, or to give any other reasons for them to show up.

        But how will I know they're not just knocking at my door out of a desire to make my acquaintance?

      • Re:If you want to test it (Score:5, Interesting)

        by Anonymous Coward on Wednesday August 18, 2010 @04:36PM (#33294402)

        Even then, they would probably spend a long time creating other circumstances in which to pick you up that would give plausible deniability as to how they caught on.

        One can google one's own references as I'm sort of lazy today, but a good example: the British had thoroughly broken Enigma during WWII, and at one point in the war knew where -every- German U-boat was. This created a dilemma for them: should they act on this information, and if so, how to do it without tipping their hand? If they just went and rounded up every single one, it would be pretty obvious that the code had been broken.

        What they did, according to the stories, is send out disinformation that a) they had ramped up production of a bunch of new long-range sea-spotting planes (they didn't, they only had the resources for a few); and b) these planes would fly near where they already -knew- the U-boat was, and 'spot it' (making sure it was obvious they'd been seen by the U-boat itself before flying back). The British were also careful not to find too many U-boats -- only the ones that they needed out of the way for critical operations. The Germans were convinced they just had really bad luck and were the victim of a very expensive and thorough patrol system by the British.

        If the guys in dark suits can crack PGP, Blowfish, etc. easily, they won't obviously act on it until they first get dirt on you via other means. :p

        • Re: (Score:2)

          by geggo98 ( 835161 )
          Better yet: The Brittish military created an urban legend, still famous today. They spread the word that eating carrots would improve vision and this would help them to spot submarines more easily. Although this was not done to cover that they broke Enigma, but to hide the fact that they invented radard. (Source [snopes.com])

          But the fact remains: To hide an invetion they used misinformation. And they did it so well, that it is still effective today.

      • That's a great idea. However, I'm not sure what you mean by 'questionable content'. Would you mind emailing me a few examples?

    • Possible, yes. Within the realm of imaginable possibility, no.

      • Re: (Score:2)

        by MagicM ( 85041 )

        Within the realm of imaginable possibility, yes. Within the realm of possible possibility, no.

    • Re:conspiracy theory (Score:5, Insightful)

      by woolpert ( 1442969 ) on Wednesday August 18, 2010 @04:04PM (#33294048)

      I wonder if "THEY" already have one of these quantum computers and are keeping a lid on it so they can snoop on the PGP of our enemies. Would it be possible to develop one of these in secrecy?

      Simplistically:
      If THEY bought out 50% of the researchers in the field, without arousing suspicion amongst those who turned down the offer, THEY would only have a 50% chance of having one first.

      More realistically,
      If THEY bought out a significant percentage of the researchers in the field, without arousing suspicion amongst those who turned down the offer, THEY would likely only be a few months / years (at best) ahead.
      And since the outlook on the QC front is rather bleak (in terms of a functional QC with any real power) the odds are strongly in favor of THEY not having squat.

      Especially in today's world it isn't like top researchers are fragmented and isolated. In the past it was possible for a governmental organization to use its greater vision to collect isolated researchers and be the first to introduce them to each other, magnifying their individual efforts. Today everybody who is anybody in these fields is at least aware of the others, if not following closely.

      • Re: (Score:3, Insightful)

        by Anubis IV ( 1279820 )
        Of course, your point doesn't consider the fact that the information sharing only goes one way. If THEY come up with something new, it's not always put back out into the field where it can be worked on by others and built upon. If THEY then find something new, THEY can be the first and only ones building upon it, and THEY do not have to sacrifice the ability to build on everything else that is coming out in the field as well. If that something new is a breakthrough concept, then THEY may be able to build a

        • Despite that, I seem to recall hearing stories of various encryption ideas the NSA developed in the '70s and '80s which weren't developed in the open until the late '90s and early 2000s (sorry, no citation).

          Of course, the late 90s and early 2000s were also when the serious speed and ease of communication issues were really addressed for the majority of researchers. So this fact, if anything, decreases the probability that a major player has managed a serious breakthrough that it's successfully kept hidden.

      • Re: (Score:3, Funny)

        by euxneks ( 516538 )

        Simplistically: If THEY bought out 50% of the researchers in the field, without arousing suspicion amongst those who turned down the offer, THEY would only have a 50% chance of having one first.

        Unfortunately, that same 50% chance collapsed to a more stable 0 once observed.

      • Re: (Score:2)

        by mrops ( 927562 )

        So what you are saying is that both the possibilities exist but we won't know until the cat is out of the box, where did I hear this before?

      • Real World:

        The NSA creates a front company called Quantum Research and funds it with black project money.

        DARPA creates a front company called Skynet Research Ltd and again funds it with black project money which is unreported to congress or the public.

        Both companies then hire CEO's from the public sector and give them no knowledge who they really work for. Quantum Research then gets "VC Money" from Skynet Research and goes on a hiring spree to develop quantum computers and hires and provides grants to 50% o

        • Re: (Score:3, Informative)

          by garyebickford ( 222422 )

          Only 50,000 sq. ft.? Times have changed, computers are getting smaller as they get bigger. Back in the day, that was a mid-size corporate server farm. Of course now, that's a lot more computing power.

          As for power, most secure computing facilities have their own power generation capability - if nothing else then just a motor-generator to assure clean power all the time. An old Army base's power system is not likely to be up to the standards of today for this purpose.

          There's a facility in the wilds east o

      • So the top five people in QC go to the international conference in Hawaii. Two of them have cooperated on a revolutionary new method, but since it's so new they have made some hints, but haven't been able to share any of the details with their colleagues but they will be doing a short intro at the conference.

        While they are in Hawaii they all 'happen to' all be winners of a conference-provided free sightseeing helicopter ride around Kauai. The tourists on the cliffs see that the helo, instead of staying clos

    • I think you are too optimistic. I do not mean that "THEY" have one (I do not know/not answer). The issue is that the statement should read:

      I wonder if "THEY" already have one of these quantum computers and are keeping a lid on it so they can snoop on the PGP of their enemies.

      After all, why limit it to only "ours" enemies after spending so much on it?

    • Of course we don't have any of the quantum computers the grey aliens ga... eh, I mean, we haven't come that far yet.

    • I wonder if "THEY" already have one of these quantum computers

      Pardon my lack of paranoia. It's because "they" are out to get you, not me.

    • Re: (Score:2)

      by gtall ( 79522 )

      Alright, damnit! You caught us, us being they. Our representatives will be contacting you shortly to see about how you came by this wonder.

  • New assymetric algorithms needed? (Score:5, Interesting)

    by mlts ( 1038732 ) * on Wednesday August 18, 2010 @03:58PM (#33293962)

    Symmetric algorithms are at least in their second generation (DES/Lucifer now AES) of production use, with decades of study and close analysis by a lot of good minds.

    Asymmetric algorithms are still essentially the first generation. Take RSA. It has been out for so long that its patent has expired more than 15 years ago. Even elliptic curve cryptography has been out at least 20 years, because the NeXT had it in NeXTStep 3.0 (and ended up getting pulled out of the OS due to ITAR).

    Even cryptographic hashes have been through a number of iterations. We had MD4, then MD5, then SHA-1, then SHA-256, now are looking for something to replace SHA, similar to how Rijndael replaced 3DES and DES.

    Maybe it is time to have a contest to have a standard asymmetric algorithm to replace RSA, DSS, and ElGamal? Something fundamentally designed to resist quantum computer attack as well as other threats.

    • Re: (Score:2)

      by Kjella ( 173770 )

      If we had a fundamental understanding of problems that aren't solvable by quantum computing, some insight into whether P != NP or not then maybe. But we don't and until then, RSA has a lot going for it - for one it's extremely simple. So simple we went through and did examples on paper, of course with reduced bits. People have been trying to find an algorithm to factor integers for the last 2000 years, it's not a trivial task using conventional computers.

      Shor's algorithm is impressive but it needs registers

  • It's "Caltech", not "CalTech" or "Cal Tech" (Score:3, Informative)

    by 3.1415926535 ( 243140 ) on Wednesday August 18, 2010 @04:09PM (#33294096)

    Seriously, Slashdot gets it wrong EVERY TIME. Next time, would it kill the editor to go to http://www.caltech.edu/ [caltech.edu] and, you know, read any of the words on the page?

    • Re: (Score:3, Funny)

      by Anonymous Coward

      Pidantic much? {sic}

    • Re: (Score:2)

      by lgw ( 121541 )

      Slashdot has editors? You do realize that the guys who post stories on the front page aren't editors in the classic sense, right? They have only the "content controller" role, and don't do the sort of editing one associates with "edited prose". Your UID is low enough that none of this should be news to you.

      Also, no one cares how you spell Cal Tech.

      • Well, they sure as hell have changed around the wording for every story I've ever had accepted. If that's not editing, what the hell is it?

  • Early connection? (Score:5, Interesting)

    by steve_bryan ( 2671 ) on Wednesday August 18, 2010 @04:31PM (#33294350)

    A sociological observation is that Shor was an undergrad at Caltech when McEliece was a professor there formulating the cryptosystem that would resist the quantum algorithm that Shor would develop years later. I wonder if knew each other.

  • Secure encryption (Score:2, Interesting)

    by SnarfQuest ( 469614 )

    The only encryption method I've heard about that has not been found to be breakable is the one time pad. This method has the problem of exchanging the pads beforehand.

    All of the major encryption machines used during WWII appear to have been broken. The new encryption methods are currently much harder to break, but the spooks are likely to discover some innovative method to break such algorithms.

    Current methods using large prime numbers sounds like they are soon (next few decades) to be broken. If we got int

    • I'm not convinced that all these major breakthroughs in computing are just sitting right out of reach, waiting for a little war funding to make it happen. Computer technology has been moving so quickly the past couple of decades, and there's so much money to be made in these various fields, I'm sure the best and brightest are already working plenty hard on it.

  • In the simplest of terms

    I thought the whole point of the quantum computer was was it did the equivalent of brute forcing every single possible answer simultaneously

    instead of checking a password say from

    a
    b
    c ..z
    aa
    ab
    ac ..az
    ba
    bb
    bc ..bz

    so a one letter password (normal computer) can be checked in 26 steps, and a 2 letter password in 676 steps..
    each once then proceeding,

    and on a quantum computer, I thought it threw the equivalent of the OED (all possible answers, all possible combinations) at the same time.

    but on

    • will someone please tell me where my basis is way off?

      ... and how do you get the answer to a particular choice of password out of the quantum computer?

    • Re: (Score:3, Interesting)

      by NonSequor ( 230139 )

      No, it doesn't brute force every possible combination. You can perform an operation on a superposition of all possible k-bit strings, but you can't actually get all of the 2^k outcomes of that operation. If you measure the result, you'll get one of the 2^k outcomes at random.

      Basically you start from that superposition of k-bit strings, then you apply some operations to that state so that all of the the correct answers are in phase with each other and constructively interfere. Effectively, you can only apply

    • Re: (Score:2)

      by julesh ( 229690 )

      Simplistically: there are only certain algorithms it can perform such a search over. One of them is factorization (Shor's algorithm), and this can be applied to most current asymmetric ciphers because they're essentially isomorphic to one another.

  • Introduction to post-quantum cryptography (Score:2, Informative)

    by Anonymous Coward

    There is an old paper, written by DJB, which gives a quick introduction to some (this and) other quantum computer resistant encryption methods: Introduction to post-quantum cryptography [pqcrypto.org]

  • Here is a link to the paper on the arxiv:

    http://arxiv.org/abs/1008.2390 [arxiv.org]

    Reading through the abstract, I see that a significant feature of this cryptosystem is that it cannot be solved by "strong Fourier sampling", which makes the situation more interesting because it is only a slight exaggeration to say that quantum Fourier transforms are the only trick we know of that lets us get exponential speed-ups in quantum algorithms.

  • This doesn't rule out other methods of speeding up using quantum tricks. Also, keep in mind that this may all be for naught since no work of this form can rule out the existence of a fast classical algorithm for handling the problem. Thus, implicitly, all these sorts of results are interesting primarily if one assumes that these sorts of problems don't lie in P. The good news is that the hidden subgroup problem is very likely not in P.
  • I thought it had been proven that quantum computation was a pipe dream (you can't physically compute 2^N operations with less than 2^N atoms). Is the hypothesis still considered plausible ?

Slashdot Top Deals

Any sufficiently advanced technology is indistinguishable from magic. -- Arthur C. Clarke

Close