Publication Date

1996

Technical Report Number

TR96-09

Subjects

Theory of Computation, Mathematics of Computing

Abstract

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 not equal to 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 is a subset of DTIME(2^{n^epsilon}) for all epsilon>0.) Such consequences are not known to follow from the weaker hypothesis that P is not equal to NP.

Share

COinS