Article

Free access

Pseudo-random generators under uniform assumptions

Author:

J. HåstadAuthors Info & Claims

STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of Computing

Pages 395 - 404

https://doi.org/10.1145/100216.100270

Published: 01 April 1990 Publication History

PDF eReader

References

[1]

{BM} Blum, M. and Micali, S. "How to generate cryptographically strong sequences of pseudo-random bits", SIAM J. on Computing, 13 (1984), pp. 850- 864.

Digital Library

Google Scholar

[2]

{G} Goldreich, O. "A Note on Computational Indistiguishability", technical report 89-051, International Computer Science Institute.

Google Scholar

[3]

{GKL} Goldreich, O., Krawczyk, H. and Luby, M. "On the existence of pseudo-random generators", Proc. 29th Annual Conf. on Foundations of Computer Science, (1988), pp. 12-24.

Google Scholar

[4]

{GL} Goldreich, O. and Levin, L. "A hard-core predicate for all one-way functions", Proc. 21st Symp. on Theory of Computing, (1989), pp. 25-32.

Digital Library

Google Scholar

[5]

{ILL} Impagliazzo, R., Levin L. and Luby, M. "Pseudo-random number generation from one-way functions", Proc. 21st Symp. on Theory of Computing , (1989), pp. 12-24.

Digital Library

Google Scholar

[6]

{K} Knuth D. "The are of computer programming, vol. 2; seminumerical algorithms", second edition, Addison-Wesley, Reading, Mass.

Digital Library

Google Scholar

[7]

{L} Levin L. "One-way functions and pseudo-random generators", Proc. 17th Symp. on Theory of Computing, (1985), pp. 363-365.

Digital Library

Google Scholar

[8]

{Y} Yao A. "Theory and application of trapdoor functions", Proc. 23rd Annual Conf. on Foundations of Computer Science, (1982), pp. 80-91.

Digital Library

Google Scholar

Cited By

View all

Harmon LDelavignette GOliveira H(2024): Homomorphic Encryption of Rationals Using Laurent PolynomialsInformation Security and Privacy10.1007/978-981-97-5025-2_10(180-195)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5025-2_10
Maji HWang M(2021)Computational Hardness of Optimal Fair Computation: Beyond MinicryptAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84245-1_2(33-63)Online publication date: 11-Aug-2021
https://doi.org/10.1007/978-3-030-84245-1_2
Maji H(2020)Computational Hardness of Collective Coin-Tossing ProtocolsEntropy10.3390/e2301004423:1(44)Online publication date: 30-Dec-2020
https://doi.org/10.3390/e23010044
Show More Cited By

Index Terms

Pseudo-random generators under uniform assumptions
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
  2. Probability and statistics
    1. Probabilistic reasoning algorithms
      1. Random number generation
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Design and analysis of algorithms

Recommendations

Bit-Wise Behavior of Random Number Generators

In 1985, G. Marsaglia proposed the m-tuple test, a runs test on bits, as a test of nonrandomness of a sequence of pseudorandom integers. We try this test on the outputs from a large set of pseudorandom number generators and discuss the behavior of the ...
Simple extractors via constructions of cryptographic pseudo-random generators

Trevisan has shown that constructions of pseudo-random generators from hard functions (the Nisan-Wigderson approach) also produce extractors. We show that constructions of pseudo-random generators from one-way permutations (the Blum-Micali-Yao approach) ...
Resolution-stationary random number generators

Besides speed and period length, the quality of uniform random number generators (RNGs) is usually assessed by measuring the uniformity of their point sets, formed by taking vectors of successive output values over their entire period length. For F"2-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of Computing

April 1990

574 pages

ISBN:0897913612

DOI:10.1145/100216

Editor:
Harriet Ortiz

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC90

Sponsor:

SIGACT

STOC90: 22nd Annual ACM Symposium on Theory of Computing

May 13 - 17, 1990

Maryland, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

70
Total Citations
View Citations
597
Total Downloads

Downloads (Last 12 months)95
Downloads (Last 6 weeks)15

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Harmon LDelavignette GOliveira H(2024): Homomorphic Encryption of Rationals Using Laurent PolynomialsInformation Security and Privacy10.1007/978-981-97-5025-2_10(180-195)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5025-2_10
Maji HWang M(2021)Computational Hardness of Optimal Fair Computation: Beyond MinicryptAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84245-1_2(33-63)Online publication date: 11-Aug-2021
https://doi.org/10.1007/978-3-030-84245-1_2
Maji H(2020)Computational Hardness of Collective Coin-Tossing ProtocolsEntropy10.3390/e2301004423:1(44)Online publication date: 30-Dec-2020
https://doi.org/10.3390/e23010044
Maji HWang M(2020)Black-Box Use of One-Way Functions is Useless for Optimal Fair Coin-TossingAdvances in Cryptology – CRYPTO 202010.1007/978-3-030-56880-1_21(593-617)Online publication date: 10-Aug-2020
https://doi.org/10.1007/978-3-030-56880-1_21
Chung KLin HMahmoody MPass RKleinberg R(2013)On the power of nonuniformity in proofs of securityProceedings of the 4th conference on Innovations in Theoretical Computer Science10.1145/2422436.2422480(389-400)Online publication date: 9-Jan-2013
https://dl.acm.org/doi/10.1145/2422436.2422480
Boldyreva AKumar V(2012)A new pseudorandom generator from collision-resistant hash functionsProceedings of the 12th conference on Topics in Cryptology10.1007/978-3-642-27954-6_12(187-202)Online publication date: 27-Feb-2012
https://dl.acm.org/doi/10.1007/978-3-642-27954-6_12
Ding XYang YDeng RWang S(2010)A new hardware-assisted PIR with O(n) shuffle costInternational Journal of Information Security10.1007/s10207-010-0105-29:4(237-252)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1007/s10207-010-0105-2
Nakano MIida MSueyoshi T(2009)Improvement of Execution Efficiency on the MX CoreProceedings of the 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies10.1109/PDCAT.2009.81(420-425)Online publication date: 8-Dec-2009
https://dl.acm.org/doi/10.1109/PDCAT.2009.81
Bresson EChevassut OPointcheval D(2007)Provably secure authenticated group Diffie-Hellman key exchangeACM Transactions on Information and System Security10.1145/1266977.126697910:3(10-es)Online publication date: 1-Jul-2007
https://dl.acm.org/doi/10.1145/1266977.1266979
Wullschleger J(2007)Oblivious-Transfer AmplificationProceedings of the 26th annual international conference on Advances in Cryptology10.1007/978-3-540-72540-4_32(555-572)Online publication date: 20-May-2007
https://dl.acm.org/doi/10.1007/978-3-540-72540-4_32
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Bit-Wise Behavior of Random Number Generators

Simple extractors via constructions of cryptographic pseudo-random generators

Resolution-stationary random number generators