Re: Q: One-way functions

From: Rick Wash (rwash@citi.umich.edu)
Date: 03/30/03 

From: Rick Wash <rwash@citi.umich.edu>
Date: Sun, 30 Mar 2003 18:37:39 GMT

In article <3E872EB5.B8112511@t-online.de>, Mok-Kong Shen wrote:
>
> A presumably extremely dumb question: In AC (1996 edition)
> Schneier wrote:
>
> If we are being strictly mathematical, we have no proof
> that one-way functions exist, nor any real evidence that
> they can be constructed.
>
> Have researches in the meantime ameriolated in 'any' sense
> that picture? (Any references?) Thanks in advance.

Since then, I don't know of anything that has significantly changed in
finding "real" evidence that they can be constructed. A proof that P==NP
would pretty much say that they don't exist. A proof that P!=NP would be a
strong indication that they do exist. If a provable one-way function was
found, that would also be a proof that P!=NP (to show you how hard it is to
find one). I believe this is the kind of evidence that he is talking about.

However, there is good empirical evidence that we can construct one-way
functions. For example, consider the RSA function. As far as we can tell
right now it appears to be a one-way function. We can't prove this, but
it seems plausible. Similarly with the Discrete Log Function.

Unfortunately, nothing significant has changed since that was written.

  Rick

Relevant Pages