OneWay Functions
Asymptotic Definition
A oneway 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:
Defintion: \(F\) is a oneway function if \(Adv_{A,F}(t)\) is negligible.
A oneway permutation \(\pi\) is a oneway function where for all \(\lambda\in\{0,1\}^*\) with \(\pi.in(\lambda) = \pi.out(\lambda)\) and \(\pi_\lambda\) is onetoone.
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 oneway 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)\)oneway 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)\)oneway for some \(t, \epsilon\). Note: Oneway functions/permutations are considered "fast" primitives.
Amplification of Onewayness
Suppose \(f:\{0,1\}^n\rightarrow\{0,1\}^m\) is \((t,\epsilon)\) oneway.
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)\)oneway then \(g_1(x,y)\) is \(((\epsilon^2/4) t, 6\epsilon^2)\)oneway.
Onewayness of \(g_2\) follows from Yao’s XOR lemma.
Applications of Oneway functions
Using the BlumMicali Generator, oneway 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 LubyRackoff construction.
Oneway functions also imply (inefficient) signature schemes.
Nonapplications of Oneway functions
It is known that oneway functions are not sufficient for the following.

Collision resistant hash functions

Key exchange