{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:04:38Z","timestamp":1750694678057},"reference-count":25,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1987,9,1]],"date-time":"1987-09-01T00:00:00Z","timestamp":557452800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":9451,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[1987,9]]},"DOI":"10.1016\/0890-5401(87)90022-8","type":"journal-article","created":{"date-parts":[[2004,12,16]],"date-time":"2004-12-16T20:34:26Z","timestamp":1103229266000},"page":"226-240","source":"Crossref","is-referenced-by-count":19,"title":["One-way functions and circuit complexity"],"prefix":"10.1016","volume":"74","author":[{"given":"R.B.","family":"Boppana","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.C.","family":"Lagarias","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0890-5401(87)90022-8_BIB1","series-title":"Proceedings, 9th Annual ACM Symposium on Theory of Computing","first-page":"151","article-title":"Reducibility, randomness, and intractibility","author":"Adleman","year":"1977"},{"key":"10.1016\/0890-5401(87)90022-8_BIB2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","article-title":"\u03a311-formulae on finite structures","volume":"24","author":"Ajtai","year":"1983","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/0890-5401(87)90022-8_BIB3_1","series-title":"Randomness and computation","article-title":"Deterministic simulation of probabilistic constant depth circuits","volume":"Vol. 5","author":"Ajtai","year":"1987"},{"key":"10.1016\/0890-5401(87)90022-8_BIB3_2","series-title":"Proceedings, 26th Annual IEEE Symposium on Foundations of Computer Science, Portland","first-page":"11","article-title":"Deterministic simulation of probabilistic constant depth circuits","author":"Ajtai","year":"1985"},{"key":"10.1016\/0890-5401(87)90022-8_BIB22","unstructured":"Barrington, D. (1985), personal communication."},{"key":"10.1016\/0890-5401(87)90022-8_BIB4","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","article-title":"How to generate cryptographically strong sequences of pseudo random bits","volume":"13","author":"Blum","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0890-5401(87)90022-8_BIB5","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1109\/TIT.1983.1056754","article-title":"Relativized cryptography","volume":"29","author":"Brassard","year":"1983","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/0890-5401(87)90022-8_BIB6","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0213028","article-title":"Constant depth reducibility","volume":"13","author":"Chandra","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0890-5401(87)90022-8_BIB7","series-title":"Proceedings, 3rd Annual ACM Symposium on Theory of Computing","first-page":"151","article-title":"The complexity of theorem proving procedures","author":"Cook","year":"1971"},{"key":"10.1016\/0890-5401(87)90022-8_BIB8","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","article-title":"Parity, circuits, and the polynomial time hierarchy","volume":"17","author":"Furst","year":"1984","journal-title":"Math. Systems Theory"},{"key":"10.1016\/0890-5401(87)90022-8_BIB9","series-title":"Proceedings, 25th Annual IEEE Symposium on Foundations of Computer Science","first-page":"495","article-title":"Complexity measures for public-key cryptosystems","author":"Grollman","year":"1984"},{"key":"10.1016\/0890-5401(87)90022-8_BIB10","article-title":"One-way permutations in NC0","author":"Hastad","year":"1986","journal-title":"Infom. Process. Lett."},{"key":"10.1016\/0890-5401(87)90022-8_BIB11_1","series-title":"Randomness and Computation","article-title":"Improved lower bounds for small depth circuits","volume":"Vol. 5","author":"Hastad","year":"1987"},{"key":"10.1016\/0890-5401(87)90022-8_BIB11_2","series-title":"Proceedings, 18th Annual ACM Symposium on Theory of Computing","first-page":"6","article-title":"Improved lower bounds for small depth circuits","author":"Hastad","year":"1986"},{"key":"10.1016\/0890-5401(87)90022-8_BIB12","series-title":"Proceedings, 15th Annual ACM Symposium on Theory of Computing","first-page":"347","article-title":"Languages which capture complexity classes","author":"Immerman","year":"1983"},{"key":"10.1016\/0890-5401(87)90022-8_BIB13_1","first-page":"191","article-title":"Turing machines that take advice","volume":"28","author":"Karp","year":"1982","journal-title":"Enseign. Math."},{"key":"10.1016\/0890-5401(87)90022-8_BIB13_2","series-title":"Some connections between non-uniform and uniform complexity classes","first-page":"302","article-title":"Turing machines that take advice","author":"Karp","year":"1980"},{"key":"10.1016\/0890-5401(87)90022-8_BIB14","series-title":"Proceedings, 17th Annual ACM Symposium on Theory of Computing","first-page":"363","article-title":"One-way functions and pseudorandom generators, Combinatorica","author":"Levin","year":"1987"},{"key":"10.1016\/0890-5401(87)90022-8_BIB15","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0304-3975(81)90007-4","article-title":"On \u03b3-reducibility versus polynomial time many-one reducibility","volume":"14","author":"Long","year":"1981","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(87)90022-8_BIB16","series-title":"Advances in Cryptology\u2014Proceedings of Eurocrypt 84","first-page":"224","article-title":"Discrete logarithms in finite fields and their cryptographic significance","volume":"Vol. 209","author":"Odlyzko","year":"1985"},{"key":"10.1016\/0890-5401(87)90022-8_BIB17","author":"Savage","year":"1976"},{"key":"10.1016\/0890-5401(87)90022-8_BIB18","series-title":"Remarks about natural self-reducible sets in NP and complexity measures for public key cryptosystems","author":"Selman","year":"1984"},{"key":"10.1016\/0890-5401(87)90022-8_BIB19","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","article-title":"Relative complexity of checking and evaluating","volume":"5","author":"Valiant","year":"1976","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0890-5401(87)90022-8_BIB20","series-title":"Proceedings, 23rd Annual IEEE Symposium on Foundations of Computer Science","first-page":"80","article-title":"Theory and applications of trapdoor functions","author":"Yao","year":"1982"},{"key":"10.1016\/0890-5401(87)90022-8_BIB21","series-title":"Proceedings, 26th Annual IEEE Symposium on Foundations of Computer Science","first-page":"1","article-title":"Separating the polynomial-time hierarchy by oracles","author":"Yao","year":"1985"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540187900228?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540187900228?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,31]],"date-time":"2019-01-31T01:26:05Z","timestamp":1548897965000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0890540187900228"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,9]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1987,9]]}},"alternative-id":["0890540187900228"],"URL":"https:\/\/doi.org\/10.1016\/0890-5401(87)90022-8","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[1987,9]]}}}