Publication Details
Title: One-Way Functions Are Essential for Complexity Based Cryptography (Extended
Author: R. Impagliazzo and M. Luby
Group: ICSI Technical Reports
Date: May 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-31.pdf
Overview:
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 Information:
ICSI Technical Report TR-89-031
Bibliographic Reference:
R. Impagliazzo and M. Luby. One-Way Functions Are Essential for Complexity Based Cryptography (Extended. ICSI Technical Report TR-89-031, May 1989
Author: R. Impagliazzo and M. Luby
Group: ICSI Technical Reports
Date: May 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-31.pdf
Overview:
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 Information:
ICSI Technical Report TR-89-031
Bibliographic Reference:
R. Impagliazzo and M. Luby. One-Way Functions Are Essential for Complexity Based Cryptography (Extended. ICSI Technical Report TR-89-031, May 1989