10 March 2022
One-Way Functions
As its name suggests, a one-way function is easy to evaluate but hard to invert. One-way functions are natural objects to consider since they help create our desired asymmetry in the resource demands of signer and forger. The formal definition goes as follows, again written in the language of game.
Definition. Let \(f: \set{0,1}^* \to \set{0,1}^*\) be a polynomial-time computable function. Consider the inversion game:
If for all polynomial-time randomised algorithms implementing \(I\), the success probability \(\Pr(J \text{ returns true})\) is negligible, then we call \(f\) a one-way function. As usual, the “polynomial-time” and “negligible” are both measured with respect to \(k\). It is possible that for some particular image \(y\) the inverter could quickly answer a correct preimage, but the point here is that he cannot handle a general random image sampled from an exponentially large domain.
People believe that one-way functions do exist.
There are multiple promising candidates and we will investigate two of them shortly. However, proofs are still out of current reach, especially in view of the following theorem:
Theorem 3. If one-way functions exist, then P ≠ NP.
Proof. Let \(f: \set{0,1}^* \to \set{0,1}^*\) be a one-way function. For binary strings \(t,x \in \set{0,1}^*\), we denote \(t \sqsubseteq x\) if \(t\) is a prefix of \(x\). Consider the language
\[L := \set{(1^\ell,t,y) ~\middle\vert~ \exists x \in \set{0,1}^\ell: t \sqsubseteq x \land f(x)=y}.\]It is easy to see \(L \in \mathrm{NP}\). This is because \((1^\ell,t,y) \in L\) iff there exists an \(x \in \set{0,1}^\ell: t \sqsubseteq x \land f(x)=y\) by definition. Such \(x\) serves as a polynomially-bounded certificate for \((1^\ell,t,y)\), and the condition \(t \sqsubseteq x \land f(x)=y\) is polynomial-time decidable.
Next we argue \(L \not\in \mathrm{P}\). Suppose to the contrary that there exists a polynomial-time algorithm \(M\) that decides \(L\). We will use it as an oracle to construct an inverter \(I\) that inverts \(f\). The idea is to exploit self-reducibility of language \(L\) to guide our inversion. In what follows, we use \(\epsilon\) to denote the empty string.
The inverter first uses \(M\) to detect the correct length \(\ell\) of the preimage. Note that the length is polynomially bounded by the length of \(x\) since \(f\) is polynomially computable. After knowing \(\ell\), the inverter incrementally searches for a preimage by revealing one bit at a time. Overall, \(I\) runs in polynomial time and succeeds with non-negligible probability (in fact, 1), contradicting the fact that \(f\) is a one-way function.
Combining the two parts we have P ≠ NP. ∎
With essentially no modification, the same argument also yields a strengthening:
Corollary 4. If one-way function exists, then RP ≠ NP. ∎
We are now ready to prove Proposition 2 from last time. Note that it is implied by Corollary 4 and the Lemma 5 below.
Lemma 5. If there is a ?NM secure scheme, then there exists a one-way function.
Proof.
Let \(\Sigma := (\gen,\sgn,\vrf)\) be a ?NM secure scheme. Let’s define a function \(f(r)\). Given “external random source” \(r \in \set{0,1}^*\), we drive the algorithm gen with \(r\) and obtain a key pair \((sk,pk)\). We define the function value \(f(r) := pk\).
Because gen is a polynomial-time algorithm, the function \(f\) is polynomial-time computable. It is also hard to invert; otherwise we could derive \(r\) (and hence \(sk\)) from \(pk\) and implement ?NM attack with non-negligible success probability. The formal argument is left as an exercise. ∎
In the remaining time we investigate two popular candidates of one-way functions.
Let \((G,\times)\) be a finite group of order \(n\), generated by element \(g \in G\). That is, \(G = \set{g^\theta: \theta \in \Int_n }\).
Consider the exponentiation function \((\theta \in \Int_n) \mapsto (g^\theta \in G)\). It is bijective and can be computed easily by the standard “square power” technique. Its inverse operation, also known as discrete logarithm, appears difficult for certain groups.
Here is a caveat. The words “easy” and “difficult” make no sense if the group is fixed – everything would be constant time then. So the group should really be parameterized by \(k\). Explicitly, we are considering (a family of) groups \((G_k,\times)\) of order \(n_k \to \infty\), generated by \(g_k \in G_k\). The computational complexity could thus be measured with respect to \(k\).
The exponentiation function \((\theta \in \Int_{n_k}) \mapsto (g_k^{\theta} \in G_k)\) appears to be one-way for certain (but not all) group families. An obviously bad choice would be \((G_k,\times) := (\Int_{n_k},+)\) with generator \(g_k := 1\). A traditional good choice is \((G_k,\times) := (\Int_{p_k}^*, \times)\) where prime \(p_k\) grows exponentially with \(k\). More recently, elliptic curve groups are receiving more attention because of their implementation efficiency.
For easy reference, we restate the common belief in one-wayness of the exponentiation function:
People believe that the exponentiation function is one-way for certain group family \((G_k,\times)\) with generator \(g_k\) and order \(n_k\). Namely, no inverter could succeed with non-negligible probability (measured as function of \(k\)) in the following attack
Let \(p, q\) be distinct primes and \(n := p q\). From basic number theory we have \(\phi(n) := \lvert \Int_n^* \rvert = (p-1)(q-1)\) where \(\phi(\cdot)\) denotes Euler’s totient function. Choose \(e \in \Int_{\phi(n)}^*\). Consider the power function
\[(x \in \Int_n) \mapsto (x^e \in \Int_n).\]It is bijective because it has an inverse mapping (“root function”) defined as follows. Let \(d := e^{-1} \pmod{\phi(n)}\), which always exists by our choice of \(e\). Given any image \(x^e\), we may recover the preimage \(x\) by computing \((x^e)^d = x^{1 + \lambda \phi(n)} = x\), where the last equality follows from Euler’s theorem. (To be precise, Euler’s theorem only works for \(x \in \Int_n^*\). We need Chinese remainder theorem for general \(x \in \Int_n\).)
Again, to measure complexity we have to parameterize everything by \(k\), so that now we have \(p_k, q_k, e_k\). But then we see that the power function is not one-way! As the parameters \(p_k, q_k, e_k\) are specified beforehand, the inverter can calculate \(\phi(n_k) = (p_k-1)(q_k-1)\) and consequently \(d_k := e_k^{-1} \pmod{\phi(n)}\). Then he can invert the function readily, using the discussion in previous paragraph.
The problem here is the existence of a “trapdoor” \(d\) computable from parameters \(p, q\). To arrive at a truly one-way function, we need to protect our choices for \(p, q\). This can be done by wrapping them in the input, leading to the so-called RSA function:
\[(p, q, e, x) \mapsto (n, e, x^e \bmod n) \quad \text{where } n := pq.\]The input domain is parameterized by \(k\). Standard choice calls for:
For easy reference, we state the RSA assumption as follows.
People believe that the RSA function is one-way. That is, no inverter could succeed with non-negligible probability in the following attack
