16
$\begingroup$

A function $f \colon \{0, 1\}^* \to \{0, 1\}^*$ is one-way if $f$ can be computed by a polynomial time algorithm, but for every randomized polynomial time algorithm $A$,

$\Pr[f(A(f(x))) = f(x)] < 1/p(n)$

for every polynomial $p(n)$ and sufficiently large $n$, assuming that $x$ is chosen uniformly from $\{ 0, 1 \}^n$. The probability is taken over the choice of $x$ and the randomness of $A$.

So... do "One Way Functions" have any applications outside cryptography? If yes, what are they?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I corrected formulas to LaTeX form, but there seems to be a glitch in MathJax, since it previews equations correctly, but shows the error `Misplaced \`. I think it will be corrected soon... $\endgroup$
    – Sadeq Dousti
    Commented Nov 11, 2010 at 9:05
  • 1
    $\begingroup$ To me this looks more like a bug in SE. For some reason, it doesn't seem to recognise a double-\ as an escape sequence that should output a single \, which would then be processed by MathJax. $\endgroup$
    – Jukka Suomela
    Commented Nov 11, 2010 at 9:23
  • 2
    $\begingroup$ In post it is $Pr[f(A(f(x),1^n)=x]<1/p(n)$, but it needs one additional closing bracket ")". $\endgroup$
    – Oleksandr Bondarenko
    Commented Nov 12, 2010 at 16:54
  • 2
    $\begingroup$ @Sadeq and Jukka: This might be related to a recently fixed bug in SE: meta.math.stackexchange.com/questions/1115/… $\endgroup$
    – Tsuyoshi Ito
    Commented Nov 12, 2010 at 19:33
  • $\begingroup$ @Tsuyoshi: Thanks for informative comment! $\endgroup$
    – Sadeq Dousti
    Commented Nov 13, 2010 at 4:04

5 Answers 5

Reset to default
22
$\begingroup$

One-way functions show up crucially in the Razborov-Rudich natural proofs result. I wouldn't consider circuit lower bounds as part of "cryptography", so maybe this fits your criteria.

Improve this answer
$\endgroup$
11
$\begingroup$

One-way functions also featured in some discussions around the Berman-Hartmanis isomorphism conjecture. Joseph and Young conjectured that if one-way functions existed then the isomorphism conjecture fails (one-way against deterministic adversaries, not probabilistic ones, but hopefully that's close enough for the purposes of this question). John Rogers gave a relativized world where the Joseph-Young conjecture failed (that is, where one-way functions exist but the isomorphism conjecture holds). But as far as I know the JY conjecture is still one of the main pieces of technical evidence that lead people to think the Isomorphism Conjecture is false (if they do think that).

The essence of the idea of Joseph and Young is that if $f$ is a one-way function, then $f(SAT)$ is $NP$-complete but "shouldn't" be isomorphic to SAT.

Improve this answer
$\endgroup$
8
$\begingroup$

Yes, a hash table or a hash map requires a one-way function. Also duplicate detection (see this and this) can be done very efficiently using one-way functions. Both cases require "good" (with low chances of collision) one-way functions while cryptographic strength is usually not required.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, hash functions a widely used for hash-tables. $\endgroup$
    – Gamlor
    Commented Nov 11, 2010 at 9:15
  • 2
    $\begingroup$ your answer is not correct. What is required for duplicate detection is collision-resistance, which is not the same as being one-way. See the definition in the original question for a careful definition of one-way. Sometimes people loosely use the phrase "one-way hash" as a synonym for cryptographic hash function, but that is highly misleading, as in many applications it is not the "one-way" property that is important, but rather collision-resistance (as in duplicate detection) or behavior like a random oracle (as in hashing). $\endgroup$
    – D.W.
    Commented May 11, 2011 at 8:56
6
$\begingroup$

There are lots of "cryptographic hardness" results (just Google this phrase) for learning problems. These are hardness results assuming that one way functions exist.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Can you give me a precise definition of "cryptographic hardness" ? $\endgroup$
    – Tarek Radwan
    Commented Nov 12, 2010 at 21:06
  • 1
    $\begingroup$ Standard hardness results assume that P does not equal NP; if this the case, then the problem takes super-polynomial time. The "cryptographic hardness" results assume something stronger: that one way functions exist. This assumption implies (and is stronger than) average-case hardness of some problems. $\endgroup$
    – Dana Moshkovitz
    Commented Nov 13, 2010 at 15:45
5
$\begingroup$

One-way functions have an application in Kolmogorov Complexity:

The symmetry of information theorem states that the information contained in a string $x$ about a string $y$ is symmetric up to a logarithmic additive error. Similarly, The polynomial-time bounded symmetry of information conjecture states that

$K^q(x, y) = K^q(x) + K^q(y|x) + O(\log n)$ for any polynomial $q$

If one-way functions exist, then the polynomial-time bounded symmetry of information conjecture is false.

L. Longpre and S. Mocas. Symmetry of information and one-way functions. Information processing Letters, 46(2):95{100, 1993

L. Longpre and O. Watanabe. On symmetry of information and polynomial time invertibility. Information and Computation, 121(1):14{22, 1995

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.