Cryptography

A one-way function $F$ provides the following interface:

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

• $F.\mathrm{in}(\lambda )$ the input space to $F_{\lambda }$

• $F.\mathrm{out}(\lambda )$ the output space of $F_{\lambda }$

• $F.\mathrm{eval}(\lambda ,X)=F_{\lambda }(X):F.\mathrm{in}(\lambda )\to F.\mathrm{out}(\lambda )$

Security: For a randomized algorithm $A$ define:

$${\mathrm{Adv}}_{A,F}(t)=\mathrm{Pr}[F_{\lambda }(A(F_{\lambda }(x)))=F_{\lambda }(X)\mid \lambda \leftarrow F.\mathrm{gen}(t),X\leftarrow F.\mathrm{in}(\lambda )]$$

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

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

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

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

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

Problem: $F^{\mathrm{DES}}$ defined by $F^{\mathrm{DES}}(K)={\mathrm{DES}}_K(0)$ is not an asymptotically one-way function, as it does not depend on security parameters. == Fixed Security Parameter Definition == Definition: $f:\{\mathrm{0,1}{\}}^n\to \{\mathrm{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

$$\mathrm{Pr}[F(A(F(X)))=F(X)\mid X\leftarrow \{\mathrm{0,1}{\}}^n]<\epsilon .$$

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

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

Define: $g_1(x,y)=f(x)\mid \mid 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.

• Collision resistant hash functions

• Key exchange

• Oblivious Transfer