Quantum Computing Kills Encryption

Imagine a world where the most widely-used cryptographic methods turn out to be broken: quantum computers allow encrypted Internet data transactions to become readable by anyone who happened to be listening. No more HTTPS, no more PGP. It sounds a little bit sci-fi, but that’s exactly the scenario that cryptographers interested in post-quantum crypto are working to save us from. And although the (potential) threat of quantum computing to cryptography is already well-known, this summer has seen a flurry of activity in the field, so we felt it was time for a recap.

How Bad Is It?

If you take the development of serious quantum computing power as a given, all of the encryption methods based on factoring primes or doing modular exponentials, most notably RSA, elliptic curve cryptography, and Diffie-Hellman are all in trouble. Specifically, Shor’s algorithm, when applied on a quantum computer, will render the previously difficult math problems that underlie these methods trivially easy almost irrespective of chosen key length. That covers most currently used public-key crypto and the key exchange that’s used in negotiating an SSL connection. That is (or will be) bad news as those are what’s used for nearly every important encrypted transaction that touches your daily life.

crypto-quantum-computers-quoteAll is not doom and gloom, however. There are families of public-key algorithms that aren’t solved by Shor’s algorithm or any of the other known quantum algorithms, although they haven’t been subjected to as much (classical) cryptanalysis and the algorithms and protocols aren’t as polished yet. (More on this topic below.)

Strong symmetric ciphers, algorithms that use the same key for encryption and decryption (AES, Blowfish, etc.) will also be easier to crack with quantum computers, but only by roughly a factor of two. So if you are happy with AES-128 today, you’ll be happy with AES-256 in a quantum-computing future. That’s good news for a lot of the nation’s classified documents, for instance.

But let’s just reiterate that the hollowing-out of essentially all public-key crypto would be a very bad thing.

Is Quantum for Real?

Quantum computing is still in its infancy, but it may already be time to start worrying about your data today. As a warning sign, the NSA backed off of its previous recommendations because they weren’t robust to quantum computing attacks. For sheer Schadenfreude, read the following excerpt from this August update to their website:

For those vendors and partners that have already transitioned to Suite B [elliptic curve cryptography], we recognize that this took a great deal of effort on your part, and we thank you for your efforts. … Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, which has made it clear that elliptic curve cryptography is not the long term solution many once hoped it would be. Thus, we have been obligated to update our strategy.

In other words, “sorry we got you to spend lots of money switching over to something that’s now looking to be obsolete in the near future”. So the NSA is taking the quantum threat seriously.

While it’s sweet to see the NSA publicly eat a little bit of (pre-emptive) crow, the fact that they’re afraid that quantum cryptanalysis is going to break things in the near future, but they don’t have any solid recommended alternatives yet, should scare you a little bit. Indeed, on their list of recommendations, only AES is not completely destroyed by quantum computing. That’s kinda spooky. This article sparked by NSA’s revelation at Ars Technica is a good read.

How Soon?

In short, it looks like the quantum computing apocalypse is coming, but there’s current research going on and hopefully we’ll get some solid procedures in place in time. Nobody really knows how long we’ve got until quantum computers will be able to handle real-world cryptanalysis, but the numbers that the post-quantum folks toss around are in the ten-to-thirty year range.

Sometime before flying cars, then. As far as Shor’s algorithm goes, the largest quantum-computer-factored multiple-of-primes is 21. (Which two primes those are is left as an exercise to the reader.) Before laughing too hard, bear in mind that five years ago the largest possible factor was fifteen, and there’s a lot of research money and brains going into the quantum computing problem.

And when the computers arrive, they’ll have a whole spate of potential algorithms waiting for them to crunch on. The Quantum Algorithm Zoo, maintained by [Stephen Jordan], a physicist at NIST, is frequently updated and takes stock of the state of the art. Looking through the list, if you think your problem is hard but it’s in the “superpolynomial” improvement category, it probably won’t be hard forever.

What Can Be Done?

In early September, a group of crypto scientists working on post-quantum cryptography met up for a week-long seminar in a German mansion and put their heads together. This Nature article nicely summarizes the meeting, and if you’re interested in what you could be doing now to safeguard your data further than a couple decades into the future, the initial recommendations for post-quantum encryption systems that came out of the seminar summarize the state of the art.

In particular, McEliece cryptosystems come out looking like a good alternative to the current public-key infrastructure. Instead of relying on factoring large numbers, a McEliece system hides your data by first wrapping it up with an error-correcting code (ECC) and then deliberately adding noise to it. Quantum computers, incidentally, turn out not to be very useful in computing some types of ECCs, which is the whole point of this operation.

Normally ECCs make it easy to recover a signal that has noise added to it; they’re not “codes” in the encryption sense at all. The crucial step in McEliece cryptography is that you create the ECC with an easy-to-reverse code, and then convert the ECC into a hard-to-solve one by pre- and post-multiplying by matrices. These matrices, that turn the hard problem into the easy problem and vice-versa, become the secret key. So you take your data, add error correction, then add noise, and then make removing the noise difficult unless you’ve got the “password”.

If you’re interested in digging a little bit deeper into the methods of quantum computing and quantum-proof crypto, this mathy but still readable survey of the field from 2001 (PDF) is a great start.

Punchline

Practical quantum computing is probably ten to thirty years away. When it comes, whatever you’ve encrypted using today’s standard public-key encryption systems will be trivial to decrypt. Anyone storing your (or your government’s) data now will likely be able to read it when today’s toddler is enrolling in college. And you can bet that a good part of the rationale for the NSA’s recommendation about transitioning away from susceptible technologies is that they know of some large, well-funded government agencies who are doing that storing on a large scale today.

So is changing our public-key crypto today too early or too late? The tide seems to be just turning. The risk of switching right now to a quantum-proof method like McEliece is that it’s less battle-tested than RSA, and certainly slower to implement because it hasn’t yet been über-optimized, but the costs of not switching are growing year by year. It’s like Frogger, where you’re waiting for a log with a fly on it, but you’re also scrolling off the side of the screen. We’ve probably all got to jump, but when?

79 thoughts on “Quantum Computing Kills Encryption

  1. While it obviously doesn’t really work for mass communication, there will always be the notepad based communications that work off computer. Security by obscurity is always more reasonable than mainstream.

    1. one will quickly argue that a obscure security implementation will never be compatible with an open source platform. The reason security goes to clear mathematical algorithms is because there are many situations when we want to present the lock mechanism (and even advertise how good it is), but hold the keys in our pocket.

    2. There was a great part in The Kingsmen about this, where the villain is writing down a list of evil deeds while being spied on by the good guys. he shows the notepad he’s using to his bodyguard and says “you know what I love about this? it’s unhackable”

    3. If you mean “one-time pad” then that’s theoretically uncrackable for ever. Seems logical that it’s impervious by definition.

      If you just mean “let’s make up our own cypher code and not put it on a computer”, it’s probably not too hard to type it into a computer, once you have the notepad.

      An obscure cypher might not be crackable using mainstream, available cracking technology. But if someone puts their mind to it, you’ve no idea how long it will actually stand up. The big encryption schemes have the advantage of people with massive brains putting them to real tests. Arrested for some big crime, you might wish you’d stuck to something proven to stand up to the giant mega-crackers.

      And you can always just make your key longer.

      As ever, reasonable effort is proportional to risk.

      1. In principle, you could do both. Use a standard cypher, and your own around it. The total security will be somewhere between the maximum of both individual methods and the sum of both methods.

        1. No.
          If you’re the kind of person who thinks using your own cypher is at all helpful, you’re the kind of person who will be sloppy about other things, and crypto has lots of subtle implementation things you can do wrong. (Early PGP, for instance, was so concerned about saving bits that it used variable-length data formats that could easily be bullied into accepting data of the wrong length and leaking keying information. And RC4 has lots of “don’t ever do THIS” kinds of rules that Microsoft and many other people have gotten wrong.)

          A recent famous database compromise found that the system was storing passwords in a very secure hash format, but also storing an abbreviated version of them in a fairly insecure format, so you could brute-force those (in lower-case-only form), and then check the ones you found against the more secure hash, checking multiple combinations of upper/lower case, and break into lots of the accounts.

    4. There is still one time pad and AES256 which are still largely immune form any real attack. This is another academic story with no real implications in actual usage. Your information is secure. Too many kids with minimal cryptography knowledge are jumping onto the “quantum” bandwagon without investigating real attacks and strength of current algorithms. Also anything promoted or developed by NSA is suspect at the key generation point from all accounts especially including the elliptic curve related key generators.

  2. I think the title is a little misleading. It implies future advances in technology will kill future encryption techniques, when instead its about future technology that would kill present days encryption. Which is obvious, and it’s one of the reasons progress is being made on the encryption side as well.

    1. Key point. Quantum computing can make the future’s *encryption* technology better. Encryption is based on the idea that today’s large primes can’t be easily factored by today’s technology. By the same principle, tomorrow’s even larger primes, computed by quantum computing methods, won’t be easily factored by tomorrow’s quantum technology. It’s the same cat and mouse game, just as it always has been.

        1. If bits of entropy in our passwords because the limiter then, uh, I’m not sure what can be done about that. Biometrics, I guess, using high-res photos. But my face is available for everyone to see, and fingerprints are just a matter of following me around until I buy a drink in a disposable cup (which could also get them my DNA).

          This is going to end with me logging into my work PC by swiping my wang, isn’t it?

          Quickly followed by the condom equivalent to those credit card skimmers thieves stick to the outside of an ATM’s card slot.

          I feel like there’s a decent cyberpunk novel in there somewhere.

          1. Biometrics is pretty much a loser at this time, as are most of the other non-password options when dealing with remote authentication. The biggest issue is that you can’t change the bio when there is a failure in the system like can be done with a password. For local authentication, bio isn’t a terrible choice, but much of the current consumer grade is less than ideal.

            Physical token authentication is also really only appropriate for local use, though it is a bit better than bio as the tokens can be replaced (think losing your house key, for example)

            I leave it to bigger brains than mine to deal with the authentication issue. I have some comfort that by the time quantum is a major factor I will no longer be a factor, as I am not young.

            If I am wrong in thinking that the ten year timescale is terribly optimistic, then there there will be bigger issues to worry about. I would guess that the thirty year scale is in the ballpark, and maybe still a bit optimistic, but I am not current in the field, so my guess is worth what was paid for it.

          2. “This is going to end with me logging into my work PC by swiping my wang, isn’t it?”

            haha! thanks buddy, I owe you a beer. Got a bitcoin address?

          3. So much for chicks having a future in tech…

            Wang Login V.2 is going to have to accept boobs as an alternate (but equal!) method.

            This could make for a very awkward work environment!

      1. Actually, no it’s not the same. The reason we can use primes and prime factoring in cryptography is that it is currently much harder to factor (crack the encryption) the the public key, than it is to encrypt/decrypt knowing the private key. What quantum computing and Shor’s algorithm does is that it make both operations cost effectively (within the scope of cryptography) the same.

        If you use a 2048bit key today, you will have to use a key that is in one word: huge.

        How huge ?

        If my calculations are correct …

        A 512bit RSA key today would be about a billion time _harder_ to crack than a 2000000bit key when you have access to a quantum compute rrunning Shor’s algoritm.

        And a 2048bit RSA key is much more than a a trillion times harder to crack than a 512bit RSA key.

        Essentially: Any key that would be long enough to not be easily cracked by Shor’s algorithm would _probably_ not even fit in the memory of all the computers in the world.

        1. Quantum computing is not happening in the lifetime of the universe any faster than time travel. Another science fiction dream by some dumb kid with a laptop and a hackaday login….

          1. It’s certainly possible to do quantum computing, it has already been done. The hard problem is making a practical quantum computer that is general enough purpose to be interesting to a wide audience.

            Conjecture: Nobody is going to be able to make a somewhat believable prediction about the impossibility of that task unless substantial theoretical results would somehow emerge. Reason being that the configuration space that could enable a useful quantum computing device is quite big, as the behaviours necessary are – quite literally – embodied in every physical system in existence.

            Time travel is almost certainly impossible, to further complicate it, it appears as if time might not even exist in any useful sense of the word.

        2. A reasonable analogy would be comparing quantum computing with cold fusion. Both are absolutely possible and have been done. The question is “when will it be cost effective to scale up and do useful work with them?”

      2. The threat of quantum computing can force us to develop better or different algorithms, make keys longer, etc. That doesn’t make the future’s encryption “better” – it may be stronger, but that has a cost (not just money/speed, which Moore’s Law tends to fix – for instance, it’s really convenient to be able to fit a 256-bit ECC key into an IP packet along with other data, but if you need to go to 16384-bit RSA, that won’t fit, so you need to change your protocols.)

        Ignoring the fact that we don’t know how to make useful quantum computers now, and there’s no sign that we’re actually on the way to doing it any time soon, symmetric-key systems only lose a factor of 2 in key-length strength, so they’ll continue to be useful, and if we really have to, we can go back to Key-Distribution-Center systems like Kerberos or Needham-Schroeder or other things I’ve mostly been able to forget.

        Alternatively, there’s research into whether ECC is still safe (it was looking like it for a while, but there’s some doubt floating around), or Lattice-based cryptosystems (IIRC, that’s what the McEliece stuff is), which need a lot more bits of keying than RSA, and require learning yet another bunch of tricky math, but they can probably do the job (again, with the “redesign your key exchange protocols to use multiple packets” headaches, which include the problem of people swapping out packets during your key exchange.)

        And somebody else has already included the XKCD cartoon with the $5 wrench.

  3. A chain is as strong as its weakest link. Breaking crypto is hard, it’s much easier to ‘crack’ the computers the crypto is running on. This is the method of choice for current hackers.

    1. In my experience the weakest link is between keyboard and desk.

      Honestly, the fact that the world isn’t constantly on fire is imo proof positive that most people are fundamentally if not good then at least a solid neutral.

  4. This is interesting to me because anything that is 10-20 years away is usually in the hands of the government already. It is known that the FBI has a method to de-anonymize users/services in the Tor network. Tor uses public/private key systems to encrypt the traffic for every hop. So if the NSA had the tech to break that encryption, it is feasible that the FBI could ask for favors occasionally, and come down on the Silk Road 1-4. It’s prolly some warehouse sized supercomputer, and I’m sure it’s no trivial task, but if they are publicly stating that they want crypto that is quantum-hardened, chances are they know more than they are letting on.

      1. I presented a well-reasoned statement with supporting details… The heartbeat detector that NASA used to help find victims buried in rubble is just one of the many examples I could give, but since you’re either shilling or trolling, it doesn’t matter to me anyway. It’s not paranoia as much as hoping my tax dollars are doing something productive.

        1. The heartbeat detector is also used by Customs to find people hiding in lorries. You touch the sensor to any part of the vehicle, a wheel will do, and it picks up heartbeats by vibrations. Bloody amazing! It’s been part of their standard equipment for years.

          Do a feature on that, HAD!

          They also have CO2 sniffers for the same thing.

          1. Call me cynical but that sounds more like drug-dog mumbo jumbo than working tech. Not saying it’s not possible, just that it’d be much easier for Customs to build a movie-prop ‘detector’ which they can then cite as probable cause to search any vehicle they want.

    1. A snooper only needs access to many exit nodes, brute forcing the key and sitting there for a while following that, a bit of traffic analysis and a government friendly ISP and boom lists of users matched with visited sites.
      Easy for a large organization with the resource, quite hard for the majority and scary! Imagine thinking you were speaking freely in China for the gov to smash the door down because the ISP said you made that initial connection.
      Tor’s relatively simple which is it’s weakness but you need the resource and skill to interpret the data into something the top men can understand.
      As it stands, there is still no way to actually decrypt it real time only to match in + out traffic = user
      The tools are all over git if you fancied having a go!

    2. Hmm? The way to link actions to users in Tor is well known – statistical analysis. That requires a lot of data though which means having control over exit nodes is a must, the more, the better. I think that weakness was stated from the start of the project?

      And the state of the art isn’t far from the publicly known state of the art unless you are talking about some obscure technology – 20 years ahead? No way, that’s unfounded paranoia.
      In fact we know (by analysis of facts) that the publicly known state of art for crypto analysis passed the one of the NSA in at least one case.

      The way Silk Road was brought down wasn’t by cracking public key encryption – if so FBI would be incompetent not arresting a lot of other sellers and for taking such a long time to do unnecessary things like infiltrating the network over a long time.

      This is simply the NSA doing what they are tasked with – protecting US interests by 1) indicating that practical quantum cryptography may perhaps have a chance to come into existence in not to far future (in this case 50 years is within a reasonable timeframe – as some secret data could otherwise leak decades after it being sent) 2) indicating that an algorithm considered relatively safe against quantum computers may not be so.

    3. Yeah, well, we can’t all have a nearly unlimited supply of alien technology due to all those crashes spaceships and recovered stargates now can we?

      But the one real amazing technological feat they pull is being ahead of the curve by such a margin and still seem technologically inept even by today’s standards.

      But seriously, The government only has the money to spend on niche applications of technology that exists today. It does not have technology which has not been invented yet.. by definition. It does not poses silicon with radically advanced topologies or a lithographic process an order of magnitude finer than what is in Intel’s pipeline. Like any user of technology, governments are following academia and the industry just as we users are.

    4. Anyone using the word “prolly” is not to be heard with any respect. Sounds like a stupid kid with minimal knowledge and another Govt. can do anything dreamer. Our govt. cannot even make a website that works. Do you really think that ANY cryptographic algorithm has been effectively “hacked” to speed up finding the key or information? Only the NSA developed suites are suspect and of those elliptic curve keying algorithms are particularly to be avoided. One time pad still works especially now that memory sizes are large enough for substantial key material.

    5. Exactly. “The NSA’s recommendation about transitioning away from susceptible technologies is that they know of some large, well-funded government agencies who are doing that storing on a large scale today.” – No, the NSA *is* a large, well-funded government agency which exists in large part to gather information. If they’re recommending that you move to a particular platform, it’s because they already have access to crack it but they think no-one *else* can do so yet.

      1. If I could push a button and get all the remaining gold in the world, I could flood the market and make a killing at any price. If you started selling all presently unmined bitcoins at USD $1 a piece, the value of the bitcoin would be $1. And concentrating all that value in one person would leave the system forever in peril of that sword of Damocles, rendering it pointless.

        1. Both Gold and Bitcoins are a finite resource though. There’s ~171k tonnes of gold and 21 million bitcoins. If your computer mines the remaining 7 million bitcoins, sure you could flood the market as you suggest, but they still have value. You can’t hyperinflate a finite resource. The commodities market will take a hit but it will equilibrate to the new market landscape. Or a cartel will emerge like we see with OPEC and de Beers et al,.
          Price is driven by rarity, since we can no more make more bitcoins than we can make more gold (for practical purposes) they will still hold value, just diminished. You’re describing economics 101, not a catastrophic market crash.

          1. I’m not a cryptographer, or a bitcoin core developer, or anything like that, but I believe the issue here is that anyone could sign any transaction. Which means I can spend your bitcoins… And if anyone can spend any bitcoins from any address (since they can use their quantum computer to derive the private key from the public key), bitcoins are then WORTHLESS.

          2. “but they still have value”

            No they don’t.

            Fiat money derives its value from the obligation to pay back a debt, which means the person who originally created the currency must accept it back at some point. Bitcoin doesn’t have any obligation to take it back, and it isn’t based on any physical value, so it has no value. It’s entirely imaginary.

            It’s not “rare” because anybody can just start a new chain and create 21 million more bitcoins, and then some. When the mining becomes too hard, all the miners simply move on and Bitcoin is left dead in the water because nobody wants it. It becomes actually worthless.

      2. If you could speed up the computational power by orders of magnitude you could hijack transactions and make them your own. Even right now bitcoin is susceptible to manipulation by someone with a control over a sufficiently big portion of its compute network. That’s in fact what’s protecting bitcoin, the large enough decentralized network. But a quantum [pun intended] leap in performance could upset that balance.

        Bitcoin is an interesting idea, but a large waste of energy nonetheless.

    1. I’ve always thought it was far away as well. But the fact that the NSA folks are taking it seriously enough to do an about-face on elliptic curve crypto is a real thinker.

      Even if there’s a 10% chance of a 256-bit factoring quantum computer in 10 years, that’s a hideous risk from a crypto standpoint. Much riskier (probability x damage) than other potential flaws in RSA, for instance.

    1. I fail to understand how it does protect you today.
      The incognito mode simply means, it does not save the page in bookmarks and history.

      It is like you are talking with a well known gangster in real life.
      Even if noone is hearing what you are talking about, everyone assumes the worst.

  5. While I can’t offer an intelligent insight on quantum computing, I did restore a friend’s Frogger arcade machine. The female frog is the bonus character that the author was thinking of. The fly only appears in the five top slots along with the alligator.

  6. The problem with quantum computing is that maintaining coherence is very hard and nobody knows exactly what needs to be done to trick the Universe into doing all these calculations for you by not shrugging and collapsing the state vector. It will be a kick in the pants if it turns out the Universe collapses the state vector because the computational costs of maintaining coherence become too high…

    1. My suspicion is that the failure rate of a quantum computer rises exponentially with the number of q-bits, with a significant irreducible error rate even with 1 q-bit. Get enough q-bits to attack a good public key and the computer fails randomly most of the time.

  7. Is this based on google and NASA together buying a quantum computer recently? (yes NASA, I did not accidentally insert an extra A – I’m told..) Because I hear that quantum computer isn’t quite what you expect from a quantum computer, but then again, you get told a lot on the internet.

    1. No – the only quantum computers that you can actually sort-of buy are from D-Wave, which are an adiabatic quantum computing system that’s not capable of running the calculations Shor’s Algorithm uses to do factoring, so they’re not a threat to cryptography. There are some research quantum computers that have factored numbers up to 15 and 21, and in some very special cases have factored a few special-form numbers up to about 65,000, but none of them have enough resolution to do anything usefully threatening.

  8. I predicted this years ago, in fact got as far as suggesting a way to achieve semi-classical computing shortly after the news on RowHammer broke for the express purpose of breaking Cryptowall/SimpleLocker/etc.

    Actually have the beginnings of working code that runs on a 2GB DDR3-8500S stick, the method I used is intentionally overclocking it using the SPD chip (requires soldering as the stock chip isn’t reprogrammable easily) and controlling the temperature of the module to within 0.05C using a very simple analogue circuit.
    The fiddly part is to get the laptop to POST with the overclocking, I did this by cooling the SODIMM down briefly using Peltier module after first using a domestic freezer and then used the same module to keep the system stable.

    Worked out that with an optimized 2*16GB setup the number of qubits would be in the tens of thousands (ie byebye RSA-2048) and using parallel processing on the entire address space could find the decryption key in about a week of processing time.
    The slightly annoying problem is that it only works with certain chips, found one in a pile of used modules
    but am loathe to experiment any more in case that one breaks completely.
    If anyone is interested please message me on here…
    The same method could also work on the RPi 2 as the chip is essentially a multilayered DDR3 running at lower clock speed.

      1. Its in the very early stages but yes the chips on one side of the module (SEC K481G0846E line 2 GSHD89ABC) seem to exhibit the effect whereas the others do not.
        I have also noticed that the DDR3 4GB stick on my HP seems to be immune probably because it is 10600S, perhaps it has to be that one manufacturer?
        Have to try it on a Samsung 1GB stick as the chips are virtually identical by the looks of it…

  9. In the 90’s the new way to save money was to use the Internet for data communications. The big companies and governments started tunneling their data over this inexpensive pipe. Before that time, they had point-to-point leased lines, and you couldn’t sit at a desk in your underwear in Mongolia and hack into it. You’re only as secure as your infrastructure. Most military bases and government agencies also consolidated their servers and routers to one building. Pearl Harbor all over again, with all the ships in one place and no one holding a gun. Encryption is just a tree in the forest.

  10. Eh. Is it disappointing that the “bulletproof” encryption we use is turning out to be a bit flimsy? Sure. But they’re still a loooooong way from being able to break it with a quantum computer, especially considering it’s FAR easier to add more bits to an encryption algorithm than it is to add more qbits to a quantum computer. The reason the maximums are so small is because we can’t build quantum computers with more than about 100 qbits. (No, D-Wave does not count. The’re almost certainly a scam until they produce REAL results)

    As for the computers themselves, quantum computers are hardly as amazing or flexible as they’re made out to be. (and 10 years? really?) They may be good at figuring out a few really hard math problems we can’t crack on regular computers, but there’s a LOT they suck at. Technically, they arn’t even computers, rather more like a very expensive math co-processor. Not only that, but there are a few more issues than just “we can’t keep enough qbits stable yet.” Quantum computers have to abide by stupid rules that regular computers do not, i.e. they can’t use a particular quantum state more than once. If you try to copy it, the two sets remain entangled and one will collapse when the other is read, meaning the information must be re-prepared each time.

    I think it will be trivial once we see actual quantum-assisted computers on the horizon (or even now, knowing the algorithms we do) to implement encryption “wrappers” in existing systems that make them quantum-proof, like the matrix-ecc-noise one mentioned above. If we’re not sure one will work, add two. Processing time is cheap. Either that, or we can use our turring-complete computers to implement protocols that are a pain in the ass to quantum-assisted computers, forcing them to redo the same problem over and over, and abandon their advantage.

  11. Shamir’s Secret Sharing is impervious against quantum computing. Especially if you use a rolling polynomial (i.e. each chunk uses a different polynomial). The only major downside is the stored data is multiplicitively larger, at least 3x. You can also run your data through XOR (which is also secure, but requires a key size comparable to the data) or AES prior to, for added security.

  12. The only thing I found that’s kind of funny is that I remember reading an article about 15 or so years ago, and it described quantum computing technology as being “10 to 30 years off”, so… Right on track then?

    1. Yeah. That’s kinda what I meant with the “just after flying cars” bit. I’m personally skeptical — that is I assign a small probability to it happening in 10-20 years. We’ve gotten from factoring 15 to factoring 21 in the last ten years…

      But then, if larger quantum computers do become affordable, the magnitude of the problem if people are still using non-quantum-proof codes makes the issue worth considering nonetheless. (Which is what I think the NSA is thinking.)

  13. Interesting argument, is compressing encrypted data a way to reduce the file size? I seem to recall that one implementation of compression looks for strings of predictable characters (ie PI) multiplied or divided by a constant or in some cases just the file header position.

  14. “[…] will also be easier to crack with quantum computers, but only by roughly a factor of two. So if you are happy with AES-128 today, you’ll be happy with AES-256” –> This doesn’t compute.

    Either of the two statements is true, but not both:
    – If it’s roughly a factor of two, you’ll be happy with AES-129 (hypothetically speaking). You lose one bit of strength.
    – If in the QC future AES-256 is as secure as AES-128 today, it’s a factor of 2^128 difference in strength (square root of initial effort)

  15. Bullshit. Not only any one time pad encryptation is absolutely safe against any computational attack, since there will be magnitudes of possible interpretations of the transmitted information of which none can be verified as being the correct if you don’t have the original one time code. And the problem of running out of one time used binary code can be very simply solved by using the binary code twice (filling the tank again).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s