Fundamentet til [[Kryptografi]], i den forstand at uten énveisfunksjoner kan kryptografi ikke eksistere. Énveisfunksjoner er tilstrekkelig til å bygge - [[Symmetrisk kryptografi]] - [[Digitale signaturer]] - [[Kunnskapsløse beviser]] ... men *ikke* [[Offentlig-nøkkel kryptering]]/[[Key Encapsulation Mechanisms]]. (Er dette vist, eller et åpent spørsmål? Mistenker sistnevnte.) Spørsmålet om deres eksistens er åpent: Hvis [[P]] = [[NP]] så eksisterer de så klart ikke (så altså ikke i [[Algorithmica]], og sikkert ikke i [[Pessiland]] heller, men i [[Minicrypt]]—og så klart [[Cryptomania]]?). #### Énveisfunksjoner og [[Kolmogorov-kompleksitet]] Men spørsmålet viser seg å være enda tettere knyttet [[Kolmogorov-kompleksitet]], som beskrevet i [denne Quanta-artikkelen](https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/): > The existence of true one-way functions, they proved, depends on one of the oldest and most central problems in another area of computer science called complexity theory, or computational complexity. This problem, known as Kolmogorov complexity, concerns how hard it is to tell the difference between random strings of numbers and strings that contain some information. > > Liu and Pass proved that if a certain version of Kolmogorov complexity is hard to compute, in a specific sense, then true one-way functions do exist, and there’s a clear-cut way to build one. Conversely, if this version of Kolmogorov complexity is easy to compute, then one-way functions cannot exist. “This problem, [which] came before people introduced one-way functions, actually turns out to fully characterize it,” Pass said. > > (...) > > In 1985, [Leonid Levin](https://www.cs.bu.edu/~lnd/), a computer scientist at Boston University, answered this question in a formal sense, [demonstrating](https://dl.acm.org/doi/10.1145/22145.22185) a “universal” one-way function that is guaranteed to be a one-way function if anything is. But his construction was “very artificial,” said [Eric Allender](https://people.cs.rutgers.edu/~allender/), a computer scientist at Rutgers University. It is “not something anybody would have studied for any reason other than to get a result like that.” > > What cryptographers were really after was a universal one-way function that stemmed from some natural problem — one that would give real insight into whether one-way functions exist. Researchers long had a particular problem in mind: Kolmogorov complexity, a measure of randomness that originated in the 1960s. But its connection with one-way functions was subtle and elusive. Spesifikt omhandler det spørsmålet om hvor vanskelig det er å beregne time-bounded [[Kolmogorov-kompleksitet]]: > More specifically, suppose you’ve set your sights on a less lofty goal than calculating the exact time-bounded Kolmogorov complexity of every possible string — suppose you’re content to calculate it approximately, and just for most strings. If there’s an efficient way to do this, Liu and Pass showed, then true one-way functions cannot exist. In that case, all our candidate one-way functions would be instantly breakable, not just in theory but in practice. > > (...) > > Conversely, if calculating the approximate time-bounded Kolmogorov complexity is too hard to solve efficiently for many strings, then Liu and Pass showed that true one-way functions must exist. If that’s the case, their paper even provides a specific way to make one. > > (...) > > And if their function can be made practical, it should be used in preference to the candidate one-way functions based on multiplication and other mathematical operations. For if anything is a one-way function, this one is. Fin optimisme på slutten her: > Now cryptography and complexity have a shared goal, and each field offers the other a fresh perspective: Cryptographers have powerful reasons to think that one-way functions exist, and complexity theorists have different powerful reasons to think that time-bounded Kolmogorov complexity is hard. Because of the new results, the two hypotheses bolster each other.