One-Way Functions and Balanced NP Lutz, Jack
dc.contributor.department Computer Science 2018-02-13T22:51:22.000 2020-06-30T01:55:06Z 2020-06-30T01:55:06Z 1992-05-01
dc.description.abstract <p>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.</p>
dc.identifier archive/
dc.identifier.articleid 1129
dc.identifier.contextkey 5339324
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath cs_techreports/112
dc.source.bitstream archive/|||Fri Jan 14 18:44:32 UTC 2022
dc.subject.disciplines Theory and Algorithms
dc.title One-Way Functions and Balanced NP
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
328.88 KB
Adobe Portable Document Format