The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Pseudo-random generation from one-way functions
Open accessAbstract
We show that the existence of one-way functions is necessary and sufficient for the existence of pseudo-random generators in the following sense. Let ƒ be an easily computable function such that when x is chosen randomly: (1) from ƒ(x) it is hard to recover an x1 with ƒ(x1) = ƒ(x) by a small circuit, or; (2) ƒ has small degeneracy and from ƒ(x) it is hard to recover x by a fast algorithm. From one-way functions of type (1) or (2) we show how to construct pseudo-random generators secure against small circuits or fast algorithms, respectively, and vice-versa. Previous results show how to construct pseudo-random generators from one-way functions that have special properties ([Blum, Micali 82], [Yao 82], [Levin 85], [Goldreich, Krawczyk, Luby 88]).
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb01338.x · Cited by 88,486
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb00917.x · Cited by 48,949
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285
Goldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603
Universal classes of hash functions
Carter, J. L., & Wegman, M. N. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90044-8 · Cited by 2,519
How to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,115
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Blum, M., & Micali, S. (1984) · SIAM Journal on Computing · doi:10.1137/0213053 · Cited by 1,322
A hard-core predicate for all one-way functions
Goldreich, O., & Levin, L. A. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73010 · Cited by 1,193
Self-citationTheory and application of trapdoor functions
Yao, A. C.-C. (1982) · doi:10.1109/sfcs.1982.95 · Cited by 1,008
Universal one-way hash functions and their cryptographic applications
Naor, M., & Yung, M. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73011 · Cited by 959
Cited by
Handbook of applied cryptography
(1997) · Choice Reviews Online · doi:10.5860/choice.34-4512 · Cited by 10,357
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
Dodis, Y., Reyzin, L., & Smith, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_31 · Cited by 2,038
Entity Authentication and Key Distribution
Bellare, M., & Rogaway, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48329-2_21 · Cited by 1,752
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
Dodis, Y., Ostrovsky, R., Reyzin, L., & Smith, A. (2008) · SIAM Journal on Computing · doi:10.1137/060651380 · Cited by 1,717
A Pseudorandom Generator from any One-way Function
HÅstad, J., Impagliazzo, R., Levin, L. A., & Luby, M. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539793244708 · Cited by 1,653
Self-citationSoftware protection and simulation on oblivious RAMs
Goldreich, O., & Ostrovsky, R. (1996) · Journal of the ACM · doi:10.1145/233551.233553 · Cited by 1,617
A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack
Cramer, R., & Shoup, V. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0055717 · Cited by 1,437
Generalized privacy amplification
Bennett, C. H., Brassard, G., Crepeau, C., & Maurer, U. M. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.476316 · Cited by 1,417
How to time-stamp a digital document
Haber, S., & Stornetta, W. S. (1991) · Journal of Cryptology · doi:10.1007/bf00196791 · Cited by 1,483
Goldreich, O., Micali, S., & Wigderson, A. (1991) · Journal of the ACM · doi:10.1145/116825.116852 · Cited by 1,349
Characterizing quantum supremacy in near-term devices
Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H. (2018) · Nature Physics · doi:10.1038/s41567-018-0124-x · Cited by 1,175
Cramer, R., & Shoup, V. (2003) · SIAM Journal on Computing · doi:10.1137/s0097539702403773 · Cited by 978
Universal one-way hash functions and their cryptographic applications
Naor, M., & Yung, M. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73011 · Cited by 959
Bellare, M., & Rogaway, P. (1995) · Lecture Notes in Computer Science · doi:10.1007/bfb0053428 · Cited by 906
Bit commitment using pseudorandomness
Naor, M. (1991) · Journal of Cryptology · doi:10.1007/bf00196774 · Cited by 807
Quantum random number generators
Herrero-Collantes, M., & Garcia-Escartin, J. C. (2017) · Reviews of Modern Physics · doi:10.1103/revmodphys.89.015004 · Cited by 791
Fiat, A., & Naor, M. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48329-2_40 · Cited by 728
The round complexity of secure protocols
Beaver, D., Micali, S., & Rogaway, P. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100287 · Cited by 721
One-way functions are necessary and sufficient for secure signatures
Rompel, J. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100269 · Cited by 695
Chaos and cryptography: block encryption ciphers based on chaotic maps
Jakimoski, G., & Kocarev, L. (2001) · IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications · doi:10.1109/81.904880 · Cited by 673
The Operational Meaning of Min- and Max-Entropy
Konig, R., Renner, R., & Schaffner, C. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2025545 · Cited by 659
Entropic uncertainty relations and their applications
Coles, P. J., Berta, M., Tomamichel, M., & Wehner, S. (2017) · Reviews of Modern Physics · doi:10.1103/revmodphys.89.015002 · Cited by 658
Lossy Trapdoor Functions and Their Applications
Peikert, C., & Waters, B. (2011) · SIAM Journal on Computing · doi:10.1137/080733954 · Cited by 649
Nisan, N., & Zuckerman, D. (1996) · Journal of Computer and System Sciences · doi:10.1006/jcss.1996.0004 · Cited by 634
One-Way Accumulators: A Decentralized Alternative to Digital Signatures
Benaloh, J., & de Mare, M. (1994) · Lecture Notes in Computer Science · doi:10.1007/3-540-48285-7_24 · Cited by 572
Witness indistinguishable and witness hiding protocols
Feige, U., & Shamir, A. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100272 · Cited by 523
On the effectiveness of secret key extraction from wireless signal strength in real environments
Jana, S., Premnath, S. N., Clark, M., Kasera, S. K., Patwari, N., & Krishnamurthy, S. V. (2009) · Proceedings of the 15th annual international conference on Mobile computing and networking · doi:10.1145/1614320.1614356 · Cited by 518
The MD4 Message Digest Algorithm
Rivest, R. L. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-38424-3_22 · Cited by 486
Micali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424
How to Time-Stamp a Digital Document
Haber, S., & Stornetta, W. S. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-38424-3_32 · Cited by 404
The Security of Cipher Block Chaining
Bellare, M., Kilian, J., & Rogaway, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48658-5_32 · Cited by 394
Impagliazzo, R., & Zuckerman, D. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63486 · Cited by 387
Self-citationFree randomness can be amplified
Colbeck, R., & Renner, R. (2012) · Nature Physics · doi:10.1038/nphys2300 · Cited by 379
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
One-way functions are essential for complexity based cryptography
Impagliazzo, R., & Luby, M. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63483 · Cited by 339
Self-citationUniversally Composable Privacy Amplification Against Quantum Adversaries
Renner, R., & König, R. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_22 · Cited by 337
Cryptographic Primitives Based on Hard Learning Problems
Blum, A., Furst, M., Kearns, M., & Lipton, R. J. (1994) · Lecture Notes in Computer Science · doi:10.1007/3-540-48329-2_24 · Cited by 332
Quantum Information Processing with Finite Resources
Tomamichel, M. (2016) · SpringerBriefs in Mathematical Physics · doi:10.1007/978-3-319-21891-5 · Cited by 329
Incremental Cryptography: The Case of Hashing and Signing
Bellare, M., Goldreich, O., & Goldwasser, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48658-5_22 · Cited by 312
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
Babai, L., Fortnow, L., Nisan, N., & Wigderson, A. (1993) · Computational Complexity · doi:10.1007/bf01275486 · Cited by 310
Leftover Hashing Against Quantum Side Information
Tomamichel, M., Schaffner, C., Smith, A., & Renner, R. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2158473 · Cited by 303
Secret Key Extraction from Wireless Signal Strength in Real Environments
Premnath, S. N., Jana, S., Croft, J., Gowda, P. L., Clark, M., Kasera, S. K., Patwari, N., & Krishnamurthy, S. V. (2013) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2012.63 · Cited by 297
Micali, S. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365746 · Cited by 293
Robust Non-interactive Zero Knowledge
De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., & Sahai, A. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_33 · Cited by 293
Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
Guruswami, V., Umans, C., & Vadhan, S. (2009) · Journal of the ACM · doi:10.1145/1538902.1538904 · Cited by 281
Simple and Tight Bounds for Information Reconciliation and Privacy Amplification
Renner, R., & Wolf, S. (2005) · Lecture Notes in Computer Science · doi:10.1007/11593447_11 · Cited by 258
Device-independent quantum random-number generation
Liu, Y., Zhao, Q., Li, M.-H., Guan, J.-Y., Zhang, Y., Bai, B., Zhang, W., Liu, W.-Z., Wu, C., Yuan, X., et al. (2018) · Nature · doi:10.1038/s41586-018-0559-3 · Cited by 258
Computationally private information retrieval (extended abstract)
Chor, B., & Gilboa, N. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258609 · Cited by 249
Postprocessing for quantum random-number generators: Entropy evaluation and randomness extraction
Ma, X., Xu, F., Xu, H., Tan, X., Qi, B., & Lo, H.-K. (2013) · Physical Review A · doi:10.1103/physreva.87.062327 · Cited by 241
Extracting all the randomness and reducing the error in Trevisan's extractors
Raz, R., Reingold, O., & Vadhan, S. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301292 · Cited by 171
Metadata
- Authors
- Impagliazzo, R., Levin, L. A., & Luby, M.
- Venue
- Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89
- Publisher
- ACM Press
- Published
- 1989
- Pages
- 12-24
- OpenAlex
- W2064423787
- Cited by
- 724
- References
- 28
- FWCI
- 15.37
- Type
- conference paper
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.