<p>Here's an argument that one-way functions should be hard to invert. Suppose there is a class of 3-SAT problems with planted solutions that are hard to solve. Consider the following map:</p>

<p>$$(x, r) \rightarrow s$$</p>

<p>where $x$ is any string of bits, $r$ is a string of bits (you could use these to seed a random number generator, or you can ask for as many random bits as you need) and $s$ is a $k$-SAT problem having $x$ as a planted solution, where the random number generator determines exactly which $k$-SAT problem you choose. To invert this one-way function, you need to solve a $k$-SAT problem with a planted solution. </p>

<p>This argument shows that inverting a one-way function is as hard as solving $k$-SAT problems with planted solutions. And since $k$-SAT is an NP-complete problem, if you can figure out how to construct hard instances with planted solutions for any NP problem, you can plant solutions in $k$-SAT formulas. </p>

<p>It has not been proven that it's possible to come up with a class of NP-complete problems with planted solutions that are just as hard as arbitrary NP-complete problems (and even if this is true, it's going to be incredibly hard to prove), but people definitely know how to plant solutions in $k$-SAT problems in ways that nobody currently knows how to solve. </p>

<p>ADDED: I now realize that this connection was already given (in more detail) in <a href="http://dx.doi.org/10.1007/0-387-34799-2_23">Abadi, Allender, Broder, Feigenbaum, and Hemachandra</a>; they point out that one-way functions can give solved hard instances of SAT, and vice versa.</p>

<p>Putting it in more informal language, the non-existence of one-way functions shows that truly hard puzzles can't exist. If there is a type of puzzle where somebody can come up with both a puzzle and its solution algorithmically, then there is also a polynomial-time algorithm for finding a solution to the puzzle. This seems very counter-intuitive to me. Of course, a polynomial gap could exist; it might be the case that if creating the puzzle took $n$ steps, then solving it might take $O(n^3)$ steps. However, my intuition says that there should be a superpolynomial gap.  </p>

CC BY-SA 3.0
2011-11-06T21:23:19.897Z
Isn’t this ultimately the same argument as Sadeq’s, in the sense that both rely on some problems which no one currently knows how to solve in spite of a lot of effort?
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-06T21:44:35.767Z
The existence of random number generators (in cryptographic sense) implies the existence of OWFs. In particular, any PRG is a OWF (given the output of a PRG, it is hard to find the seed). Moreover, generating solved instance of hard problems is difficult; see http://www.springerlink.com/content/trt9vatu0u298jry/.
Sadeq Dousti
CC BY-SA 3.0
2011-11-06T22:10:34.647Z
@Sadeq: you can give the algorithm essentially all the random bits that you need for this argument; you don't really need a PRG, and certainly not a cryptographically strong one.
Peter Shor 
CC BY-SA 3.0
2011-11-06T22:35:03.653Z
I see.  Your comment on Sadeq’s answer made me think that you were going to write about some very different approach.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-06T22:43:34.497Z
@Tsuyoshi: I think that generating hard cases of NP problems with planted solutions is quite a bit more general than factoring or discrete log; for one thing, it's not known to be in BQP.
Peter Shor 
CC BY-SA 3.0
2011-11-06T22:54:57.307Z
@Tsuyoshi: I would love to see a different approach; unfortunately, I don't have one. But what this means is that truly hard puzzles can't exist; if there is a type of puzzle where somebody can come up with a puzzle and its solution algorithmically, there is also a polynomial-time algorithm for solving the puzzle. This seems very counter-intuitive to me.
Peter Shor 
CC BY-SA 3.0
2011-11-07T07:35:30.543Z
Well, you do not have to argue to me why one-way functions should exist; I already know those arguments, although I am not familiar enough with the subject either to trust them or to doubt them.  I was just confused because you wrote “there has to be a better argument […] than we know a bunch of functions that we don't know how to invert yet. I'll see if I can come up with one” as a comment to Sadeq’s answer and you then posted this answer which did not address the point of your comment.  In other words, it was not clear to me that this answer was unrelated to your comment on Sadeq’s answer.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-09T16:24:19.240Z
@Tsuyoshi: I think Peter's point is that there aren't just two or three candidates for OWFs; candidates are extremely plentiful and almost trivial to come up with.  For example if you look at the work surrounding NIST's SHA-3 competition, it seems to be "easy" to construct OWFs, and people are mostly concerned with designing superfast OWFs that still meet a very stringent notion of security.
Timothy Chow
CC BY-SA 3.0
2011-11-09T17:44:30.057Z
@TimothyChow: I did not interpret Peter’s comment on Sadeq’s answer that way because “bunch of” sounded like many more than “two or three.”  But if you disagree, I am fine with it.  (If you reply, I will probably read the reply, but I will not respond because I do not want to continue this discussion, at least in this thread.)
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-06T17:40:10.430Z
2011-11-07T16:20:22.340Z
2011-11-07T16:20:22.340Z
Peter Shor 
<p>I'll give a short answer: The existence of seemingly-hard problems, such as FACTORING or DISCRETE LOG made theorists believe that OWF exist. In particular, they tried for decades (since 1970s) to find efficient (probabilistic polynomial-time) algorithms for such problems, but no attempt succeeded. This reasoning is very similar to why most researchers believe that P ≠ NP.</p>

CC BY-SA 3.0
2011-11-05T23:41:03.493Z
What I don't like about that belief is that both problems are in BQP, so if they are indeed one-way and quantum computers turn out to be practical, then the definition of one-way function should be changed (to resist quantum poly-time adversaries instead of just randomized). Do you know any candidates for strong one-way functions in that sense?
Are there candidates of the kind of strong one-way functions that assume Razborov-Rudich in their theorem?
didest
CC BY-SA 3.0
2011-11-06T00:06:36.033Z
Answer to my first question: http://dx.doi.org/10.1016/j.tcs.2007.03.013
didest
CC BY-SA 3.0
2011-11-06T10:37:48.557Z
I.e. we don't have any argument for this other than that no one has broken these problems yet. That is a very week argument. Along the same lines, we would believe in hardness of anything we haven't solved yet. We could say that it is widely believe that factoring is not in $DTIME(\exp(n^{1/4}))$ but I haven't seen anyone claiming that. There must be some other reason for widely believing in the existence of OWFs.  Comparison with [P vs NP](http://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP) is not fair. There are many natural equivalent NP-complete problems.
Anonymous
CC BY-SA 3.0
2011-11-06T13:26:28.273Z
@Diego: My answer assumed that the underlying model of computation is that of Turing machines. But for post-quantum cryptography, natural one-way functions (conjectured) exists, such as lattice problems.
Sadeq Dousti
CC BY-SA 3.0
2011-11-06T13:35:52.693Z
@Anonymous: There in fact exist exist exponential hardness assumptions for FACTORING; see for example [here](http://books.google.com/books?id=m-9Zj-e-HDsC&pg=PA93&lpg=PA93&dq=factoring+exponential+hardness). But they are not very common since we haven't even established simpler, super-polynomial hardness yet. And well, I accept that the comparison with P vs. NP is not fair, but it was just a "metaphor". For the same reason you mentioned, there is a belief that it might be the case where P ≠ NP but OWFs do not exist (See http://cstheory.stackexchange.com/q/1026/873).
Sadeq Dousti
CC BY-SA 3.0
2011-11-06T13:37:39.167Z
@Anonymous: (Cont'd) On the other hands, there exists so many hardness assumptions (from which one can derive OWFs), that it seems to be very realistic to assume that OWFs exist. See http://cstheory.stackexchange.com/q/5961/873 for more info.
Sadeq Dousti
CC BY-SA 3.0
2011-11-06T16:15:24.390Z
There has to be a better argument for why one-way functions exist than that we know a bunch of functions that we don't know how to invert yet. I'll see if I can come up with one.
Peter Shor 
CC BY-SA 3.0
2014-04-30T01:43:12.443Z
@Anonymous: re: "widely believe [sic] that factoring is not in $DTIME(exp(n^{1/4}))$" you might check out the recent improvements in discrete log: http://eprint.iacr.org/2013/400 (following http://eprint.iacr.org/2013/095).
Joshua Grochow
CC BY-SA 3.0
2011-11-05T22:25:25.663Z
2011-11-06T11:12:07.757Z
2011-11-06T11:12:07.757Z
Sadeq Dousti
<p>Sasho's argument relies on the eternal P=NP problem for which no consensus currently exists.</p>

<p>However, if we follow C. Shannon's cryptanalysis of the one-time pad, declassified in 1947, that is: there is no mathematically secure encryption algorithm other than the one time pad. His argument is based on the idea that, if we have a truly random sequence of numbers $r_1,r_2,r_3,\ldots,r_n$ and for some sequence to encrypt, $s_1,s_2,s_3,\ldots,s_n$, we encrypt as follows:</p>

<p>$f(r_i,s_i) = r_i \oplus s_i = c_i$</p>

<p>If the sequence is truly random, we would try to compute $f^{-1}(r_i,s_i)$ and the result would then be that all sequences are equiprobable.</p>

<p>We could mimic Shannon's result for one-way functions.</p>

<p>The function is the map $f:\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}$ and the inverse function is the map $f:\mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$.</p>

<p>The catch is that we do not know if there exists truly random numbers as the question is equivalent to Einstein's comment on "God does not play dices".</p>

<p>However, for all purposes, a random number generator based on a physical process is considered random enough by experts.</p>

<p>This said, the moment we are trying to reverse $(c_i,r_i)$, that is, the random numbers are no longer secret, reversal is trivial.</p>

<p>Furthermore, this one-way function does not have the nice properties of most cryptographically-secure hashing functions such as collision-resistance. Moreover, we have the situation that $f(r_i,s_k)\neq f(r_j,s_k)$. This means that a same value $s_k$ gets hashed to two different values. And $f(r_i,s_i) = f(r_j,s_j)$ is common.</p>

CC BY-SA 3.0
2014-04-29T04:28:33.340Z
Shannon's result is about information-theoretic security (where the adversary has unbounded computation power).  That's not what the question is asking about.  The question is asking about one-way functions with computational security (where the adversary is limited to polynomial-time computations).  Consequently, Shannon-style arguments don't say anything about whether there exist computationally secure one-way functions.
D.W.
CC BY-SA 3.0
2014-04-29T17:07:34.547Z
Read the definition of [one-way function](http://en.wikipedia.org/wiki/One-way_function).
Kaveh
CC BY-SA 3.0
2014-04-30T03:04:34.460Z
Ker-I Ko defines a one-way function with respect to the P=NP problem and polynomial isomorphism. More specifically, if one-way functions exist, then Cook's conjecture about NP-completeness, i.e. isomorphism between NP-complete sets, does not hold. The interest of positing things from the perspective of information entropy is to show that the isomorphism class of mathematically definable functions is only secure (irreversible) if a random set can be defined. I am not certain of Shannon's input on intractability and the use of the expression "mathematically secure".
mathersjj1
CC BY-SA 3.0
2014-05-01T01:56:59.477Z
cstheory is not a discussion forum or a personal blog, it is a Q&A site. Your post is not an answer to the question asked about one-way functions (as defined in the link). Check [about] and [help/on-topic] for the explanation of the scope of cstheory.
Kaveh
CC BY-SA 3.0
2014-04-29T01:40:49.110Z
2014-05-18T06:25:31.663Z
2014-05-18T06:25:31.663Z
mathersjj1
<p>Would it be as easy as suggesting for example the Sine function?</p>

<p>Because for a given input and output the input can be increased or decreased by 360 degrees (or 2 pi if you're into radians) it is many-to-one, so you can never be sure which input you had?</p>

<p>Do tell me if I've misunderstood the question though.</p>

CC BY-SA 3.0
2011-11-07T00:03:59.873Z
Check [the definition](http://en.wikipedia.org/wiki/One-way_function).
Kaveh
CC BY-SA 3.0
2011-11-07T00:17:19.603Z
You're mixing two concepts: One-way functions, and uninvertible functions. While the Sine function is uninvertible, it's not one way. In particular, you can always come up with *a* preimage (to whatever precision you like), even if it is not *the* preimage.
Sadeq Dousti
CC BY-SA 3.0
2011-11-07T09:15:40.573Z
I see, thanks for explaining the distinction.
Aaron Robson
CC BY-SA 3.0
2011-11-06T23:50:51.710Z
2011-11-06T23:50:51.710Z
Aaron Robson
<p>I have read in several papers that the existence of <a href="http://en.wikipedia.org/wiki/One-way_function">one-way functions</a> is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-way functions?</p>

<cc.complexity-theory><cr.crypto-security><big-picture><one-way-function>
Arguments for existence of one-way functions
Anonymous
# Arguments for existence of one-way functions

(Asked by: username_0 on 2011-11-05)

I have read in several papers that the existence of [one-way functions](http://en.wikipedia.org/wiki/One-way_function) is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-way functions?

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


---

## 4 answers

### Answer by username_1 on 2011-11-06. Score: 23

Here's an argument that one-way functions should be hard to invert. Suppose there is a class of 3-SAT problems with planted solutions that are hard to solve. Consider the following map:

$$(x, r) \rightarrow s$$

where $x$ is any string of bits, $r$ is a string of bits (you could use these to seed a random number generator, or you can ask for as many random bits as you need) and $s$ is a $k$-SAT problem having $x$ as a planted solution, where the random number generator determines exactly which $k$-SAT problem you choose. To invert this one-way function, you need to solve a $k$-SAT problem with a planted solution.

This argument shows that inverting a one-way function is as hard as solving $k$-SAT problems with planted solutions. And since $k$-SAT is an NP-complete problem, if you can figure out how to construct hard instances with planted solutions for any NP problem, you can plant solutions in $k$-SAT formulas.

It has not been proven that it's possible to come up with a class of NP-complete problems with planted solutions that are just as hard as arbitrary NP-complete problems (and even if this is true, it's going to be incredibly hard to prove), but people definitely know how to plant solutions in $k$-SAT problems in ways that nobody currently knows how to solve.

ADDED: I now realize that this connection was already given (in more detail) in [Abadi, Allender, Broder, Feigenbaum, and Hemachandra](http://dx.doi.org/10.1007/0-387-34799-2_23); they point out that one-way functions can give solved hard instances of SAT, and vice versa.

Putting it in more informal language, the non-existence of one-way functions shows that truly hard puzzles can't exist. If there is a type of puzzle where somebody can come up with both a puzzle and its solution algorithmically, then there is also a polynomial-time algorithm for finding a solution to the puzzle. This seems very counter-intuitive to me. Of course, a polynomial gap could exist; it might be the case that if creating the puzzle took $n$ steps, then solving it might take $O(n^3)$ steps. However, my intuition says that there should be a superpolynomial gap.

> **Comments:**
> **username_2**: Isn’t this ultimately the same argument as Sadeq’s, in the sense that both rely on some problems which no one currently knows how to solve in spite of a lot of effort?  
> **username_3**: The existence of random number generators (in cryptographic sense) implies the existence of OWFs. In particular, any PRG is a OWF (given the output of a PRG, it is hard to find the seed). Moreover, generating solved instance of hard problems is difficult; see http://www.springerlink.com/content/trt9vatu0u298jry/.  
> **username_1**: @Sadeq: you can give the algorithm essentially all the random bits that you need for this argument; you don't really need a PRG, and certainly not a cryptographically strong one.  
> **username_2**: I see.  Your comment on Sadeq’s answer made me think that you were going to write about some very different approach.  
> **username_1**: @Tsuyoshi: I think that generating hard cases of NP problems with planted solutions is quite a bit more general than factoring or discrete log; for one thing, it's not known to be in BQP.  
> **username_1**: @Tsuyoshi: I would love to see a different approach; unfortunately, I don't have one. But what this means is that truly hard puzzles can't exist; if there is a type of puzzle where somebody can come up with a puzzle and its solution algorithmically, there is also a polynomial-time algorithm for solving the puzzle. This seems very counter-intuitive to me.  
> **username_2**: Well, you do not have to argue to me why one-way functions should exist; I already know those arguments, although I am not familiar enough with the subject either to trust them or to doubt them.  I was just confused because you wrote “there has to be a better argument […] than we know a bunch of functions that we don't know how to invert yet. I'll see if I can come up with one” as a comment to Sadeq’s answer and you then posted this answer which did not address the point of your comment.  In other words, it was not clear to me that this answer was unrelated to your comment on Sadeq’s answer.  
> **username_4**: @Tsuyoshi: I think Peter's point is that there aren't just two or three candidates for OWFs; candidates are extremely plentiful and almost trivial to come up with.  For example if you look at the work surrounding NIST's SHA-3 competition, it seems to be "easy" to construct OWFs, and people are mostly concerned with designing superfast OWFs that still meet a very stringent notion of security.  
> **username_2**: @TimothyChow: I did not interpret Peter’s comment on Sadeq’s answer that way because “bunch of” sounded like many more than “two or three.”  But if you disagree, I am fine with it.  (If you reply, I will probably read the reply, but I will not respond because I do not want to continue this discussion, at least in this thread.)  

---

### Answer by username_3 on 2011-11-05. Score: 14

I'll give a short answer: The existence of seemingly-hard problems, such as FACTORING or DISCRETE LOG made theorists believe that OWF exist. In particular, they tried for decades (since 1970s) to find efficient (probabilistic polynomial-time) algorithms for such problems, but no attempt succeeded. This reasoning is very similar to why most researchers believe that P ≠ NP.

> **Comments:**
> **username_5**: What I don't like about that belief is that both problems are in BQP, so if they are indeed one-way and quantum computers turn out to be practical, then the definition of one-way function should be changed (to resist quantum poly-time adversaries instead of just randomized). Do you know any candidates for strong one-way functions in that sense? Are there candidates of the kind of strong one-way functions that assume Razborov-Rudich in their theorem?  
> **username_5**: Answer to my first question: http://dx.doi.org/10.1016/j.tcs.2007.03.013  
> **username_0**: I.e. we don't have any argument for this other than that no one has broken these problems yet. That is a very week argument. Along the same lines, we would believe in hardness of anything we haven't solved yet. We could say that it is widely believe that factoring is not in $DTIME(\exp(n^{1/4}))$ but I haven't seen anyone claiming that. There must be some other reason for widely believing in the existence of OWFs.  Comparison with [P vs NP](http://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP) is not fair. There are many natural equivalent NP-complete problems.  
> **username_3**: @Diego: My answer assumed that the underlying model of computation is that of Turing machines. But for post-quantum cryptography, natural one-way functions (conjectured) exists, such as lattice problems.  
> **username_3**: @username_0: There in fact exist exist exponential hardness assumptions for FACTORING; see for example [here](http://books.google.com/books?id=m-9Zj-e-HDsC&pg=PA93&lpg=PA93&dq=factoring+exponential+hardness). But they are not very common since we haven't even established simpler, super-polynomial hardness yet. And well, I accept that the comparison with P vs. NP is not fair, but it was just a "metaphor". For the same reason you mentioned, there is a belief that it might be the case where P ≠ NP but OWFs do not exist (See http://cstheory.stackexchange.com/q/1026/873).  
> **username_3**: @username_0: (Cont'd) On the other hands, there exists so many hardness assumptions (from which one can derive OWFs), that it seems to be very realistic to assume that OWFs exist. See http://cstheory.stackexchange.com/q/5961/873 for more info.  
> **username_1**: There has to be a better argument for why one-way functions exist than that we know a bunch of functions that we don't know how to invert yet. I'll see if I can come up with one.  
> **username_6**: @username_0: re: "widely believe [sic] that factoring is not in $DTIME(exp(n^{1/4}))$" you might check out the recent improvements in discrete log: http://eprint.iacr.org/2013/400 (following http://eprint.iacr.org/2013/095).  

---

### Answer by username_7 on 2014-04-29. Score: -5

Sasho's argument relies on the eternal P=NP problem for which no consensus currently exists.

However, if we follow C. Shannon's cryptanalysis of the one-time pad, declassified in 1947, that is: there is no mathematically secure encryption algorithm other than the one time pad. His argument is based on the idea that, if we have a truly random sequence of numbers $r\_1,r\_2,r\_3,\ldots,r\_n$ and for some sequence to encrypt, $s\_1,s\_2,s\_3,\ldots,s\_n$, we encrypt as follows:

$f(r\_i,s\_i) = r\_i \oplus s\_i = c\_i$

If the sequence is truly random, we would try to compute $f^{-1}(r\_i,s\_i)$ and the result would then be that all sequences are equiprobable.

We could mimic Shannon's result for one-way functions.

The function is the map $f:\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}$ and the inverse function is the map $f:\mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$.

The catch is that we do not know if there exists truly random numbers as the question is equivalent to Einstein's comment on "God does not play dices".

However, for all purposes, a random number generator based on a physical process is considered random enough by experts.

This said, the moment we are trying to reverse $(c\_i,r\_i)$, that is, the random numbers are no longer secret, reversal is trivial.

Furthermore, this one-way function does not have the nice properties of most cryptographically-secure hashing functions such as collision-resistance. Moreover, we have the situation that $f(r\_i,s\_k)\neq f(r\_j,s\_k)$. This means that a same value $s\_k$ gets hashed to two different values. And $f(r\_i,s\_i) = f(r\_j,s\_j)$ is common.

> **Comments:**
> **username_8**: Shannon's result is about information-theoretic security (where the adversary has unbounded computation power).  That's not what the question is asking about.  The question is asking about one-way functions with computational security (where the adversary is limited to polynomial-time computations).  Consequently, Shannon-style arguments don't say anything about whether there exist computationally secure one-way functions.  
> **username_9**: Read the definition of [one-way function](http://en.wikipedia.org/wiki/One-way_function).  
> **username_7**: Ker-I Ko defines a one-way function with respect to the P=NP problem and polynomial isomorphism. More specifically, if one-way functions exist, then Cook's conjecture about NP-completeness, i.e. isomorphism between NP-complete sets, does not hold. The interest of positing things from the perspective of information entropy is to show that the isomorphism class of mathematically definable functions is only secure (irreversible) if a random set can be defined. I am not certain of Shannon's input on intractability and the use of the expression "mathematically secure".  
> **username_9**: cstheory is not a discussion forum or a personal blog, it is a Q&A site. Your post is not an answer to the question asked about one-way functions (as defined in the link). Check [about] and [help/on-topic] for the explanation of the scope of cstheory.  

---

### Answer by username_10 on 2011-11-06. Score: -6

Would it be as easy as suggesting for example the Sine function?

Because for a given input and output the input can be increased or decreased by 360 degrees (or 2 pi if you're into radians) it is many-to-one, so you can never be sure which input you had?

Do tell me if I've misunderstood the question though.

> **Comments:**
> **username_9**: Check [the definition](http://en.wikipedia.org/wiki/One-way_function).  
> **username_3**: You're mixing two concepts: One-way functions, and uninvertible functions. While the Sine function is uninvertible, it's not one way. In particular, you can always come up with *a* preimage (to whatever precision you like), even if it is not *the* preimage.  
> **username_10**: I see, thanks for explaining the distinction.  

---

