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

TitleOne-Way Functions Are Essential for Complexity Based Cryptography (Extended
Publication TypeTechnical Report
Year of Publication1989
AuthorsImpagliazzo, R., & Luby M.
Other Numbers530

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.

Bibliographic Notes

ICSI Technical Report TR-89-031

Abbreviated Authors

R. Impagliazzo and M. Luby

ICSI Publication Type

Technical Report