How Quantum Computers Break The Internet… Starting Now
A quantum computer in the next decade could crack the encryption our society relies on using Shor’s Algorithm. Head to https://brilliant.org/veritasium to start your free 30-day trial, and the first 200 people get 20% off an annual premium subscription.
▀▀▀
A huge thank you to those who helped us understand this complex field and ensure we told this story accurately – Dr. Lorenz Panny, Prof. Serge Fehr, Dr. Dustin Moody, Prof. Benne de Weger, Prof. Tanja Lange, PhD candidate Jelle Vos, Gorjan Alagic, and Jack Hidary.
A huge thanks to those who helped us with the math behind Shor’s algorithm – Prof. David Elkouss, Javier Pagan Lacambra, Marc Serra Peralta, and Daniel Bedialauneta Rodriguez.
▀▀▀
References:
Joseph, D., et al. (2022). Transitioning organizations to post-quantum cryptography. Nature, 605(7909), 237-243. – https://ve42.co/Joseph2022
Bernstein, D. J., & Lange, T. (2017). Post-quantum cryptography. Nature, 549(7671), 188-194. – https://ve42.co/Bernstein2017
An Insight, An Idea with Sundar Pichai – Quantum Computing, Wold Economic Forum via YouTube – https://ve42.co/QCWEFyt
Migrating to Post-Quantum Cryptography, The White House – https://ve42.co/PQCWhiteHouse
Kotas, W. A. (2000). A brief history of cryptography. University of Tennessee – https://ve42.co/Kotas2000
Hellman, M. (1976). New directions in cryptography. IEEE transactions on Information Theory, 22(6), 644-654. – https://ve42.co/Hellman1976
Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126. – https://ve42.co/Rivest1978
Kak, A. (2023). Lecture 12: Public-Key Cryptography and the RSA Algorithm – https://ve42.co/Kak2023
Calderbank, M. (2007). The RSA Cryptosystem: History, Algorithm, Primes. University of Chicago. – https://ve42.co/Calderbank2007
Cryptographic Key Length Recommendation, Keylength – https://ve42.co/KeyLength
Coppersmith, D. (2002). An approximate Fourier transform useful in quantum factoring. arXiv preprint quant-ph/0201067. – https://ve42.co/Coppersmith2002
Quantum Fourier Transform, Qiskit – https://ve42.co/Qiskit
Shor, P. W. (1994, November). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124-134). IEEE. – https://ve42.co/Shor1994
Shor’s algorithm, Wikipedia – https://ve42.co/ShorWiki
Euler’s totient function, Wikipedia – https://ve42.co/EulerWiki
Asfaw, A. (2020). Shor’s Algorithm Lecture Series, Qiskit Summer School – https://ve42.co/ShorYT
How Quantum Computers Break Encryption, minutephysics via YouTube – https://ve42.co/PQCmpyt
Breaking RSA Encryption – an Update on the State-of-the-Art, QuintessenceLabs – https://ve42.co/QuintessenceLabs
O’Gorman, J., & Campbell, E. T. (2017). Quantum computation with realistic magic-state factories. Physical Review A, 95(3), 032338. – https://ve42.co/OGorman2017
Gidney, C., & Ekerå, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, 433. – https://ve42.co/Gidney2021
2021 Quantum Threat Timeline Report, Global Risk Institute – https://ve42.co/QuantumRisk
The IBM Quantum Development Roadmap, IBM – https://ve42.co/IBMQC
Post-Quantum Cryptography, Computer Security Resource Center (NIST) – https://ve42.co/CSRCPQC
Alagic, G., et al. (2022). Status report on the third round of the NIST post-quantum cryptography standardization process. US Department of Commerce, NIST. – https://ve42.co/Alagic2022
Thijs, L. (2015). Lattice cryptography and lattice cryptanalysis – https://ve42.co/Thijs2015
▀▀▀
Special thanks to our Patreon supporters:
Tj Steyn, Meg Noah, Bernard McGee, KeyWestr, Elliot Miller, Jerome Barakos, M.D., Amadeo Bee, TTST, Balkrishna Heroor, Chris LaClair, John H. Austin, Jr., Eric Sexton, john kiehl, Anton Ragin, Diffbot, Gnare, Dave Kircher, Burt Humburg, Blake Byers, Evgeny Skvortsov, Meekay, Bill Linder, Paul Peijzel, Josh Hibschman, Mac Malkawi, Juan Benet, Ubiquity Ventures, Richard Sundvall, Lee Redden, Stephen Wilcox, Marinus Kuivenhoven, Michael Krugman, Cy ‘kkm’ K’Nelson, Sam Lutfi.
▀▀▀
Written by Casper Mebius & Derek Muller
Edited by Trenton Oliver
Filmed by Raquel Nuno
Animated by Ivy Tello & Mike Radjabov
Additional video/photos supplied by Getty Images & Pond5
Music from Epidemic Sound & Jonny Hyman
Produced by Derek Muller, Petr Lebedev, & Emily Zhang
As a science educator you should be particularly proud of this video. I’ve never seen this topic explained anywhere close to as good as what this video does. Kudos!
@kaka That is modified version of Einstein quote: If you can’t explain it to a six year old, you don’t understand it yourself.
If you cannot give a good explanation you dont have a good understanding of it
@Don’t Read Profile Photo okay, I will not.
I didn’t understand anything in the video explained.
I’m a CS student and have been trying to understand this concept recently, but the explanations I’ve found in the internet have been too complex. This was the best explanation I’ve found. I’m not sure if I understand everything you said but I understood most of it. Thanks!
Like PBS space time. 😂
@Jesse can it be 0 and 1 at the same time?
Just imagine the logical gateway that remains in both states simultaneously.
That’s basically it from the IT perspective.
GPT4…
Instead of bits, we now have qubits, 0 and 1 until measured, a superstition state until measured. Once measured and revealed, the qbits can possibly be 0 and 1 in many probabilities.
I am just 18 but I really wish that I could complete my college and dive into one of these heavy research projects. You really inspired me to study physics and mathematics, and I am grateful for that.
what about you go chase some money? u gonna need cash, but not just cash, u gonna need big cash.
Honestly, I wish you good luck. Your first year or two in physics will let you know very quickly if you want to still be there. It’s an intense degree. I’m glad I was exposed to it, but I’m also glad I didn’t finish it and switched.
I did some RA work in Quantum Computing at the University of Waterloo as part of my degree. It was amazing and probably the most interesting thing I did in those years. If you have the willpower to enjoy failure, you will enjoy physics. I’d avoid Maths just because as a University level field it’s a bit more focused on the theoretical side and not practical applications in other subjects.
@Rohan Ganapathy what was your jee rank
You got time to make it in to this research! Make your dream come true!
I hope all will work out well for you. I am just 9 years old, and i also really wish that i could dive into one of these heavy research projects allready. I am so inspired! luckily I am in a position where I was allowed to skipp multiple years. So now I follow classes with peers somewhat on the same intellectual level as me. Good luck with your science career.
I just wrote a report about this exact topic less than sixth months ago, and it’s so fulfilling to see you making the same points and using the same resources I did. Seeing someone as accomplished as you in this area of education doing the same thing I did makes me feel very validated.
Sixth. Lol
As a computer science student this is one of the best videos i have seen on quantum computing and has helped me understand this more than I ever have before. anytime i get asked about this stuff (which is more often than I would have hoped for) I am going to forward them this video. Wonderful work Derek
Your a student bro … no one is asking you 😂😂😂
This was some of your best work so far, at least for me. Your explanation of both conventional and lattice encryption was super clear and the visuals were just what I needed at any moment. I’m in awe of your ability to find, research and find interesting bitesized insights into such a broad range of topics while still retaining everything that makes this channel unique. Thank you.
There is no science educator like Derek in youtube platform. I’m really consfused as in how he select his next topic for the video, and he nails it. Kudos to him and his team!
Derek is not an expert in the fields he presents and it shows. He’s pretty good though.
Kurzgesagt is also a very good science education channel.
You clearly haven’t watched 3blue1brown. This video looks like it’s very much inspired by this channel, even the music.
Both are great since communicators, but regarding math, there is just noone who beats 3blue1brown imho.
I remember studying the RSA algorithm in my group theory module during my undergrad. The lattice-based encryption method was very interesting to learn! I don’t really know much about quantum computing, but this video explained everything very clearly.
Thanks you for the comment and support hit me up I got package 📦 for you🏆🏆
So exciting!! I’m so happy that you covered quantum computers! What a great day today has been. It is always upsetting to see the word ‘quantum’ being thrown around without much explanation in many sources. And it looks like you did a fantastic job again at demystifying the topic without over simplifying. Thanks a lot.
Thanks for making this video. As a software engineer I was already mostly aware of the problem but not many people know about it. This could change so much of our lives.