As Nisha Tiwari pointed out, we did fact miss the 512 in our powers of 2 visualization at 5:35. So Let's all thank Nisha for offering the definitive proof that Matt is not in fact a quantum computer. A Correction GIF will be posted on the community tab later in the week.
Isn't that proof that Matt in fact is a quantum computer? (giving right answers only with some probability) This time the superposition just didn't collapse in the right state when measured, we just need to repeat.
LOL... I was just about to post about 512. I immediately saw it. That sequence is used all the time in computers. I'm sure a lot of people noticed it missing.
You're one of those TH-camr's whose voice, accent, and narrative skills make you so pleasant to listen to one could listen to you narrate paint drying. Add to that the fact that you actually talk about awesome and interesting and fascinating stuff, and have an outstanding ability to convey all this advanced and complex science to us, ordinary people, in more or less understandable ways, and the fact that your humor is the dryest ever, and you're by far one of my favorite TH-camrs to watch. BTW, don't mistake me calling you a TH-camr for me not acknowledging you're actually a professor in astrophysics at NY City University, and I also think it's awesome so many actual scientists have found their way to TH-cam, and if nothing else, we can actually thank Covid-19 and the Coronavirus for quite a few finding their way just this year. My favorite is Sean Carroll and the great questions podcast thingie he does. Not as soothing voice or accent as you but a truly great explainer of science and astronomy too. Anyway, you're welcome for me watching all your videos, and thank you very much for making all your videos. They are very much appreciated. Love from Norway.
5:18 Ah "Infinite Series" - in a parallel universe, you're still making fun Math episodes that are the perfect complement to the fantastic PBS Space Time. Alas the yang has disappeared from our universe so we have to satisfied with yin alone. Please PBS consider reforming this quintessential duality.
It's one of those "wow" moments when I realize you're talking about the proliferation of powerful quantum computers as inevitable, when it feels like just yesterday it wasn't clear if they could even exist.
@@AB-ii5uy Not quite. DH is based on the discrete logarithm problem (either the standard version or the ecliptic version) while RSA is based on the prime factor problem. However, both of thise are based on the Alebian hidden subgroup problem which is what shor's algorithm solves.
Ah yes, RSA. I teach RSA encryption in my Discrete Math course. Since I pointed out your error with the powers of 2, it seems fair for me to share an error I made my first time teaching RSA. A Dumb Error I should have noticed: I was showing an example using "blank space = 0" "A = 1" "B = 2" ... "Y = 25" "Z = 26" and then RSA encrypting those numbers. RSA encryption begins with two primes. I had decided to let the class decide what two primes we would use. The class chose 3 and 7. If you are familiar with RSA then you like notice what I should have and asked for two different primes. I could encrypt without a noticable problem. As for decryption, most numbers decrypted correctly, but those that should have decrypted to the last few letters in the alphabet did not decrypt correctly. Then the obvious dawned on me. 3×7 = 21. The product is the mod for encryption & decryption. The mod MUST be at least 27 so we can have a all room for all 26 letters and the 0 for a space.
Ah discrete math, one of the hardest courses I've ever taken. Big respect for being able to understand such a difficult topic to a high enough degree to teach it.
Whoops. And that number gets higher the more characters are in the encryption. The ten digits, various punctuation marks, add 26 more if you have separate uppercase and lowercase...even without going into the more esoteric special characters, that fills up fast.
That bit about the hypothetical life inside stars being very ancient immediately made me think of the Doctor Who episode "Rings of Akhaten" (S07E07), search for the doctor's speech in that episode, it's amazing!
"Every email ... is secured by the fact that it's a lot harder to factor out prime numbers". Uh, fun fact, email isn't typically encrypted. You can explicitly encrypt your emails, but that's not very commonplace, and it's something you have to opt into. You can use email services that will only enable you to access your inbox through an encrypted connection (such as Gmail), and emails between users of that same service would presumably not leave that service's servers unencrypted. But for anything else, who knows how many of the steps an email goes through from the sender to the receiver use an encrypted connection. It's probably few of them.
That was one of the fun things about getting into networking in school... connecting to an open WiFi hotspot, starting a traffic capture, and looking for unencrypted packets.
@@ReptilianLepton This is the ultimate form of data safeguarding. Once a hacker reads that at the _bottom_ of the email, their mind is instantly wiped and their location reported to the authorities.
If both participants use servers (or services) which are set up to use encryption (which is super common these days), emails between them should at least be encrypted any time they cross the network. It won't be end-to-end encrypted, but it's a step in a better direction than we started in. For example let's assume I'm emailing someone from Gmail and they're on some other corporate or commercial email system. I write the email and send it. If I'm using Gmail's web interface, then it is encrypted with HTTPS. If I'm using, say, IMAP, then that connection is encrypted. Gmail's servers will use encryption if it needs to shuffle the message around internally. Then Gmail will connect to the remote service preferentially using SMTP over TLS. Then the user gets their email, again using HTTPS or IMAP or whatever. If the servers are compromised that's an issue, but random third parties have to break the encryption to eavesdrop. Of course, is still possible to configure SMTP servers which don't use TLS. That's becoming a lot rarer, but would expose your email to more snooping. Or you might be able to use an unencrypted protocol to read your email, though honestly that's super rare these days. Long story short, things have improved since the nineties when email was routinely not encrypted for most of those links. We don't have end-to-end encryption as standard, but it's a step in that direction.
That's not entirely true. Nearly all email providers at least use encrypted transport mechanisms (such as a TLS-secured connection) for SMTP and POP3/IMAP. Although the email itself may not be encrypted anymore after it has reached the server, the transmission is secured.
I still feel that line came from their scientific consultants. It's the most absolutely accurate thing in the MCU. I grew up watching astronauts in space suits on their space station unloading space snacks off their space ship. If string theory is ever proven, I expect everything will become "string (noun)".
When trying to break a quantum encryption, this message will pop up: “Your password is both correct, unknown, incorrect, blue, seven, yes, The Rock, and everything inbetween until it is set. Would you like to try again?”
Dude, I think you can decohere the function of any encrypted message using the interference pattern of this same state by just using symmetry on your side, you should aproach the outer waves perpendicularly...
*screams in crypto nerd* 3:35 explains the idea behind the Diffie-Hellman key exchange which is based on discrete logarithms and NOT prime factoring. Also not all public key crypto is based on large primes like RSA is, most notably Diffie-Hellman based systems. Elliptic curve cryptography is another system which uses multiplications on discrete elliptic curves. There are relations between these three which means that quantum computers breaks them all. The shortest vector problem does not concern itself with what the shortest distance between two arbitrary points of a lattice is (which is a trivial problem as the metric is usually given), but what the shortest possible vector (aside from 0) produced using the lattice's base vectors is. Also given your explaination of lattice cryptography using noise, the more relevant problem is the closest vector problem: Given a point slightly off the lattice, find the closest next point on the lattice. Also you should mention that symmetric cryptography is safe from quantum computers; doubling their key length is enough to reach pre-QC strength.
Speaking of elliptic curves, there are new systems using elliptic curves to form isogeny graphs. You create a graph where the nodes are supersingular ECs and the edges are isogenies (maps) from one EC to another. The hard problem is to pathfind arround the graph when finding the isogenies is very complex. Especifically, there is a algorithm called Supersingular isogeny Diffie-Hoffman key exchange (SIDH). It has similiar key lenggh of RSA, is "perfect forward secret", and is analogous to DH, so can be used in symetrical and asymetrical encryption. No known algorithm is known to solve this problem with subexponential complexity. I found a lecture from one of the developers where gives an overview of isogeny-based cryptology, including hash functions. If you are interested: th-cam.com/video/AoE-uQinzqU/w-d-xo.html
Thanks for the clarifications. I missed the Diffie-Hellman thing, but I have to say I did think there was something a bit off about that lattice section. Glad I wasn't just imagining it.
At 7:23 you say: "guess the factors of a prime number", I think you meant to say guess the factors of the modulo N, as used in RSA, which is the product of two large primes (those are secret), we are trying to find. Guessing the factors of a prime number makes no sense, they’re just 1 and the prime number. :P
1:03 I just want to point out that "thousands to billions of years" sounds like quite the large range, and it is... but it's very true. The fun of how adding more bits to keys scales things by orders of magnitude.
8MB doesn't sound like a crazy huge data size to improve on, so I am guessing some form of compression wouldn't help with transmission? Or is the problem less about transmission and more about the amount of computation?
@@robwhiteston2348 You can't compress encryption keys at all. They are designed to have maximum entropy, that is to say, they are indistinguishable from noise. If you compress a file, like a text file, into, say, a zip file, and you then look at the file it will look like random noise. If you then try to compress that file again, you'll find the resulting zip file bigger than the original (by a tiny amount). The amount is only so tiny because the compressor realizes it's only making things worse and will use the "store" compression method instead. It still has to add the information that the "store" method is needed, which increases the file by a tiny amount. If the software were to actually use the compression algorithm, the doubly-compressed file would be significantly bigger than the original zip file. One way to overcome these issues is to use secret keys rather than public keys. The 8MB might not be a problem if you only have to do it once per website. The device could use the massive key to negotiate a shared secret with the website in question. Both the device and the web server could store the secret key in some way. To provide forward secrecy, the key should be a ratcheting key (as used in the Signal protocol, for instance). Because shared keys cannot be brute forced no matter how many computers you have (like infinite computers as in quantum computing), it's impossible to crack (assuming you implement it right, such as never use the same key twice). And so forth and so on. Wikipedia has more info.
@@memberwhen22 Sorry buddy, but you're wrong. Sure, what I called a "secret key" is not a complete descriptor, as I didn't call it a "shared secret", which is usually a part of a symmetric cryptosystem, which is what I was referring to. Certainly, the private key is also secret, so I see the confusion. What you got wrong, however is 2 things: I may not be an expert in cryptography, but I've studied it and I _am_ a software developer, for 25 years now. What's really wrong though is the idea that the public key is derived from the private key using a hash function. At least in the most commonly used cryptosystem, namely RSA. I believe ECC (elliptic curve crypto) has a similar derivation as well, and it's _not_ a hash function in either case. In RSA, the public key is a combination of p*q where p and q are the secret primes and e, where e is usually 65537, must be coprime with some fancy number rolling out of something called a totient function that has as inputs the q and the p, again. The same p and q. So both e and n (which is what p*q is usually called by you can call it "fred" for all I care) are at least partially derived from p and q (the private key) but not through a one way hash function. Granted, multiplication is technically a one way function given primes, but not a "one way hash function". Hash functions return fixed-sized output, something a multiplication isn't designed to do. I think what you did was miss the idea of symmetric crypto. And that was what the whole second part of my comment was about...
Finally a video that I can comment on!! So here it is: Today keys are 1.based on a 180 digit number. 2. The key is static, that is people don't change it. A simple solution to quantum comp. threats would be to 1. increase the digit number. 2. Estimate the minimum time it would take for the 'best' quantum computer to find the factors, lets call that 't". 3 Regularly change your key within that timeframe, 't'. The End. If this qualifies for the Nobel Prize, publish it for me: you can collect the 'tacky' award and we can split the $1 mil prize. Call me anytime except between 1Pm & 2pm EST (Jerry Springer show is on)
Public/private RSA key can be understood via this analogy I always give as an example: If a person wants to mail you, then they request a special cascet (public key) from you. Such cascet is initially open but once it's closed it became locked: only key (private key) owner can open it. Once the person is done with writing, they put the letter into the cascet and lock it; at this point it is safe to share such cascet with anyone because only you hold its key hence only you can unlock it (not even letter owner can do it - only you)
please do an episode on kerr newman black holes. im honestly on the edge of my seat about them. feels like if we could directly measure the magnetic field generated by one we could learn a lot, like whether there's anything to the idea of a ringularity.
I'm very glad this topic was attempted and there was even some pretty good content in it. But the paint mixing example described an analogy for Diffie-Hellman key exchange which relies on the difficulty of discrete logarithms in finite fields, not the difficulty of factoring large semi-primes. Also Elliptic Curve Cryptography (ECC) was ignored which also doesn't rely on the difficulty of factoring. Quantum algorithms also defeat discrete log and ECC but for reasons other than Shor's algorithm.
So the same technology that can be used as a weapon can be used as a shield, and apparently older technology can be a good enough shield against the new weapons.
In the novel "The After On" there is a quantum AI that uses quantum hacking for RSA and DH. From the words of this AI - she always gets the password from the second try and the way it works - an infinite amount of these AI's try a random password on the first try and then the information from the ones who got it correct is shared through all the multiverse.
It's uncanny how seemingly important the significance and frequency of the number 21 is. It keeps reoccurring throughout mathematics, it's kind of like that phenomenon in real life and in Grand theft auto where the car you focus on starts to materialize in your little part of the matrix. Keep your eye out for 21 and you will begin to see it literally everywhere.
The biggest issue is that I might have secrets, encypted with RSA, out there. It is “public”, available for anyone, but not readable due to the encryption. Someone might make a copy of it, save it, wait for the quantum computers to be production ready, and break my secret later. And these are ALREADY out there, I can do nothing about it.
That's a good point. Quantum encryption will only work for newly publicized data that it encrypts. It couldn't protect anything that's already out there and accessible. Then again, there's an awfully large amount of data currently out there under our present encryption schemes. How would the attacker know what is valuable, and therefore worthy of saving for a later date, if they can't read it?
oquinc There are peoples and businesses out there, and it might worth to specifically target them, and record their communications. I’m probably okay, but if I would be a politician for example with things to hide, I would be worried.
One tiny meth problem? Someone at my ISP is going to expose my history unless I get them- {Turns on closed captioning} Ooohh! Math problem! That makes more sense.
This channel... It makes me actually want to research and understand things I currently don't >_< I'm bad at advanced math okay? Stop being so goooooood.
Okay so first collapsing the Digital World, then Matt on Green Hill Zone and maybe even a Counter Strike level. Referencing 2-3 video game in a single episode is wild
One important thing: *the existence of one way functions has not been proven.* It is an unsolved mathematical problem. They are necessary for quantum resistant cryptography to even exist without a quantum internet. Pointing this out because any chosen algorithm is going to be a gamble unless this is resolved. Even solving the P=NP problem won't resolve it necessarily (depending on how it is resolved) because NP could still be equal to one of the probabilistic polynomial time complexity classes(BPP, ZP, RP, BQP). None of these classes are suspected to be equal to NP, but none of that has been proven yet. Also if BQP = NP, then no quantum resistant encryption algorithms exist regardless of whether or not one way functions exist. *TLDR:* It is a difficult problem because it is currently not clear if it is even theoretically possible.
I have a really serious question (not really). I know that NP is all the problems which a solution can be verified in polynomial time (fast for classical computers), but which the solution may not be possible to find in polynomial time. NP-complete problems are a special subset of NP, when a NP problem A can be converted in polynomial time to another NP problem B, than B is NP-complete (correct me if I'm wrong). So if you find an algorithm that solves a NP-complete problem B (fast or slow), then you can convert any problem to that problem B in polynomial time and thus solve all NP problems, (if that algorithm solves it in polynomial time, then P = NP). As far as I understood, cryptography needs to be a NP problem, easy to verify a solution, hard to find the solution and I also learned that the NP class is the only one that has this property, it's the definition. Any encryption algorithm, if it can be polynomially verified but not polynomially solved, is a NP problem. If quantum computers can solve one NP-complete problem in polynomial time, since it supposedly can verify all solutions at once, then it can solve all of them, so the whole class becomes useless for cryptography by definition? TL;DR. Cryptography needs to be a NP problem (because of the unique property of that class), quantum computers can solve as fast as a classical computer can verify. So doesn't that mean that any ever attempt of cryptography will be useless? or I am making any wrong assumption? (which is probably the case)
These one-way functions sound an awful lot like entropy. So, how good is this analogy of encryption to the notion of entropy, and what is the quantum version of that concept? Also, does that mean that mean that breaking the encryption is akin to creating an 'open system' where the entropy of one part of the system, i.e. the encrypted message is decreased by expending energy and creating at least that much or more entropy elsewhere?
Aww, no word to my favorite PQ algorithm (now an alternate candidate in the competition) of SIKE. I would have loved seeing your illustration of the isogeny graph. It doesn't have the same large key size problems as all the other candidates, with the keys being similar in size to RSA (sadly not to ECC, which is what we use right now, with keys less than a hundred bytes long). But what it has in small key sizes, it sadly lacks in performance, because while the computation necessary for lattices is using your standard arithmetic, computing things on curves isn't something computers are currently good at. It also is a far younger crypto system compared to the error correcting codes or even the lattice based ones.
There is something quantic with Matt O'Dowd's hands in this video. Too much cafeine ? Or a quantum computer is threatening to decode his old My Space account password, something like that. (Seriously, I hope it's nothing serious, your channel is one of my favorite)
Great videos! I like to put on one of your playlists as I fall asleep. I just wanted to remind you that you have not added the last 10 or so episodes to the Space Time playlist, not a big deal but hey. Anyways, have great day everyone
I have a question for the next time - assuming two blackholes merge and assuming each one contains new big bang/white hole/universe or even “just” a singularity; that happens with each corresponding “something” inside a black holes? Which one keep existing or both are destroyed and new one created? Is it even have meaning to talk about something happening with “entities” inside a black hole from point if view from out universe? Even if not - how information paradox of black holes is affected by merging two together?
*Your thumbnail is shiv lingam. GoogIe "haribhakt shiv lingam" to clear your apprehensions. Vedic science on cosmic and quantum principles are amazing. GoogIe now.*
I just learned about the Dzhanibekov Effect on Veritisium, and now I want to see an episode about rotating bodies from PBS Space Time. Oumuamua, rockets, asteroids, planets, etc. I am also wondering...is the Dzhanibekov Effect caused by precession?
Great! The most important application of the quantum encryption will be in the brain-machine interfaces (as the ones researched at Neuralink). So we can take full advantage of these amazing technologies, with 0% probability of being hacked.
Can we use equations related to probabilities of quantum mechanics (say superposition principle and other uncertainties and then having different parameters of the current prime factor method would lead to almost infinite range of answers) and then set a limit? Like a range of values would give us this value and then apply that inverted on the other end? Applying this can make the use of quantum encryption to the next level. Like 👍 and reply if you agree.
drdca listen, do you know about the superposition principle of particles like electrons and photons? We cannot determine their actual position a particular time period. But there exists some equations that help us in finding the probability of the position. Now first of all we have to select the equations which is not a big deal for us and then use the current encryption and decryption methods to g get the parameters to solve it. And by defining specific values to specific characters or numbers, we can get almost infinite easier ways to encrypt our private data. Hope so now you’re clear, but still you can ask your queries?
Devarsh Dave I have watched all of a first class on QM. I don’t mean a first lecture, I mean all the lectures of a quarter’s class on QM were uploaded to youtube, and they were pretty good. I can fetch the link if you want to watch it. So, yes. I’m familiar with the concept of a superposition of states. Ok, so it sounds like you are describing, using a classical computer to simulate the probabilities of some quantum system having some result, and calculating them to some given level of precision, and using that with some cryptography stuff in order to do other cryptography stuff? Is that an accurate description of what you are describing? If not, what about it is inaccurate?
drdca I’ve also watched all of them! Yes they are great 👍 and I’m trying to expand the current encryption decryption system by introducing a concept that could help us in Even more logical approach to it, just like a sum to solve whose parameters are encrypted by current methods and if we even figure out the actual parameters still we won’t know how to solve it or by placing the values in which equation which won’t also indeed have any exact answers but the range would be like an equation of a curve which would yield the actual DATA. 👍
I thought super positional states were 1 or 0, neither and both all at once. Is that not the case? Just on/off and both, not also neither on nor off included? 6:30
The way government bypasses your encryption is to directly read the data before it gets encrypted (ie the yellow and blue) or intercepts the sent data (ie the purple and orange).
I have been blogging and monitoring about this for quite a few years. A few corrections and thoughts: 1. SHOR's algorithm specifically breaks "asymmetric" cryptography. And that is only used for establishing a key to use for symmetric cryptography (AES / ChaCha20). 2. RSA isn't the only asymmetric cryptography for TLS, there's also ECC, and that is apparently also vulnerable. (Although a Post-Quantum protocol might exist for ECC) 3. Quantum Internet is way overhyped. Importantly TLS is used for communication between two hosts (and users behind) that have never met before. Quantum Internet is built in a very direct manner. For less cost, and way more portability you can simply distribute 2x 10TB hard disks with pure random data that is used to directly encrypt (One Time Pad) or derive the same symmetric keys. 4. It doesn't matter that Post-Quantum cryptography is not mature. You can use both RSA and McEliece together. They both generate their own keys, and then you can XOR them together for a final combined symmetric key. Then you get the maturity of RSA and the PQC of McElise. If maturity of McElise fails, you still have RSA; if RSA falls to a quantum computer, you still have McElise. 5. An 8MB key is less and less problematic as technology improves, and engineering can also reduce the amount of keys needed. 6. If we are happy to live with a 8MB McEliece key, why not live with an 8MB RSA key? Perhaps a quantum computer can break a 4k RSA key, but surely an 8MB one would require a quantum computer that is a lot more powerful.
Isn't RSA working without a shared secret ? Encryption using the public key is only reversible with the private key (other way around is signature). The colour demonstration is a diffie-hellman exchange protocol where you create a shared secret and only need to "add" and "remove" it to get the message.
To be honest if we don't find something tinier we might as well use multiple algorithms and it wouldn't be much of a problem. For latency intensive day to day messages we could still use the good old rsa based algos, but for anything that doesn't care much about that(eg. an email or a transaction with your bank) we would have those new safer ones.
I knew it! Ever since they considered the Photon to be a particle used in processing for quantum computers, I knew processing would speed up! It may not be light speed, but it is damn close!
As someone who works with computers a lot, going from Manual to Classical to Quantum almost feels like going from Analog to Digital then back to Analog... But this time it's *magic* Analog...
Definitely having some feels here for Infinite Series. I really enjoyed the episodes on Shor's algorithm in particular, and was glad to see the reference. After Dual_EC_DRBG I'm not keen on following NISTs guidance wrt crypto. DJB seems to be backing NTRU Prime, so that's where my money is.
As Nisha Tiwari pointed out, we did fact miss the 512 in our powers of 2 visualization at 5:35. So Let's all thank Nisha for offering the definitive proof that Matt is not in fact a quantum computer. A Correction GIF will be posted on the community tab later in the week.
Isn't that proof that Matt in fact is a quantum computer? (giving right answers only with some probability) This time the superposition just didn't collapse in the right state when measured, we just need to repeat.
512.... 5 -1 = 4 and add back the 2, i.e. 42. Coincidence? I think not! Matt is Deep Thought.
Hmm, I smell conspiracy
This may be a bad time to mention that you in fact missed the "in" in "in fact".
LOL... I was just about to post about 512. I immediately saw it. That sequence is used all the time in computers. I'm sure a lot of people noticed it missing.
You're one of those TH-camr's whose voice, accent, and narrative skills make you so pleasant to listen to one could listen to you narrate paint drying.
Add to that the fact that you actually talk about awesome and interesting and fascinating stuff, and have an outstanding ability to convey all this advanced and complex science to us, ordinary people, in more or less understandable ways, and the fact that your humor is the dryest ever, and you're by far one of my favorite TH-camrs to watch. BTW, don't mistake me calling you a TH-camr for me not acknowledging you're actually a professor in astrophysics at NY City University, and I also think it's awesome so many actual scientists have found their way to TH-cam, and if nothing else, we can actually thank Covid-19 and the Coronavirus for quite a few finding their way just this year. My favorite is Sean Carroll and the great questions podcast thingie he does. Not as soothing voice or accent as you but a truly great explainer of science and astronomy too.
Anyway, you're welcome for me watching all your videos, and thank you very much for making all your videos. They are very much appreciated.
Love from Norway.
Here here, love from Belgium
5:18 Ah "Infinite Series" - in a parallel universe, you're still making fun Math episodes that are the perfect complement to the fantastic PBS Space Time. Alas the yang has disappeared from our universe so we have to satisfied with yin alone. Please PBS consider reforming this quintessential duality.
A fusion between Infinite Series and Space Time would bring back balance to the world.
I'd love to see a return of Infinite Series as well. :(
Upvote this comment, and tell people to go take the annual survey! If enough people do it, maybe it'll come back?
Ah, Infinite Series. Still a fresh wound after all this time.
:,(
Seems finite to me
I mention it in the PBS survey every year
This could have been a good collaboration video if only PBS Infinite Series was still around.
@@togamid me too
It's one of those "wow" moments when I realize you're talking about the proliferation of powerful quantum computers as inevitable, when it feels like just yesterday it wasn't clear if they could even exist.
me, connecting to quantum internet:
*_Please wait. There is a 67.5±2.9% chance that the webpage is loading_*
There has to be at least a slight chance that the page is and isn't destroyed, and someone else gets the one that wasn't.
Please have your alternate selves whose pages fail to load contact us at....
The Rogue Wolf TECH SUPPORT!!!
Might get loaded and not loaded at the same time.
If you don't see it another you from another mini-world got it.
I heard "lettuce-based cryptography" and I'm sticking to it.
I'm just imagine a bunch of rabbits furiously typing away in a dark room while eating salad
@@Celestialeris 999 x10^99^99^99 iq
@@smellthel with enough rabbits, you can reach any collective IQ
Thank you! Me too. I kept hearing it.
My lettuce leaf is unique in all the world! No one can copy it exactly, and it'll last for... aw, crap.
4:16 - that’s a Diffie-Hellman key exchange, not RSA. Wikipedia entry on DH even has the exact same visualisation.
I was starting to wonder if my whole life was based on a lie #csStudentLife
Nice catch*
Good catch - both DH and RSA are based on the same principles, and I can see how he confused them.
@@AB-ii5uy Not quite. DH is based on the discrete logarithm problem (either the standard version or the ecliptic version) while RSA is based on the prime factor problem. However, both of thise are based on the Alebian hidden subgroup problem which is what shor's algorithm solves.
Thank you. Annoying how people get these mixed up. That’s going to be a coding error to watch out for in the next few decades
Ah yes, RSA. I teach RSA encryption in my Discrete Math course.
Since I pointed out your error with the powers of 2, it seems fair for me to share an error I made my first time teaching RSA.
A Dumb Error I should have noticed:
I was showing an example using "blank space = 0" "A = 1" "B = 2" ...
"Y = 25" "Z = 26" and then RSA encrypting those numbers.
RSA encryption begins with two primes. I had decided to let the class decide what two primes we would use. The class chose 3 and 7.
If you are familiar with RSA then you like notice what I should have and asked for two different primes.
I could encrypt without a noticable problem. As for decryption, most numbers decrypted correctly, but those that should have decrypted to the last few letters in the alphabet did not decrypt correctly.
Then the obvious dawned on me.
3×7 = 21. The product is the mod for encryption & decryption. The mod MUST be at least 27 so we can have a all room for all 26 letters and the 0 for a space.
Ah discrete math, one of the hardest courses I've ever taken. Big respect for being able to understand such a difficult topic to a high enough degree to teach it.
Whoops. And that number gets higher the more characters are in the encryption. The ten digits, various punctuation marks, add 26 more if you have separate uppercase and lowercase...even without going into the more esoteric special characters, that fills up fast.
I can already see quantum internet now:
"You may or may not have a new message!"
"You have a new message, but you can't read it" Heisenberg's unopenable principle.
theemissary1313 unopenability.
You don't know whether you have a new message until you open it. lmao
I fail to see the difference :-D
KohuGaly I made that word up so I don’t blame you lol
That bit about the hypothetical life inside stars being very ancient immediately made me think of the Doctor Who episode "Rings of Akhaten" (S07E07), search for the doctor's speech in that episode, it's amazing!
Burn with me.
5:20 Ahh yes, twist that knife in my heart, thank you very much.
"Every email ... is secured by the fact that it's a lot harder to factor out prime numbers". Uh, fun fact, email isn't typically encrypted. You can explicitly encrypt your emails, but that's not very commonplace, and it's something you have to opt into. You can use email services that will only enable you to access your inbox through an encrypted connection (such as Gmail), and emails between users of that same service would presumably not leave that service's servers unencrypted. But for anything else, who knows how many of the steps an email goes through from the sender to the receiver use an encrypted connection. It's probably few of them.
That was one of the fun things about getting into networking in school... connecting to an open WiFi hotspot, starting a traffic capture, and looking for unencrypted packets.
@@moosemaimer the good 'ol days of sniffing passwords out of telnet and ftp connections.
@@ReptilianLepton This is the ultimate form of data safeguarding. Once a hacker reads that at the _bottom_ of the email, their mind is instantly wiped and their location reported to the authorities.
If both participants use servers (or services) which are set up to use encryption (which is super common these days), emails between them should at least be encrypted any time they cross the network. It won't be end-to-end encrypted, but it's a step in a better direction than we started in.
For example let's assume I'm emailing someone from Gmail and they're on some other corporate or commercial email system. I write the email and send it. If I'm using Gmail's web interface, then it is encrypted with HTTPS. If I'm using, say, IMAP, then that connection is encrypted. Gmail's servers will use encryption if it needs to shuffle the message around internally. Then Gmail will connect to the remote service preferentially using SMTP over TLS. Then the user gets their email, again using HTTPS or IMAP or whatever.
If the servers are compromised that's an issue, but random third parties have to break the encryption to eavesdrop.
Of course, is still possible to configure SMTP servers which don't use TLS. That's becoming a lot rarer, but would expose your email to more snooping. Or you might be able to use an unencrypted protocol to read your email, though honestly that's super rare these days.
Long story short, things have improved since the nineties when email was routinely not encrypted for most of those links. We don't have end-to-end encryption as standard, but it's a step in that direction.
That's not entirely true. Nearly all email providers at least use encrypted transport mechanisms (such as a TLS-secured connection) for SMTP and POP3/IMAP. Although the email itself may not be encrypted anymore after it has reached the server, the transmission is secured.
"Do you guys just put the word Quantum in front of everything?" -- Ant-Man.
I still feel that line came from their scientific consultants. It's the most absolutely accurate thing in the MCU.
I grew up watching astronauts in space suits on their space station unloading space snacks off their space ship. If string theory is ever proven, I expect everything will become "string (noun)".
Sounds like C++ was way ahead of its time then
1:16 "A quantum computer that could factor a prime number in a human lifetime, or a human lunchbreak" -> I don't need a quantum computer for that. ;)
he missed the 512 in the powers of 2
And then displays the remainders of the later divisions incorrectly
yes, and reminders got wrong from 1024, it's 512 that has reminder of 2, than 1024 has reminder of 4 and 2048 has reminder of 3
Cause that’s what you should be taking away from this video 🤦🏻♂️
It's all part of his McEliece crypto message. Your error decoders, obviously, operated as required.
@@dahliaspumpski5837 pointing out a mistake doesn't mean that was the only takeaway. Your comment is concerning.
That color analogy is spot on. Wish my lecturers explained it that way back in college!
When trying to break a quantum encryption, this message will pop up:
“Your password is both correct, unknown, incorrect, blue, seven, yes, The Rock, and everything inbetween until it is set. Would you like to try again?”
Dude, I think you can decohere the function of any encrypted message using the interference pattern of this same state by just using symmetry on your side, you should aproach the outer waves perpendicularly...
if you try to enter the password often enough the prompt will turn into a bowl of petunias and a very surprised-looking whale.
'Press any key to delete everything or any other key to continue'
And I will be in the superposition of
“You may have killed the cat! Quit now so it won’t know.”
*screams in crypto nerd*
3:35 explains the idea behind the Diffie-Hellman key exchange which is based on discrete logarithms and NOT prime factoring.
Also not all public key crypto is based on large primes like RSA is, most notably Diffie-Hellman based systems. Elliptic curve cryptography is another system which uses multiplications on discrete elliptic curves. There are relations between these three which means that quantum computers breaks them all.
The shortest vector problem does not concern itself with what the shortest distance between two arbitrary points of a lattice is (which is a trivial problem as the metric is usually given), but what the shortest possible vector (aside from 0) produced using the lattice's base vectors is. Also given your explaination of lattice cryptography using noise, the more relevant problem is the closest vector problem: Given a point slightly off the lattice, find the closest next point on the lattice.
Also you should mention that symmetric cryptography is safe from quantum computers; doubling their key length is enough to reach pre-QC strength.
Speaking of elliptic curves, there are new systems using elliptic curves to form isogeny graphs. You create a graph where the nodes are supersingular ECs and the edges are isogenies (maps) from one EC to another. The hard problem is to pathfind arround the graph when finding the isogenies is very complex. Especifically, there is a algorithm called Supersingular isogeny Diffie-Hoffman key exchange (SIDH). It has similiar key lenggh of RSA, is "perfect forward secret", and is analogous to DH, so can be used in symetrical and asymetrical encryption.
No known algorithm is known to solve this problem with subexponential complexity.
I found a lecture from one of the developers where gives an overview of isogeny-based cryptology, including hash functions. If you are interested:
th-cam.com/video/AoE-uQinzqU/w-d-xo.html
Yeah, the video's description of lattice-based crypto seemed garbled. Or I failed to understand the explanation, at the very least.
Thanks for the clarifications. I missed the Diffie-Hellman thing, but I have to say I did think there was something a bit off about that lattice section. Glad I wasn't just imagining it.
Thanks for these comments!
“Factor a prime number” (at about 1:20); factoring prime numbers is really easy! It just takes one step...
At 7:23 you say: "guess the factors of a prime number", I think you meant to say guess the factors of the modulo N, as used in RSA, which is the product of two large primes (those are secret), we are trying to find. Guessing the factors of a prime number makes no sense, they’re just 1 and the prime number. :P
That color mixing example 3:26 helped me understand public / private key crypto more than reading books on the subject has.
5:20 RIP Infinite Series 😥
I miss that series, too.
F
From Canada, we love you; along with the rest of the world. ❤
1:03 I just want to point out that "thousands to billions of years" sounds like quite the large range, and it is... but it's very true. The fun of how adding more bits to keys scales things by orders of magnitude.
My face when someone uses this or "exponentially" correctly 😊
I've been doing computer stuff for almost 20 years but it never occurred to me the analogy of RSA with combining color. That's brilliant!
I might be one year late but if you haven't yet, I suggest you look into color encryption, it goes way deeper
We need to develop quantum cryptography to send secret messages to the Venusians or the Sun-Dwellers will know all our secrets!
2:41 "Fortunately, there is another option, and one that will be a lot cheaper than building a quantum internet." Yep. It is called, "pay with cash."
"Secret Brown" is my favorite electro-funk fusion band.
"Shamed Excrement"
I did research in this using the McEliece crypto system, we are getting close but don’t have anything usable.
8MB doesn't sound like a crazy huge data size to improve on, so I am guessing some form of compression wouldn't help with transmission? Or is the problem less about transmission and more about the amount of computation?
@@robwhiteston2348 You can't compress encryption keys at all. They are designed to have maximum entropy, that is to say, they are indistinguishable from noise. If you compress a file, like a text file, into, say, a zip file, and you then look at the file it will look like random noise. If you then try to compress that file again, you'll find the resulting zip file bigger than the original (by a tiny amount). The amount is only so tiny because the compressor realizes it's only making things worse and will use the "store" compression method instead. It still has to add the information that the "store" method is needed, which increases the file by a tiny amount. If the software were to actually use the compression algorithm, the doubly-compressed file would be significantly bigger than the original zip file.
One way to overcome these issues is to use secret keys rather than public keys. The 8MB might not be a problem if you only have to do it once per website. The device could use the massive key to negotiate a shared secret with the website in question. Both the device and the web server could store the secret key in some way. To provide forward secrecy, the key should be a ratcheting key (as used in the Signal protocol, for instance).
Because shared keys cannot be brute forced no matter how many computers you have (like infinite computers as in quantum computing), it's impossible to crack (assuming you implement it right, such as never use the same key twice).
And so forth and so on. Wikipedia has more info.
@@memberwhen22 Sorry buddy, but you're wrong. Sure, what I called a "secret key" is not a complete descriptor, as I didn't call it a "shared secret", which is usually a part of a symmetric cryptosystem, which is what I was referring to. Certainly, the private key is also secret, so I see the confusion. What you got wrong, however is 2 things: I may not be an expert in cryptography, but I've studied it and I _am_ a software developer, for 25 years now. What's really wrong though is the idea that the public key is derived from the private key using a hash function. At least in the most commonly used cryptosystem, namely RSA. I believe ECC (elliptic curve crypto) has a similar derivation as well, and it's _not_ a hash function in either case. In RSA, the public key is a combination of p*q where p and q are the secret primes and e, where e is usually 65537, must be coprime with some fancy number rolling out of something called a totient function that has as inputs the q and the p, again. The same p and q. So both e and n (which is what p*q is usually called by you can call it "fred" for all I care) are at least partially derived from p and q (the private key) but not through a one way hash function. Granted, multiplication is technically a one way function given primes, but not a "one way hash function". Hash functions return fixed-sized output, something a multiplication isn't designed to do.
I think what you did was miss the idea of symmetric crypto. And that was what the whole second part of my comment was about...
Matt O’Dowd for president 2020
Finally a video that I can comment on!! So here it is: Today keys are 1.based on a 180 digit number. 2. The key is static, that is people don't change it. A simple solution to quantum comp. threats would be to 1. increase the digit number. 2. Estimate the minimum time it would take for the 'best' quantum computer to find the factors, lets call that 't". 3 Regularly change your key within that timeframe, 't'. The End. If this qualifies for the Nobel Prize, publish it for me: you can collect the 'tacky' award and we can split the $1 mil prize. Call me anytime except between 1Pm & 2pm EST (Jerry Springer show is on)
PBS Spacetime gets a "like" from me before the episode even starts. I love this show!!
username checks out
@@aethrya haha yup
Public/private RSA key can be understood via this analogy I always give as an example: If a person wants to mail you, then they request a special cascet (public key) from you. Such cascet is initially open but once it's closed it became locked: only key (private key) owner can open it. Once the person is done with writing, they put the letter into the cascet and lock it; at this point it is safe to share such cascet with anyone because only you hold its key hence only you can unlock it (not even letter owner can do it - only you)
I've seen many explanations for public/private key encryption, but this visualization was very clear in terms of explaning the concept.
please do an episode on kerr newman black holes. im honestly on the edge of my seat about them. feels like if we could directly measure the magnetic field generated by one we could learn a lot, like whether there's anything to the idea of a ringularity.
5:36 Matt missed 512 in the powers of 2.. This does in fact prove that matt is not a supercomputer...
I loved Gabe passion and contribution to both Space Time and Infinite Series channels. I hope to see him as a guest in one of your future episodes!
I'm very glad this topic was attempted and there was even some pretty good content in it. But the paint mixing example described an analogy for Diffie-Hellman key exchange which relies on the difficulty of discrete logarithms in finite fields, not the difficulty of factoring large semi-primes. Also Elliptic Curve Cryptography (ECC) was ignored which also doesn't rely on the difficulty of factoring. Quantum algorithms also defeat discrete log and ECC but for reasons other than Shor's algorithm.
My favourite show to geek-out to 😎😀
That color analogy for public key encryption was genius, kudos!
They didn't invent it though. It's a pretty standard analogy.
Great visualization idea of keys as colors!
Henceforth I will refer to humans as "Intelligent Electric Monopole Based Lifeforms"
I'm not so sure about the intelligent part though.
Counterpoint: mud-based life
The colour analogy for RSA is absolutely amazing... Definitely stealing that one
So the same technology that can be used as a weapon can be used as a shield, and apparently older technology can be a good enough shield against the new weapons.
08:00 Nowhere did it explain how quantum computers work, and thanks to this video I understood how it works
In the novel "The After On" there is a quantum AI that uses quantum hacking for RSA and DH. From the words of this AI - she always gets the password from the second try and the way it works - an infinite amount of these AI's try a random password on the first try and then the information from the ones who got it correct is shared through all the multiverse.
It's uncanny how seemingly important the significance and frequency of the number 21 is. It keeps reoccurring throughout mathematics, it's kind of like that phenomenon in real life and in Grand theft auto where the car you focus on starts to materialize in your little part of the matrix. Keep your eye out for 21 and you will begin to see it literally everywhere.
The biggest issue is that I might have secrets, encypted with RSA, out there. It is “public”, available for anyone, but not readable due to the encryption.
Someone might make a copy of it, save it, wait for the quantum computers to be production ready, and break my secret later. And these are ALREADY out there, I can do nothing about it.
That's a good point. Quantum encryption will only work for newly publicized data that it encrypts. It couldn't protect anything that's already out there and accessible.
Then again, there's an awfully large amount of data currently out there under our present encryption schemes. How would the attacker know what is valuable, and therefore worthy of saving for a later date, if they can't read it?
oquinc There are peoples and businesses out there, and it might worth to specifically target them, and record their communications. I’m probably okay, but if I would be a politician for example with things to hide, I would be worried.
16:43 That's deep...
Using Sycamore to simulate a quantum system is like using an hourglass to simulate the flow of sand.
I had no idea there were any Quantum resistant algorithms to begin with, really great video on the basics and advances of crypto.
12:58 So, how many takes did you do to pronounce this bit? :D That sounded like a complicated sentence to articulate
One tiny meth problem? Someone at my ISP is going to expose my history unless I get them-
{Turns on closed captioning}
Ooohh! Math problem! That makes more sense.
Same... What did I hear?
Don't do meth. Smoke Salvia instead.
"maybe he's dead?"
"Did what? Maybe he did, maybe he didnt!"
"One day I will be able to understand these videos". This is the thought that keeps me going through life
4:04 "The current dominant encryption protocol" is not RSA any more, it is ECC (Elliptic Curve Cryptography)
8:20 - 8:32 "which honestly I could do in my head" lmao
I love you guys!
6:08 hey, I love to watch things of this guy that inspired my own name. This time caught me off-guard!
This channel... It makes me actually want to research and understand things I currently don't >_< I'm bad at advanced math okay? Stop being so goooooood.
Why was 512 skipped in the powers-of-2 example? @5:33
To prove that humans made this video. Venusians wouldn't have made such a simple mistake.
I might not understand everything in this video but one thing I do understand is that a lettuce-based cryptosystem sounds amazing!
Really nice editing on this one, props to the team.
8:00 how exactly do they suppress all possible periods besides the correct one?
Okay so first collapsing the Digital World, then Matt on Green Hill Zone and maybe even a Counter Strike level. Referencing 2-3 video game in a single episode is wild
One important thing: *the existence of one way functions has not been proven.* It is an unsolved mathematical problem. They are necessary for quantum resistant cryptography to even exist without a quantum internet.
Pointing this out because any chosen algorithm is going to be a gamble unless this is resolved. Even solving the P=NP problem won't resolve it necessarily (depending on how it is resolved) because NP could still be equal to one of the probabilistic polynomial time complexity classes(BPP, ZP, RP, BQP). None of these classes are suspected to be equal to NP, but none of that has been proven yet.
Also if BQP = NP, then no quantum resistant encryption algorithms exist regardless of whether or not one way functions exist.
*TLDR:* It is a difficult problem because it is currently not clear if it is even theoretically possible.
I have a really serious question (not really). I know that NP is all the problems which a solution can be verified in polynomial time (fast for classical computers), but which the solution may not be possible to find in polynomial time. NP-complete problems are a special subset of NP, when a NP problem A can be converted in polynomial time to another NP problem B, than B is NP-complete (correct me if I'm wrong). So if you find an algorithm that solves a NP-complete problem B (fast or slow), then you can convert any problem to that problem B in polynomial time and thus solve all NP problems, (if that algorithm solves it in polynomial time, then P = NP). As far as I understood, cryptography needs to be a NP problem, easy to verify a solution, hard to find the solution and I also learned that the NP class is the only one that has this property, it's the definition. Any encryption algorithm, if it can be polynomially verified but not polynomially solved, is a NP problem. If quantum computers can solve one NP-complete problem in polynomial time, since it supposedly can verify all solutions at once, then it can solve all of them, so the whole class becomes useless for cryptography by definition?
TL;DR. Cryptography needs to be a NP problem (because of the unique property of that class), quantum computers can solve as fast as a classical computer can verify. So doesn't that mean that any ever attempt of cryptography will be useless? or I am making any wrong assumption? (which is probably the case)
These one-way functions sound an awful lot like entropy. So, how good is this analogy of encryption to the notion of entropy, and what is the quantum version of that concept? Also, does that mean that mean that breaking the encryption is akin to creating an 'open system' where the entropy of one part of the system, i.e. the encrypted message is decreased by expending energy and creating at least that much or more entropy elsewhere?
The method shown to get a shared key (RSA protocol) is called a Diffie-Hellman key exchange to be more precise.
when you really feel like watching a new episode and the notification shows up one second later... 👊 super!
Sabin covered it just few days back, common topic would have common story behind it. So good idea to space videos with similar topics apart a bit.
0:12 Wha-Wha-Wha
"Prime number factoring" is trivially easy !
The factors are itself and 1 ;-)
Aww, no word to my favorite PQ algorithm (now an alternate candidate in the competition) of SIKE. I would have loved seeing your illustration of the isogeny graph. It doesn't have the same large key size problems as all the other candidates, with the keys being similar in size to RSA (sadly not to ECC, which is what we use right now, with keys less than a hundred bytes long). But what it has in small key sizes, it sadly lacks in performance, because while the computation necessary for lattices is using your standard arithmetic, computing things on curves isn't something computers are currently good at. It also is a far younger crypto system compared to the error correcting codes or even the lattice based ones.
Telescopic collapse revealing assymetry, pretty cool.
finaly you came with another video i need learn
I'm studying for a cryptography certification right now. while this is way out of scope for the test it really motivated me to study.
There is something quantic with Matt O'Dowd's hands in this video. Too much cafeine ? Or a quantum computer is threatening to decode his old My Space account password, something like that.
(Seriously, I hope it's nothing serious, your channel is one of my favorite)
This is an eye opener 😳....
Great videos! I like to put on one of your playlists as I fall asleep. I just wanted to remind you that you have not added the last 10 or so episodes to the Space Time playlist, not a big deal but hey. Anyways, have great day everyone
I have a question for the next time - assuming two blackholes merge and assuming each one contains new big bang/white hole/universe or even “just” a singularity; that happens with each corresponding “something” inside a black holes? Which one keep existing or both are destroyed and new one created? Is it even have meaning to talk about something happening with “entities” inside a black hole from point if view from out universe? Even if not - how information paradox of black holes is affected by merging two together?
*Your thumbnail is shiv lingam. GoogIe "haribhakt shiv lingam" to clear your apprehensions. Vedic science on cosmic and quantum principles are amazing. GoogIe now.*
This is probably the clearest explanation of RSA that I have ever come across
(Actually, it's more akin to Diffie-Hellman, but still, great way to explain Asymetric Cryptography)
im excited to see were it takes us forsure
I just learned about the Dzhanibekov Effect on Veritisium, and now I want to see an episode about rotating bodies from PBS Space Time. Oumuamua, rockets, asteroids, planets, etc. I am also wondering...is the Dzhanibekov Effect caused by precession?
Great! The most important application of the quantum encryption will be in the brain-machine interfaces (as the ones researched at Neuralink). So we can take full advantage of these amazing technologies, with 0% probability of being hacked.
Finaly a free floating matt is back :)
5:52 where's 512? Also, all of your answers are off starting at 1024 (you forgot 512 :P)
No he didn't. 16*16 is 256 and 32*32 is 1024.
@@pilotavery it's powers of two and they already admitted to missing it in another comment
*You are good observer of old comments.* 😂🤣😂
Can we use equations related to probabilities of quantum mechanics (say superposition principle and other uncertainties and then having different parameters of the current prime factor method would lead to almost infinite range of answers) and then set a limit? Like a range of values would give us this value and then apply that inverted on the other end? Applying this can make the use of quantum encryption to the next level. Like 👍 and reply if you agree.
Sorry, not sure what you are describing here.
drdca listen, do you know about the superposition principle of particles like electrons and photons? We cannot determine their actual position a particular time period. But there exists some equations that help us in finding the probability of the position. Now first of all we have to select the equations which is not a big deal for us and then use the current encryption and decryption methods to g get the parameters to solve it. And by defining specific values to specific characters or numbers, we can get almost infinite easier ways to encrypt our private data. Hope so now you’re clear, but still you can ask your queries?
Devarsh Dave I have watched all of a first class on QM. I don’t mean a first lecture, I mean all the lectures of a quarter’s class on QM were uploaded to youtube, and they were pretty good. I can fetch the link if you want to watch it.
So, yes. I’m familiar with the concept of a superposition of states.
Ok, so it sounds like you are describing, using a classical computer to simulate the probabilities of some quantum system having some result, and calculating them to some given level of precision,
and using that with some cryptography stuff in order to do other cryptography stuff?
Is that an accurate description of what you are describing? If not, what about it is inaccurate?
drdca I’ve also watched all of them! Yes they are great 👍 and I’m trying to expand the current encryption decryption system by introducing a concept that could help us in Even more logical approach to it, just like a sum to solve whose parameters are encrypted by current methods and if we even figure out the actual parameters still we won’t know how to solve it or by placing the values in which equation which won’t also indeed have any exact answers but the range would be like an equation of a curve which would yield the actual DATA. 👍
1:17: I'm pretty sure I can factor a prime number in my head in almost no time.
In addition to quantum security, lattice-based cryptosystems can also support homomorphic encryption (see ring-LWE).
This is why PBS Infinite Series needs to make a comeback...
I thought super positional states were 1 or 0, neither and both all at once.
Is that not the case? Just on/off and both, not also neither on nor off included?
6:30
The way government bypasses your encryption is to directly read the data before it gets encrypted (ie the yellow and blue) or intercepts the sent data (ie the purple and orange).
I have been blogging and monitoring about this for quite a few years. A few corrections and thoughts:
1. SHOR's algorithm specifically breaks "asymmetric" cryptography. And that is only used for establishing a key to use for symmetric cryptography (AES / ChaCha20).
2. RSA isn't the only asymmetric cryptography for TLS, there's also ECC, and that is apparently also vulnerable. (Although a Post-Quantum protocol might exist for ECC)
3. Quantum Internet is way overhyped. Importantly TLS is used for communication between two hosts (and users behind) that have never met before. Quantum Internet is built in a very direct manner. For less cost, and way more portability you can simply distribute 2x 10TB hard disks with pure random data that is used to directly encrypt (One Time Pad) or derive the same symmetric keys.
4. It doesn't matter that Post-Quantum cryptography is not mature. You can use both RSA and McEliece together. They both generate their own keys, and then you can XOR them together for a final combined symmetric key. Then you get the maturity of RSA and the PQC of McElise. If maturity of McElise fails, you still have RSA; if RSA falls to a quantum computer, you still have McElise.
5. An 8MB key is less and less problematic as technology improves, and engineering can also reduce the amount of keys needed.
6. If we are happy to live with a 8MB McEliece key, why not live with an 8MB RSA key? Perhaps a quantum computer can break a 4k RSA key, but surely an 8MB one would require a quantum computer that is a lot more powerful.
Isn't RSA working without a shared secret ? Encryption using the public key is only reversible with the private key (other way around is signature). The colour demonstration is a diffie-hellman exchange protocol where you create a shared secret and only need to "add" and "remove" it to get the message.
To be honest if we don't find something tinier we might as well use multiple algorithms and it wouldn't be much of a problem. For latency intensive day to day messages we could still use the good old rsa based algos, but for anything that doesn't care much about that(eg. an email or a transaction with your bank) we would have those new safer ones.
I knew it! Ever since they considered the Photon to be a particle used in processing for quantum computers, I knew processing would speed up! It may not be light speed, but it is damn close!
As someone who works with computers a lot, going from Manual to Classical to Quantum almost feels like going from Analog to Digital then back to Analog... But this time it's *magic* Analog...
Definitely having some feels here for Infinite Series. I really enjoyed the episodes on Shor's algorithm in particular, and was glad to see the reference.
After Dual_EC_DRBG I'm not keen on following NISTs guidance wrt crypto. DJB seems to be backing NTRU Prime, so that's where my money is.
Every time I try to grasp the mathematical reasoning behind calculations based on quantum superposition my brain slides off like a well oiled pan.