One-Way Functions and Balanced NP

Lutz, Jack H. (1996) One-Way Functions and Balanced NP. Technical Report TR96-09, Department of Computer Science, Iowa State University.

Abstract

One-Way Functions and Balanced NP
Jack H. Lutz
Department of Computer Science
Iowa State University
Ames, Iowa  50011
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.


Subjects:
All uncategorized technical reports


ID code:
00000129
Deposited by:
Staff Account on 30 September 1996





Contact site administrator at: ssg@cs.iastate.edu