One-Way Functions

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

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

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.

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

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.

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.

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.

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