<p>One-way functions also featured in some discussions around the <a href="http://dx.doi.org/10.1145/800113.803628">Berman-Hartmanis isomorphism conjecture</a>.  <a href="http://dx.doi.org/10.1016/0304-3975(85)90140-9">Joseph and Young conjectured</a> 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).  <a href="http://dx.doi.org.proxy.uchicago.edu/10.1006/jcss.1997.1486">John Rogers</a> 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).</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-12T15:55:49.997Z
2010-11-12T15:55:49.997Z
Joshua Grochow
<p>Yes, a <a href="http://en.wikipedia.org/wiki/Hash_table" rel="nofollow noreferrer">hash table</a> or a hash map requires a one-way function. Also duplicate detection (see <a href="https://stackoverflow.com/q/862346/57428">this</a> and <a href="https://stackoverflow.com/q/4123818/57428">this</a>) can be done very efficiently using one-way functions. Both cases require "good" (with low chances of collision) one-way functions while <a href="https://stackoverflow.com/q/4032209/57428">cryptographic strength is usually not required</a>.</p>

CC BY-SA 2.5
2010-11-11T09:15:03.610Z
Yes, hash functions a widely used for hash-tables.
Gamlor
CC BY-SA 3.0
2011-05-11T08:56:34.493Z
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).
D.W.
CC BY-SA 2.5
2010-11-11T08:43:20.533Z
2010-11-11T08:43:20.533Z
2017-05-23T12:40:09.333Z
sharptooth
<p>There are lots of "cryptographic hardness" results (just Google this phrase) for learning problems. These are hardness results assuming that one way functions exist.</p>

CC BY-SA 2.5
2010-11-12T21:06:22.857Z
Can you give me a precise definition of "cryptographic hardness" ?
Tarek Radwan
CC BY-SA 2.5
2010-11-13T15:45:25.593Z
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.
Dana Moshkovitz
CC BY-SA 2.5
2010-11-12T19:17:40.447Z
2010-11-12T19:17:40.447Z
Dana Moshkovitz
<p>One-way functions have an application in Kolmogorov Complexity:</p>

<p>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</p>

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

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

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

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

CC BY-SA 2.5
2010-11-11T07:16:31.597Z
2010-11-11T07:16:31.597Z
Mohammad Al-Turkistany
<p>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. </p>

CC BY-SA 2.5
2010-11-11T03:05:16.367Z
2010-11-11T03:05:16.367Z
mikero
<p>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$,</p>

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

<p>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$.</p>

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

CC BY-SA 2.5
2010-11-11T09:05:03.927Z
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...
Sadeq Dousti
CC BY-SA 2.5
2010-11-11T09:23:34.963Z
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.
Jukka Suomela
CC BY-SA 2.5
2010-11-12T16:54:36.507Z
In post it is $Pr[f(A(f(x),1^n)=x]<1/p(n)$, but it needs one additional closing bracket ")".
Oleksandr Bondarenko
CC BY-SA 2.5
2010-11-12T19:33:24.970Z
@Sadeq and Jukka: This might be related to a recently fixed bug in SE: http://meta.math.stackexchange.com/questions/1115/different-behavior-in-parsing-latex-code-in-the-previewer-and-in-the-saved-post
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-13T04:04:48.853Z
@Tsuyoshi: Thanks for informative comment!
Sadeq Dousti
<cc.complexity-theory><cr.crypto-security><one-way-function>
Do "One Way Functions" have any applications outside crypto ?
Tarek Radwan
# Do "One Way Functions" have any applications outside crypto ?

(Asked by: username_0 on 2010-11-10)

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?

**Tags:** cc.complexity-theory, cr.crypto-security, one-way-function

> **Comments:**
> **username_1**: 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...  
> **username_2**: 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.  
> **username_3**: In post it is $Pr[f(A(f(x),1^n)=x]<1/p(n)$, but it needs one additional closing bracket ")".  
> **username_4**: @Sadeq and Jukka: This might be related to a recently fixed bug in SE: http://meta.math.stackexchange.com/questions/1115/different-behavior-in-parsing-latex-code-in-the-previewer-and-in-the-saved-post  
> **username_1**: @Tsuyoshi: Thanks for informative comment!  

---

## 5 answers

### Answer by username_11 on 2010-11-11. Score: 22 | Accepted answer

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.


---

### Answer by username_5 on 2010-11-12. Score: 11

One-way functions also featured in some discussions around the [Berman-Hartmanis isomorphism conjecture](http://dx.doi.org/10.1145/800113.803628). [Joseph and Young conjectured](http://dx.doi.org/10.1016/0304-3975(85)90140-9) 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](http://dx.doi.org.proxy.uchicago.edu/10.1006/jcss.1997.1486) 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.


---

### Answer by username_6 on 2010-11-11. Score: 8

Yes, a [hash table](http://en.wikipedia.org/wiki/Hash_table) or a hash map requires a one-way function. Also duplicate detection (see [this](https://stackoverflow.com/q/862346/57428) and [this](https://stackoverflow.com/q/4123818/57428)) 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](https://stackoverflow.com/q/4032209/57428).

> **Comments:**
> **username_7**: Yes, hash functions a widely used for hash-tables.  
> **username_8**: 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).  

---

### Answer by username_9 on 2010-11-12. Score: 6

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

> **Comments:**
> **username_0**: Can you give me a precise definition of "cryptographic hardness" ?  
> **username_9**: 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.  

---

### Answer by username_10 on 2010-11-11. Score: 5

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


---

