The mathematical 'worlds' of cryptography: Which universe do we live In?

Рет қаралды 44,185

Күн бұрын

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/

Пікірлер: 83

@gubgubbubbub Ай бұрын

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...

@gogonogo2069 Ай бұрын

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 😭😭

@gubgubbubbub Ай бұрын

@@gogonogo2069 Possibly a skill issue

@LeelandOC Ай бұрын

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.

@joaoguerreiro9403 Ай бұрын

Everything about Computer Science fascinates me so much… I truly love this science ❤️

@tuams Ай бұрын

I'm happy you are putting out more content. Such good information to learn about the boundaries of our understanding! Thank you.

@Mattapple97 Ай бұрын

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.

@MrMctastics Ай бұрын

Cryptography is kind of boring in my opinion. Very important tho. Just look at TLS and you’re good

@1stlullaby484 Ай бұрын

Of course there's not enough time to learn all.

@lonestarr1490 Ай бұрын

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.

@1stlullaby484 Ай бұрын

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)

@bimrebeats Ай бұрын

@@MrMctasticseverything is boring if you look at it from the most boring perspective or distance.

@joshuacarlisle9901 22 сағат бұрын

Love this guys whole vibe. Adorable yet genius

@cobana4730 Ай бұрын

did not expect to see Geisel in my KZfaq feed

@massimopiemontese4776 Ай бұрын

Really good, but why is the music louder than his voice?

@gregyoung6510 Ай бұрын

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.

@Simon-ir6mq Ай бұрын

Randomly came across the paper some months ago. Was a great read! Nice to see quanta cover it!

@BM-rm7vr Ай бұрын

Do you perhaps know how to describe the double slit experiment? I’m looking for people who understand it well.

@MrAlRats Ай бұрын

@@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 Ай бұрын

I think I understand the connection to Euler’s formula. However I am interested In finding real world apps for imaginary numbers. I can see how Euler’s formula can predict the way the wave function evolves in space and around obstacles. But I had the idea that the probability wave is real and flows and evolves but we can’t directly detect that operation because to do so would constrain that degree of freedom from Hilbert Space. I feel like Hilbert Space isn’t real but it exists, that any attempt at directly measuring a property in Hilbert Space brings forth that property into the information network? Tell me if I am wrong in this idea, that when an event happens the world can tell as an electron changed or energy levels. But the world only knows that an event happened, say a photon was emitted but not what direction. At that point the system has only one fixture point, the fixed position of the emitter. But when the quantum wave interacts with the slit detector, now azimuth information has been constrained and the quantum object now has vector information. So, turning on the slit detector allows the formation of a line, fixed emitter position to detector and the the fringe pattern disappears. But say you put the emitter into an X superposition parallel with the screen axis, now even though you have the slit detector on, you lost the fixed emitter position and the fringe pattern will reappear. Is that accurate?

@MrAlRats Ай бұрын

@@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.

@MrAlRats Ай бұрын

@morkovija Ай бұрын

that house on top of a building was super cute and awesome!

@NicholasHay1982 Ай бұрын

Going to school at UCSD really is a like attending Lewis Carroll's Wonderland

@existenceisillusion6528 Ай бұрын

We're just not going to talk about that house 4:07 and 4:09?

@Patashu Ай бұрын

Ooh, there's a sixth world now? That made my day! I wanna learn about it lmao

@sushantap Ай бұрын

Is 4:09 where the happy professor lives? : )

@offlinevods8487 Ай бұрын

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.

@rajivkrishnakumar9925 Ай бұрын

Wouldn't QKD still be a viable form of cryptography in 'algorithmica' or am I misunderstanding something?

@ronankenny8148 Ай бұрын

what is up with the small blue house on the building?

@anon42ger74 Ай бұрын

oh my god why is he so adorably cute?

@kautzz Ай бұрын

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?

@AntonAdelson Ай бұрын

Piggybacking

@inamotel6772 Ай бұрын

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.

@kautzz Ай бұрын

@@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?

@AntonAdelson Ай бұрын

@@kautzz lol, I meant I'm piggybacking to your question! Didn't even know there's a comp sci tech called piggybacking o.o

@kautzz Ай бұрын

@@AntonAdelson 🤣 that point passed by me so far away I didn't even know there was one

@nanashipersonne4151 Ай бұрын

Does he recommend any literature? Did he write a book himself?

@MathFromAlphaToOmega Ай бұрын

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?

@DeathSugar Ай бұрын

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)

@DeathSugar Ай бұрын

@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.

@finnsoutherland7382 Ай бұрын

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.

@Boltzmann1906 Ай бұрын

We’re pretty sure P is not NP. Not in this lifetime

@luizhenriqueamaralcosta629 Ай бұрын

This guy looks good-hearted

@primenumberbuster404 Ай бұрын

Just 5 mins? ;)

@notsojharedtroll23 Ай бұрын

I'm a simple man, I see the UCSD's Geisel Library and I like

@InquilineKea Ай бұрын

Alignment and human intelligence enhancement for cryptography

@crehenge2386 22 күн бұрын

What about non-computational math then? How could you have that in a computational universe...?

@BM-rm7vr Ай бұрын

Anyone know where I can find Russell Impagliazzo‘s stand-up comedy?

@gogonogo2069 Ай бұрын

His ucsd lecture podcasts

@BM-rm7vr Ай бұрын

Gracias

@lh4394 Ай бұрын

Everyone will have to start encrypting everything using lavalamps

@markshiman5690 Ай бұрын

tilted house?

@jareedm Ай бұрын

It’s an art piece called Fallen Star at UCSD

@Bob-Fields Ай бұрын

Legitimate users @0:50?

@johnjones8330 Ай бұрын

A technical point, but even in Algorithmica we have one time pads, not as useful but better than nothing.

@kingki1953 Ай бұрын

We build on NVIDIA Universe Chip 💀

@jpphoton Ай бұрын

hmmmmmm .. seems a lil platitudinous err broad but vague categories

@dewiz9596 Ай бұрын

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”.

@axioms22 Ай бұрын

Ok?