But quantum computers change this thinking. These machines are far more powerful than classical computers and should be able to break these codes with ease.
That raises an important questionwhen will quantum computers be powerful enough to do this? After that date, any information protected by this form of encryption becomes insecure.
So computer scientists have attempted to calculate the resources such a quantum computer might need and then work out how long it will be until such a machine can be built. And the answer has always been decades.
Today, that thinking needs to be revised thanks to the work of Craig Gidney at Google in Santa Barbara and Martin Eker at the KTH Royal Institute of Technology in Stockholm, Sweden. These guys have found a more efficient way for quantum computers to perform the code-breaking calculations, reducing the resources they require by orders of magnitude.
Consequently, these machines are significantly closer to reality than anyone suspected. The result will make uncomfortable reading for governments, military and security organizations, banks, and anyone else who needs to secure data for 25 years or longer.
First some background. Back in 1994, the American mathematician Peter Shor discovered a quantum algorithm that outperformed its classical equivalent. Shors algorithm factors large numbers and is the crucial element in the process for cracking trapdoor-based codes.
Trapdoor functions are based on the process of multiplication, which is easy to perform in one direction but much harder to do in reverse. For example, it is trivial to multiply two numbers together: 593 times 829 is 491,597. But it is hard to start with the number 491,597 and work out which two prime numbers must be multiplied to produce it.
And it becomes increasingly difficult as the numbers get larger. Indeed, computer scientists consider it practically impossible for a classical computer to factor numbers that are longer than 2048 bits, which is the basis of the most commonly used form of RSA encryption.
Shor showed that a sufficiently powerful quantum computer could do this with ease, a result that sent shock waves through the security industry.
And since then, quantum computers have been increasing in power. In 2012, physicists used a four-qubit quantum computer to factor 143. Then in 2014 they used a similar device to factor 56,153.
Its easy to imagine that at this rate of progress, quantum computers should soon be able to outperform the best classical ones.
Not so. It turns out that quantum factoring is much harder in practice than might otherwise be expected. The reason is that noise becomes a significant problem for large quantum computers. And the best way currently to tackle noise is to use error-correcting codes that require significant extra qubits themselves.
Taking this into account dramatically increases the resources required to factor 2048-bit numbers. In 2015, researchers estimated that a quantum computer would need a billion qubits to do the job reliably. Thats significantly more than the 70 qubits in todays state-of-the-art quantum computers.
On that basis, security experts might well have been able to justify the idea that it would be decades before messages with 2048-bit RSA encryption could be broken by a quantum computer.
Now Gidney and Eker have shown how a quantum computer could do the calculation with just 20 million qubits. Indeed, they show that such a device would take just eight hours to complete the calculation. [As a result], the worst case estimate of how many qubits will be needed to factor 2048 bit RSA integers has dropped nearly two orders of magnitude, they say.
Their method focuses on a more efficient way to perform a mathematical process called modular exponentiation. This is the process of finding the remainder when a number is raised to a certain power and then divided by another number.
This process is the most computationally expensive operation in Shors algorithm. But Gidney and Eker have found various ways to optimize it, significantly reducing the resources needed to run the algorithm.
Thats interesting work that should have important implications for anyone storing information for the future. A 20-million-qubit quantum computer certainly seems a distant dream today. But the question these experts should be asking themselves is whether such a device could be possible within the 25 years they want to secure the information. If they think it is, then they need a new form of encryption.
Indeed, security experts have developed post-quantum codes that even a quantum computer will not be able to crack. So it is already possible to safeguard data today against future attack by quantum computers. But these codes are not yet used as standard.
For ordinary people, there is little risk. Most people use 2048-bit encryption, or something similar, for tasks like sending credit card details over the internet. If these transactions are recorded today and broken in 25 years, little will be lost.
But for governments, there is more at stake. The messages they send todaybetween embassies or the military, for examplemay well be significant in 20 years and so worth keeping secret. If such messages are still being sent via 2048-bit RSA encryption, or something similar, then these organizations should start worryingquickly.
Ref: arxiv.org/abs/1905.09749 : How To Factor 2048 Bit RSA Integers In 8 Hours Using 20 Million Noisy Qubits
See original here:
How a quantum computer could break 2048-bit RSA encryption ...
- Quantum computers are on the path to solving bigger problems for BMW, LG and others - CNET - December 31st, 2021
- Research Opens the Door to Fully Light-Based Quantum Computing - Tom's Hardware - December 31st, 2021
- 10 science breakthroughs of 2021 that you need to know about - India Today - December 31st, 2021
- 7 Tech Trends Where Israel Could Make An Impact In 2022 - NoCamels - Israeli Innovation News - December 31st, 2021
- Research Fellow, Theory, Centre for Quantum Technologies job with NATIONAL UNIVERSITY OF SINGAPORE | 275976 - Times Higher Education (THE) - December 24th, 2021
- The Spanish who have entered this year 2021 in the Guinness Book of Records | Life - Central Valley Business Journal - December 24th, 2021
- Quantum computation is helping uncover materials that turn wasted heat into electricity - The Next Web - December 22nd, 2021
- Quantum Cryptography Market Share-Size, Growth Drivers 2021, Global Demand, Emerging Trends, Opportunities in Grooming Regions, Key Players... - December 22nd, 2021
- What Is Quantum Computing? - Data Center Knowledge - December 16th, 2021
- Quantum computing now has an out-of-this-world problem: Cosmic rays - ZDNet - December 16th, 2021
- Lecturer in Computer Science, Quantum Computing job with ROYAL HOLLOWAY, UNIVERSITY OF LONDON | 275274 - Times Higher Education (THE) - December 16th, 2021
- Atos announces hybridisation projects at its 8th Quantum Advisory Board - Scientific Computing World - December 16th, 2021
- IonQ Stock Is an Investment in Cutting Edge, Global Solutions - InvestorPlace - December 16th, 2021
- Another setback for 'Majorana' particle as Science paper earns an expression of concern - Retraction Watch - December 16th, 2021
- US is risking APOCALYPSE with millions lining up for food & water if theres a cyberattack on power grid,... - The Sun - December 16th, 2021
- ColdQuanta and Strangeworks Announce Addition of Hilbert Quantum Computer to Strangeworks Ecosystem - The Grand Junction Daily Sentinel - December 8th, 2021
- Atos confirms role as global leader in quantum hybridization technologies at its 8th Quantum Advisory Board - Yahoo Finance - December 3rd, 2021
- Breakthroughs in quantum computing drive higher processing power - Digital Nation - November 25th, 2021
- US blocks export of quantum computing tech to Chinese organizations - CNET - November 25th, 2021
- Why Blockchain isnt as secure as you think - Evening Standard - November 25th, 2021
- Tech pioneers to headline Princeton conference on innovation and entrepreneurship - Princeton University - November 25th, 2021
- Quantum Turing machine - Wikipedia - November 11th, 2021
- Is Quantum Computing the Future of AI? - Datanami - November 11th, 2021
- Multiverse Computing Partners with IonQ to Bring Quantum Computing to Global Finance - HPCwire - November 11th, 2021
- Leading Technology Executive Max Schireson Joins Quantum Machines' Board of Directors - HPCwire - November 11th, 2021
- Andrew Chi-Chih Yao receives the 2021 Kyoto Prize in Advanced Technology: Commemorative Lecture on his wonderful journey in computer science to be... - November 11th, 2021
- Clever Combination of Quantum Physics and Molecular Biology - SciTechDaily - November 11th, 2021
- QuTech creates a time crystal - Innovation Origins - November 6th, 2021
- Grover's algorithm - Wikipedia - November 1st, 2021
- Quantum Engineering | Electrical and Computer Engineering - November 1st, 2021
- First Photonic Quantum Computer on the Cloud - IEEE Spectrum - November 1st, 2021
- Quantum Computer Maker Rigetti to Go Public via $1.5 ... - November 1st, 2021
- Building a large-scale quantum computer is a huge challenge. Will we ever get there? - ZDNet - November 1st, 2021
- Two UCSB Scientists Receive Award to Partner With Ciscos New Quantum Research Team - Noozhawk - November 1st, 2021
- Researchers show new strategy for detecting non-conformist particles called anyons - Brown University - November 1st, 2021
- IonQ to Report Third Quarter 2021 Financial Results on November 15, 2021 - Yahoo Finance - November 1st, 2021
- UCSB and Cisco Systems Collaboration Aims to Push the Boundaries of Quantum Technologies - AZoQuantum - November 1st, 2021
- 'Quantum computer algorithms are linear algebra, probabilities. This is not something that we do a good job of teaching our kids' - The Register - October 2nd, 2021
- Quantum computer company IonQ makes Wall Street debut - Financial Times - October 2nd, 2021
- Fujitsu and Osaka University Deepen Collaborative Research and Development for Fault-Tolerant Quantum Computers - HPCwire - October 2nd, 2021
- Fermilab on the trail for a new building block of matter and quantum computing power - Medill Reports Chicago - Medill Reports: Chicago - October 2nd, 2021
- A Boulder Company Is Leading the Next Technology Revolution - 5280 - 5280 | The Denver Magazine - October 2nd, 2021
- Judith Olson, Senior Physicist at ColdQuanta, Named Next Generation Leader of the Year at Women in IT Awards - HPCwire - October 2nd, 2021
- Quantum Computing in Manufacturing Market Still Has Room To Grow: International Business Machines, D-Wave Systems, Microsoft - Digital Journal - October 2nd, 2021
- The coevolution of particle physics and computing - Symmetry magazine - September 30th, 2021
- The Fourth Industrial Revolution (4IR) Takeover: IoT and Quantum-Resistant Blockchains Are Setting the Trend - FinanceFeeds - September 30th, 2021
- $5M NSF Grant to Fund Research on Quantum Internet Foundations - Maryland Today - September 19th, 2021
- 3 Quantum Computing Stocks to Buy for Their Promising Healthcare Potential - InvestorPlace - September 19th, 2021
- DoD Buys Two New Supercomputers That Rank Among Its Most Powerful Ever - Breaking Defense - September 19th, 2021
- College Park's IonQ and the University of Maryland are teaming up to open a $20M quantum lab - Technical.ly DC - September 15th, 2021
- Where the laws of matter break down, a quantum discovery crops up - UPJ Athletics - September 15th, 2021
- Small, diamond-based quantum computers could be in our hands within five years - Cosmos Magazine - August 26th, 2021
- IBM partners with the University of Tokyo on quantum computer - Illinoisnewstoday.com - August 26th, 2021
- A Simple Crystal Could Finally Give Us Large-Scale Quantum Computing, Scientists Say - ScienceAlert - August 16th, 2021
- IBM Partnering with University of Tokyo on Quantum Computer - Datamation - August 16th, 2021
- 40 years ago the first IBM PC was presented, that's how it was and what it knew how to do - Tech Gaming Report - August 14th, 2021
- The week in science news: Olympic Bat, controlled qubits, and speeding metal stars - TechRadar - August 14th, 2021
- Quantum information and quantum field theory: Study found a new connection between them - Tech Explorist - August 14th, 2021
- Global AI Chipsets for Wireless Networks and Devices, Cloud and Next Generation Computing, IoT, and Big Data Analytics to 2026 -... - August 14th, 2021
- What is quantum computing? Everything you need to know about the strange world of quantum computers - ZDNet - July 29th, 2021
- Is Bitcoin (BTC) Safe from Grover's Algorithm? - Yahoo Finance - July 29th, 2021
- Will the NSA Finally Build Its Superconducting Spy Computer? - IEEE Spectrum - July 29th, 2021
- IBM's newest quantum computer is now up-and-running: Here's what it's going to be used for - ZDNet - July 27th, 2021
- URI to host international experts for conference on future of quantum computing - URI Today - July 27th, 2021
- Research by University of Surrey and Arqit reveals Quantum Threat to Digital Assets - Business Wire - July 27th, 2021
- A Roadmap On The Geopolitical Impact Of Emerging Technologies By Chuck Brooks And Dr. David Bray - Forbes - July 27th, 2021
- IBM and CERN on quantum computing to track the elusive Higgs boson - Tech News Inc - July 27th, 2021
- The Convergence of Communication and Computation with Dr. Vida Ilderem - RCR Wireless News - July 27th, 2021
- Quantum Computing Market is anticipated to surge at a CAGR of 33.7% over the next ten years - PRNewswire - July 21st, 2021
- Quantum Computing for the Future Grid - Transmission & Distribution World - July 21st, 2021
- Red Hat embraces quantum supremacy as it looks to the future - SiliconANGLE News - July 21st, 2021
- Quantum Computing Is Coming. What Can It Do? - Harvard Business Review - July 16th, 2021
- Rigetti Computing Partners with Riverlane, Astex Pharmaceuticals on Quantum Computing for Drug Discovery - HPCwire - July 16th, 2021
- Quantware Launches the World's First Commercially Available Superconducting Quantum Processors, Accelerating the Advent of the Quantum Computer. -... - July 16th, 2021
- The Future of Data Encryption: What You Need to Know Now - FedTech Magazine - July 16th, 2021
- Quantum computing: this is how quantum programming works using the example of random walk - Market Research Telecast - July 16th, 2021
- IBM shows the advantages of a quantum computer over traditional computers - Tech News Inc - July 16th, 2021
- Quantum Blockchain Technologies Plc - Working with D-Wave Systems - Yahoo Finance UK - July 6th, 2021
- Conclusions from Forum TERATEC 2021: European Cooperation, Novel Uses of HPC - HPCwire - July 6th, 2021
- IBM researchers demonstrate the advantage that quantum computers have over classical computers - ZDNet - July 2nd, 2021