In this note we discuss one-way functions and pitfalls in constructing them from more complicated primitives (sPRPGs, PRFGs, PRNGs). This note accompanies notes 6.
One-way functions are functions that are easy to compute in polytime (i.e. the function can be evaluated on an $n$-bit input in time $poly(n)$), but hard to invert on average. One might express the hardness-of-average-case-inversion property of a function $f$ as follows: \begin{equation} \forall \mathcal{A} \in PPT \quad \Pr[ y \leftarrow f(U_n) ; A(y) \in f^{-1}(y) ] = n^{-\omega(1)} \end{equation}
A canonical application of one-way functions
One-way functions abound in cryptography in that one-wayness is necessary for essentially all applications. For a canonical example of an application where they are also sufficient consider the following.
We wish to design a system for authenticating users based on passwords with the following constraints:
- users are assigned passwords which cannot be changed
- the password file must be publicly readable
- it must be the case that no user may learn another's password
- there is no global secret
A first attempt
If we were permitted to have a global secret, we could set the password file to store $(U, Enc_k(pwd_U))$ for each user $U$ and $Enc$ a private-key encryption scheme.
Apart from there being a global secret (which will need to be access-controlled), one may complain that the system must compute $U$'s actual password (making it available for theft for other reasons - other implementation bugs) with every authentication request, even those that are unsuccessful
A good scheme
We don't need to store the password in a way that allows them to be recovered, only in a way that allows us to compare, for equality, something offered in the future with something recorded in the past.
So let's store, in the password file, the list of tuples $(U, f(pwd_U))$ where $f$ is a one-way function. We can check whether $p$ is $U$'s password by checking whether $f(p)$ equals the value stored for $U$. Meanwhile, since $f$ is one-way, and all of the initial $pwd_U$ where chosen by the system (and so we could have chosen them uniformly at random), it is hard for an attacker when seeing $f(pwd_U)$ to find any preimage, exactly the security we need.
Implementing a one-way functions from a stronger primitive
So what one-way function should we use? What was used in early unix systems was the function \begin{equation} \label{eq:owf_from_des} f:x \mapsto DES_x(\overline{0}) \end{equation} Supposing that the $DES$ cipher is a sPRPG, should $f$ be a one-way function? Remember that the property of being a strongly pseudorandom permutation generator has to do with being unable to distinguish a $DES_x(\cdot)$ oracle from a totally random oracle.
You should think of \eqref{eq:owf_from_des} as truncating some of your output. To see why this might be a bad idea, we discussed the following construction:
Even if $f$ outputs up to $\log n$ bits of $G$, $f$ still has no hope of being a one-way function.
Of course PRNGs are one-way functions. Let me say that again as a proposition.
It's also the case that you can't ruin one-wayness by throwing away only a few bits of your output. You're asked to prove a version of this precisely on your assignment 3.
The last example we discussed in class concerned truncating 'ideal AES'. By ideal AES we mean the function \begin{equation} AES_{k_1,\ldots,k_m}^p(x) = p( \ldots p(p(x) \xor k_1) \xor k_2 \ldots ) \xor k_m \end{equation} Can you see why $f:x \mapsto AES_x(\overline{0})$ is not one-way, no matter what $m$ you pick?