Limits on the Provable Consequences of One-way Functions

Steven Rudich

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-88-468

, 1988

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-468.pdf

We present strong evidence that the implication, "if one-way permutations exist, then secure secret key agreement is possible", is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model. We consider a world where all parties have access to a black box for a randomly selected permutation. Being totally random, this permutation will be strongly one-way in a provable, information-theoretic way. We show that, if P = NP, no protocol for secret key agreement is secure in such a setting. Thus, to prove that a secret key agreement protocol which uses a one-way permutation as a black box is secure is as hard as proving P does not equal NP. We also obtain, as a corollary, that there is an oracle relative to which the implication is false, i.e., there is a one-way permutation, yet secret-exchange is impossible. Thus, no technique which relativizes can prove that secret exchange can be based on any one-way permutation. Furthermore, we show that if a certain combinatorial conjecture is true, then there is similar evidence to show that a one-way permutation can't be constructed from a one-way function. Our results present a general framework for proving statements of the form, "Cryptographic application X is not likely possible based solely on complexity assumption Y".

Advisors: Manuel Blum

BibTeX citation:

@phdthesis{Rudich:CSD-88-468,
    Author= {Rudich, Steven},
    Title= {Limits on the Provable Consequences of One-way Functions},
    School= {EECS Department, University of California, Berkeley},
    Year= {1988},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6060.html},
    Number= {UCB/CSD-88-468},
    Abstract= {We present strong evidence that the implication, "if one-way permutations exist, then secure secret key agreement is possible", is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model. We consider a world where all parties have access to a black box for a randomly selected permutation. Being totally random, this permutation will be strongly one-way in a provable, information-theoretic way. We show that, if <i>P</i> = <i>NP</i>, no protocol for secret key agreement is secure in such a setting. Thus, to prove that a secret key agreement protocol which uses a one-way permutation as a black box is secure is as hard as proving <i>P</i> does not equal <i>NP</i>. We also obtain, as a corollary, that there is an oracle relative to which the implication is false, i.e., there is a one-way permutation, yet secret-exchange is impossible. Thus, no technique which relativizes can prove that secret exchange can be based on any one-way permutation. Furthermore, we show that if a certain combinatorial conjecture is true, then there is similar evidence to show that a one-way permutation can't be constructed from a one-way function.   <p>Our results present a general framework for proving statements of the form, "Cryptographic application <i>X</i> is not likely possible based solely on complexity assumption <i>Y</i>".},
}

EndNote citation:

%0 Thesis
%A Rudich, Steven 
%T Limits on the Provable Consequences of One-way Functions
%I EECS Department, University of California, Berkeley
%D 1988
%@ UCB/CSD-88-468
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6060.html
%F Rudich:CSD-88-468