Communications of the ACM
Technical Perspective: Finding Connections between One-Way Functions and Kolmogorov Complexity
Credit: Shutterstock
Cryptography requires "useful" sources of computational hardness for most of its constructs. For example, in the classic setting of encryption schemes, decryption should be easy when given an appropriate decryption key, while it must be infeasible without it. Fortunately, the theory of computational complexity generously provides a wide variety of sources of computational hardness, but which ones may be useful for cryptography?
The long-celebrated interplay between cryptography and computational complexity has been challenged constantly with understanding what "useful" hardness means, where it may be found, and how it may be utilized. This has led the cryptography community to embark on an exciting journey initiated by the pioneering work of Whitfield Diffie and Martin Hellman back in 1976. One of the most instrumental early contributions of this fruitful journey was the introduction of an extremely modest cryptographic primitive referred to as a one-way function—a function that is easy to evaluate but hard to invert. The modest nature of one-way functions turned out to serve as a "minimal" form of useful hardness in the sense that the existence of nearly any cryptographic construct implies that of a one-way function. Despite their modest nature, a significant effort over the years showed that one-way functions are in fact sufficient for many of the most central cryptographic tasks. Specifically, one-way functions suffice for nearly all private-key primitives (for example, private-key encryption schemes and signature schemes).
No entries found