The Quanta Podcast cover image

Researchers Identify 'Master Problem' Underlying All Cryptography

The Quanta Podcast

00:00

Is There a One Way Function?

Time bounded comogorov complexity is computable. Leo and pass showed if there's an efficient way to do this, then true one way functions can't exist. On the other hand, if calculating the approximate time bounded comograph complexity is too hard to solve efficiently for many strings, then layo and past showed that true one way function must exist. If that's the case, their paper even provides a specific way to make one.

Transcript
Play full episode

The AI-powered Podcast Player

Save insights by tapping your headphones, chat with episodes, discover the best highlights - and more!
App store bannerPlay store banner
Get the app