Cryptography's Mathematical 'Worlds': Which One Do We Live In?
Vložit
- čas přidán 31. 05. 2024
- For forty years, Russell Impagliazzo has worked at the forefront of computational complexity theory, the study of the intrinsic difficulty of different problems. The most famous open question in this field, called the P versus NP problem, asks whether many seemingly hard computational problems are actually easy, with the right algorithm. An answer would have far-reaching implications for science and the security of modern cryptography. In 1995, Impagliazzo wrote a seminal paper where he reformulated possible solutions to P versus NP in the language of five hypothetical worlds we might inhabit, whimsically dubbed Algorithmica, Heuristica, Pessiland, Minicrypt and Cryptomania. Impagliazzo’s five worlds have inspired a generation of researchers, and they continue to guide research in the flourishing subfield of meta-complexity
CINEMATOGRPAHY: Jesse Aragon
----------
Read the full article for links to papers:
www.quantamagazine.org/the-re...
Read the Quanta article about Impagliazzo's Five Worlds - Which Computational Universe Do We Live In?
www.quantamagazine.org/which-...
----------
Chapters:
00:00 Cryptography is the killer app of Computational Complexity
01:31 Impagliazzo's Five Worlds
02:03 World 1 - Algorithmica
02:27 World 2 - Heuristica
02:53 World 3 - Pessiland
03:15 World 4 - Minicrypt
03:52 World 5 - Cryptomania - cryptography as we know it
----------
- VISIT our website: www.quantamagazine.org
- LIKE us on Facebook: / quantanews
- FOLLOW us Twitter: / quantamagazine
Quanta Magazine is an editorially independent publication supported by the Simons Foundation: www.simonsfoundation.org/ - Věda a technologie
I had him as a professor last quarter! Good-natured and wicked smart - solved a problem I'd been struggling with for weeks in a few minutes...
I had him 2 quarters ago and his entire course was not put together at all. He may be wicked smart at his studies but actually teaching a class is not his strong suit 😭😭
@@gogonogo2069 Possibly a skill issue
I love content like this. I don't know how else I would connect (even briefly) with the lives of so many people who are slowly advancing the boundaries of human shared knowledge.
I feel addicted to mathematics. When I was in grad school, I studied Theoretical CS and wrote my thesis on cryptography (zero-knowledge). Ever since getting out of academia, I spend my free time reading and self studying the math I never got a chance to formally learn like abstract algebra and quantum physics. But then I see a video like this that convinces me I need to spend the next year just going full send on complexity theory and cryptography. 😢 I just dont know if there's enough time in life to learn all the things I want to learn.
Cryptography is kind of boring in my opinion. Very important tho. Just look at TLS and you’re good
Of course there's not enough time to learn all.
If this topic intrigues you, I'd advice you to spend your time on number theory and algebraic topology/geometry. Most modern cryptography is basically an application of elliptic curves, homology and cohomology theory.
So basically what lonestarr1490 is saying is that learn the following(if you're serious about this) if you aren't familiar with them.
( someone needs to refine this list a bit, probably)
1. Number theory
(some introductory set theory included, you can postpone set theory tho, but it's a must before metric space and topology)
2. Abstract algebra
3. Real analysis (essentially rigorous calculus)
(Not a must but otherwise you won't appreciate topology)
4. Metric space
( be careful depending on which book you choose this one might confuse you while learning topology, only at the beginning of course)
(Again not a must but if you wish to learn topology at length then go for it)
5. Topology ( i recommend Topology by James R Mukres, Read the preface, there you'll find the dependence of the topics and chapters )
( if you haven't learnt real analysis or metric space this will be tough)
6. Algebraic Topology ( Core part can be learnt from the same book i recommended for topology)
@@MrMctasticseverything is boring if you look at it from the most boring perspective or distance.
Everything about Computer Science fascinates me so much… I truly love this science ❤️
I'm happy you are putting out more content. Such good information to learn about the boundaries of our understanding! Thank you.
Randomly came across the paper some months ago. Was a great read! Nice to see quanta cover it!
@@BM-rm7vr Are you familiar with complex numbers and Euler's formula? If so I can point to some educational resources that describe the double slit experiment.
@@BM-rm7vr A good place to start is to get a hold of the book, 'The Character of Physical Law' (MIT Press, 2020) by Richard Feynman. Once you have thoroughly digested the chapter titled, 'Probability and Uncertainty - the Quantum Mechanical view of Nature'; then try reading the third volume of the book, 'The Feynman Lectures on Physics' (Volume III), chapter 1 - 'Quantum behaviour', chapter 3 - 'Probability Amplitudes' and chapter 4 - 'Identical Particles'. When you have read and understood these chapters thoroughly, then read the American Journal of Physics article, 'Quantum mysteries revisited again' by P.K. Aravind.
@@BM-rm7vr A good place to start is to get a hold of the book, 'The Character of Physical Law' (MIT Press, 2020) by Richard Feynman. Once you have thoroughly digested the chapter titled, 'Probability and Uncertainty - the Quantum Mechanical view of Nature'; then try reading the third volume of the book, 'The Feynman Lectures on Physics' (Volume III), chapter 1 - 'Quantum behaviour', chapter 3 - 'Probability Amplitudes' and chapter 4 - 'Identical Particles'. When you have read and understood these chapters thoroughly, then read the American Journal of Physics article, 'Quantum mysteries revisited again' by P.K. Aravind.
@@BM-rm7vr Check out the following texts.
@@BM-rm7vr Check out the following texts:
Love this guys whole vibe. Adorable yet genius
Really good, but why is the music louder than his voice?
This is terrific. I can't wait to see where the sixth world takes us. Quanta is the most informative platform i have been able to find for science explanations that are easily understood.
that house on top of a building was super cute and awesome!
We're just not going to talk about that house 4:07 and 4:09?
did not expect to see Geisel in my CZcams feed
Going to school at UCSD really is a like attending Lewis Carroll's Wonderland
what is up with the small blue house on the building?
Is 4:09 where the happy professor lives? : )
No its called "fallen star" and its a little house on top of a ucsd engineering building where the floors, ceiling, furniture are all tilted so it feels disorientating to walk into but you get used to it.
Ooh, there's a sixth world now? That made my day! I wanna learn about it lmao
I'm certainly not an expert on cryptography, but it seems like much of it depends on P=NP being false. Is there a plan for how to "fix" things if P=NP turns out to be true?
There are post quantum algorithms which supposedly overcome quantum oracles and make cryptography secure enough (for now), but so far it's the farthest we went for now.
Also, there's no any evidences about them being equal as far as I know, so no point in thinking about it unless anyone introduce any conjectures that could point to it. And since noone can predict how this would work out - you can't defend against things you can't imagine. There are known functions from higher computational domains, so we probably could use some of them, when time comes, so nothing much to be concerned here yet.
If I understand it correctly, P=NP could only destroy asymmetric encryption, so you could still get an AES key from a company (e.g. in a personal letter in form of a QR code) and use that to log into your online account. (Correct me if I'm wrong)
@its depends on complexity of algorithm, so AES could be vulnerable, if XSL attack contains NP subroutines. Currently it's potentially 2^100 ops at worst case, but it could drop drastically if P=NP. Can't tell for sure, since didn't read details about attack.
The first world, Algorithimca, is the one where P=NP. In this case I think the idea is there's really no way to have cryptography (other than things like one time pads). As I understand it, in order for your intended receiver to know that they have successfully decrypted your message (in polynomial (read "a reasonable amount of") time), the problem at the core of your cryptography can't be outside of NP. So if P=NP and your intended receiver can check that they've received your message, any observer can also read the message.
We’re pretty sure P is not NP. Not in this lifetime
Wouldn't QKD still be a viable form of cryptography in 'algorithmica' or am I misunderstanding something?
oh my god why is he so adorably cute?
I'm curious what are the three longstanding encryption methods? Is he talking about asymmetric, symmetric and ... hashing? I learned a long time ago that hashing is not encryption. Am I wrong?
Piggybacking
He says "only like three" with respect to Cryptomania, so I'm guessing Discrete-Log based encryption, residuosity based encryption, and encryption based on lattices.
@@AntonAdelson that does not protect the data at all AFAIK. it's a technique for increasing network efficiency - data is still sent in clear - no?
@@kautzz lol, I meant I'm piggybacking to your question!
Didn't even know there's a comp sci tech called piggybacking o.o
@@AntonAdelson 🤣 that point passed by me so far away I didn't even know there was one
Does he recommend any literature? Did he write a book himself?
This guy looks good-hearted
Just 5 mins? ;)
What about non-computational math then? How could you have that in a computational universe...?
I'm a simple man, I see the UCSD's Geisel Library and I like
Alignment and human intelligence enhancement for cryptography
Everyone will have to start encrypting everything using lavalamps
Legitimate users @0:50?
tilted house?
It’s an art piece called Fallen Star at UCSD
A technical point, but even in Algorithmica we have one time pads, not as useful but better than nothing.
We build on NVIDIA Universe Chip 💀
hmmmmmm .. seems a lil platitudinous err broad but vague categories
Is it just me or does the voice sound mechanical or a bit off..Perhaps A.I generated?
Just you
Making UCSD look not like the concrete jungle that it is, ok good job I guess, he probably sits in one of the less-ugly buildings.
How do you square a fart?
Show me this guys ide setup so i can decide whether or not to trust him
only trust ppl that use vim!
I wrote, for my own entertainment, a program which emulates the Enigma Machine in Software. . . (to the extent that I understand the Enigma Machine). My starting point was a 1987 Byte Magazine article describing a pseudorandom number generator, in Pascal. I rewrote it in C. Unlike “out of the box” random number generators, it could actually produce duplicate numbers. Eliminating these duplicates while retaining the random sequence is “left as an exercise for the reader”.
Ok?
Of course as an experimentalist you know that nature doesn't do any computations at all. ;-)
First