Publication Date


Technical Report Number



Mathematics of Computing, Theory of Computation


The existence of cryptographically secure one-way 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^k-one-way with exponential security. (That is, no 2^{n^k}-time-bounded 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 polynomial-time statistical tests. (This result is a partial converse of Yao, Boppana, and Hirschfeld's theorem, that the existence of pseudorandom generators passing all polynomial-size 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.