Quantum Computing: Threats to Encryption Algorithms
Explore the potential vulnerabilities of today's encryption algorithms to quantum computing, including Grover's algorithm and Shor's algorithm. Understand the symmetric threat posed by Grover's algorithm and the asymmetric threat from Shor's algorithm. Learn about the reality of qubit requirements and receive advice on ensuring security. References to key studies provide insights into the impact of quantum computing on encryption standards.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
QUANTUM COMPUTING THE POTENTIAL VULNERABILITY OF TODAY S ENCRYPTION ALGORITHMS
AGENDA The Threats Grover s algorithm Shor s algorithm Reality check
SYMMETRIC THREAT - GROVERS ALGORITHM Conventional Compute: To guess the correct key, on average you have to try half the combinations. E.g. 232 has 4,294,967,296 combinations 231 has 2,147,483,648 combinations @ 1,000 guesses per second = ~ 25 days Quantum Compute: Grover s algorithm requires only the square root of all combinations Our 232 keyspace can be solved in 216 guesses 216is 65,536 Is this a problem? 2128 keyspace with Grover s algorithm would require 264 guesses @ 1,000,000 guesses per second = 584,554 years!
ASYMMETRIC THREAT SHORS ALGORITHM Leverages quantum superposition to solve the factorisation of large primes Factorisation? RSA relies on the product of two large primes, p and q (pq = n) Factorisation is the reversal of the product E.g., 15 = 5 x 3 To factor RSA-2048 with classical means is estimated to take longer than the life of universe! Gidney and Eker suggest RSA-2048 could be factored in ~8 hours with 20 million qubits [1]
THE REALITY Lots of qubits are needed 2953 for AES-128 4099 for RSA-2048 6681 for AES-256 At least 1000 physical qubits required per logical qubit [3] 20m for RSA-2048 Qubit count remains low Diagram from: Cheng, et al. doi: 10.1109/AERO50100.2021.9438392 [2]
ADVICE Don t panic yet AES is probably safe RSA adopt longer key lengths e.g. RSA-4096
REFERENCES [1] C. Gidney and M. Eker , "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits," (in en-GB), Quantum, vol. 5, p. 433, April 15 2021, doi: 10.22331/q-2021-04-15-433 [2] J. K. Cheng, E. M. Lim, Y. Y. Krikorian, D. J. Sklar, and V. J. Kong, "A Survey of Encryption Standard and Potential Impact Due to Quantum Computing," in 2021 IEEE Aerospace Conference (50100), March 6-13 2021, pp. 1-10, doi: 10.1109/AERO50100.2021.9438392. [Online]. Available: https://ieeexplore.ieee.org/document/9438392/ [3] G. Lichfield. "Inside the race to build the best quantum computer on Earth." https://www.technologyreview.com/2020/02/26/916744/quantum-computer-race-ibm-google/ (accessed September 19, 2021).
