The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
How to generate cryptographically strong sequences of pseudo random 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.
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 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
Kenny, A. (2018) · Carl Strehlow’s 1909 Comparative Heritage Dictionary: An Aranda, German, Loritja and Dieri to English Dictionary with Introductory Essays · doi:10.22459/cschd.08.2018.04 · Cited by 3,216
Pohlig, S., & Hellman, M. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055817 · Cited by 1,199
Probabilistic encryption & how to play mental poker keeping secret all partial information
Goldwasser, S., & Micali, S. (1982) · Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82 · doi:10.1145/800070.802212 · Cited by 883
Self-citationOn the generation of cryptographically strong pseudorandom sequences
Shamir, A. (1983) · ACM Transactions on Computer Systems · doi:10.1145/357353.357357 · Cited by 268
A subexponential algorithm for the discrete logarithm problem with applications to cryptography
Adleman, L. (1979) · 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) · doi:10.1109/sfcs.1979.2 · Cited by 242
On Digital Signatures and Public-Key Cryptosystems.
Rivest, R. L., Adi Shamir, Z., & Adleman, L. (1977) · Defense Technical Information Center (DTIC) · Cited by 179
On the generation of cryptographically strong pseudo-random sequences
Adi Shamir, Z. (1981) · Lecture notes in computer science · doi:10.1007/3-540-10843-2_43 · Cited by 103
Inferring a sequence generated by a linear congruence
Plumstead, J. B. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.73 · Cited by 76
Cited by
Handbook of applied cryptography
(1997) · Choice Reviews Online · doi:10.5860/choice.34-4512 · Cited by 10,357
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
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
Self-citationA 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-citationVerifynet: 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
Nisan, N., & Wigderson, A. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80043-1 · Cited by 808
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-citationReconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption)*
Abadi, M., & Rogaway, P. (2002) · Journal of Cryptology · doi:10.1007/s00145-001-0014-7 · Cited by 613
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
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
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-citationAn Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information
Blum, M., & Goldwasser, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-39568-7_23 · Cited by 262
Self-citationCan 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
“For example, commonly used pseudorandom generators 6 can achieve an (cid:15) that is bounded by a negligible function 1 /b t of the number of bits b used in the seed of the generator for a positive integer t 7 [37, 38].”
Method
Metadata
- Authors
- Blum, M., & Micali, S.
- Venue
- 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982)
- Publisher
- IEEE
- Published
- 1982-11
- Pages
- 112-117
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2138109426
- Cited by
- 252
- References
- 9
- FWCI
- 6.52
- Type
- conference paper
- 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.