25

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?

Anonymous
  • 4,041
  • 19
  • 43
  • 1
    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. –  Nov 07 '11 at 00:38

4 Answers4

22

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.

Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
Peter Shor
  • 24,763
  • 4
  • 93
  • 133
  • 1
    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 Nov 06 '11 at 21:23
  • 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 Nov 06 '11 at 21:44
  • 2
    @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 Nov 06 '11 at 22:10
  • I see. Your comment on Sadeq’s answer made me think that you were going to write about some very different approach. – Tsuyoshi Ito Nov 06 '11 at 22:35
  • 6
    @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 Nov 06 '11 at 22:43
  • 3
    @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 Nov 06 '11 at 22:54
  • 1
    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 Nov 07 '11 at 07:35
  • 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. – Timothy Chow Nov 09 '11 at 16:24
  • @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 Nov 09 '11 at 17:44
13

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.

Dana Moshkovitz
  • 10,979
  • 1
  • 50
  • 77
Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
  • 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 Nov 05 '11 at 23:41
  • 1
    Answer to my first question: http://dx.doi.org/10.1016/j.tcs.2007.03.013 – didest Nov 06 '11 at 00:06
  • 3
    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. – Anonymous Nov 06 '11 at 10:37
  • @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 Nov 06 '11 at 13:26
  • @Anonymous: There in fact exist exist exponential hardness assumptions for FACTORING; see for example here. 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 Nov 06 '11 at 13:35
  • @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 Nov 06 '11 at 13:37
  • 11
    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 Nov 06 '11 at 16:15
  • 1
    @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 Apr 30 '14 at 01:43
-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.

Community
  • 1
mathersjj1
  • 29
  • 2
  • 5
    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. Apr 29 '14 at 04:28
  • Read the definition of one-way function. – Kaveh Apr 29 '14 at 17:07
  • 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 Apr 30 '14 at 03:04
  • 2
    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 May 01 '14 at 01:56
-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.

Aaron Robson
  • 9
  • 2