How Quantum Computers Break Encryption | Shor's Algorithm Explained
HTML-код
- Опубликовано: 26 сен 2024
- Go to www.dashlane.co... to download Dashlane for free, and use offer code minutephysics for 10% off Dashlane Premium!
Support MinutePhysics on Patreon! / minutephysics
This video explains Shor’s Algorithm, a way to efficiently factor large pseudoprime integers into their prime factors using a quantum computer. The quantum computation relies on the number-theoretic analysis of the factoring problem via modular arithmetic mod N (where N is the number to be factored), and finding the order or period of a random coprime number mod N. The exponential speedup comes in part from the use of the quantum fast fourier transform which achieves interference among frequencies that are not related to the period (period-finding is the goal of the QFT FFT).
REFERENCES
RSA Numbers (sample large numbers to try factoring)
en.wikipedia.o...
IBM on RSA
www.ibm.com/su...
Modulo Multiplication Group Tables
mathworld.wolfr...
Difference of squares factorization
en.wikipedia.o...
Euclid’s Algorithm
en.wikipedia.o...
Rational sieve for factoring
en.wikipedia.o...
General Number field Sieve
en.wikipedia.o...
Scott Aaronson blog post about Shor’s Algorithm
www.scottaaron...
Experimental implementation of Shor’s Algorithm (factoring 15, 21, and 35)
arxiv.org/pdf/...
Adiabatic Quantum Computation factoring the number 291311
arxiv.org/pdf/...
Scott Aaronson course notes
www.scottaaron...
www.scottaaron...
Shor’s Algorithm on Quantiki
www.quantiki.o...
TLS And SSL use RSA encryption
en.wikipedia.o...
Dashlane security whitepaper
www.dashlane.c...
Link to Patreon Supporters: www.minutephysi...
MinutePhysics is on twitter - @minutephysics
And facebook - / minutephysics
Minute Physics provides an energetic and entertaining view of old and new problems in physics -- all in a minute!
Created by Henry Reich
Me at the half mark: "This couldn't get anymore complicated."
minutephysics: *_"Fourier Transforms!"_*
Imma just code a basic version of this real quick
Quantum Fourier Transformation
The fourier transform is definetely the simple part of this.
Me after concepts of concepts back to back: 🤯
lmao same
My brain waves superpositioned in a way that only the neurons which did not undertand got positive interference
You sir, you got the point of the video.
¡Olé!
Since you were able to isolate the non-understanding neurons, subtract them from your results to get total understanding of the video.
You're welcome.
Hahaha 🤣
5Head
Hey, that's a lot of minutes of physics.
ghufran ullah Exactly 17.5 minutes. Though I’m not complaining.
wait. that’s illegal
Actually pretty much half of the video was purely minutes of maths and not physics.
Hey, that's pretty good!
It's only a minute of physics if run in a Quantum Computer
Him: "...and here's the clever part."
Me: "WHAT WAS THE REST OF THIS?!"
getting to the clever part
Its can even get complicated, when your first language isnt English, but Russian...
@@ДмитрийАвиО well you’re doing better than all the russian people who cant speak english at all so
@@ДмитрийАвиО I can confirm you're Russian
Source: your name and first 5 words
@@danielyuan9862 you misunderstand. The above commenter is saying that it ALL seems clever (i.e. Complex and complicated) to them.
"I'm going to attempt to explain"
*me: brain explodes*
Yea, every other video he explains something ... quantum encryption he ATTEMPTS to explain
Yours exploded? Mine was removed from existence!
I am a physics and maths guy and still get lost
That's nothing to worry about. It took me a long time to understand anything in my lectures on quantum chemistry/advanced math. This stuff takes just buttload of time and a lot of different sources since it gets super abstract and we have nothing to relate it to. Even after a couple of years, I would consider myself not even a newbie in this field.
Just take some facts that interest you from the vid and general idea and ignore the math for a bit. Like these:
- Cryptography is based on us lacking raw computational resources to crack the encryption
- Using some clever math, you can skew this encryption by removing the unwanted "stuff" using cool quantum properties
- Your browser history is safe for the foreseeable future, since getting quantum computers to actually work, with reasonable qbits (computational power) is hella hard
Filip Antončík ok but how does the quantum computer cancel the wrong stuff out that’s physically impossible to do with artificial intelligence
As a physics student I clicked into this thinking it's just another super basic introductory video...
Ends up thoroughly reviewing 2 weeks of solid materials from my quantum computing class
Edit: Highly recommend a quantum computing class if you can take one! More of a math class than physics but still super interesting
how is quantum computing classes ? I'm thinking to take them in my college next year
@@anjalimittal5706 I myself have only attended an introductory class of a course that I ended up not taking, far as I recall half the syllabus was theoretical introductory subtopics before they get to the gates and how quantum computers are/work
AJ Ok
I wish my lecturer in Quantum Computing taught it this well. I finally get it. Only 6 years late!
@@AJ-ds5gf why are you mad? Are you jealous that he didn't drop out of school?
0:59 With you so far
1:02 Shor's Algorithm... never heard of it but I can dig it
3:57 Ok... just explain what Shor's Algorithm is...
7:31 Uhh....
8:56 Ok wait, stop
11:52 Ok man, you just keep talking, I'm gonna go write a comment
Has this been marked a top comment yet? It needs to be.
i slept mid video
The official history of this video xD
I feel attacked.
Followed this to a T. Around 11 mins in i decided to read the comments
It's amazing to see that someone can grasp such difficult concepts well enough to make this "simple" explanation. I don't have the knowledge to understand, but I still can have an idea of what it's about. And it's even more reassuring to see comments from physics students who find this video useful in addition to their study material. Thank you very much and keep the good work!
I‘m gonna be honest, at a certain point I didn’t understand it anymore, but just the fact that I understood half of it is good enough and it just shows how good you explain things. Great channel, keep it up!
It's an overview.plus you dont know anything about the computer itself, so its not really possible to understand everything just from this video, only if you have studied many different pieces separately already.
Ya, I feel like you need to understand what a quantum computer is and how it works, to understand the second half of the video.
David von Doom I actually get that a quantum computer works by randomly searching off data, while a normal computer does it in an order, and that this is due to super position, but it‘s hard to understand not knowing much about electronics and computers in particular.
@@DanDan-yy5bo No I dont think it does anything randomly. I dont know how it works too be upfront, but if it was random the computation would be random in its results. For want of a better metaphor, imagine a hypercube, hard to picture in your mind, but easier to compute. Quantum computers can make use of extra "dimensions" exponentially based on the number of qubits it has available...that's a metaphor still...
My point is only that its not random, just complex and very different to how classical computing works. I wish I knew more and I dont understand it myself.
@@DanDan-yy5bo Oh you don't need to know any electronics to understand quantum computer. You only need to know some basic quantum physics.
Me: I'm safe! My computer is using RSA-256 to store passwords
Quantum computer: Hold my P
256?
RSA is cracked
Use aes-256
@@ligeskityler ik, that's the irony
imagine thinking encryption and hashing
are the same thing
I watch this when I’m feeling too smart
To remind myself that I’m not really smart
In watching this, I expected exactly that, but I felt extra smart instead, I think I may be delusional in my understanding of this stuff, what's your opinion?
Mywither
I don’t know, but I’m currently in my freshman year of high school writing a paper about Fourier Transforms, so I also felt extra smart. It’s crazy how often they show up.
Patriot Spring
Really?
@Patriot Spring wowww
I'm just abuse myself I don't feel smart yet here I am
I love how he makes very hard concepts approachable. Now I’ll share this video with anyone who thinks quantum computers are basically magic
Fails to explain where the math and the physical reality coincide. And the explanation of Shor's Algorithm in this video does not require QM at all.
"being cleverly arranged" "set up a quantum mechanical computer"
A block diagram represented by blue fuzz and black dots.
That still requires all guesses to be fed into it to generate "destructive interference among guesses".... somehow.
i. e. magic.
still magic for me
But the crux of the video is "because quantum computers are magic this works faster".
This vid is what convinced Quantum computers are magic lol
This was one of the best explanations I've seen of /exactly/ how quantum computers can be faster at certain problems.
Agreed, I've known the gist of it but now I feel like I actually get it. Obviously there's much more to it but now I feel like I could at least explain it to someone else, which I wasn't able to before watching this.
Thank you minutephysics
This guy pretending to get it
@@poopsmcgee2k6 it makes sense in the video. Although simplified, it should give you a basic idea.
@@perhapsso1909 Wait, this is basic? Jesus, I can't even imagine the advanced form.
@@justinl2009 Did a course on it a few years ago by accident (thought it was a good idea) 2 weeks in, I realise this shits basically all voodoo when you go into depth. But after that i've finished higher physics/maths/cs so maybe if i try going in depth again ill gain a better understanding.
Really appreciate how much effort you put into this, thanks
Yeah well, the title of this video is a bit misleading.
Let me explain... just because we might get super fast quantum computers in the future, Internet Security will NOT be destroyed instantly. Why? Simply because of a little thing called "Timeout Delay (TD)" and "Two Factor Authentication (2FA)" during the Challenge/Response phase.
Timeout is an artificially introduced delay in the log-in process (including in real time browsing encryption), specifically if you enter the first password incorrectly (or the browser send the incorrect NONCE response), there could be a 5 second timeout, and with each subsequent wrong entry the timeout delay may be increases with a predetermined amount or exponentially (similar to the iPhone's screen lock method), therefore rendering any super-fast quantum computer useless. In other words you may be able to generate all the password combinations possible in a short time, but you won't be able to enter it in a short enough time, that is before you die. ;)
Two Factor Authentication takes it a step further, incorporating the Timeout Delay, and it also sends a temporary password/prompt to a second device completely separate from log-in device, and without the proper authentication even the correct password will not work.
Both of these methods can be easily implemented into any website's log-in process (including browser encryption), practically nullifying the advantages of the fastest quantum computers on Earth, so Internet Security will NOT be destroyed just yet. ;D
@@BillAnt there's no need to brute force the password when you can brute force the secure element where the password is stored.
@Caleb Jiang < Well sure, IF you have access to that secure enclave (for example in the iPhone it's impenetrable thus far).
Karim Alibhai < I certainly understand that, I was just making an illustration with a regular password login which is quite similar in mechanism (challenge response wise) so most people would understand. Plus there are way too many "IF"s in capturing real time traffic. And let's suppose that quantum computing will becomes available, rest assured clever browser designers will implement countermeasures against real time traffic snooping such as encrypted dummy packets which will simply trip up even quantum computers by bogging them down with useless computations.
One of the best countermeasures against brute force hacking is a "timeout", meaning that there's a programmed time lapse between restries which renders even quantum computers useless, there's nothing to try till the timeout is over.
Karim Alibhai < Right, but you still can't inject an NONCE challenge no matter what tool you have till quantum computing becomes available. And by then browser makers would have already implemented methods to trip up even quantum computers by various techniques including timeouts during the challenge/response phase. I rest assure you, you can sleep just fine tonight that none's gonna steal your real time traffic as long as it's encrypted by industry standard methods.
@Karim Alibhai < Well obviously government sponsored spying taps the "data pipe" at the source and even use Zero Day OS exploits and other backdoors to read your data BEFORE it even gets encrypted by the browser. So yeah my advice is don't do anything illegal and you'll be fine. ;) (not talking to you specifically but in general) Oh and as far as cloud based storage, anyone who stores their contacts, messages, etc in a Google account for example is probably the least safe place since upon a subpoena they'll decrypt it in a heart beat.
Movie script: **Has some tech they can't explain**
Scriptwriters: *"Quantum"*
Reddit at Night yeah pisses me off tbh
Endgame spoiler alert:
Yeah marvel endgame using "quantum mechanics" to try to describe time travel while making zero sense
"Do you guys just add 'quantum' to everything?" ~Antman and the Wasp
Firefox *_Quantum_*
I know enough to make conversations... Rip black widow
The scary part of this is that breaking encryption is no longer a mathematical or scientific question, it’s an engineering question.
but all engineering questions are really fundamentally math and science questions
@@bloonspy2260 but all math and science questions are ultimately questions
@@TheMrVoguebut all questions are fundamentally sentences
@@codinghub3759but all sentences are fundamentally words
@@PurpleBaldGuy but all words are fundamentally letters
Ooooh. Now I understand.
That box full of little dots is where the maths come from.
**Slaps lid of box.**
"This bad boy can fit so many maths in it."
I think I follow. Smart computer makes maths go fast. Fast math is equal to no more computer security.
QUICK MATS
alex do good. smart boy know latest developments in computer security
alexander williams underrated comment is underrated
Not exactly. Computer security is still possible it would have to evolve.
It actually goes both ways. Quantum computers calculate faster math. That faster math can be used to _en_ -crypt or _de_ - crypt. So, no worries...
*sees 17 minute time*
Boy I'm in for a ride.
-minutephysics-
minutesphysics
And the music ran out after the first minute.
*holds his own beer*
Especially when it's about quantum physics...
russdill lmao did‘nt even notice
Me looking at quantum computers: It’s so cute.
Brutus: We must think of this quantum computer as a serpents egg, not dangerous now but will be later if not dealt with.
Shakespeare and quantum computing... Such an elegant blend
Well, you can also make quantum encryption that is resistant to this sort of thing; but I’ve only done one course of C# coding and have no idea how that works, so don’t ask me.
As a student who had to learn Shor's Algorithm for an exam: Thank you for this video!
I finally have an intuitive understanding of that the algorithm is trying to achieve, and how. Of course, I had to invest an extra couple of hours to be able to actually calculate this stuff correctly, but even when you reach that point, I found that you still lack that "feeling" for what is actually happening in front of you while you're doing all of this.
This video helped with that part, it's the easiest way to explain what is actually going on, you get this really good and informative overview, without being interrupted after every step because you have to do some laborous matrix transformation again. :)
I don't even understand this comment.
Man how did you do this? I think to understand all that stuff you have to start thinking like a quantum computer.
Okay you English major
@@cheekybambony It mostly comes down to preliminary knowledge: you have to study the parts before you're able to understand the whole.
It's hard to understand integration if you've never heard of a function before.
It's hard to understand Shor's algorithm if you've never heard of a Fourier Transform before.
It's hard to understand Fourier Transforms if you've never heard of Complex numbers.
Etc etc.......
Yeah I know how you feel. Sometimes I watch Tom Scott's tech videos for topics I already think I understand, but the explanation often lets me solidify my understanding.
Here's how quantum computers will break even the strongest encryption ridiculously easy. Now, buy our sponsor's product... encryption.
And that's why the video ends with "but encryption still works for now!"
@@eclipserepeater2466 it could bypass cryptocurrency? genius
Would have been epic if this ended with a plug for Bitcoin.
Kampfarsch, tell that to Intel 🙂
Kampfarsch quantum computers exist right now. It's just that they are billions of times weaker than binary computers atm because we don't know how to stably stack qubits together yet.
i would definitely love to hear more about the Quantum Fourier Transform!
Chloe loser
Chloe winner
Is this a thing?
Before QFT I would start with ruclips.net/video/spUNpyF58BYv/видео.html (though if you're watching MP, you probably already have.)
Does this really exist? Is this really a thing?
Nobody becomes a millionaire or a billionaire by working for others and depending on them, good investment bring millions of dollars, and consistency brings billions, the market is all about BTC at the moment now....
speaking of investing, forex trading is the best business in the world right now I know a couple of friends who make a lot of money weekly trading the financial markets
But successful people don't become that way overnight. What most people see at a glance wealth, a great career, purpose is the result of hard work and hustle over time.
@@freerchristen7357 Talking about being successful!..
@Franklin powel But of a truth there are scammers but real brokers are there too waiting for investors!
@@maxwellwilliams3644 You're right Sir
13:59 "...and I'm oversimplifying a touch here."
...Uh huh. 0_0
But I gots an A+ on coloring homewaork!! ^(ovO)^
I saw this comment while watching at the point of 13:59. Lol
Taylor G I nearly got detention for not colouring in my homework once... it wasn’t fun.
Who would ever simplify quantum mechanics? We know many explanations, but all of them are already simplifications!
Why do I get the feeling we're about to break the game?
We are in the endgame of computer science now.
Oh look who's here!
It's because that guy in the sketches with the laptop keeps vomiting. Sooner or later he's gonna get some in the laptop and then it's all over.
And now you've made me lose the game!
Hopefully we have some time before that happens. lol
me: *understands nothing*
also me: *nodding along* yes, yep that's what I thought
"Ahuh... carry the one- yes, i was about to tell you to do that."
😂🤣🤣 on jah...I'm fucking dead
Not to worry, even the people that created it were the same way, they just realized that everyone else would have the same reaction and no one would admit it made no sense, not even the people who write checks and give out grant money.
@@jamestheotherone742 What about it makes no sense?
It was easy to follow the logic.
I just have no idea about how the math works.
How does a shared factor of the factors give you the factor?
*I HAVE UNDERSTOOD. NOTHING. AT. ALL.*
Me: Follows the explanation to the end
Also me at 14:53: Oh, g stands for guess
Woooo
I remember g being used as shorthand for "generator" in my number theory course. But I must admit that I was not able to completely follow the details...
I watched this after my relativity course and kept thinking g is a metric tensor
And I kept seeing 9 instead of g :)
And p stands for power
I remember when this channel was MINUTE physics...
no regrets.
if you pronounce minute with emphasis on the second syllable, minute as in really small, then the quantum stuff is still on topic..........
youtubes algorithm kills that junk
its still called minutephysics
If they could post this video on a quantum computer, it would only take a minute to watch again.
17.5 minutephysics
I'm just going to pretend I understood even a minute of all this.
You don't have to understand per se, just get the general idea:
1. There is math for turning crappy guess into better guess. (slow on a normal computer)
2. Quantum computing, can make multiple guesses at the same time. (fast)
3. Destructive interference with all the wrong guesses leaves you with the right guess. (get right guess fast)
4. This method can break internet privacy and security, exposing everybody's data. Because it can guess correct fast.
It's like using all the keys in the world at once to unlock your door, and one of them will be correct, and you can instantly find the correct.
Me too.... 😞
I actually understood the first minute where he says that he's going to 'attempt' to explain it. In that segment, the author is saying that he will try to explain Shor's algorithm in the next segment.
This just taught me everything I forgot
You have a poor brain
I did a project on shors algorithms problems and benefits, instead of trying to explain what it did, I just summed it up with "using math" 😂.
Just send the data in plaintext. When the hackers assume you've done the right thing and transmitted encrypted data, they will try to decrypt it and just end up garbling it.
Syd Swift Reverse Psychology at its finest🤣
Very true! No hackers would actually look at the data transmitted
i know its a joke but clearly you guys have never seen a packet sniffer like wireshark in action. its immediately noticeable when something is sent in plain unencrypted text. i mean i guess you could speak in code and send that over plain text like "Mother Goose has landed" but that defeats the purpose of using the technology in the first place.
@@vanillacokejunky I have used wireshark before, and you're right, if you know which packet you're looking for then it would be easy to see that its unencrypted, but if you were to write a script to automate the process of decrypting large amounts of data then you might miss that and just skip right to processing it through your algorithm. One way to "fool" someone using this "method" would be to send a bunch of encrypted arbitrary data before the unencrypted data to make them assume that it is all encrypted. I'm not proposing anyone should transmit unencrypted data for the record, but it's a fun thought experiment.
This some mind game sh*t
Does that mean that naming my porn folder as *Homework* wont work anymore?
No that will continue to not work just like it always has
Hey it kind of IS homework. In a way.
@@macronencer um....
say more about that
@@amateurprogrammer25 Studying anatomy for art/film/painting/etc.
@Raphael yes, but if there were no net displacement, then no work would be done! You must always remember to stop exerting force in a location that was different than the start!
9:46
Lets just take a moment admire the marker changes in this part. Like goddamn, that looks satisfying!
@plastic bottle or his eyes are in a super position.
Or super observation.
ahah
Looks even better if you slow it down a bit
put video speed to 0.5x
:O
It's a superposition of markers! Sorta!
Good catch. I was so mesmerized by the information, I didn't even see the colors. It's all math to me.
Incredible and impressive that a whole video on breaking industry standard encryption with quantum computers doesn't mention prime numbers... it's like you figured that it was an extra complication that didn't need to be there for the purposes of this video, and you're right!
I mean whenever he talks about the big numbers used in encryption he’s talking about prime numbers
I got a phone call in the middle of the video. I cut it, and came back, and had just missed 10 seconds of the video. I had to go back 2 minutes to understand it again. That said, excellent video!
Me after hearing the words Fourier Transform for the first time after completing an engineering degree: *Hello darkness my old friend*
Hahahaha same here :'v
Lucky you. I have to deal with fourier transform since year 1.
*shudders*
I just spent five minutes looking for the word convolution. I remembered the math, but not the name!
Industrial Engineer ?
I was lost about two minutes in, but kept watching because it was fascinating!
Hey, it's called minute physics. That means you understood two whole videos! Good on you.
Same
This can be used against asymmetric encryption, but not symmetric encryption, which is what most data uses. Symmetric encryption takes a random string of letters and numbers, and uses that string to mash up the data in specific ways that you can't undo without knowing what the string is. No factoring is involved, and you can't use Shor's algorithm. However, getting your secret string to someone you trust usually DOES include asymmetric encryption. But if the quantum attacker missed the key exchange, you can't break in by doing this.
It can't be even used against asymmetric encryption in general. Only for the encryption that are using factorization. For lattice based algorithm there is no usage at all for it. And there are several asymmetric encryptions that are not based on factorization.
@@gotnoname3956 Some of those asymmetric encryptions, like DH and ECC, are also vulnerable to Shor's alg.
@@enochliu8316 DH and ECC are not lattice based and therefore not some of the ”those asymmetric encryptions”. CRYSTALS-Dilithium would be one example with a lattice based algo. Asymmetrical encryptions are obviously not quantum resistant in general but that was (hopefully clearly) not my point 😅
Take a drink every time he says "superposition"
I am drunk af
I think my brain is in a superposition state
A shot* A drink every time leaves you for dead.
Take a shot every time he says "if" and "but"
You must of pee’ed your self watching this video
You should make a new channel called MinuteCS.
17minuteCS.
Seriously, it will take two years and we will see hour long videos here.
This is more like MinuteAlgebra.
Minute computer science?
Thats great
He can make a playlist rather than a new channel
Nothing really CS here except for the "Magic Box" quantum computer he holds up as the solution to all of the flaws in this idea.
I'd tried reading up on Shor's algorithm before, but this is the first time I've actually understood it! Thank you so much!
that makes one of us
Lucas the Shepard - you’re kidding, aren’t you
Thanks for making this video. I took a class with Peter Shor and I still didnt understand his algorithm. But this video makes it so clear. Great work!
My girlfriend really enjoys quantum physics. She said that her physics professor really taught her some "super positions"
but he lacked the necessary mechanics?
how to get an A+
That is actually a funny dad joke...
he has a quantum dick that can be hard and soft at the same time
Okay.
*unzips*
Quantum hacking, A.K.A 'Shor's Lightsaber'.
I am calling it that from now on
shors hammer
@@elkiensad7003 shoden!
Master Shorda
"Guess P, you must."
S4R1N both sound ridiculously cool
I think a commodore 64 will crack a 1000 digit encryption code before I will understand this video.
I'm sure it could do it, given a large enough spool of tape to swap to.
Brendon Green *but would it be faster*
This is by far the best description of quantum computing for nonprofessionals I have found on youtube
Thank you. After watching this, I feel smarter and dumber at the same time now.
quantum intelligence
@@mizaelflores2360 Schrodinger's IQ.
Your IQ is in a superposition
I feel like that after learning anything new lol
So, now you can change your password account?
introducing a new youtube channel:
seventeenandahalfminutephysics
damn they really left that computer computing for 2000 years
jacob henke gotta be a simulation though, because computers have only been around for like 2 centuries at maximum.
t h a t s t h e j o k e
I don't think so... Because the computer would stop computing if there is a power shortage even for single day in those 2000 years....and it will have to start again from the scratch 😪
@@tejastakalkar7924 : 2000 years for 1 computer.
1 year for 2000 computers.
1 day for 730 000 computers.
Big numbers.
@@nicholascomet8528 r/whoosh
ME 4 MINUTES IN: I AM UNDERSTANDING EVERYTHING
ME AFTER 2 MIN: HUH,WHATS GOING ON?WHERE AM I?WHAT AM I DOING?
Same ☠️☠️☠️
Felt like I was back at my Number Theory class in CS. Scarily amazing stuff.
My neurons destructively interfered while watching this
Yeah man i lost my mind and no understood a fuck
Quantum computing does not break encryption. It breaks a select subset of encryption algorithms, primarily used for key-exchange. AES, the algorithm currently used to encrypt almost all data on the internet, is already resistant against Shor's algorithm. And quantum-safe ways for key-exchange are also readily available.
But it does break a lot of legacy techniques. Which isn't a problem so long as people actually install updates and continue to move to safer algorithms
@@sentjojo Not installing updates is already causing serious security/privacy problems. The availability of quantum computing is not going to change that, nor will it make people suddenly follow a strict update-policy. The worse it will do is lull people into a false sense of security once they _have_ patched their encryption-frameworks again quantum-attacks.
well to use AES you still need either RSA or Diffie-Hellman. I'm not sure if DH key exchange is gonna be affected by QC, but RSA definitely is
@@rizzaxc AES operates independent of the key-exchange algorithm that is used, so it does not _depend_ on RSA or DH. For DH, there is a quantum-safe variant available called 'supersingular isogeny key exchange'. So effectively, nothing will break. Files/data already encrypted using AES will remain safe. That is, of course, assuming that we will eventually be able to keep 4096+ quantumbits (needed to run Shor's algorithm for 2048-bit RSA keys) entangled without decoherence. Which is also debateable atm. But that is another discussion entirely ;)
@panaural wrong, AES doesn't depend on RSA or DH, but the use of it does. you need an effective key exchange scheme for symmetric encryption, and as stated I'm not aware whether DH is gonna be affected, but RSA definitely is. Also, the pain of updating everything to be QC-resistant is also going to be a threat
This was unarguably the best video on how quantum algorithms work and what exactly quantum computers do. Hats off
11:50 that moment when you realize they've come up with something more substantial to teach in the text books since you've graduated from college
This is an unreal video. Very complex theorem explained in a clear stepwise way. 10/10
I've taken an intro QM course and some basic math, and after watching this video I'm now left with the strange feeling of knowing many of the words he's saying but having no idea how they work together in this context.
infinitelyExplosive Words I learned from this video: Numbers, Shor's lightsaber, Hi, ?, N.
Exactly!
There is no way the next thing humanity achieves is even more mathematical computational power. So lame. Where are new vehicles, new materials, new engines, new EFFICIENT and COST EFFECTIVE sources of power, underwater settlements, medical revolutions, home acessories.
It is rape of human resources and talent pool to invest more into this field and I just know it will fail and it should fail. I want regeneration, flying cars and trips to Moon and not better hd porn or quicker pc fuck that garbage.
Isn't that the point though, they say if you think you understand quantum mechanics then you actually don't understand it
utvara1 but that "better pc" will help do all the things you just said you want.
I'm gonna be honest I only understood a tiny bit of the math but the overall concept is really cool and I am really excited about the future of computing both quantum and "regular." Thanks for the video
Internet: *Uses encryption.*
Quantum Computers: It's free real estate.
Lol. Good one.
Quantum Computers: hold my superpositions
@g00gle minus That's the stupidest way ever.. instead you have to acess facebook database of servers and made the decryptions there, you don't need to have some trashy algorithm telling you to wait
@g00gle minus This is not about guessing passwords; did you even watch the video. All they would have to do is sit on public wifi and listen to passing traffic. Usually, on most sites, like facebook, you are protected by HTTPS which uses SSL/TLS encryption, but those use RSA for the initial key exchange, which can be cracked as mentioned in this video. So all the attacker needs to do is save all the network communication, take it home to their quantum computer, break all the RSA encryption to get the symmetric keys, then use the symmetric keys to read all the data sent between you and the sites you visit. That includes your facebook password, if you logged into facebook while they were listening (or at least a password hash, which can still be used to log in in that case). No password guessing involved.
@g00gle minus they don't need to guess your password they could break into facebooks network steal the login database and then use the algorithm to decrypt your password in a very short amount of time. Or they could do a man in the middle attack and listen in to your whatsapp messages, record everything and break the encryption later.
Thanks for disabling the background music during the explanation, much appreciated
The fact the bass stops playing one minute in scares me somehow..
For anyone having trouble understanding this video:
It's not your fault. Quantum mechanics is one of the hardest fields of science to understand. Explaining the depths of Shor's algorithm (or really any quantum algorithm) in a way that a lay person can understand is, in my opinion, utterly impossible. I have a very loose grasp on what he's saying, but that's based on heaps of previous knowledge on quantum mechanics. I need to do some research on Quantum Fourier transforms.
Understanding complex things like this without preliminary knowledge just isn't gonna happen. You need to understand the parts to understand the whole. You can't build a car if you don't know what an engine is. You can't understand how a computer works if you don't know what a transistor is. And you can't understand Shor's Algorithm without knowing how a quantum computer works, which you can't know until you know what a superposition is, etc.
1:00 *chill music in the background stops*
ok some serious shit is about to come
I made a program that can guess passwords of 2 digits.
You are on Your way to decrypt Quantum Encryption.
Just keep up the good work.
Thats simple as there is only 100 possibilities.
@@yashuppot3214 Nice
@@yashuppot3214 99*
Lol sorry that bothered me a lottt
Thank you so, so much! As a graduate student in materials chemistry interested in this field, this video clears up so many of the gaps in the math that the literature just assumes the reader already knows (but I do not have the proper background for). So helpful!
Me before watching video: "Man, this is gonna be cool, I'm totally going to focus on this one!"
Me after watching video: "bplbpllbhbhblblblblblblbllblblblblllbllbbpppppphhhhh...." (drool dripping down side of chin...)
After you accept it will hurt profoundly in your brain, you start to like it.
Trust me, I'm a physics major.
I recommend you watch a video from "Primitive Technology" as an antidote to this gibberish.
my condolences for your brain damage
Elvis Amandio this sounds very sexual
@@ShantalhaitianPrincess It's a concept that can be applied to a wide range of situations.
"We've glossed over a ton of details"
14:37
mybrain.exe has encountered an unexpected error.
Ajmal Najath Was dead
LMAO
i shutdown that unnecessary process years ago
r
Mine hurts. gfycat.com/belatedlikablegoa
My god this video helped me immensely for intuitively understanding the logic behind the Shor's algorithm for my QC course ! Honestly I did not expect such a relatively indepth look at the workings of the algorithm but I was very pleasantly surprised. Thank you.
>minute physics
*>over 17 minutes*
My cell phone is very small so I see it as minute
correction, that would be one minute to the power of 17. lol
@@viceversadetroit (1 minute)^17 = 1 minute^17
I, uh, don't know what a 17-cubed minute is, but its not 17 minutes.
@@EpicScizor it was a joke not literal but I guess that's lost on you
> Condescending online Man
> Pedantic
You should do a video on how quantum computing can also save encryption
*links the password via quantum entanglement to a single arbitrary particle on Mars.*
Quantum cryptography doesn't save encryption, but just allows you to detect, if the message (eg the key exchange) has been eavesdropped on. There are actually commercial system available for this, but it doesn't "protect" the encryption, if you use the key anyway.
What you mean are PQC-algorithms, which don't use quantum computers, but just use problems, that can't be solved by quantum computers efficiently. (quantum computers can't solve all NP problems).
@@frankschneider6156 sounds like you're just being pedantic. The no cloning theorem allows a way in which a sender and recurved can ensure that their line of communication is secure before sending any sensitive information. Secure quantum key distribution is completely provable.
Edit: also I never said that quantum cryptography could save encryption. I said quantum computing would, which relies on entanglement and it's implications. One of these implications is the no cloning theorem which is the backbone of QKD.
Anthony Aportela
May I quote ? "how quantum computing can also save encryption".
I agree with the rest of what you said and am quite familiar with e.g. BB-84, but using quantum computers to protect encryption from quantum computers is completely unnecessary. Every cheap laptop can do that far better. Just don't use a vulnerable cipher. Done. That easy.
Another thing: you should be VERY careful with proofs, when it comes to security. The old saying "If it's provably secure, it's probably not" exists for a reason. Typically the logic is"secure because maths", in quantum cryptography, it is "secure because physics", which seems pretty convincing.
Problem: real world proofs are always based upon assumptions (of which in the real world a multitude are implicit and never formally stated). Just undermine a single assumption and your proof is toast. But because it has been "proven" people will still believe something to be secure, because it has been "proven to be secure", while in reality it is not. Security proofs are of course true (and I'm not stupid enough to argue the no-cloning theorem could be violated, because it can't ) but are still generally not worth a lot.
E.g. I can mathematically proof that every 12+ character password is highly secure and the chance of breaking it is negligible. We both know that in reality, that's far from being true.
Already exists
BY SHOR'S BONES! This is the challenge to enter Sovengarde!
Have you seen those Computer Scientists from Hammerfell? They have quantum computers. Quantum computers!
@@vividandlucid
Curved computation!
@@vividandlucid do you visit the quantum lab in the cloud district often? oh what am I saying..... of course you dont.
I used to be a quantum physicist like you, then I took an arrow in the knee.
@Ishmam Masud - Cuz I Can wow ... total easy mode player.
Every now and again I forget how shor's algorithm works, and every now and again this video comes up in my recommended and reminds me. Solid review of the quantum computing section of my survey of computer science. Love your videos
*This video is exactly 1 minute long!*
...if you travel at 0.99836 × c.
How far in the future will I end up, though?
@@oneofmanyparadoxfans5447 16.5 minutes.
@@Bunny-go9wf Traveling 99.836% the speed of Light in a vacuum? Did you make sure to double check your maths, there?
@@oneofmanyparadoxfans5447 The lorentz factor is about 17.5 (which should be the length of the video), so yeah they did their math pretty much right
@@jonbowman7686 I guess when condensing such a short interval of time there's not as much distortion occurring.
I understood what you tried to explain, but at the same time, I didn't. That's quantum physics for you
It might be fun to note that quantum computing won't necessarily compromise your passwords and other encrypted traffic.
Because first of all; the moment quantum computing technology becomes available it would be very cost ineffecient to just set about brute-forcing random encrypted traffic. It will thus only be usable by a government or university. Who generally aren't that interested in your personal data. (Though this could depend on the government in question).
It'll probably take a while before running tasks on a quantum computer becomes available for public use.
Secondly; encryption using factorisation of numbers is already a rather dated method and better encryption algorithms already exist and are more widely used on modern platforms.
It would only pose problems for old websites who haven't updated their encryption methods and websites who are just too lazy to be bothered with it. Though these websites do still exist in plentiful amounts.
That's a relief!
Two facts that break your bubble: (1) Shor's algorithm can be used to solve the discrete logarithm problem too (which is the basis of EC crypto), so every standardized cryptosystem for asymmetric crypto is broken by Shor's algorithm. AIUI, EC will actually break faster since fewer qubits are needed to hold the required state. (2) Symmetric crypto & hash functions weaken due to Grover's algorithm on quantum computers, but not nearly as badly -- merely increasing key/digest sizes by 2x is enough to defeat the speedup.
But yes, there are efforts underway to define, cryptanalyze, and standardize quantum-safe asymmetric crypto algorithms to replace RSA/DH/ECDSA/ECDH/etc. (Some are already known, but have severe usability issues.)
@@ZiggyGrok Huh, I hadn't heard of Grover's Alg, thanks for metioning it. Also, that's actually crazy that EC will break faster than RSA.
I know of a few alg attempts based on knot theory and group theory, and I've seen that they have been pretty poor as of yet.
Skip If a feasible way is found to crack RSA, all of the signatures have no value.
@Scott Schmit does that mean ElGamal is also broken. Is it based on discrete logarithms as well? I know it uses fields, but does it also use Galois fields?
"Design an algorithm which calculates all possible answers at once while being clever enough that the wrong answers destructively interfere with each other".
As a humble PHP programmer, the first thing I did was laugh. Then I panicked. Now I want to program on quantum computers.
php 🤮
When you connect to Harvard's University wifi by mistake
😂
It might take me crap ton of time to understand what you said in 17 minutes.
The entire video is an encryption
You don't have to understand per se, just get the general idea:
1. There is math for turning crappy guess into better guess. (slow on a normal computer)
2. Quantum computing, can make multiple guesses at the same time. (fast)
3. Destructive interference with all the wrong guesses leaves you with the right guess. (get right guess fast)
4. This method can break internet privacy and security, exposing everybody's data. Because it can guess correct fast.
It's like using all the keys in the world at once to unlock your door, and one of them will be correct, and you can instantly find the correct.
EDIT: Note, that we know the method but do not have a powerful quantum computer yet. Stay tuned for developments.
Let me guess. 2000 years? Because Im guess that thats the same for me
@@Guztav1337 why not just use genetic algorithm?
@@de0509 The biggest quantum computer is owned by Google and has 72 q-bits.!!! If I understand this correctly, that breaks all encryption NOW!
"One minute" stands for how much of the explanation I understood
I worked at a major Telecom as a PM a while back, and one day my boss asked our team to brainstorm potential future issues or threats that the company might not be prepared for.
I mentioned two things, both of which seemed obvious: pandemics and this.
He said Quantum Computing was "science fiction" and, as for pandemics, this "isn't the middle ages". He still works there, I do not.
Thanks a lot for this; I've tried to understand the algorithm prior to this video, and why it's such a breakthrough, but it always devolved into something extremely complicated that was hard to understand.
I wonder how many don't understand a single thing of this but yet watch it cause the video is entertaining.
I lost it halfway through lol
EDIT: I am only referencing 2:08 in the video. Even though I am, I urge you to check out the wikipedia page on Grover's algorithm, a random search algorithm that is the most efficient at breaking symmetric cryptography in O(sqrt(n)) time which brings AES256 to 128 bits of security; this is still momentous.
One thing that I would like to add. Near the beginning you said that encryption was like a lock, we can add more but eventually someone will get through. This is not quite true due to the vast size of the numbers we use and the rate at which the problem complexity grows with respect to the problem size. If we take a look at symmetric encryption (this is for simpler calculations. prime factorization is O(exp(sqrt(nlog^2(n))))) which would lead to less nice numbers but it is similar in spirit), the difficulty of breaking the encryption grows with 2^n where n is the number of bits in the key. This is important because a single bit makes the problem twice as hard. Because of this growth rate, we can extremely easily outpace the computational resources of the entire planet. Even if we took all the energy in all the stars in the observable universe to power computer chips made with every atom in the universe, it would still take longer than the age of the universe to crack AES256 encryption. And if someone starts trying, just add one more bit.
Kai Hicks I fail to understand why quantum computer is ridiculously fast I don't think explain the physical bits. But I agree with you, coding will always be easier then decoding. It's not the just the length of the data, and also the different multiplication they created. If by using super calculating speed you can mimic the encryption fast enough without finding the real answer(which is impossible to even think about at the moment). If it is this easy Software programmer may have to change the way selling product completely to protect their copyright, and everyone will no longer get a full copy of the software but pay to access them online.
Yeah, it's effectively impossible to break decent encryption. It's not just a deterrent, it's impossible without some insane improbabilistic amount of luck.
OP immediately made it clear he did not know what he was talking about with that statement.
Send this to me
Is standard encryption breaking you're definitely correct, but quantum computers dont grow their probability space in a 2^n fashion. Its probability space for solving problems grows by a factor n^n where n is the number of qubits you have, and adding another qubits to a Quantum Computer is trivial and has a low resource requirement, once they become scalable and economical, which is why, at the end of the day 1 extra bit does not double problem difficulty for a quantum computer. It barely even registers as a fraction more difficult, but it's practically insignificant for a sufficiently sized Quantum computer.
@@Dubanx It's possible to be safe against the brute force approach but there are other ways.
I’d like to thank you for the detailed explanation you provided in this video. I wouldn’t have understood Veritasium's video today without this one.
True 💯
Shor's algorithm is actually stupendously inefficient compared to other quantum algorithms.
Edit: he actually said it in the video, I feel stupid now.
Don't worry, bud. We ALL feel stupid after hearing him break the universe with math... especially when that math is quantum maths. Lol.
dont feel stupid theres plenty of people who wouldnt own up to a mistake to protect their ego
Александр Бантьев stoupendous means extremely impressive, imo wrong word in that context
5:19 "... and here's the clever part."
I'm obviously not very clever if things didn't get tricky until now.
That is an oof, my Edukate.
Fucking love this comment, I laughed out loud
Me: Finally! An explanation of Shor's Algorithm!
*mind blown*
Me: HOW THE HECK DID SHOR FIGURE THIS OUT?!!!
He had a lot of free time :-)
The algorithm itself makes a lot of sence though, and it is easily checked. The quantum physics here though - yeeeah, not the most sensible thing.
by not spending his time on yt and actually studying
@@phillipanselmo8540 Yeah this isn't exactly hard to understand
Shor created a small but crucial step on top of a lot of existing work. All the non-quantum things had been done before, and he slightly adapted another algorithm called Simon's Algorithm to create his quantum period-finding part for the number to raise the power. Still very impressive stuff, but when you've done a module in quantum computing, you find that most of the algorithms are very small variations on one another
Great vid, thanks minutephysics! Been following your channel since I was 9 or 10 and now I'm going into uni and your content is still great and useful.
10:00
Me: that idea sounds fine, I mean, that’s better than I could think up
Henry: NO. We need to do something clever
Me: **feels magnitude of inferiority** I thought it was....
Well aren't we all here to alter our definition of clever?
Although if I get my hands on the damn quantum computer you will need 2000 years to fix it
Aviel Yamin lol same
Awesome video! Now just to get my hands on a quantum computer to try this out....
Well, you actually can, through IBM Q
What does it even mean to compute a superposition of inputs? I mean what does that look like mechanically at the particle level.
creating a superposition is the relatively easy part. if you have an electron, just turn it on an angle and you will have a superposition of spin up or spin down. i am not sure how they interprete inputs as superposition though, maybe different angles represent different numbers? but i cant think of how that even produces anything useful. there are other types of quantum computers that use the polarization of light as its superposition.
but superposition itself doesnt do anything. the next step is to entangle the qubits so that quantum interference can take place. the superpositions you want should comstructively interfere while the superpositions are dont want should destructively interfere. then when you observe it, you are left with the results that you want. how they do that physically though is beyond my understanding
At the "particle" level you refer to the distinction between particles and waves is not clear. Consider an electron. There are many quantifiable states it may take - for simplicity let's just imagine that an electron may take a value between 0 and 1. It may also have certain probabilities of taking such a value in the interval (0,1). And maybe these probabilities are determined by a probability density function (google this and look at some pictures). This is what separates the macro/micro level from the quantum level, nothing is certain. If you look at a mug on the table, look away, and then look back again it's still going to be on the table. But if you observe an electron and it has value x between 0 and 1 and then take a second observation, y, you will find x != y.
The idea then is that qubits (quantum bits) act in a similar way. They take a _superposition_ of inputs and compute with them until you wish to observe your determined output which will be one of the superimposed states. I like to imagine many different types of sin waves (inputs) interfering to make a mess of wave, which gets manipulated by the computer and then that mess of a wave deconstructed (using fourier) to give one output sin wave. More specifically, we want the waves to superimpose in such a way that the wrong answers interfere destructively (cancel out) and the correct answer(s) interfere constructively (form to make a bigger wave).
This is hideously oversimplified as I am not a physicist but I hope it gives somewhat of an insight.
dude.....check out "the two slit experiment" at this particle level.....things get too fucky....thats a scientific term BTW.
Fun listen. I hadn't heard of Shor's algorithm, but I knew quantum mechanics and Fourier transforms. It was good to see them mated. The clever part of the decryption was the use of Fourier. The physics part was the use of a quantum computer giving an array of outputs.
Who else went 5 seconds in and got lost, but still watched the whole video?
I generally understand how some of it interlinks, vaguely, but I'm definitely going to have nightmares about P, r, N, m and g
I made it around 10 minutes in before I needed to take a break from how much talking and how quickly he talks about everything O.o
I actually understood a ways further than that. But then, superpositions. I don't speak Quantum. (Apparently, neither does the spellchecker here.)
@@joesterling4299 '...and then the voodoo happens, which allows us to find...'
@@icycloud6823 the world is easy when you have a script... if i got the gist of it, the quantum computing somehow allows us to compute on a long enough array or possibly even infinite and the creative destruction of orthogonality related fourier transformations and bam
This was really, really well done. Took me back to my physics/communications classes. Shor's algorithm, quite clever, it's use of Fourier was the chef's kiss.
This was such an intriguing video. Thank you for recapping every so often. It really helped me stay with you.
Solution? Quantum encryption.
Weird way to write enigma
Or just elliptical curve encryption such as the already widely used EC25519 that has already made it in the OpenSSH standard
Yeah but then u cut off every single normal computer in existence.
@@ftcgaming4651 to hell with them, I say
We need entire system to collapse to make a new one
@@JamieStivala ECC is still vulnerable to the IQFT/a modified shor's, you need something like NTRU/Lattice encryption (which relies on the LWE hardness assumption which QC only gives you quadratic speedup on)
I had to watch this 3 times. And I have to say, I understand almost none of it.
Same