Average case intractability
Ramarathnam Venkatesan · 1991
In the first part of this thesis, the intractability of random instances of a graph coloring problem is proved by showing its average case completeness. If such a complete problem has an algorithm which is polynomial on average, then so do all NP problems under all distributions that can be generated in polynomial time and the P = ?NP question becomes academic. The graph coloring problem considered here is a generalization of edge coloring of random digraphs. It randomly specifies the number of black edges and how the 3-node induced subgraphs with colored edges may look. Using a randomizing reduction the completeness of the problem is shown. Gurevich has earlier shown that under deterministic reductions such problems are unlikely (unless $DEXP = NEXP$) to be complete. In the second part, the task of amplifying the fraction of hard instances is considered. A method is given to transform a weak one-way function, which may be easily inverted on all but a polynomial fraction of the range, into a strong one-way function, which can be easily inverted only on a negligible fraction of the range. The previous known transformation due to Yao does not preserve the security (i.e., the running-time of the inverting algorithm) within any polynomial. Using random walks on constructive expanders, the transformation given here converts any regular (e.g., one-to-one) weak one-way function into a strong one, while preserving security. The resulting function $F(x)$ applies the weak one-way function $f$ to strings of length $\Theta (\vert x\vert)$. These security preserving constructions yield efficient pseudo-random generators and signatures based on any regular one-way function.