## One-Way Functions and Balanced NP

 dc.contributor.author Lutz, Jack dc.contributor.department Computer Science dc.date 2018-02-13T22:51:22.000 dc.date.accessioned 2020-06-30T01:55:06Z dc.date.available 2020-06-30T01:55:06Z dc.date.issued 1992-05-01 dc.description.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 <> 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.

dc.identifier archive/lib.dr.iastate.edu/cs_techreports/112/ dc.identifier.articleid 1129 dc.identifier.contextkey 5339324 dc.identifier.s3bucket isulib-bepress-aws-west dc.identifier.submissionpath cs_techreports/112 dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/19920 dc.source.bitstream archive/lib.dr.iastate.edu/cs_techreports/112/TR92_11.pdf|||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
Name:
TR92_11.pdf
Size:
328.88 KB
Format: