
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