Summary
Today we begin a tour of the theory of one-way functions and pseudorandomness.
The highlight of the theory is a proof that if one-way functions exist (with good asymptotic security) then pseudorandom permutations exist (with good asymptotic security). We have seen that pseudorandom permutations suffice to do encryption and authentication with extravagantly high levels of security (respectively, CCA security and existential unforgeability under chosen message attack), and it is easy to see that if one-way functions do not exist, then every encryption and authentication scheme suffers from a total break.
Thus the conclusion is a strong “dichotomy” result, saying that either cryptography is fundamentally impossible, or extravagantly high security is possible.
Unfortunately the proof of this result involves a rather inefficient reduction, so the concrete parameters for which the dichotomy holds are rather unrealistic. (One would probably end up with a system requiring gigabyte-long keys and days of processing time for each encryption, with the guarantee that if it is not CCA secure then every 128-bit key scheme suffers a total break.) Nonetheless it is one of the great unifying achievements of the asymptotic theory, and it remains possible that a more effective proof will be found.
In this lecture and the next few ones we shall prove the weaker statement that if one-way permutations exist then pseudorandom permutations exist. This will be done in a series of four steps each involving reasonable concrete bounds. A number of combinatorial and number-theoretic problems which are believed to be intractable give us highly plausible candidate one-way permutations. Overall, we can show that if any of those well-defined and well-understood problems are hard, then we can get secure encryption and authentication with schemes that are slow but not entirely impractical. If, for example, solving discrete log with a modulus of the order of is hard, then there is a CCA-secure encryption scheme requiring a
-bit key and fast enough to carry email, instant messages and probably voice communication. (Though probably too slow to encrypt disk access or video playback.)
1. One-way Functions and One-way Permutations
A one-way function is a function such that, for a random
, it is hard to find a pre-image of
.
Definition 1 (One-way Function) A function
is
-one way if for every algorithm
of complexity
we have
In the asymptotic theory, one is interested in one-way functions that are defined for all input lengths and are efficiently computable. Recall that a function is called negligible if for every polynomial
we have
.
Definition 2 (One-way Function — Asymptotic Definition) A function
is one-way if
is polynomial time computable and
- for every polynomial
there is a negligible function
such that for all large enough
the function
is
-one way.
Example 1 (Subset Sum) On input
, where
,
parses
as a sequence of
integers, each
-bit long, plus a subset
.
The output is
Some variants of subset-sum have been broken, but it is plausible that
is a
-one way function with
and
super-polynomial in
, maybe even as large as
.
Exercise 1 Let
be a
-secure one-way function. Show that
Definition 3 (One-way Permutation) If
is a bijective
-one way function, then we call
a
–one-way permutation.
If
is an (asymptotic) one-way function, and for every
![]()
is a bijection from
into
, then we say that
is an (asymptotic) one-way permutation.
There is a non-trivial general attack against one-way permutations.
Exercise 2 Let
be a
-secure one-way permutation. Show that
This means that we should generally expect the input length of a secure one-way permutation to be at least 200 bits or so. (Stronger attacks than the generic one are known for the candidates that we shall consider, and their input length is usually 1000 bits or more.)
Example 2 (Modular Exponentiation) Let
be a prime, and
be the group whose elements are
and whose operation is multiplication
. It is a fact (which we shall not prove) that
is cyclic, meaning that there is an element
such that the mapping
is a permutation on
. Such an element
is called a generator, and in fact most elements of
are generators.
is conjectured to be one-way for most choices of
and
.
The problem of inverting
is called the discrete logarithm problem.
The best known algorithm for the discrete logarithm is conjectured to run in time
. It is plausible that for most
and most
the discrete logarithm is a
one way permutation with
and
of the order of
.
Problems like exponentiation do not fit well in the asymptotic definition, because of the extra parameters . (Technically, they do not fit our definitions at all because the input is an element of
instead of a bit string, but this is a fairly trivial issue of data representation.) This leads to the definition of family of one-way functions (and permutations).
2. A Preview of What is Ahead
Our proof that a pseudorandom permutation can be constructed from any one-way permutation will proceed via the following steps:
- We shall prove that for any one-way permutation
we can construct a hard-core predicate
, that is a predicate
such that
is easy to compute given
, but it is hard to compute given
.
- From a one-way function with a hard-core predicate, we shall show how to construct a pseudorandom generator with one-bit expansion, mapping
bits into
.
- From a pseudorandom generator with one-bit expansion, we shall show how to get generators with essentially arbitrary expansion.
- From a length-doubling generator mapping
bits into
, we shall show how to get pseudorandom functions.
- For a pseudorandom function, we shall show how to get pseudorandom permutations.
3. Hard-Core Predicate
Definition 4 (Hard-Core Predicate) A boolean function
is
-hard core for a permutation
if for every algorithm
of complexity
Note that only one-way permutations can have efficiently computable hard-core predicates.
Exercise 3 Suppose that
is a
-hard core predicate for a permutation
, and
is computable in time
. Show that
is
-one way.
It is known that if is one-way, then every bit of
is hard-core.
Our first theorem will be that a random XOR is hard-core for every one-way permutation.
Theorem 5 (Goldreich and Levin) Suppose that
is an algorithm of complexity
such that
(where
.) Then there is an algorithm
of complexity at most
such that
Hi Luca,
These notes are very helpful, thanks.
I think there’s a slight technical concern, e.g. in example 1. Shouldn’t SS(x) also output x_1, … x_k, and omit only the index set I? Otherwise it seems an adversary could easily manufacture a solution.
Also it looks like there is some confusion between the statements of Ex. 1 & 2, viz. ‘function’ vs. ‘permutation’.
thanks for the corrections, Andy.