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.
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.
You're one of those RUclipsr'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 RUclipsrs to watch. BTW, don't mistake me calling you a RUclipsr 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 RUclips, 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.
@@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!
*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: ruclips.net/video/AoE-uQinzqU/видео.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.
"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...
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...
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)
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)
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.
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
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.
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.
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.
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 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?
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.
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.
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.
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.
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).
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. 👍
3:26 - Using a visual demonstration of the Diffie-Hellman algorithm to explain how RSA uses one way functions is a bit... awkward. Diffie-Hellman plays a totally different role, and the mathematical properties of Diffie-Hellman aren't necessarily comparable to those of RSA's algorithm. It really throws in a lot more potentially confusing details than were necessary to explain one-way functions. It would have been easier and more correct to simply say that if you have two paint colors and mix them together, it is difficult to unmix those paint colors. That's a one way function, and the mixed paint color is your cryptographic key, and you can't decrypt the message unless you know the original colors that were mixed to create the mixed color. This episode definitely needed a lot more research.
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?
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
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.
It is only me, or anyone else thinks that the exponentially increasing difficulty in maintaining more and more qbits coherent will eventually put a hard limit on the size of quantum computers, with something akin to 2nd law of thermodynamic, that emerges as statistically true on macroscopic level, even if not obvious from the standpoint of individual microscopic interactions?
I will preface this by saying that I'm no expert in quantum computing, but humans have an extended history of believing they've found a hard limit and then realizing there are ways to do better. So, I would certainly believe that there could *be* a hard limit, but I might be skeptical of any particular claim to have found it... 😁 It's also possible that a limit exists, but it's high enough that we can't get to it for centuries or longer.
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.
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.
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.
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.
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...
I welcome a world in which governmental, corporate, and private foundation shenanigans are easily exposed. The end of classical encryption isn't a disaster, but a breath of fresh air. If you aren't doing anything unsavory, you have nothing to fear from publicity.
@@KohuGaly Why would you think I engage in any online financial transactions? What sort of fool do you take me for?🤣🤣 Just so you know, I'm an ordained cleric, and I've taken a vow of minimal complicity with commercial activity. You can't serve both God and Mammon. I have a low paying job that I perform mostly for the glorious heavy physical labor that it requires, but I purchase next to nothing and engage mostly in barter and charitable activities for others. Money only tempts you to do evil things, like living inside buildings, owning motor vehicles, and ruining your moral center in the pursuit of pointless doodads and baubles.
I disagree strongly. Unsavory is in the eye of the beholder. There are several governments right now that disable internet because any communication with the outside is deemed "unsavory". The fourth amendment is there for good reason. It should be bolstered, not reduced. The Fed trying to force tech to put backdoors is wrong; it is in their interest, not the citizen's interest. Edward Snowden is a patriot.
@@concinnity9676 I'm not sure you understand my meaning. I'm a big fan of the work of Snowden and Assange. The primary targets of encryption hacking will obviously be the organizations that are engaged in behaviors that threaten others, hence the list I gave. If some guy wants to have dirty email conversations with his wife's sister, who besides his wife and brother-in-law would have a motivation to expose it? If he has financial entanglements with entities that could use the information against him, he shouldn't be doing it. What you're essentially saying, as far as I can tell, is that people should be immune from negative consequences for immoral behavior. If that's the case, then I'd say don't do the crime if you can't do the time. Actions, whether good or bad, should have consequences. Personally, I always encourage people to criticize any moral failings they think I have, and I never react defensively to such criticism, though I often disagree. Doing good is easy when you understand the consequences of doing bad. Just to clarify, I should point out that, in my religion, thoughts, feelings and beliefs are only relevant to the degree that they precipitate actions. Actions and their results are the only legitimate bases for morally judging others. Intentions are fairly meaningless.
1. Is the matrix problem similar to a QR code? The same information is repeated like 6 times and rotated to provide redundancy for error correction. So, the key would be to know which bits are mirrored instead of known handpicked practical error resistant shape? 2. What is the computational complexity of factorisation on quantum computer? Even if it's linear you could use big key only to encrypt and propagate a temporary small one. I think this technique is even used now. Big keys are used to authenticate and then smaller keys are used for communication and swapped on short periods of time. The slow down might not be so big, especially if regular encryption would be practically quantum resistant on short time scales.
Hey can u please give answer to this question - If a person is in a elevator and the cables of the elevator brakea and the person starts to fall...will the peron be floating around ?...and yes then why ?
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
*Your thumbnail is shiv lingam. GoogIe "haribhakt shiv lingam" to clear your apprehensions. Vedic science on cosmic and quantum principles are amazing. GoogIe now.*
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.
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
Don’t forget mentioning Leonid Xanfomality (Леонид Ксанфомалити), a Soviet and Russian scientist, who got famous for supposing that some life forms might still be on Venus. Well, in recent time. But actually, he was one of the scientists who launched space probes on Venus. Dear viewers and commenters, please, before “debunking” ask yourself, would anyone notice this man otherwise? No! By the way, in his lectures, he stressed that the only way to find out for sure, whether Venus is sterile or not, is to launch a new reinforced probe that would gather more data. I like how he ended that lecture: “Believing or not believing-leave it to church. Science is all about testing.”
Question. How would a classical computer visualize or use a matrix or lattice. Seems like any compute would have to store or send a huge amount of data just for the inscription. Trading one large data problem for another.
Isn't "Supersingular isogeny DH key exchange" a better solution against quantum decryption? It is based on well understood properties of elliptic curves and supersingular isogeny graphs. It has one of the smallest key-sizes, and on top of that, it offers perfect forward secret. And is analogous to today's Diffie-Hellman key exchange protocol. So it supports both symmetric and asymmetric encryption (for key exchange). It is based on the hard problem of computing endomorphism rings of supersingular elliptic curves to find the connections (isogenies) to pathfind in a isogeny graph. Translating as I understand: The nodes in the graph are elliptic curves, the edges are isogenies (which are maps from a EC1 to EC2). The secret is the path you take to go from node A to B. The problem is trying to follow the same path when it is very hard to "track" for "prints". I found this lecture from one of the pioneers of this system. It is a full lecture, not only on encryption but an overview on many applications of isogeny-based encryption. ruclips.net/video/AoE-uQinzqU/видео.html
With an 8 megabyte key a pad key could be used with a new line of code every 4-5 letters of the message. Messages would not be so long as to repeat a pad line.
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.
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.
You're one of those RUclipsr'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 RUclipsrs to watch. BTW, don't mistake me calling you a RUclipsr 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 RUclips, 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
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.
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.
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 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.
*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:
ruclips.net/video/AoE-uQinzqU/видео.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!
"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.
That color analogy is spot on. Wish my lecturers explained it that way back in college!
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
“Factor a prime number” (at about 1:20); factoring prime numbers is really easy! It just takes one step...
"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
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.”
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. ;)
5:20 Ahh yes, twist that knife in my heart, thank you very much.
That color mixing example 3:26 helped me understand public / private key crypto more than reading books on the subject has.
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...
From Canada, we love you; along with the rest of the world. ❤
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)
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
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
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)
5:20 RIP Infinite Series 😥
I miss that series, too.
F
"Secret Brown" is my favorite electro-funk fusion band.
"Shamed Excrement"
I've seen many explanations for public/private key encryption, but this visualization was very clear in terms of explaning the concept.
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)
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 😊
The colour analogy for RSA is absolutely amazing... Definitely stealing that one
We need to develop quantum cryptography to send secret messages to the Venusians or the Sun-Dwellers will know all our secrets!
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
PBS Spacetime gets a "like" from me before the episode even starts. I love this show!!
username checks out
@@aethrya haha yup
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.
Matt O’Dowd for president 2020
That color analogy for public key encryption was genius, kudos!
They didn't invent it though. It's a pretty standard analogy.
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.
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 studying for a cryptography certification right now. while this is way out of scope for the test it really motivated me to study.
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!
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."
5:36 Matt missed 512 in the powers of 2.. This does in fact prove that matt is not a supercomputer...
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.
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.
"One day I will be able to understand these videos". This is the thought that keeps me going through life
I had no idea there were any Quantum resistant algorithms to begin with, really great video on the basics and advances of crypto.
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?
I might not understand everything in this video but one thing I do understand is that a lettuce-based cryptosystem sounds amazing!
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.
8:00 how exactly do they suppress all possible periods besides the correct one?
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.
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.
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.
0:12 Wha-Wha-Wha
"Prime number factoring" is trivially easy !
The factors are itself and 1 ;-)
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).
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)
Really nice editing on this one, props to the team.
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. 👍
3:26 - Using a visual demonstration of the Diffie-Hellman algorithm to explain how RSA uses one way functions is a bit... awkward. Diffie-Hellman plays a totally different role, and the mathematical properties of Diffie-Hellman aren't necessarily comparable to those of RSA's algorithm.
It really throws in a lot more potentially confusing details than were necessary to explain one-way functions.
It would have been easier and more correct to simply say that if you have two paint colors and mix them together, it is difficult to unmix those paint colors. That's a one way function, and the mixed paint color is your cryptographic key, and you can't decrypt the message unless you know the original colors that were mixed to create the mixed color.
This episode definitely needed a lot more research.
Using Sycamore to simulate a quantum system is like using an hourglass to simulate the flow of sand.
The method shown to get a shared key (RSA protocol) is called a Diffie-Hellman key exchange to be more precise.
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?
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
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.
when you really feel like watching a new episode and the notification shows up one second later... 👊 super!
6:08 hey, I love to watch things of this guy that inspired my own name. This time caught me off-guard!
It is only me, or anyone else thinks that the exponentially increasing difficulty in maintaining more and more qbits coherent will eventually put a hard limit on the size of quantum computers, with something akin to 2nd law of thermodynamic, that emerges as statistically true on macroscopic level, even if not obvious from the standpoint of individual microscopic interactions?
I will preface this by saying that I'm no expert in quantum computing, but humans have an extended history of believing they've found a hard limit and then realizing there are ways to do better.
So, I would certainly believe that there could *be* a hard limit, but I might be skeptical of any particular claim to have found it... 😁
It's also possible that a limit exists, but it's high enough that we can't get to it for centuries or longer.
Great visualization idea of keys as colors!
Every time I try to grasp the mathematical reasoning behind calculations based on quantum superposition my brain slides off like a well oiled pan.
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.
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!"
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.
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.
4:04 "The current dominant encryption protocol" is not RSA any more, it is ECC (Elliptic Curve Cryptography)
My favourite show to geek-out to 😎😀
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!
8:20 - 8:32 "which honestly I could do in my head" lmao
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...
I welcome a world in which governmental, corporate, and private foundation shenanigans are easily exposed.
The end of classical encryption isn't a disaster, but a breath of fresh air. If you aren't doing anything unsavory, you have nothing to fear from publicity.
Good luck telling that to your bank, when someone intercepts your internet banking connection, cracks it and empties your bank account.
@@KohuGaly Why would you think I engage in any online financial transactions? What sort of fool do you take me for?🤣🤣
Just so you know, I'm an ordained cleric, and I've taken a vow of minimal complicity with commercial activity. You can't serve both God and Mammon. I have a low paying job that I perform mostly for the glorious heavy physical labor that it requires, but I purchase next to nothing and engage mostly in barter and charitable activities for others. Money only tempts you to do evil things, like living inside buildings, owning motor vehicles, and ruining your moral center in the pursuit of pointless doodads and baubles.
I disagree strongly. Unsavory is in the eye of the beholder. There are several governments right now that disable internet because any communication with the outside is deemed "unsavory". The fourth amendment is there for good reason. It should be bolstered, not reduced. The Fed trying to force tech to put backdoors is wrong; it is in their interest, not the citizen's interest. Edward Snowden is a patriot.
@@concinnity9676 I'm not sure you understand my meaning. I'm a big fan of the work of Snowden and Assange. The primary targets of encryption hacking will obviously be the organizations that are engaged in behaviors that threaten others, hence the list I gave. If some guy wants to have dirty email conversations with his wife's sister, who besides his wife and brother-in-law would have a motivation to expose it? If he has financial entanglements with entities that could use the information against him, he shouldn't be doing it. What you're essentially saying, as far as I can tell, is that people should be immune from negative consequences for immoral behavior. If that's the case, then I'd say don't do the crime if you can't do the time.
Actions, whether good or bad, should have consequences. Personally, I always encourage people to criticize any moral failings they think I have, and I never react defensively to such criticism, though I often disagree. Doing good is easy when you understand the consequences of doing bad. Just to clarify, I should point out that, in my religion, thoughts, feelings and beliefs are only relevant to the degree that they precipitate actions. Actions and their results are the only legitimate bases for morally judging others. Intentions are fairly meaningless.
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.
In addition to quantum security, lattice-based cryptosystems can also support homomorphic encryption (see ring-LWE).
1. Is the matrix problem similar to a QR code? The same information is repeated like 6 times and rotated to provide redundancy for error correction. So, the key would be to know which bits are mirrored instead of known handpicked practical error resistant shape?
2. What is the computational complexity of factorisation on quantum computer? Even if it's linear you could use big key only to encrypt and propagate a temporary small one. I think this technique is even used now. Big keys are used to authenticate and then smaller keys are used for communication and swapped on short periods of time. The slow down might not be so big, especially if regular encryption would be practically quantum resistant on short time scales.
Hey can u please give answer to this question -
If a person is in a elevator and the cables of the elevator brakea and the person starts to fall...will the peron be floating around ?...and yes then why ?
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
*Your thumbnail is shiv lingam. GoogIe "haribhakt shiv lingam" to clear your apprehensions. Vedic science on cosmic and quantum principles are amazing. GoogIe now.*
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.
Telescopic collapse revealing assymetry, pretty cool.
7:11, top left corner: CS 1.6 dust 2, memories.
Anyway you say magnetic monopoles don't exist but what about div B = 0? Or is that an approximation?
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
Thanks a lot Mr. Shor, Cybertronian rule is inevitable
Don’t forget mentioning Leonid Xanfomality (Леонид Ксанфомалити), a Soviet and Russian scientist, who got famous for supposing that some life forms might still be on Venus. Well, in recent time. But actually, he was one of the scientists who launched space probes on Venus. Dear viewers and commenters, please, before “debunking” ask yourself, would anyone notice this man otherwise? No! By the way, in his lectures, he stressed that the only way to find out for sure, whether Venus is sterile or not, is to launch a new reinforced probe that would gather more data. I like how he ended that lecture: “Believing or not believing-leave it to church. Science is all about testing.”
1:17: I'm pretty sure I can factor a prime number in my head in almost no time.
Question. How would a classical computer visualize or use a matrix or lattice. Seems like any compute would have to store or send a huge amount of data just for the inscription. Trading one large data problem for another.
In a nutshell, cat is out the bag... Better be on this when it rolls around lol
Isn't "Supersingular isogeny DH key exchange" a better solution against quantum decryption? It is based on well understood properties of elliptic curves and supersingular isogeny graphs. It has one of the smallest key-sizes, and on top of that, it offers perfect forward secret. And is analogous to today's Diffie-Hellman key exchange protocol. So it supports both symmetric and asymmetric encryption (for key exchange).
It is based on the hard problem of computing endomorphism rings of supersingular elliptic curves to find the connections (isogenies) to pathfind in a isogeny graph. Translating as I understand: The nodes in the graph are elliptic curves, the edges are isogenies (which are maps from a EC1 to EC2). The secret is the path you take to go from node A to B. The problem is trying to follow the same path when it is very hard to "track" for "prints".
I found this lecture from one of the pioneers of this system. It is a full lecture, not only on encryption but an overview on many applications of isogeny-based encryption.
ruclips.net/video/AoE-uQinzqU/видео.html
With an 8 megabyte key a pad key could be used with a new line of code every 4-5 letters of the message. Messages would not be so long as to repeat a pad line.
The Caesar Salad Cipher is my favorite lettuce-based crisp-o system.