One-Way Functions Are Essential for Complexity Based Cryptography (Extended

In much of modern cryptography, the security of a protocol is based on the intractability of a problem such as factorization of randomly chosen large numbers. The problems assumed intractable all have the same form; they are based on a one-way function, i.e. one that is easy to compute but hard to invert. This is not a coincidence. We show that for many cryptographic tasks any secure protocol for the task can be converted into a one-way function, and thus any proposed protocol for these tasks is implicitly based on a one-way function. Tasks examined here are chosen to cover a spectrum of cryptographic applications: private-key encryption, identification/authentication, bit commitment and coin-flipping by telephone. Thus, unless one-way functions exist, secure protocols for these tasks are impossible.

ICSI Technical Report TR-89-031

Technical Report