One-Way Functions and Balanced NP







Deposit Papers 


Lutz, Jack H. (1992) One-Way Functions and Balanced NP. Technical Report TR92-11, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF


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
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.

Subjects:All uncategorized technical reports
ID code:00000017
Deposited by:Staff Account on 01 May 1992

Contact site administrator at: