One-Way Functions

Asymptotic Definition

A one-way function \(F\) provides the following interface:

  • \(F.gen(t) : \mathbb{Z}^+ \rightarrow \{0,1\}^*\) is a randomized polynomial time algorithm in \(t\) such that given a security parameter \(t\), it outputs a function description \(\lambda \in \{0,1\}^*\).

  • \(F.in(\lambda)\) the input space to \(F_\lambda\)

  • \(F.out(\lambda)\) the output space of \(F_\lambda\)

  • \(F.eval(\lambda, X) = F_\lambda(X):F.in(\lambda) \rightarrow F.out(\lambda)\)

Security: For a randomized algorithm \(A\) define:

\[ Adv_{A,F}(t) = Pr[F_\lambda(A(F_\lambda(x))) = F_\lambda(X) | \lambda \leftarrow F.gen(t), X \leftarrow F.in(\lambda) ] \]

Defintion: \(F\) is a one-way function if \(Adv_{A,F}(t)\) is negligible.

A one-way permutation \(\pi\) is a one-way function where for all \(\lambda\in\{0,1\}^*\) with \(\pi.in(\lambda) = \pi.out(\lambda)\) and \(\pi_\lambda\) is one-to-one.

Example: \(\pi^{RSA}.gen(t)\): generate two \(t\)-bit primes \(p,q\) such that \(p=q=2 (mod 3)\), output \(\lambda=\langle N=pq \rangle\).

\(\pi^{RSA}.in(\lambda) = \pi^{RSA}.out(\lambda) = \mathbb{Z}^*_N\)

\(\pi^{RSA}.eval(X) = X^3 mod N\)

Problem: \(F^{DES}\) defined by \(F^{DES}(K)=DES_K(0)\) is not an asymptotically one-way function, as it does not depend on security parameters.

Fixed Security Parameter Definition

Definition: \(f:\{0,1\}^n\rightarrow\{0,1\}^n\) is \((t,\epsilon)\)-one-way if there exists an "efficient" algorithm for evaluating \(f\), and for all probabilistic \(t\)-time algorithms \(A\), we have

\[Pr[F(A(F(X)))=F(X)|X\leftarrow\{0,1\}^n] \lt \epsilon.\]

Then \(F^DES(K)=DES_K(0)\) is \((t,\epsilon)\)-one-way for some \(t, \epsilon\). Note: One-way functions/permutations are considered "fast" primitives.

Amplification of One-wayness

Suppose \(f:\{0,1\}^n\rightarrow\{0,1\}^m\) is \((t,\epsilon)\) one-way.

Define: \(g_1(x,y) = f(x) || f(y), g_2(x,y) = f(x) \oplus f(y)\).

Theorem: If \(f(x)\) is \((t,\epsilon)\)-one-way then \(g_1(x,y)\) is \(((\epsilon^2/4) t, 6\epsilon^2)\)-one-way.

One-wayness of \(g_2\) follows from Yao’s XOR lemma.

Applications of One-way functions

Using the Blum-Micali Generator, one-way functions can be used to construct Pseudo Random Number Generators, which enable us to construct Pseudo Random Functions (by using the GGM method for example), which in turn can be used to make Pseudo Random Permutations via the Luby-Rackoff construction.

One-way functions also imply (inefficient) signature schemes.

Nonapplications of One-way functions

It is known that one-way functions are not sufficient for the following.


Ben Lynn blynn@cs.stanford.edu 💡