Sign In

Communications of the ACM

Research Highlights

Technical Perspective: Finding Connections between One-Way Functions and Kolmogorov Complexity

one-way and don't-walk signage on a city street corner

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

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account