[Cryptography] The race to Quantum machines. Crypto
IBM believes that commercial quantum machines will be here in about 3-5 years. If encrypted data at rest today has value or is a liability in the next 3-5 years quantum resistant keys seem important. Encrypted data streams that can be intercepted and stored should be reviewed as well. I am curious how long the WikiLeak encrypted dump will stay encrypted. Yes it will take a while to figure out how to code these attacks and match the attack to interesting data but it is a race that some will win. "IBM is set to commercialize its quantum computers in the next 3-5 years, when they can outperform existing supercomputers in terms of computing capability in some specific domains, according to Norishige Morimoto, director of IBM Research in Tokyo and global vice president at IBM. "Morimoto made the disclosure when speaking at the opening session of IBM think Summit Taipei held on May 22. "Starting its R&D on quantum computing as early as in 1996, IBM released a 5-qubit quantum computer in 2016 and unveiled the world's first 20-qubit system, dubbed IBM Q System One, at CES 2019, Morimoto said, disclosing that the company will soon launch 58-qubit quantum computers." https://www.digitimes.com/news/a20190523PD205.html -- T o m M i t c h e l l _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Tom Mitchell <mitch@niftyegg.com>​ writes: >IBM believes that commercial quantum machines will be here in about 3-5 >years. If encrypted data at rest today has value or is a liability in the >next 3-5 years quantum resistant keys seem important. Uhh, you need to read the rest of the article, which you've actually quoted: "Starting its R&D on quantum computing as early as in 1996, IBM released a 5-qubit quantum computer in 2016 and unveiled the world's first 20-qubit system, dubbed IBM Q System One, at CES 2019, Morimoto said, disclosing that the company will soon launch 58-qubit quantum computers." From that we have at least a few data points, and there's more from non-IBM sources, so we can extrapolate over time. Technically we can't actually do that because from everything I've read it's nonlinear, the first steps are relatively easy and then it gets harder and harder [0], but let's say it's linear just for argument's sake. Anyway, to break 1kbit RSA you need about a million qubits. Soon we'll have a computer with 58 qubits. Graphing things and drawing a line to where even 1kbit RSA is at risk is left as an exercise for the reader. Peter. [0] Like getting a manned settlement set up on Mars. So far we can get the whole thing a few hundred meters closer to Mars. After that, it gets a lot harder. _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
On Sun, May 26, 2019 at 3:08 AM Peter Gutmann <pgut001@cs.auckland.ac.nz> wrote: > Tom Mitchell <mitch@niftyegg.com>​ writes: > > >IBM believes that commercial quantum machines will be here in about 3-5 > >years. If encrypted data at rest today has value or is a liability in > the > >next 3-5 years quantum resistant keys seem important. > > Uhh, you need to read the rest of the article, which you've actually > quoted: > > "Starting its R&D on quantum computing as early as in 1996, IBM released > a > 5-qubit quantum computer in 2016 and unveiled the world's first 20-qubit > system, dubbed IBM Q System One, at CES 2019, Morimoto said, disclosing > that > the company will soon launch 58-qubit quantum computers." > > From that we have at least a few data points, and there's more from non-IBM > sources, so we can extrapolate over time. Technically we can't actually do > that because from everything I've read it's nonlinear, the first steps are > relatively easy and then it gets harder and harder [0], but let's say it's > linear just for argument's sake. Anyway, to break 1kbit RSA you need > about a > million qubits. Soon we'll have a computer with 58 qubits. Graphing > things > and drawing a line to where even 1kbit RSA is at risk is left as an > exercise > for the reader. > > Peter. Found this paper: https://arxiv.org/pdf/1905.09749.pdf How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits Craig Gidney1 , ∗ and Martin Eker Near the end in Conclusions. << In, Mosca poses the hypophoric question: “How many physical qubits will we need to break RSA-2048? [...] << Current estimates range from tens of millions to a billion physical qubits”. The upper bound of “a billion physical qubits” is likely from [9]. Our physical assumptions are more pessimistic than the physical assumptions used in that paper (see Table II), so our results can be directly compared. Doing so shows that, in the four years since 2015, the worst case estimate of how many qubits will be needed to factor 2048 bit RSA integers has dropped nearly two orders of magnitude; from a billion to twenty million.”>> > -- Tinny keyboard.. Mobile ... I am _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
On Tue, May 28, 2019 at 12:17 PM Tom Mitchell <mitch@niftyegg.com> wrote: > > On Sun, May 26, 2019 at 3:08 AM Peter Gutmann <pgut001@cs.auckland.ac.nz> > wrote: > >> Tom Mitchell <mitch@niftyegg.com> writes: >> >> >IBM believes that commercial quantum machines will be here in about 3-5 >> >years. If encrypted data at rest today has value or is a liability in >> the >> >next 3-5 years quantum resistant keys seem important. >> >> Uhh, you need to read the rest of the article, which you've actually >> quoted: >> >> "Starting its R&D on quantum computing as early as in 1996, IBM >> released a >> 5-qubit quantum computer in 2016 and unveiled the world's first 20-qubit >> system, dubbed IBM Q System One, at CES 2019, Morimoto said, disclosing >> that >> the company will soon launch 58-qubit quantum computers." >> >> From that we have at least a few data points, and there's more from >> non-IBM >> sources, so we can extrapolate over time. Technically we can't actually >> do >> that because from everything I've read it's nonlinear, the first steps are >> relatively easy and then it gets harder and harder [0], but let's say it's >> linear just for argument's sake. Anyway, to break 1kbit RSA you need >> about a >> million qubits. Soon we'll have a computer with 58 qubits. Graphing >> things >> and drawing a line to where even 1kbit RSA is at risk is left as an >> exercise >> for the reader. >> >> Peter. > > > Found this paper: > > https://arxiv.org/pdf/1905.09749.pdf > > How to factor 2048 bit RSA integers in 8 hours using 20 million noisy > qubits > Craig Gidney1 , ∗ and Martin Eker > > Near the end in Conclusions. > << In, Mosca poses the hypophoric question: “How many physical qubits will > we need to break RSA-2048? [...] > > << Current estimates range from tens of millions to a billion physical > qubits”. The upper bound of “a billion physical qubits” is likely from [9]. > Our physical assumptions are more pessimistic than the physical assumptions > used in that paper (see Table II), so our results can be directly compared. > Doing so shows that, in the four years since 2015, the worst case estimate > of how many qubits will be needed to factor 2048 bit RSA integers has > dropped nearly two orders of magnitude; from a billion to twenty million.”>> > Oh the number of Qbits needed has indeed reduced. But the optimizations that they are employing are not necessarily valid for the problem of factorizing RSA moduli. Consider for example, this special case: https://medium.com/the-physics-arxiv-blog/the-mathematical-trick-that-helped-smash-the-record-for-the-largest-number-ever-factorised-by-a-77fde88499 Pretending to factor large numbers on a quantum computer https://arxiv.org/abs/1301.7007 Basically, Smolin and Co show that the optimizations being employed to reduce the number of QBits required to implement Shor's algorithm kinda depend on already knowing the factors of the number. So yes they are implementing Shor's algorithm but no, they are not developing systems that can break a deployed RSA scheme. Oh and it gets worse (or better from my point of view). The claims being made for increasing the number of QBits don't necessarily represent an increase in processing capability. It is all really murky. The bottom line is that we need to take the potential for quantum cryptanalysis seriously because it could be devastating for electronic commerce. But we certainly do not need to panic. The engineering obstacles that need to be overcome to make Quantum Cryptanalysis viable are of the same order as those required to make fusion power work. The other point to bear in mind is that we won't know whether there is a limit to quantum entanglement until we encounter it. There is no law of physics that states we must be able to form arbitrarily complex superpositions of quantum states. That is an assumption in our current models of physics. _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
As others have said, there's a lot to slip between the cup and the lip. We should prepare for the eventual creation of quantum computers, of course, and this means continued investment in post-quantum cryptography, especially because as we deploy it, we're going to find interesting implementation glitches that have serious security issues. We'll get through them of course, but there's going to be a decade in which "hybrid" encryption where we use both conventional and post-quantum asymmetric algorithms will be *less* secure than conventional encryption because the weakest point is going to be the issues in the post-quantum. Also as others have said, building bigger quantum computers is likely to get harder the more qubits one makes. The theory people say that the theory is all done and all that's left is "just engineering problems." Let us also remember that colonies on the moon, cities on Mars, and useful fusion power are also just engineering problems. Yet, let's cast those aside for the moment. If we start with some basics, like IBM releasing 20 qubits this year, and assume a Moore's-Law like doubling of bits, we need ~20 generations of doubling to get to the needed ~20M qubits. If that doubling is every year-and-a-half, then we get there around 2050. If it's every two years, around 2060. (For what it's worth, I have a standing bet that they can't break 4K RSA by 2050. I picked this because it's about where RSA runs out assuming Moore's Law continues in classical computers indefinitely.) So there's where some reasoning can come from. Yes, a more efficient algorithm that decreases the number of qubits by 100x is good, but that's only 6.5 generations of doubling. The clock speed of the generation is more important -- if there's another 100x efficiency, but the doubling takes six months longer, then it's pretty much a wash. We're still talking about it really being practical in the 2050-2060 time period. Far more important is that exponent. We assumed that it's 2 (doubling) per generation. If it's not 2 but the square root of 2 (~1.4), then we hit that point in the early 2080s, not the 2050s (assuming a 1.5 year generation). This is a completely reasonable thing for it to be; silicon has the nice feature that halfing the element size gets you 4x the transistors, not 2x. I made myself a spread sheet to calculate some of these numbers. I made variables for generation clock tick, generation increase, and just played around. Now consider that their paper lets you break a key in eight hours. With a static TLS key for a site, that's powerful, but with ephemeral keys, there's still a pretty big haystack for those needles. The bottom line, I think is that while yes plan for quantum computers, but it's not the cakewalk some claim it will be. Jon _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
On May 28, 2019, at 1:53 PM, Phillip Hallam-Baker <phill@hallambaker.com> wrote: > The other point to bear in mind is that we won't know whether there is a limit to quantum entanglement until we encounter it. That’s true, but... > There is no law of physics that states we must be able to form arbitrarily complex superpositions of quantum states. That is an assumption in our current models of physics. That’s not quite true. (Or perhaps it’s more correct to say that it’s true, but misleading.) It’s true in the same sense that the speed of light being a constant is the same in all reference frames is an “assumption.” The evidence that this is correct is overwhelming, and the evidence that quantum mechanics applies to arbitrarily large systems of entangled states is likewise overwhelming. All attempts to find an experimental regime where quantum mechanics fails have failed. If you seek solace against the possibility of cryptographic keys falling to quantum computers you are better off looking for it in engineering constraints than in the prospect of discovering new physics. rg _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
On 2019-05-29 10:33, Jon Callas wrote: > If we start with some basics, like IBM releasing 20 qubits this year, and assume a Moore's-Law like doubling of bits, we need ~20 generations of doubling to get to the needed ~20M qubits. If that doubling is every year-and-a-half, then we get there around 2050. If it's every two years, around 2060. It is a good deal worse than that. To get large numbers of qbits in the straightforward way requires exponentially high Q and accuracy, which is obviously physically impossible. So, you need some kind of quantum error correction, which means you need large number of qubits with reasonable precision and Q to give the functional equivalent of a much smaller number of qubits with unreasonable precision and unreasonably high Q. Probably we can find a way to do this without an exponentially large number of reasonable precision and reasonable Q qubits, but even that is not clear, and chances are it is going to be polynomially large. It is also probably going to be hierarchically multilayered, with a huge number of physically reasonable very fast qubits giving rise to the functional equivalent of a large number of slower qubits with unreasonably high Q, which in turn give rise to the functional equivalent of a depressingly small number of qbits with effectively infinite Q but depressingly low speed. _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
On Wed, May 29, 2019 at 2:24 AM Ron Garret <ron@flownet.com> wrote: > > On May 28, 2019, at 1:53 PM, Phillip Hallam-Baker <phill@hallambaker.com> > wrote: > > > The other point to bear in mind is that we won't know whether there is a > limit to quantum entanglement until we encounter it. > > That’s true, but... > > > There is no law of physics that states we must be able to form > arbitrarily complex superpositions of quantum states. That is an assumption > in our current models of physics. > > That’s not quite true. (Or perhaps it’s more correct to say that it’s > true, but misleading.) It’s true in the same sense that the speed of light > being a constant is the same in all reference frames is an “assumption.” > The evidence that this is correct is overwhelming, and the evidence that > quantum mechanics applies to arbitrarily large systems of entangled states > is likewise overwhelming. All attempts to find an experimental regime > where quantum mechanics fails have failed. If you seek solace against the > possibility of cryptographic keys falling to quantum computers you are > better off looking for it in engineering constraints than in the prospect > of discovering new physics. > "All attempts to find an experimental regime where quantum mechanics fails have failed" That is not remotely true. We still haven't figured out how to make gravity work. More relevantly, what exactly do we mean by decoherence? what exactly is it that causes it? The assumption here seems to be that the only reason to build quantum computers is to break RSA. That is not the case. Quantum simulation is the real prize and what I am saying is that we might well find that there is some effect that imposes a limit there. We have yet to see a situation where investing $x.Y produces a quantum computer that is more than x times faster than investing $Y in a quantum computer. It is not just the number of QBits that is at issue here, it is the number of operations you can perform before you lose coherence. People should recognize that quantum computers are a cheap way to do experiments in fundamental physics at this point. This is science, not engineering. I used to do experimental particle physics so it is science I am somewhat familiar with. But it is still not engineering and unlikely to be for another decade or two if ever. _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
On May 29, 2019, at 6:34 AM, Phillip Hallam-Baker <phill@hallambaker.com> wrote: > On Wed, May 29, 2019 at 2:24 AM Ron Garret <ron@flownet.com> wrote: > > On May 28, 2019, at 1:53 PM, Phillip Hallam-Baker <phill@hallambaker.com> wrote: > > > The other point to bear in mind is that we won't know whether there is a limit to quantum entanglement until we encounter it. > > That’s true, but... > > > There is no law of physics that states we must be able to form arbitrarily complex superpositions of quantum states. That is an assumption in our current models of physics. > > That’s not quite true. (Or perhaps it’s more correct to say that it’s true, but misleading.) It’s true in the same sense that the speed of light being a constant is the same in all reference frames is an “assumption.” The evidence that this is correct is overwhelming, and the evidence that quantum mechanics applies to arbitrarily large systems of entangled states is likewise overwhelming. All attempts to find an experimental regime where quantum mechanics fails have failed. If you seek solace against the possibility of cryptographic keys falling to quantum computers you are better off looking for it in engineering constraints than in the prospect of discovering new physics. > > "All attempts to find an experimental regime where quantum mechanics fails have failed" > > That is not remotely true. We still haven't figured out how to make gravity work. Let me be more precise then: QM has been experimentally demonstrated with objects up to 10,000 AMU mass [https://arxiv.org/abs/1310.8343]. The smallest gravitational field that has ever been measured (AFAICT) was produced by a mass of ~10^22 AMU [http://jetp.ac.ru/cgi-bin/dn/e_067_10_1963.pdf] (~100 mg). That’s a gap of 17 orders of magnitude. It is known that QM and GR are mathematically incompatible with each other, so somewhere in that gap one or the other of the two theories has to give. But all attempts to find an experimental regime where either theory can be demonstrated to fail have failed, and all attempt to determine whether it is QM or GR that has to give have also failed. All I’m saying is that, given the above facts, betting the future of digital security on the hypothesis that QM fails before it gets to the point where you can implement Shor’s algorithm is unwise. Personally, my money is on gravity being quantized, and also that to demonstrate this requires a field strength on the order of what is found near the event horizon of a black hole, so we’re unlikely to see this question definitively settled in a laboratory any time soon. > More relevantly, what exactly do we mean by decoherence? what exactly is it that causes it? That has been well understood for decades now. The seminal papers on decoherence were published in 1970. For an accessible layman’s account I recommend David Z. Alberts excellent book, “Quantum Mechanics and Experience”, chapter 5. The short version of the story is that a system decoheres if any of its degrees of freedom become entangled with anything outside of the system (and note that entanglement is not an all-or-nothing phenomenon. Entanglement is a continuum.) When that happens, the system considered in isolation is no longer in a pure state and can no longer self-interfere. The more degrees of freedom a system has, the harder it becomes as a practical matter to keep all of them isolated from (i.e. prevent them from becoming entangled with) their environment. It really is just as simple as that. > The assumption here seems to be that the only reason to build quantum computers is to break RSA. No, the assumption is that breaking RSA will be catastrophic, and so the prospect of developing QC is a cause for concern in the context of a discussion list dedicated to cryptography. I certainly never meant to imply that that’s the *only* reason anyone should care about quantum computing, but it’s certainly *a* reason. > This is science, not engineering. I used to do experimental particle physics so it is science I am somewhat familiar with. But it is still not engineering and unlikely to be for another decade or two if ever. Yes, I’m not denying that. All I’m saying is that *if* there turns out to be a insurmountable obstacle to breaking crypto with QC, that obstacle is more likely to be an engineering limitation than a scientific one. rg _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
On Wed, May 29, 2019 at 8:46 AM Ron Garret <ron@flownet.com> wrote: > > On May 29, 2019, at 6:34 AM, Phillip Hallam-Baker <phill@hallambaker.com> > wrote: > > > ..... > All I’m saying is that, given the above facts, betting the future of > digital security on the hypothesis that QM fails before it gets to the > point where you can implement Shor’s algorithm is unwise. > > anything outside of the system (and note that entanglement is not an > all-or-nothing phenomenon. Entanglement is a continuum.) When that > happens, the system considered in isolation is no longer in a pure state > and can no longer self-interfere. The more degrees of freedom a system > has, the harder it becomes as a practical matter to keep all of them > isolated from (i.e. prevent them from becoming entangled with) their > environment. It really is just as simple as that. > > The assumption here seems to be that the only reason to build quantum > computers is to break RSA. > > > No, the assumption is that breaking RSA will be catastrophic, and so the > prospect of developing QC is a cause for concern in the context of a > discussion list dedicated to cryptography. I certainly never meant to > imply that that’s the *only* reason anyone should care about quantum > computing, but it’s certainly *a* reason. > Missing in this discussion is the design of processors (silicon layout and design) by more modest quantum computers and design of quantum machines themselves. i.e. A difficult problem today is the optimization of programming languages and hardware description languages. Currently computation has been moved by silicon advances but some difficult problems will fall to clever insights. The book "Programming Perls" is a good reminder that algorithms and insights can change expectations. An attacker has control of data in and the public key so there is a lot of leverage in the hands of a determined decryption effort attempting to discover the private key. The window of risk is a long way out for some data. BTW: this has been educational. I learned a lot from this, thank you all. -- T o m M i t c h e l l _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
89.2 MB — 3,873 messages
Last sync: 15 July 2019 22:44

Move Messages

Save

Apply Labels


Warning: Unknown: write failed: No space left on device (28) in Unknown on line 0

Warning: Unknown: Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/var/lib/php/sessions) in Unknown on line 0