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?

$\endgroup$
  • 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$ – M.S. Dousti Nov 11 '10 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 Nov 11 '10 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 Nov 12 '10 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 Nov 12 '10 at 19:33
  • $\begingroup$ @Tsuyoshi: Thanks for informative comment! $\endgroup$ – M.S. Dousti Nov 13 '10 at 4:04
23
$\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.

$\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.

$\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.

$\endgroup$
  • $\begingroup$ Yes, hash functions a widely used for hash-tables. $\endgroup$ – Gamlor Nov 11 '10 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. May 11 '11 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.

$\endgroup$
  • 4
    $\begingroup$ Can you give me a precise definition of "cryptographic hardness" ? $\endgroup$ – Tarek Radwan Nov 12 '10 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 Nov 13 '10 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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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