One-Way Functions

Having introduced semantic security, the question remains whether computationally indistinguishable encryption schemes exit. A very important theorem states that such encryption schemes do exist, if and only if one-way functions (OWF) exist. This is pretty remarkable, because almost everything in cryptography is based on one-way functions. One can say that OWF is one of the most basic building blocks, a.k.a. a cryptographic primitive. In this crypto bite we'll introduce two kinds of OWF: (strong) one-way functions, and weak one-way functions. We'll see that strong one-way functions exist if and only if weak one-way functions exist.

Unfortunately, as of this writing, we don't know whether OWFs exist at all! For if they did, this would imply that \(\mathcal{P} \ne \mathcal{NP}\), answering the hardest open problem in Complexity Theory. Because we don't know whether OWFs exist, the best we can do is to define candidate one-way functions. These are functions that are based on mathematical problems that are conjectured to be hard (intractable), like e.g. the factoring problem, the discrete logarithm problem (DLP), the subset sum problem, and so on. When using such candidate functions, we should always keep in mind that our constructions will break down if someone solved the underlying mathematical problem.

Strong One-Way Functions

Informally, a (strong) one-way function (OWF) is a function that is easy to compute, but that is hard to invert. More precisely, given an OWF \(f\), the image \(f(x)\) can be efficiently computed by a polynomial time algorithm, but given \(f(x)\), no ppt algorithm exists which can find a preimage \(x' = f^{-1}(f(x))\) with more than negligible probability. Note that we don't require that \(x' = x\): finding any preimage would be sufficient, i.e. OWF are not necessarily bijective (but can be). The formal definition is thus[FOC, Volume 1, Definition 2.2.1 (Strong One-Way Functions)]:

Definition (Strong One-Way Function): A function \(f \colon \{0,1\}^* \rightarrow \{0,1\}^*\) is called (strongly) one-way, if the following two conditions hold:

  1. Easy to compute: There exists a (deterministic) polynomial time algorithm \(A\) such that on input \(x\), algorithm \(A\) outputs \(f(x)\) (i.e., \(A(x) = f(x)\)).
  2. Hard to invert: For every probabilistic polynomial time algorithm \(A'\), for every positive polynomial \(p(.)\), and for all sufficiently large \(n\)'s,
    \[ \operatorname{Pr}[A'(f(U_n), 1^n) \in f^{-1}(f(U_n))] \lt \frac{1}{p(n)} \]

As usual, \(U_n\) denotes a random variable uniformly distributed over \(\{0,1\}^n\). This means that for every \(\alpha \in \{0,1\}^n\), we have \(\operatorname{Pr}[U_n = \alpha] = 2^{-n}\). Note that if the same random variable is reused in such an expression (as is the case with \(U_n\) above), it refers to the same event/value drawn from that random variable.

An equivalent formulation for the hard-to-invert probability condition is:

\[ \operatorname{Pr}_{\substack{x \in \{0,1\}^n \\ \text{coin tosses of} A'}}[A'(f(x)) = x' \text{such that} f(x) = f(x') ] \lt \frac{1}{p(n)} \]

In this definiton, the auxillary input \(1^n\) is the security parameter.

Note that we allow ppt inverter algorithms to succeed with negligible probability.

Inconsistency? In the advanced lecture below, Shafi Goldwasser defines an OWF the same way, but allows for the algorithm \(A\) in the "easy" direction to be probabilistic. This is not the case in [FOC], where the easy direction is deterministic. Discuss.

Example

Consider the function \(f(x,y) = xy\), where \(|xy| = k\). Is this a good candidate OWF?

This is an abuse of notation, since \(x\), und \(y\) are natural numbers in \(\mathbb N\), while the formal definition of OWF requires strings in \(\{0,1\}^*\) as input and output arguments. To encode the output argument, we can e.g. use binary notation, i.e. base 2, to convert a natural number to a string. To encode both input arguments, we use the usual trick in Computability: we encode both \(x\) and \(y\) as a single string \(\langle x,y \rangle\). How? It doesn't matter in this crypto bite. Another abuse of notation is \(|xy| = k\). By this, we mean than the output \(xy\) of \(f\), encoded as a (binary) string, has length \(k\) bits.

Of course, \(f(x,y)\) is easy to compute. But what about hardness to invert? For most of the inputs of length \(k\), this function is easy to invert! In particular, there is a ppt algorithm \(A'\) that will succeed with probability \(\frac{3}{4}\) for uniformly sampled random inputs: define \(A'(xy) := (2,z/2)\) if \(z\) is even, and \(0\) otherwise. [Shafi's lecture at 53:00].

So \(f\) doesn't satisfy the definition of an OWF, which requires than no \(A'\) succeeds with probability more than \(1/2 + \operatorname{negl}(n)\).

But if we restrict the input of \(f\) to prime numbers (i.e. that \(f(p,q) = pq\) for \(p \in \mathbb P\) and \(q \in \mathbb P\)), then there is still hope. The best currently available inverter uses the General Number Field Sieve (GNFS), which still can't achieve polynomial time to factorize the product of two primes. However, we can't rule out that one day, such an efficient ppt inverter will be found. For example, using quantum computers, Shor's algorithm[S94] dramatically shortens this task.

Weak One-Way Functions

The previous example showed that some functions may not be candidates for (strong) OWF on all inputs, but that if we restrict the input to some subset, we may still obtain OWFs. In the case of multiplication of two natural numbers in \(\mathbb N\), we didn't have an OWF candidate. But the multiplication of two prime numbers in \(\mathbb P\) is as of this writing very well such an OWF candidate.

In this particular case, the subset of "hard input" was easy to determine: there exist an efficient deterministic polynomial time primality test which don't turn the candidate function into something non-polynomial when it is used as a subroutine, e.g. the AKS primality test due to Manindra Agrawal, Neeraj Kayal, Nitin Saxena[AKS04].

But in general, the subset of "hard inputs" isn't known, i.e. we can't efficiently recognize such "hard inputs". But can we still use \(f\) somehow?

This motivates the definition of weak one-way functions

  • for which there is a "hard-core" fraction of inputs ("hard inputs"),
  • but we don't know in advance who/what they are

For weak one-way functions, we will see how to "squeeze out" the hardness.

The formal definition of a weak one-way function is[FOC, Volume 1, Definition 2.2.2 (Weak One-Way Functions)]:

Definition (Weak One-Way Functions): A function \(f \colon \{0,1\}^* \rightarrow \{0,1\}^*\) is called weakly one-way if the following two conditions hold:

  1. Easy to compute: There exists a (deterministic) polynomial time algorithm \(A\) such that on input \(x\), algorithm \(A\) outputs \(f(x)\) (i.e., \(A(x) = f(x)\)).
  2. Slightly hard to invert: There exists a polynomial \(p(.)\) such that for every probabilistic polynomial-time algorithm \(A'\) and for all sufficiently large \(n\)'s,
    \[ \operatorname{Pr}[A'(f(U_n), 1^n) \notin f^{-1}(f(U_n))] \gt \frac{1}{p(n)} \]

An equivalent formulation for the slightly-hard-to-invert probability condition is

\[ \operatorname{Pr}_{\substack{x \in \{0,1\}^n \\ \text{coin tosses of} A'}}[A'(f(x)) \ne x' \text{such that} f(x) = f(x') ] \gt \frac{1}{p(n)} \]

Important! The order of the quantifiers matter! There exists a single polynomial \(p(.)\), such that \(1 / p(n)\) lower-bounds the failure probability of all ppt algorithms trying to invert \(f\) on \(f(U_n)\).

Inconsistency? In the advanced lecture below, Shafi Goldwasser defines a weak OWF the same way, but allows for the algorithm \(A\) in the "easy" direction to be probabilistic. This is not the case in [FOC], where the easy direction is deterministic. Discuss.

How can we interpret this definition? Intuitively, there is a hard-core polynomial fraction \(1 / p(n)\) of inputs on which it is always hard to invert, no matter what inverter algorithm \(A'\) we may come up with. Or, in other words: there are "enough" inputs that are "hard inputs", i.e. that are hard to invert. We don't know which inputs are hard, but some of them are.

Note that the subset of hard-to-invert inputs to the inverter, may be very small, compared to the set of all possible images. For example, if that subset were \(n^{100}\) elements, compared to the set of all possible \(2^n\) elements (if \(f\) were bijective), the fraction of "hard inputs" is the very small \(\frac{n^{100}}{2^n}\).

Still, weak one-way functions contain "enough" hardness inside, that we can turn them into (strong) one-way functions. In other words, we can "extract the hardness" of weak one-way functions and use that hardness to create a strong one-way function... even if we don't know what the hard-core of inputs to the weak one-way function was.

Exercise*: If one-way functions exist at all, does a weak one-way function exist, that is not strong one-way? In other words, did we define with weak one-wayness a different notion than (strong) one-wayness, and does this notion contain instances, i.e. functions? Hint: transform a strong one-way function \(f\) into another function \(g(y, x) = (y, f(x))\) if \(y\) starts with \(\operatorname{log}_2 |x|\) zeroes, otherwise \(g(y, x) = (y, x)\). Show that \(g\) is weakly one-way. Answer: [FOC, Volume 1, Proposition 2.3.1].

Turning Weak OWF into Strong OWF

As we've already said in the introduction to this crypto bite, there is a theorem[FOC, Volume 1, Theorem 2.3.2] which states that (strong) one-way functions exist if and only if weak one-way functions exist:

Theorem: Weak one-way functions exist if and only if strong one-way functions exist.

Proof: First of all, strong one-way functions are always weak one-way. For the  other direction, we can transform a weak one-way function into a strong one-way function using Amplification (see [FOC, Volume 1, Section 2.3.1: Proof of Theorem 2.3.2]. See also Section 2.3.3 Discussion regarding the used reducibility arguments). \(\Box\)

The corollary is that whenever we assume the existence of one-way functions, there is no need to specify whether we refer to weak or strong ones. Given a weak one-way function, we can transform it into a strong one-way function using the method show in the proof above. But that transformation is not practical, because it is not efficient enough. Another transformation that is much more efficient uses one-way permutations (OWP), which are bijective OWFs [FOC, Volume 1, Section 2.3.3.3].

Shafi's construction

In the lecture below, Shafi shows this example construction to transform a weak OWF into a strong OWF:

Construction (Weak OWF to Strong OWF): Suppose \(f\) is a weak OWF for a hard core of \(1/Q(n)\) instance. Then the following \(F\) is a strong one-way function:

\[ F(x_1 \dots x_N) := f(x_1) || f(x_2) || \dots || f(x_N) \text{, for} |x_i|=n, N=2nQ(n) \]

where \(x || y\) means the concatenation of strings \(x\) and \(y\).

Intuitive argument (not a proof): An adversary could try to invert \(F\) by inverting each coordinate \(x_i\) individually. He will succeed with a probability less than \((1-1/Q(n))^{2nQ(n)}\), which itself is less than \([(1-1/Q(n))^{Q(n)}]^{2n}\), which finally is less than \(1/e^{2n}\) which is negligible (i.e. less than \(1/\operatorname{poly}(n)\) for every polynomial \(\operatorname{poly}\)).

But this is not a formal proof, because the adversary can use more clever strategies than piecewise inverting.

Proof (by reduction): We prove that \(F \text{ not strong} \implies f \text{ not weak}\). Then, by contraposition, it follows that if \(f\) is weak one way, \(F\) must be strong one-way.

Define again as before:

\[ F(x_1 \dots x_N) := f(x_1) || f(x_n) || \dots || f(x_N), N=2nQ(n), \text{ let } n'=nN \]

Assume for contradiction than \(F\) is not a (strong) one-way function. Then, there exists a non-negligible function \(\varepsilon(.)\) and a ppt algorithm \(A'\), such that for infinitly many \(n'\):

\[ \operatorname{Pr}[A'(F(x_1 \dots x_N)) \text{ inverts} ] \gt \varepsilon(n') \]

With this algorithm \(A'\) as a subroutine, we construct an ppt algorithm \(A\) which we'll show can invert the \(f(x_i)\):

Algorithm A(y): For each position \(i = 1, \dots, N\), repeat for \(\gt 2n(\varepsilon(n')/N)^{-1}\) trials:

  1. Choose random \(x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_N \in_{R} \{0,1\}^n\)
  2. Compute \(z = f(x_1) || \dots || f(x_{i-1}) || y || f(x_{i+1}) || \dots || f(x_N)\)
  3. Run \(A'(z)\). If it fails, contine. Else set \((x'_1 \dots x'_N) = A'(z)\) such than \(f(x'_i) = f(x_i)\). Output \(x'_i\) such that \(f(x'_i) = y\).

That algorithm \(A\) is a ppt algorithm if \(A'\) is ppt is hopefully obvious. It can be formally shown [Shafi's lecture, last minute starting at 1:18:33] that if algorithm \(A'\) inverts the long string \(x_1 \dots x_N\) with non-negligible probability, then algorithm \(A\) is a ppt algorithm which inverts a single \(f(x_i)\) also with non-negligible probability. Therefore \(f\) can't be a (weak) one-way function. The actual claim from Shafi's construction follows by contraposition: \(F\) must be (strong) one-way. \(\Box\)

(... todo: add diagram of this reduction proof)

Efficient Amplification of OWPs

Unfortunatly, the proofs and construction above are not a practical way to turn a weak one-way function into a strong one-way function. The intermediary results must be huge. That's why this construction, though of important theoretical value, isn't used in practice. But, if we restrict ourselves to bijective one-way functions, called one-way permutations (OWPs), then to turns out than an efficient construction exists.

[FOC, Volume 1, Section 2.6.1] shows how to efficiently construct an efficient stong OWP out of a family of weak one-way permutations.

The Existence of OWF Implies P != NP

Shafi Goldwasser and Mihir Bellare explain it best in their own words in [GB08, Section 2.1: One-Way Functions: Motivation]:

In secure encryption schemes, the legitimate user is able to decipher the messages (using some private information available to him), yet for an adversary (not having this private information) the task of decrypting the ciphertext (i.e., “breaking” the encryption) should be infeasible. Clearly, the breaking task can be performed by a non-deterministic polynomial-time machine. Yet, the security requirement states that breaking should not be feasible, namely could not be performed by a probabilistic polynomial-time machine. Hence, the existence of secure encryption schemes implies that there are tasks performed by non-deterministic polynomial-time machines yet cannot be performed by deterministic (or even randomized) polynomial-time machines. In other words, a necessary condition for the existence of secure encryption schemes is that \(\mathcal{NP}\) is not contained in \(\mathcal{BPP}\) (and hence that \(\mathcal{P} \ne \mathcal{NP}\)).[GB08]
 
Interestingly, the reverse is not true:
 
However, the above mentioned necessary condition (e.g., \(\mathcal P \ne \mathcal{NP}\)) is not a sufficient one.  \(\mathcal P \ne \mathcal{NP}\) only implies that the encryption scheme is hard to break in the worst case. It does not rule-out the possibility that the encryption scheme is easy to break in almost all cases. In fact, one can easily construct "encryption schemes" for which the breaking problem is NP-complete and yet there exist an efficient breaking algorithm that succeeds on 99% of the cases. Hence, worst-case hardness is a poor measure of security. Security requires hardness on most cases or at least average-case hardness. Hence, a necessary condition for the existence of secure encryption schemes is the existence of languages in \(\mathcal{NP}\) which are hard on the average. Furthermore, \(\mathcal P \ne \mathcal{NP}\) is not known to imply the existence fo languages in \(\mathcal{NP}\) which are hard on the average.[GB08]

Candidate One-Way Functions

Since we don't know whether one-way functions exist, we are left in a somewhat difficult position, at least from a theoretical point of view. Leonid A. Levin states the existence of a Universal One-Way Function, i.e. a combinatorial complete function that is one-way, if any function is[L00]. (If you think you've understood the previous sentence, think again.) But, here too, we still have no proof that OWFs exist in the first place.

Fortunately, we can still practice cryptography with some caveats, if we are willing to make additional assumptions. Using intractable mathematical problems, one can construct functions that are easy to compute, and that are hard to invert (with more than negligible probability). These functions would behave like OWFs, provided that the underlying mathematical problem is hard. We therefore name them "candidate owfs". A candidate owf is for all practical purposes like an owf, except that we're not 100% sure. The hard-to-invert property hinges on the fact, that the mathematical problem remains hard, despite a huge crowd of researchers trying to break it.

Of course, just because the problem hasn't been solved yet, doesn't mean that is has no solution. Some adversary may very well have broken one of these problems, but instead of publishing their results, they are keeping it to themselves, for fun and profit. Or, more precisely: some math genius at the NSA, GCHQ, etc. may have found a way to factorize composites or to solve the DLP problem in polynomial time. They may be using this breakthrough right now to decrypt internet traffic in real time! We simply don't know. In any case, we have to keep a eye on math publications.

If you're interested in candidate owfs, Vinod Vaikuntanathan introduces the discrete logarithm problem (DLP) in his lecture (see below).

Sources

One-way functions are one of the most fundamental building blocks in cryptography and are extensively presented in [FOC, Volume 1, Chapter 2]. However, the reader is advised to check the Errata, and clarifications on one-way permutations. [KL15] also shows theoretical foundations of OWF and their applications, but relies heavily on [FOC] anyway. A high-level theoretical overview of OWFs is in [L00].

Shafi Goldwasser presents strong and weak one-way functions in the lecture "L2. One-Way Functions" of an advanced course, starting at 43:46. While the embedded video starts at this point, you can also rewind to watch the whole lecture.

Candidate one-way functions, especially derived from the discrete logarithm problem (DLP), are presented by Vinod Vaikuntanathan in the follow-up lecture "L3. Number Theory" of the same advanced course.

Literature