Hackaday has a interesting posting Quantum Computing Kills Encryption. It talks how the arrival of practical quantum computers will affect the current state of encryption.
One extreme end goes like this: 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
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 as Shor’s algorithm, when applied on a quantum computer, will render the previously difficult math problems trivially easy. This will make current public-key crypto and key exchange pretty much useless.
But it does not mean that all crypto algorithms are in suuch big damage: 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.
Quantum computing is still in its infancy, but maybe you should think if you should prepare to it (transitioning away from susceptible technologies) – it is estimated that quantum computers are practical in ten-to-thirty year range. And that’s what some cryptographers are doing: developing algorithms that are not easy for quantum computers to solve. For example McEliece cryptosystems look like a good alternative to the current public-key infrastructure – but it needs to be researched more to know that it is really safe.
9 Comments
Tomi Engdahl says:
Spy Agencies Fund IBM’s Quantum Computing Research
http://www.eetimes.com/document.asp?doc_id=1328472&
The US Intelligence Advanced Research Projects Activity (IARPA) program has notified IBM that it will award the company’s scientists a major multi-year research grant to advance the building blocks for a universal quantum computer. IBM announced the grant on Dec. 8.
IBM is not disclosing further terms of the award because “it is subject to completion of final contract negotiations,” according to the company.
IARPA is the research arm of the 17-member U.S. Intelligence Community, which includes the CIA. We think a universal quantum computer could be great at addressing intelligence challenges such as deciphering encrypted data. IBM has other use-cases in mind.
Spy Agencies Fund IBM’s Quantum Computing Research
http://www.informationweek.com/government/leadership/spy-agencies-fund-ibms-quantum-computing-research/a/d-id/1323513?
Big Blue gets a multi-year grant from the US intelligence community for the development of quantum computing technology. A universal quantum computer could tackle challenges such as safeguarding against cyberattacks and speeding up medical R&D.
IBM Awarded IARPA Grant to Advance Research Towards a Universal Quantum Computer
IBM scientists will focus on building the first logical quantum bit
http://www.prnewswire.com/news-releases/ibm-awarded-iarpa-grant-to-advance-research-towards-a-universal-quantum-computer-300189567.html
YORKTOWN HEIGHTS, N.Y., Dec. 8, 2015 /PRNewswire/ — IBM (NYSE: IBM) announced today that the U.S. Intelligence Advanced Research Projects Activity (IARPA) program has notified IBM that it will award its scientists a major multi-year research grant to advance the building blocks for a universal quantum computer.
A universal quantum computer uses quantum mechanics to process massive amounts of data and perform computations in powerful new ways not possible with today’s conventional computers. This type of leap forward in computing could one day shorten the time to discovery for life-saving cancer drugs to a fraction of what it is today; unlock new facets of artificial intelligence by vastly accelerating machine learning; or safeguard cloud computing systems to be impregnable from cyber-attack.
IBM Infographic – The three known types of quantum computing and their applications, generality, and computational power.
IBM Infographic – The three known types of quantum computing and their applications, generality, and computational power.
Earlier this year, IBM scientists demonstrated critical breakthroughs to detect quantum errors by combining superconducting quantum bits (qubits) in lattices on computer chips – and whose quantum circuit design is the only physical architecture that can scale to larger dimensions.
The award is funded under the Logical Qubits (LogiQ) program of IARPA led by Dr. David Moehring. The LogiQ Program seeks to overcome the limitations of current quantum systems by building a logical qubit from a number of imperfect physical qubits.
IBM Scientists Achieve Critical Steps to Building First Practical Quantum Computer
Two Milestones Overcome Obstacles to a Working System
https://www-03.ibm.com/press/us/en/pressrelease/46725.wss
Yorktown Heights, N.Y., – 29 Apr 2015: IBM (NYSE: IBM) scientists today unveiled two critical advances towards the realization of a practical quantum computer. For the first time, they showed the ability to detect and measure both kinds of quantum errors simultaneously, as well as demonstrated a new, square quantum bit circuit design that is the only physical architecture that could successfully scale to larger dimensions.
With Moore’s Law expected to run out of steam, quantum computing will be among the inventions that could usher in a new era of innovation across industries. Quantum computers promise to open up new capabilities in the fields of optimization and simulation simply not possible using today’s computers. If a quantum computer could be built with just 50 quantum bits (qubits), no combination of today’s TOP500 supercomputers could successfully outperform it.
The IBM breakthroughs, described in the April 29 issue of the journal Nature Communications (DOI: 10.1038/ncomms7979), show for the first time the ability to detect and measure the two types of quantum errors (bit-flip and phase-flip) that will occur in any real quantum computer. Until now, it was only possible to address one type of quantum error or the other, but never both at the same time. This is a necessary step toward quantum error correction, which is a critical requirement for building a practical and reliable large-scale quantum computer.
IBM’s novel and complex quantum bit circuit, based on a square lattice of four superconducting qubits on a chip roughly one-quarter-inch square, enables both types of quantum errors to be detected at the same time. By opting for a square-shaped design versus a linear array – which prevents the detection of both kinds of quantum errors simultaneously – IBM’s design shows the best potential to scale by adding more qubits to arrive at a working quantum system.
Tomi Engdahl says:
MIT’s New 5-Atom Quantum Computer Could Make Today’s Encryption Obsolete
http://news.slashdot.org/story/16/03/06/1913213/mits-new-5-atom-quantum-computer-could-make-todays-encryption-obsolete
In traditional computing, numbers are represented by either 0s or 1s, but quantum computing relies on atomic-scale units, or “quibits,” that can be simultaneously 0 and 1 — a state known as a superposition that’s far more efficient. It typically takes about 12 qubits to factor the number 15, but researchers at MIT and the University of Innsbruck in Austria have found a way to pare that down to five qubits, each represented by a single atom, they said this week.
That, in turn, presents new risks for factorization-based methods such as RSA, used for protecting credit cards, state secrets and other confidential data.
MIT’s new 5-atom quantum computer could make today’s encryption obsolete
The scalable new system could easily crack RSA techniques
http://www.pcworld.com/article/3041115/security/mits-new-5-atom-quantum-computer-could-transform-encryption.html#tk.rss_all
Tomi Engdahl says:
Quantum Computers Crack Public-Key Encryption
RSA encryption not immune
http://www.eetimes.com/document.asp?doc_id=1329155&
No shortage of encryption and decryption schemes exists, but for those schemes that merely depend on the difficulty of finding the factors of two large prime numbers multiplied together, their days may be numbered, according to a team of researchers.
Known as public-key encryption, this encryption method—the most notable example being the popular Rivest-Shamir-Adleman (RSA) scheme —appears to be doomed by quantum computing, according to Massachusetts Institute of Technology (MIT, Cambridge) theorists working with prototyping experts at the University of Innsbruck (Austria). Using an algorithm invented by MIT professor Peter Shor and made scalable by Professor Alexei Kitaev at the California Institute of Technology (CalTech, Pasadena), a quantum computer was built to prove the concept, as presented in the paper Realization of a Scalable Shor Algorithm.
“Shor’s quantum factoring algorithm would probably help with breaking schemes which employ padding and hashing, but it would not suffice by itself,” Chuang told EE Times in an exclusive interview.
On the other hand, when quantum computers do become common, it will be possible to use quantum cryptography methods to produce uncrackable codes—even by others who have quantum computers.
“Quantum cryptography is a well-known scheme, which is uncrackable, as long as the laws of quantum physics are correct, as known today,”
Tomi Engdahl says:
Shor’s Algorithm In Five Atoms
http://hackaday.com/2016/05/01/shors-algorithm-in-five-atoms/
If you want to factor a number, one way to do it is Shor’s algorithm. That’s a quantum algorithm and finds prime factors of integers. That’s interesting because prime factorization is a big deal of creating or breaking most modern encryption techniques.
Back in 2001, a group at IBM factored 15 (the smallest number that the algorithm can factor) using a 7 qubit system that uses nuclear magnetic resonance. Later, other groups duplicated the feat using photonic qubits. Typical implementations take 12 qubits. However, recent work at MIT and the University of Innsbruck can do the same trick with 5 atoms caught in an ion trap. The researchers believe their implementation will easily scale to larger numbers.
Each qubit is an atom and LASER pulses perform the logic operations.
The beginning of the end for encryption schemes?
New quantum computer, based on five atoms, factors numbers in a scalable way.
https://news.mit.edu/2016/quantum-computer-end-encryption-schemes-0303
What are the prime factors, or multipliers, for the number 15? Most grade school students know the answer — 3 and 5 — by memory. A larger number, such as 91, may take some pen and paper. An even larger number, say with 232 digits, can (and has) taken scientists two years to factor, using hundreds of classical computers operating in parallel.
Because factoring large numbers is so devilishly hard, this “factoring problem” is the basis for many encryption schemes for protecting credit cards, state secrets, and other confidential data. It’s thought that a single quantum computer may easily crack this problem, by using hundreds of atoms, essentially in parallel, to quickly factor huge numbers.
In 1994, Peter Shor, the Morss Professor of Applied Mathematics at MIT, came up with a quantum algorithm that calculates the prime factors of a large number, vastly more efficiently than a classical computer. However, the algorithm’s success depends on a computer with a large number of quantum bits. While others have attempted to implement Shor’s algorithm in various quantum systems, none have been able to do so with more than a few quantum bits, in a scalable way.
Now, in a paper published today in the journal Science, researchers from MIT and the University of Innsbruck in Austria report that they have designed and built a quantum computer from five atoms in an ion trap. The computer uses laser pulses to carry out Shor’s algorithm on each atom, to correctly factor the number 15. The system is designed in such a way that more atoms and lasers can be added to build a bigger and faster quantum computer, able to factor much larger numbers. The results, they say, represent the first scalable implementation of Shor’s algorithm.
Tomi Engdahl says:
The Race Is On to Protect Data From the Next Leap in Computers. And China Has the Lead.
https://www.nytimes.com/2018/12/03/technology/quantum-encryption.html?utm_campaign=Email%20Newsletter&utm_source=hs_email&utm_medium=email&utm_content=68985424&_hsenc=p2ANqtz-81rZr8dEZ7ofLibIJoAknH3rnePNz0vqUw0KoxjHhfifRGCEFcbwTfBB2Rkiw8mBey_HGPdHXWDNXGSWeJ-3a4npHlk1IxOkaQZvZDWxv0pN4MZGk&_hsmi=68985424
The world’s leading technology companies, from Google to Alibaba in China, are racing to build the first quantum computer, a machine that would be far more powerful than today’s computers.
This device could break the encryption that protects digital information, putting at risk everything from the billions of dollars spent on e-commerce to national secrets stored in government databases.
An answer? Encryption that relies on the same concepts from the world of physics. Just as some scientists are working on quantum computers, others are working on quantum security techniques that could thwart the code-breaking abilities of these machines of the future.
It is a race with national security implications, and while building quantum computers is still anyone’s game, China has a clear lead in quantum encryption. As it has with other cutting-edge technologies, like artificial intelligence, the Chinese government has made different kinds of quantum research a priority.
“China has a very deliberate strategy to own this technology,” said Duncan Earl, a former researcher at Oak Ridge National Laboratory who is president and chief technology officer of Qubitekk, a company that is exploring quantum encryption. “If we think we can wait five or 10 years before jumping on this technology, it is going to be too late.”
Tomi Engdahl says:
https://threatpost.com/chinese-quantum-computing-warning-security/161935/
Tomi Engdahl says:
RSA’s demise from quantum attacks is very much exaggerated, expert says | Ars Technica
https://arstechnica.com/information-technology/2023/01/fear-not-rsa-encryption-wont-fall-to-quantum-computing-anytime-soon/
Expert says the focus on quantum attacks may distract us from more immediate threats.
Scientists and cryptographers have known for two decades that a factorization method known as Shor’s algorithm makes it theoretically possible for a quantum computer with sufficient resources to break RSA. That’s because the secret prime numbers that underpin the security of an RSA key are easy to calculate using Shor’s algorithm. Computing the same primes using classical computing takes billions of years.
The only thing holding back this doomsday scenario is the massive amount of computing resources required for Shor’s algorithm to break RSA keys of sufficient size. The current estimate is that breaking a 1,024-bit or 2,048-bit RSA key requires a quantum computer with vast resources. Specifically, those resources are about 20 million qubits and about eight hours of them running in superposition.
The paper, published three weeks ago by a team of researchers in China, reported finding a factorization method that could break a 2,048-bit RSA key using a quantum system with just 372 qubits when it operated using thousands of operation steps. The finding, if true, would have meant that the fall of RSA encryption to quantum computing could come much sooner than most people believed.
RSA’s demise is greatly exaggerated
At the Enigma 2023 Conference in Santa Clara, California, on Tuesday, computer scientist and security and privacy expert Simson Garfinkel assured researchers that the demise of RSA was greatly exaggerated. For the time being, he said, quantum computing has few, if any, practical applications.
“In the near term, quantum computers are good for one thing, and that is getting papers published in prestigious journals,” Garfinkel, co-author with Chris Hoofnagle of the 2021 book Law and Policy for the Quantum Age, told the audience. “The second thing they are reasonably good at, but we don’t know for how much longer, is they’re reasonably good at getting funding.”
Even when quantum computing becomes advanced enough to provide useful applications, the applications are likely for simulating physics and chemistry, and performing computer optimizations that don’t work well with classical computing. Garfinkel said that the dearth of useful applications in the foreseeable future might bring on a “quantum winter,” similar to the multiple rounds of artificial intelligence winters before AI finally took off.
Within short order, a host of researchers pointed out fatal flaws in Schnorr’s algorithm that have all but debunked it. Specifically, critics said there was no evidence supporting the authors’ claims of Schnorr’s algorithm achieving polynomial time, as opposed to the exponential time achieved with classical algorithms.
The research paper from three weeks ago seemed to take Shor’s algorithm at face value. Even when it’s supposedly enhanced using QAOA—something there’s currently no support for—it’s questionable whether it provides any performance boost.
“All told, this is one of the most actively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen … many,” Scott Aaronson, a computer scientist at the University of Texas at Austin and director of its Quantum Information Center, wrote. “Having said that, this actually isn’t the first time I’ve encountered the strange idea that the exponential quantum speedup for factoring integers, which we know about from Shor’s algorithm, should somehow ‘rub off’ onto quantum optimization heuristics that embody none of the actual insights of Shor’s algorithm, as if by sympathetic magic.”
In geological time, yes; in our lifetime, no
On Tuesday, Japanese technology company Fujitsu published a press release that provided further reassurance that the cryptocalypse isn’t nigh. Fujitsu researchers, the press release claimed, found that cracking an RSA key would require a fault-tolerant quantum computer with a scale of roughly 10,000 qubits and 2.23 trillion quantum gates, and even then, the computation would require about 104 days.
“For example, when [the Fujitsu researchers] say 10,000 qubits in the press release, do they mean logical or physical qubits?” Samuel Jaques, a doctoral student at the University of Cambridge, wrote in an email. “In my view, the best estimate for quantum factoring is still [Craig] Gidney and [Martin] Ekerå from 2020, who estimate that factoring RSA-2048 would need 20 million physical qubits and 8 hours. If Fujitsu’s result drops the physical qubit count from 20 million to 10,000, that’s a huge breakthrough; if instead they need 10,000 logical qubits, then that’s much more than Gidney and Ekerå so I would need to check carefully to see why.”
Even when the day comes that there’s a quantum computer with the power envisioned by Gidney and Ekerå, the notion that RSA will fall in one stroke is misleading. That’s because it would take this 20 million-qubit quantum system eight hours in constant superposition to crack a single encryption key. That would certainly be catastrophic since someone might be able to use the capability to cryptographically sign malicious updates with a Microsoft or Apple key and distribute them to millions of people.
But even then, the scenario that nation-states are storing all encrypted communications in a database and will decrypt them all in bulk once a quantum computer becomes available is unrealistic, given the number of keys and the resources required to crack them all.
Tomi Engdahl says:
Quantum Decryption Brought Closer by Topological Qubits
https://www.securityweek.com/quantum-decryption-brought-closer-by-topological-qubits/
Quantinuum claims the most powerful quantum computer currently available –through cloud-based access from Quantinuum, and available through Azure Quantum in June 2023.
Quantinuum has demonstrated the controlled creation and manipulation of non-Abelian anyons – or, put more simply, brought the arrival of large-scale, error resistant quantum computers much closer.
Quantinuum
The processing power of quantum computers is derived from the ability of qubits (quantum bits) to offer multiple states, rather than the simple binary offering available in classical computers. The problem is that qubits are not stable and are highly subject to external disturbance from noise and heat. The most common solution to this problem is to use additional qubits to provide error correction to the operational qubits – but the result is that a general purpose operational quantum computer will require millions of qubits working together.
There is an alternative approach. Rather than use additional fragile ‘traditional’ qubits for error correction, create more stable qubits that require less error correction. This is the purpose of the topological qubit.
Tomi Engdahl says:
Kvanttitietokoneen teho kasvaa ja uhkaa tietoturvaa – Pian sillä voi murtautua valtioiden kriittiseen infrastruktuuriin
Kun kvanttitietokoneen teho kasvaa tarpeeksi suureksi, se kykenee peittoamaan nykyiset salausmenetelmät. Tämä on vain ajan kysymys.
https://www.tekniikkatalous.fi/uutiset/kvanttitietokoneen-teho-kasvaa-ja-uhkaa-tietoturvaa-pian-silla-voi-murtautua-valtioiden-kriittiseen-infrastruktuuriin/57922bda-f9d2-4c88-8ccd-d9af6e9b187d