I have read in several papers that the existence of one-way functions 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?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ I find it somewhat misleading that many papers state that the existence of one-way functions is widely believed since so far we don't have any strong argument for their existence. Writing "the existence of one-way functions is widely accepted as a plausible assumption among experts which is consistent with our experience in practice and the current state of knowledge" is more appropriate and even-handed. $\endgroup$– user7130Nov 7, 2011 at 0:38
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
9
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; 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.
answered Nov 6, 2011 at 17:40
-
1$\begingroup$ 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? $\endgroup$ Nov 6, 2011 at 21:23
-
2$\begingroup$ @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. $\endgroup$ Nov 6, 2011 at 22:10
-
6$\begingroup$ @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. $\endgroup$ Nov 6, 2011 at 22:43
-
3$\begingroup$ @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. $\endgroup$ Nov 6, 2011 at 22:54
-
4$\begingroup$ @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. $\endgroup$ Nov 9, 2011 at 16:24
$\begingroup$
$\endgroup$
8
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.
answered Nov 5, 2011 at 22:25
-
$\begingroup$ 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? $\endgroup$– didestNov 5, 2011 at 23:41
-
1$\begingroup$ Answer to my first question: dx.doi.org/10.1016/j.tcs.2007.03.013 $\endgroup$– didestNov 6, 2011 at 0:06
-
3$\begingroup$ 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 is not fair. There are many natural equivalent NP-complete problems. $\endgroup$ Nov 6, 2011 at 10:37
-
11$\begingroup$ 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. $\endgroup$ Nov 6, 2011 at 16:15
-
1$\begingroup$ @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: eprint.iacr.org/2013/400 (following eprint.iacr.org/2013/095). $\endgroup$ Apr 30, 2014 at 1:43
$\begingroup$
$\endgroup$
4
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.
-
5$\begingroup$ 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. $\endgroup$– D.W.Apr 29, 2014 at 4:28
-
-
$\begingroup$ 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". $\endgroup$ Apr 30, 2014 at 3:04
-
2$\begingroup$ 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 tour and help center for the explanation of the scope of cstheory. $\endgroup$– KavehMay 1, 2014 at 1:56
$\begingroup$
$\endgroup$
3
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.
-
4
-
3$\begingroup$ 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. $\endgroup$ Nov 7, 2011 at 0:17
-
$\begingroup$ I see, thanks for explaining the distinction. $\endgroup$ Nov 7, 2011 at 9:15