One-Way Functions Are Essential for Complexity Based Cryptography (Extended
Title | One-Way Functions Are Essential for Complexity Based Cryptography (Extended |
Publication Type | Technical Report |
Year of Publication | 1989 |
Authors | Impagliazzo, R., & Luby M. |
Other Numbers | 530 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-89-31.pdf |
Bibliographic Notes | ICSI Technical Report TR-89-031 |
Abbreviated Authors | R. Impagliazzo and M. Luby |
ICSI Publication Type | Technical Report |