10 ms·
Quantum computers will break the encryption that protects the internet
- gaze 8y agoWhy are we so worried about quantum computers when there's backdoored random number generators (Dual-EC DRBG) and stuff in play? I just don't understand it.
- Cyphase 8y agoYou're falling into the fallacy of relative privation. "Why are we so worried about __________ when __________?", implying that you can't be concerned about both.
- kardos 8y agoNot sure what you mean by in play. Dual EC DRBG was widely discredited in 2013/2014; it's not part of the gamut of viable cryptographic tools anymore. Anyone still using it today is hopelessly out of date, but that's a different problem entirely than the threat/promise of quantum computing.
- elbybasolis 8y agoI’m concerned with the ability of conventional computers to keep up with cryptography in the quantum age of computation. But can’t we just jack up the current algorithms to have higher order problem sets to solve? In other words can’t we turn something like a SHA-256 into a SHA-2048 and take a hit on the time complexity to generate such cryptographic (in this case a hashing algorithm) products? Can’t we just scale up the problem size and assume that the solution will be exponentially more difficult to solve?
- bsaul 8y agoI'm not an expert at all, but fwiu quantum computers makes cryptographic encryption a linear problem.
- elbybasolis 8y agoIn that case can we start computing cryptographic products with quantum computers such that there is no gap? If we reduce the time complexity of factoring a prime number to linear wouldn’t we be able to produce larger cryptographic products? Effectively going back to where we started but with more computing power? Surely this would require easy access to quantum computation to be practical and thus a gap in power, but necessity would drive the market to make this type of power more mainstream.
- rollcat 8y ago> In that case can we start computing cryptographic products with quantum computers such that there is no gap? QC solves one kind of problems, that are hard for classical computers, but not another (see all the links to post-quantum crypto in the comments). OTOH there will be a very large window during which QC will be cheap enough to rent by the hour on AWS, but equipping every lightbulb with a QC will be prohibitively expensive (think current GPU prices).
- imranq 8y agoIt would still take linear time to determine the prime factors
- throwaway2048 8y agoThis is not true, symmetric block ciphers (AES) are at worst about halved in strength. Asymmetric crypto that depends on prime factorization or discreet logarithms (such as RSA and EDSA) are indeed fatally weakened by large enough quantum computer, but it is not a problem for other mathematically one way "hard" crypto constructs like hash trees or the McEliece cryptosystem.
- thornjm 8y agoThe world is working on it: https://csrc.nist.gov/projects/post-quantum-cryptography https://csrc.nist.gov/projects/post-quantum-cryptography You can see round one submissions on the left.
- elbybasolis 8y agoI see this playing out similarly to the Y2K situation. There will be a race to upgrade all cryptographic security measures currently in place to handle the new power in computation. In the beginning however those who would have access to such power would make a mint supplying a service (AWS and the like) to compute these products.
- daodedickinson 8y agoOnly after the real powers are done using the exploit.
- daveFNbuck 8y agoY2K was a trivial issue that everyone knew how to fix for decades. Computing was important to how the world ran, but not nearly as ubiquitous as it is now. It still took a large effort to upgrade everything for Y2K.
- keeperofdakeys 8y agoCryptography is based on "hard problems", something that is easy to solve one way, but hard the other way. Quantum computers provide algorithms that can severely break some of these (namely RSA with Shor's Algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm), and speed up all the others (namely Grovers Algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm). So it's not possible to simply increase bits to ensure algorithms are still secure, but it will work for most of them. On the bright side there is also a branch of cryptography called post-quantum cryptography, which is a collection of algorithms designed to be more resistant in the face of quantum computers https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography.
- xucheng 8y agoFYI, Elipical Curve Cryptography is also broken with the quantum computer using the same Shor’s algorithm.
- keeperofdakeys 8y agoThanks, I didn't realise that. I need to do some more reading about the topic.
- dschuetz 8y agoI'd like to see quantum computers actually do anything practical, anything at all, instead of making wild promises of what they might or might not be capable of. Stop promising, start delivering.
- tephra 8y agoI'm on Mobile and having a hard time finding the link but I'm pretty sure the Google quantum computing team (and probably others) have built low qubit computers that have factored numbers into it's prime factors.
- alfiedotwtf 8y agoAFAIR, the number is something really low like 100,000
- tialaramex 8y agoWith Shor's algorithm (the thing that would make this headline about "Quantum computers will break the encryption that protects the Internet" true) AFAIK the answer is that quantum computers have found 21 = 7 x 3 Because of interest in using quantum computers to factor big numbers there's a reason to do something other than Shor's algorithm with a big machine that can't run Shor's algorithm and thus get a big impressive number. This approach has factored six or seven digit numbers. Which your PC could also trivially do, and it doesn't use Shor's algorithm either.
- WilliamEdward 8y agoDo you keep up with the development of QCs at all or are you just an eager consumer? They're only able to make QCs with a small number of qubits at the moment and can't add more without running into sound disruption issues so it's a ways away from being able to do anything practical.
- brokenmachine 8y agoI'm far from convinced about QC yet, but the first transistor was in 1947 and now the CPU in my phone has over 3 billion. Looks like they took 30 years to get from that first transistor to the TMS 1000 with 8,000 transistors on it. https://en.wikipedia.org/wiki/Transistor_count#Microprocessors https://en.wikipedia.org/wiki/Transistor_count#Microprocesso... I just thought that was interesting...
- wavegeek 8y agoAt one point I thought I had found a fast factoring algorithm but I found that the internet no longer much depends on the difficulty of factoring large numbers and stopped work on the project. Elliptic Curve encryption for example does not depend (AFAIK) on the difficulty of factoring. (please tell me if this is wrong)
- pfortuny 8y agoAt some time we shall discover that Shor’s algorithm is polynomial but the greatest monomial has a constant of size 10^30000 and we shall go on living.
- the8472 8y agoCertificates very much do use RSA. The ephemeral handshake commonly uses ECDH.
- silur 8y agoElliptic curves are even more vulnerable to known quantum algorithms
- ShaneCurran 8y agoKind of. Elliptic Curve can be reduced to the Discrete Logarithm problem, which a variant of Shor’s Algorithm solves in polynomial time.
- moefh 8y agoElliptic curve crypto (the kind that is in common use, like ECDH) is just as broken by quantum computers as RSA. The quantum algorithm that breaks RSA (Shor's algorithm) does it by efficiently solving the hidden subgroup problem[1] for finite Abelian groups. This can be used for factoring integers (which breaks RSA) and also for solving discrete logarithms (which breaks elliptic curve crypto). [1] https://en.wikipedia.org/wiki/Hidden_subgroup_problem https://en.wikipedia.org/wiki/Hidden_subgroup_problem
- wbhart 8y agoThere are many applications of a fast factoring algorithm in number theory, and many people who would love to get their hands on one for that reason. You'd be exceptionally famous if you developed a very fast algorithm for this. That is to say nothing of the fact that it would say something about the fundamental complexity of various problems.
- adriand 8y agoIt's interesting to look at this through the lens of startup creation. Here is an example of something where there will clearly be customers that need assistance from technologically sophisticated companies. Quote: "Mr Steel says one of his clients has thousands of apps that need updating. As chips migrate into everything from cars and children’s toys to lighting systems and smart electricity meters, the amount of work will only grow." The need is clear and there is even a timeline. NIST is planning to release proposals for quantum-resistant algorithms in 2024. According to the article, Brian LaMacchia, an expert from Microsoft, predicts availability of a “cryptographically interesting” quantum computer in 2030 to 2040. The question is, when does it become sensible to start a company intended on serving the millions of other companies who will need assistance making this sort of transition? It feels too early now, but is it? Are there sensible steps to be taken now? If you're reading this and you happen to be fifteen years old, thinking about what you might want to launch when you get out of university, is this something worth diving into? The uncertain timeline carries considerable risk, but if you wanted a shot at building a sustainable company that might be worth tens of millions in two decades, this problem seems like an obvious candidate.
- DenisM 8y agoAre you imagining something akin to the Y2K-style surge in COBOL consulting jobs? I imagine it could be lucrative, but I also imagine most companies will just drag their feet as long as they can, so it will be a frustrating sales experience as it always is absent a clear deadline or at least significant time pressure.
- maxxxxx 8y agoIf you are good at hyping up vaporware then now may be a good time. If you are interested in really helping people it will probably take many years before there is anything real to do.
- basicplus2 8y agoI think we are safe for a while..aint no quantum computers around yet
- ShaneCurran 8y agoThe problems arise when data is intercepted now. Sure, some encrypted information won’t be useful/sensitive once the advent of cryptographically significant quantum computers comes but if any packets are simply stored now and saved for the future, that encryption will be rendered broken and the information leaked once there’s a practical Shor’s/Grover’s implementation.
- mewse 8y agoBut that was already the case, wasn't it? Store those packets long enough and even ordinary, non-quantum computers will become fast enough to factor the requisite large numbers within a reasonable period of time to unlock the comparatively primitive encryption which had been in use back when the packets were captured. We're really just saying that quantum computers could theoretically decrypt those old stored packets sooner than the non-quantum computers will be able to do it. But the non-quantum computers will definitely be able to do it someday. Those stored packets are not staying encrypted forever, regardless of whether or not quantum computing is eventually made to work effectively and efficiently and economically.
- ShaneCurran 8y agoThat’s true, but the absolute values of the timeframes involved are quite different. Classical computing is speeding up, for sure, but breaking RSA-4096 (as an example) will take significantly longer to be feasible than the 10-20 year estimate for quantum computers. That’s assuming that classical computers are still roughly following Moore’s Law. For quantum computers, the difference between RSA-2048 and RSA-4096 is pretty negligible (it’s linear) while it’s exponentially more difficult for classical computers. 10-20 years a short enough timeframe that all sorts of PII could remain useful. Some people haven’t changed their passwords in a decade or two. If you extend those timeframes out over 100+ years then the sensitivity of PII begins to decline pretty significantly, though admittedly not to zero.
- edoo 8y agoI wonder if you could significantly increase the qubits required by layering or interleaving cryptographic functions. By interleaving I almost imagine something like an AES algorithm where the rotated bits actually reference new keys and ciphers that are actually used on the data.
- air7 8y agoThis is a non-issue IMO. Contrary to popular belief QCs are not magical oracles that can do arbitrary exponential calculations in polynomial time. Instead QCs can do only very specific things better than conventional computers and there are a surprisingly low number of known algorithms for QCs even though people have been looking. While it's true that Shor's algorithm allows a QC to potentially factor integers in polynomial time breaking RSA, there are other popular encryption schemes with no known quantum weaknesses and there's a whole field called Post-Quantum Cryptography looking at this property explicitly. And just like upgrading SSL 3.0->TLS 1.1->TLS 1.2->TLS 1.3 was done due to discovered weaknesses yet mostly transparently and with no Y2Kish hype of "the internet is broken", so will we upgrade to quantum resistant algorithms if and when QCs become a reality.
- hannob 8y ago> This is a non-issue IMO. vs. > will we upgrade to quantum resistant algorithms if and when QCs become a reality. Sorry, I don't think your words make sense.
- tptacek 8y agoI know you know what you're talking about but I don't understand what you're trying to say here.
- WilliamEdward 8y agoI think they're trying to say OP made a contradiction. On one hand, they think its a non-issue, yet on the other hand they admit that when quantum becomes an every day reality we will have to change everything.
- maxxxxx 8y agoI think the theory is that at the time QC is starting to threaten current encryption there will be new algorithms available and the transition will be not difficult. Seems pretty likely.
- sudoaza 8y agoWhats new about this?? We'we known for years, it's still years away and we already have post quantum crypto to replace all thise...
- NotANaN 8y agoNot just years; decades. About a quarter of a century.
- torbjorn 8y agoBreaking crypto makes for a good headline but the most important application of QCs will be simulating quantum states, eg modeling molecular interactions. And obviously there is plenty of work that remains to be done in this nascent field. Also obligatory link to the best quantum computing blog out there: https://www.scottaaronson.com/blog/ https://www.scottaaronson.com/blog/. Very good at dispelling hype.
- DenisM 8y agoAdding to that: I heard that in modern chemistry there are trillions of experiments to be run and not enough time to run them all. Using QC to cull the search space can lead to discovery of some very interesting compounds. This could be “the industrial revolution” of the field.
- tychomaz 8y agoStill waiting for this to happen.
- randomsearch 8y agoSome context: breaking encryption standards will likely take millions of qubits. Current state of the (disputable) art: less than twenty.
- true_tuna 8y agoAnd there are methods to defend crypto against QC. New algorithms will become more popular as quantum computers become more capable. It is a problem we will face someday and it’s good to start thinking about it and working on it now.
- blablabla123 8y ago5 years ago most people didn't care about encryption. Most websites, disks, E-Mails, USB sticks, downloads were unencrypted - this hasn't changed much. Not to mention the software pool on closed-source Hardware. I'm not exactly sure who would have to be afraid of what. :-)
- singletoon 8y agoThis is no news for the academia, more particularly for theoretical mathematicians. It's a well known fact that RSA and all other cryptography methods based on basic number theory results, will become useless with the appropriate usage of QC. Mathematicians have already suggested that non-commutative group-based cryptography is the appropriate solution to this issue. Yet, there's no ideal group that seems to be the right fit, for the proper implementation of these new, secure algorithms. The braids group used to be an ideal example, until it was found to be linear, thus heavily exposed to linear-based type of attacks. So, the only part that remains unsolved is which group could be ideally defined to support the theory that addresses this issue. Mathematicians are already aware of this challenge, perhaps this post by The Economist suggests that more funding should be given for the according research.
- writepub 8y agoQCs will likely break existing crypto currencies. Which begs the question - if someone does own a QC how much crypto can they steal without devaluing the currency in the process.
- anon4738383 8y agoIf QC were able to factor primes, discover alternative inversions of noninvertible matrices... the obvious uses would be monetization, hacking and other legal and illegal crimes: crypto mining and hacking banking and finance.