On the generation of cryptographically strong pseudorandom sequences
Open accessThe DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
Abstract
This paper shows how to generate from a short random seed a long sequence of pseudorandom numbers which is cryptogrgraphically strong in the sense that knowing some sequence elements cannot possibly help the cryptanalyst to determine other sequence elements.The method is based on the RSA cryptosystem, and it is the first published example of a pseudorandom sequence generator for which such a property has been formally proved.
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
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
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 · cited 1×
“A simple example which shows that good one-way functions can be misused as sequence generators is supplied by the RSA (Rivest-Shamir-Adelman) encryption function [ 5 ]:”
MethodA method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012
Self-citationPrivacy and authentication: An introduction to cryptography
Diffie, W., & Hellman, M. E. (1979) · Proceedings of the IEEE · doi:10.1109/proc.1979.11256 · Cited by 470
Mackay, A. L. (1984) · The Sciences · doi:10.1002/j.2326-1951.1984.tb02705.x · Cited by 52
Cited by
Provable data possession at untrusted stores
Ateniese, G., Burns, R., Curtmola, R., Herring, J., Kissner, L., Peterson, Z., & Song, D. (2007) · Proceedings of the 14th ACM conference on Computer and communications security · doi:10.1145/1315245.1315318 · Cited by 2,705
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
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
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
Nisan, N., & Wigderson, A. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80043-1 · Cited by 808
Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials
Camenisch, J., & Lysyanskaya, A. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45708-9_5 · Cited by 732
Fiat, A., & Naor, M. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48329-2_40 · Cited by 728
Micali, 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
A Signature Scheme with Efficient Protocols
Camenisch, J., & Lysyanskaya, A. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-36413-7_20 · Cited by 662
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
Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees
Barić, N., & Pfitzmann, B. (1997) · Lecture Notes in Computer Science · doi:10.1007/3-540-69053-0_33 · Cited by 557
Random sequence generation by cellular automata
Wolfram, S. (1986) · Advances in Applied Mathematics · doi:10.1016/0196-8858(86)90028-x · Cited by 494
A complexity theoretic approach to randomness
Sipser, M. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808762 · Cited by 460
Patient controlled encryption: ensuring privacy of electronic medical records
Benaloh, J., Chase, M., Horvitz, E., & Lauter, K. (2009) · Proceedings of the 2009 ACM workshop on Cloud computing security · doi:10.1145/1655008.1655024 · Cited by 358
Secure Hash-and-Sign Signatures Without the Random Oracle
Gennaro, R., Halevi, S., & Rabin, T. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_9 · 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
True Random Bit Generation From a Double-Scroll Attractor
Yalcin, M. E., Suykens, J. A. K., & Vandewalle, J. (2004) · IEEE Transactions on Circuits and Systems I: Regular Papers · doi:10.1109/tcsi.2004.830683 · Cited by 280
Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains
Boneh, D., Bünz, B., & Fisch, B. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-26948-7_20 · Cited by 271
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
Using Channel Hopping to Increase 802.11 Resilience to Jamming Attacks
Navda, V., Bohra, A., Ganguly, S., & Rubenstein, D. (2007) · IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications · doi:10.1109/infcom.2007.314 · Cited by 252
How to generate cryptographically strong sequences of pseudo random bits
Blum, M., & Micali, S. (1982) · 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) · doi:10.1109/sfcs.1982.72 · Cited by 252
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
“It may also be worth emphasizing that the bits eventually produced, after application of an extractor, will be guaranteed to be statistically indistinguishable from uniform, a much stronger condition that the computational indistinguishability that is the criterion for cryptographic pseudorandom generators [26, 4, 30].”
BackgroundA High Speed IC Truly Random Number Generator Based on Chaotic Sampling of Regular Waveform
ERGÜN, S., GÜLER, Ü., & ASADA, K. (2011) · IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences · doi:10.1587/transfun.e94.a.180 · Cited by 53
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
- Shamir, A.
- Venue
- ACM Transactions on Computer Systems
- Published
- 1983-02
- Volume
- 1
- Issue
- 1
- Pages
- 38-44
- ISSN
- 0734-2071 (ISSN-L)
- 1557-7333
- OpenAlex
- W2087115651
- Cited by
- 268
- References
- 5
- FWCI
- 6.18
- Type
- journal article
- 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.