The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Abstract
We give a set of conditions that allow one to generate 50–50 unpredictable bits.Based on those conditions, we present a general algorithmic scheme for constructing polynomial-time deterministic algorithms that stretch a short secret random input into a long sequence of unpredictable pseudo-random bits. We give an implementation of our scheme and exhibit a pseudo-random bit generator for which any efficient strategy for predicting the next output bit with better than 50–50 chance is easily transformable to an “equally efficient” algorithm for solving the discrete logarithm problem. In particular: if the discrete logarithm problem cannot be solved in probabilistic polynomial time, no probabilistic polynomial-time algorithm can guess the next output bit better than by flipping a coin: if “head” guess “0”, if “tail” guess “1”
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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 method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
Goldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603
Self-citationApproximate formulas for some functions of prime numbers
Rosser, J. B., & Schoenfeld, L. (1962) · Illinois Journal of Mathematics · doi:10.1215/ijm/1255631807 · Cited by 1,546
Pohlig, S., & Hellman, M. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055817 · Cited by 1,199
Theory and application of trapdoor functions
Yao, A. C. (1982) · 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) · doi:10.1109/sfcs.1982.45 · Cited by 968
The Art of Computer Programming, Vol. 2
Knuth, D. E. (1981) · Medical Entomology and Zoology · Cited by 886
Riemann's hypothesis and tests for primality
Miller, G. L. (1976) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(76)80043-8 · Cited by 709
A Fast Monte-Carlo Test for Primality
Solovay, R., & Strassen, V. (1977) · SIAM Journal on Computing · doi:10.1137/0206006 · Cited by 635
Cited by
Random oracles are practical: a paradigm for designing efficient protocols
Bellare, M., & Rogaway, P. (1993) · Proceedings of the 1st ACM conference on Computer and communications security - CCS '93 · doi:10.1145/168588.168596 · Cited by 4,712
Practical Secure Aggregation for Privacy-Preserving Machine Learning
Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., & Seth, K. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3133982 · Cited by 3,956
Goldreich, O., Micali, S., & Wigderson, A. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28420 · Cited by 3,590
Self-citationNon-Interactive and Information-Theoretic Secure Verifiable Secret Sharing
Pedersen, T. P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1_9 · Cited by 2,448
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
Self-citationEntity 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
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
Software protection and simulation on oblivious RAMs
Goldreich, O., & Ostrovsky, R. (1996) · Journal of the ACM · doi:10.1145/233551.233553 · Cited by 1,617
How to time-stamp a digital document
Haber, S., & Stornetta, W. S. (1991) · Journal of Cryptology · doi:10.1007/bf00196791 · Cited by 1,483
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
A Simple Unpredictable Pseudo-Random Number Generator
Blum, L., Blum, M., & Shub, M. (1986) · SIAM Journal on Computing · doi:10.1137/0215025 · Cited by 1,036
Self-citationThe random oracle methodology, revisited
Canetti, R., Goldreich, O., & Halevi, S. (2004) · Journal of the ACM · doi:10.1145/1008731.1008734 · 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
How to Construct Pseudorandom Permutations from Pseudorandom Functions
Luby, M., & Rackoff, C. (1988) · SIAM Journal on Computing · doi:10.1137/0217022 · Cited by 938
Bellare, M., & Rogaway, P. (1995) · Lecture Notes in Computer Science · doi:10.1007/bfb0053428 · Cited by 906
Non-interactive zero-knowledge and its applications
Blum, M., Feldman, P., & Micali, S. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62222 · Cited by 904
Self-citationA secure and efficient conference key distribution system: Extended abstract
Burmester, M., & Desmedt, Y. (1995) · Lecture Notes in Computer Science · doi:10.1007/bfb0053443 · Cited by 844
Verifynet: Secure and verifiable federated learning
Xu, G., Li, H., Liu, S., Yang, K., & Lin, X. (2020) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2019.2929409 · Cited by 839
Bit commitment using pseudorandomness
Naor, M. (1991) · Journal of Cryptology · doi:10.1007/bf00196774 · Cited by 807
The NP-completeness column: An ongoing guide
Johnson, D. S. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90020-9 · Cited by 794
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
Proactive Secret Sharing Or: How to Cope With Perpetual Leakage
Herzberg, A., Jarecki, S., Krawczyk, H., & Yung, M. (1995) · Lecture Notes in Computer Science · doi:10.1007/3-540-44750-4_27 · Cited by 738
Cryptographic limitations on learning Boolean formulae and finite automata
Kearns, M., & Valiant, L. (1994) · Journal of the ACM · doi:10.1145/174644.174647 · Cited by 733
Pseudo-random generation from one-way functions
Impagliazzo, R., Levin, L. A., & Luby, M. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73009 · Cited by 724
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
Self-citationMicali, S., Rabin, M., & Vadhan, S. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814584 · Cited by 716
Self-citationThe random oracle methodology, revisited (preliminary version)
Canetti, R., Goldreich, O., & Halevi, S. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276741 · Cited by 715
Self-testing/correcting with applications to numerical problems
Blum, M., Luby, M., & Rubinfeld, R. (1993) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(93)90044-w · Cited by 712
Self-citationOne-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
Lossy Trapdoor Functions and Their Applications
Peikert, C., & Waters, B. (2011) · SIAM Journal on Computing · doi:10.1137/080733954 · Cited by 649
A rigorous and robust quantum speed-up in supervised machine learning
Liu, Y., Arunachalam, S., & Temme, K. (2021) · Nature Physics · doi:10.1038/s41567-021-01287-z · Cited by 649
Universally Composable Commitments
Canetti, R., & Fischlin, M. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_2 · Cited by 621
Limits on the provable consequences of one-way permutations
Impagliazzo, R., & Rudich, S. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73012 · Cited by 575
Security problems in the TCP/IP protocol suite
Bellovin, S. M. (1989) · ACM SIGCOMM Computer Communication Review · doi:10.1145/378444.378449 · Cited by 550
Adaptively secure multi-party computation
Canetti, R., Feige, U., Goldreich, O., & Naor, M. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.238015 · Cited by 548
P = BPP if E requires exponential circuits: derandomizing the XOR lemma
Impagliazzo, R., & Wigderson, A. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258590 · Cited by 534
Provably Secure Higher-Order Masking of AES
Rivain, M., & Prouff, E. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-15031-9_28 · Cited by 526
Bellovin, S. M., & Merritt, M. (1993) · Proceedings of the 1st ACM conference on Computer and communications security - CCS '93 · doi:10.1145/168588.168618 · Cited by 522
Towards a theory of software protection and simulation by oblivious RAMs
Goldreich, O. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28416 · Cited by 507
Random sequence generation by cellular automata
Wolfram, S. (1986) · Advances in Applied Mathematics · doi:10.1016/0196-8858(86)90028-x · Cited by 494
Simultaneous Hardcore Bits and Cryptography against Memory Attacks
Akavia, A., Goldwasser, S., & Vaikuntanathan, V. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-00457-5_28 · Cited by 490
Razborov, A. A., & Rudich, S. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1494 · Cited by 479
Protecting data privacy in private information retrieval schemes
Gertner, Y., Ishai, Y., Kushilevitz, E., & Malkin, T. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276723 · Cited by 445
ANODR: anonymous on demand routing with untraceable routes for mobile ad-hoc networks
Kong, J., & Hong, X. (2003) · Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing · doi:10.1145/778415.778449 · Cited by 432
Blum, M., De Santis, A., Micali, S., & Persiano, G. (1991) · SIAM Journal on Computing · doi:10.1137/0220068 · Cited by 427
Self-citationMicali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424
Self-citationCryptographic Extraction and Key Derivation: The HKDF Scheme
Krawczyk, H. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_34 · Cited by 408
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
Pseudorandom Generators without the XOR Lemma
Sudan, M., Trevisan, L., & Vadhan, S. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1730 · Cited by 393
Impagliazzo, R., & Zuckerman, D. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63486 · Cited by 387
Physically Observable Cryptography
Micali, S., & Reyzin, L. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24638-1_16 · Cited by 378
Self-citationNumber-theoretic constructions of efficient pseudo-random functions
Naor, M., & Reingold, O. (2004) · Journal of the ACM · doi:10.1145/972639.972643 · Cited by 368
Discrete logarithms in finite fields and their cryptographic significance
Odlyzko, A. M. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-39757-4_20 · Cited by 367
Number-theoretic constructions of efficient pseudo-random functions
Naor, M., & Reingold, O. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646134 · Cited by 353
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
RSA and Rabin Functions: Certain Parts are as Hard as the Whole
Alexi, W., Chor, B., Goldreich, O., & Schnorr, C. P. (1988) · SIAM Journal on Computing · doi:10.1137/0217013 · Cited by 339
Collision Free Hash Functions and Public Key Signature Schemes
Damgård, I. B. (2010) · Lecture Notes in Computer Science · doi:10.1007/3-540-39118-5_19 · Cited by 339
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
How to share a function securely
De Santis, A., Desmedt, Y., Frankel, Y., & Yung, M. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195405 · Cited by 328
Extractors and pseudorandom generators
(2001) · Journal of the ACM · doi:10.1145/502090.502099 · Cited by 324
On the (In)security of the Fiat-Shamir paradigm
Goldwasser, S., & Kalai, Y. T. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238185 · Cited by 311
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
Coppersmith, D., Krawczyk, H., & Mansour, Y. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48329-2_3 · Cited by 306
Self-testing/correcting with applications to numerical problems
Blum, M., Luby, M., & Rubinfeld, R. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100225 · Cited by 303
Self-citationNon-Interactive Oblivious Transfer and Applications
Bellare, M., & Micali, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_48 · Cited by 297
Self-citationMicali, S. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365746 · Cited by 293
Self-citationRECENT DEVELOPMENTS IN EXPLICIT CONSTRUCTIONS OF EXTRACTORS
SHALTIEL, R. (2004) · Current Trends in Theoretical Computer Science · doi:10.1142/9789812562494_0013 · Cited by 291
A fair protocol for signing contracts
Ben-Or, M., Goldreich, O., Micali, S., & Rivest, R. L. (1990) · IEEE Transactions on Information Theory · doi:10.1109/18.50372 · Cited by 287
Self-citationOn the Construction of Pseudorandom Permutations: Luby—Rackoff Revisited
Naor, M., & Reingold, O. (1999) · Journal of Cryptology · doi:10.1007/pl00003817 · Cited by 285
Complexity Measures for Public-Key Cryptosystems
Grollmann, J., & Selman, A. L. (1988) · SIAM Journal on Computing · doi:10.1137/0217018 · Cited by 282
Picture data encryption using scan patterns
Bourbakis, N., & Alexopoulos, C. (1992) · Pattern Recognition · doi:10.1016/0031-3203(92)90074-s · Cited by 278
Forward-Security in Private-Key Cryptography
Bellare, M., & Yee, B. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-36563-x_1 · Cited by 275
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
Klivans, A. R., & van Melkebeek, D. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539700389652 · Cited by 270
Dwork, C., & Naor, M. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892117 · Cited by 264
One way functions and pseudorandom generators
Levin, L. A. (1987) · Combinatorica · doi:10.1007/bf02579323 · Cited by 257
Generating quasi-random sequences from semi-random sources
Santha, M., & Vazirani, U. V. (1986) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(86)90044-9 · Cited by 256
Almost everywhere high nonuniform complexity
Lutz, J. H. (1992) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(92)90020-j · Cited by 254
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
Can AI-Generated Text be Reliably Detected?
Sadasivan, V. S., Kumar, A., Balasubramanian, S., Wang, W., & Feizi, S. (2023) · arXiv · doi:10.48550/arxiv.2303.11156 · Cited by 810
Certifiable quantum dice: or, true random number generation secure against quantum adversaries
Vazirani, U., & Vidick, T. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2213984 · Cited by 80
Stream cipher designs: a review
Jiao, L., Hao, Y., & Feng, D. (2020) · Science China Information Sciences · doi:10.1007/s11432-018-9929-x · Cited by 67
Practical and Robust Federated Learning With Highly Scalable Regression Training
Han, S., Ding, H., Zhao, S., Ren, S., Wang, Z., Lin, J., & Zhou, S. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2023.3271859 · Cited by 60
On the Security of Random Sources
Coron, J. S. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49162-7_3 · Cited by 37
(2014) · Informatica · Cited by 26
Revisiting Shor's quantum algorithm for computing general discrete logarithms
Ekerå, M. (2019) · arXiv · doi:10.48550/arxiv.1905.09084 · Cited by 9
About Polynomial-Ttime "Unpredictable" Generators
L'Ecuyer, P., & Proulx, R. (2005) · 1989 Winter Simulation Conference Proceedings · doi:10.1109/wsc.1989.718716 · Cited by 4
Metadata
- Authors
- Blum, M., & Micali, S.
- Venue
- SIAM Journal on Computing
- Published
- 1984-11
- Volume
- 13
- Issue
- 4
- Pages
- 850-864
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2164284862
- Cited by
- 1,322
- References
- 17
- FWCI
- 19.14
- Type
- journal article
- Language
- en
- Open access
- closed
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.