

Lutz, Jack H. (1992) OneWay Functions and Balanced NP. Technical Report TR9211, Department of Computer Science, Iowa State University.
Abstract
The existence of cryptographically secure oneway functions is related
to the measure of a subclass of NP. This subclass, called BNP
(``balanced NP''), contains 3SAT and other standard NP problems. The
hypothesis that BNP is not a subset of P is equivalent to the P <> NP
conjecture. A stronger hypothesis, that BNP is not a measure 0 subset
of E_2 = DTIME(2^polynomial) is shown to have the following two
consequences.
1. For every k, there is a polynomial time computable, honest
function f that is (2^{n^k})/n^koneway with exponential
security. (That is, no 2^{n^k}timebounded algorithm with n^k
bits of nonuniform advice inverts f on more than an
exponentially small set of inputs.)
2. If DTIME(2^n) ``separates all BPP pairs,'' then there is a
(polynomial time computable) pseudorandom generator that passes
all probabilistic polynomialtime statistical tests. (This
result is a partial converse of Yao, Boppana, and Hirschfeld's
theorem, that the existence of pseudorandom generators passing
all polynomialsize circuit statistical tests implies that
BPP\subset DTIME(2^{n^epsilon}) for all epsilon>0.)
Such consequences are not known to follow from the weaker hypothesis
that P <> NP.
Contact site administrator at: ssg@cs.iastate.edu
