The DOI matches its Crossref record; 47 of the 49 references it cites were found in a registry or an index.
Extractors and pseudorandom generators
Abstract
We introduce a new approach to constructing extractors. Extractors are algorithms that transform a “weakly random” distribution into an almost uniform distribution. Explicit constructions of extractors have a variety of important applications, and tend to be very difficult to obtain.We demonstrate an unsuspected connection between extractors and pseudorandom generators. In fact, we show that every pseudorandom generator of a certain kind is an extractor.A pseudorandom generator construction due to Impagliazzo and Wigderson, once reinterpreted via our connection, is already an extractor that beats most known constructions and solves an important open question. We also show that, using the simpler Nisan--Wigderson generator and standard error-correcting codes, one can build even better extractors with the additional advantage that both the construction and the analysis are simple and admit a short self-contained description.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Moreover, it is a strong extractor (its seed can be reused) and its seed length is the polylogarithmic function of the input.”
From Quantum random number generation (2016) · cites this paper as [97]
In the citing paper
“Trevisan ' s extractor 97,98 has been proven to be secure against quantum adversaries. 99”
From Quantum random number generation (2016) · cites this paper as [97]
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot the international journal of robotics research and application · doi:10.1108/ir.1999.04926fae.001 · Cited by 39,228
The Theory of Error-Correcting Codes
(1977) · North-Holland mathematical library · doi:10.1016/s0924-6509(08)x7030-8 · Cited by 10,891
Goldwasser, S., & Micali, S. M. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,667
Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes
Leighton, F. T. (1991) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,467
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Blum, M., & Micali, S. M. (1984) · SIAM Journal on Computing · doi:10.1137/0213053 · Cited by 1,309
A hard-core predicate for all one-way functions
Goldreich, O., & Levin, L. A. (1989) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/73007.73010 · Cited by 1,192
Theory and application of trapdoor functions
Yao, A. C.-C. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.45 · Cited by 1,019
Nisan, N., & Wigderson, A. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80043-1 · Cited by 814
Limits on the provable consequences of one-way permutations
Impagliazzo, R., & Rudich, S. (1989) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/73007.73012 · Cited by 580
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
Chor, B., & Goldreich, O. (1988) · SIAM Journal on Computing · doi:10.1137/0217015 · Cited by 551
Research works printed but not linked: 7
- ARVIND V., Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science, 235
- 10.5555/795662.796290 · DOI
- IMPAGLIAZZO R., 1998, Proceedings of the 39th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 734
- 10.1145/301250.301428 · DOI
- NISAN N., 1996, Proceedings of the 11th IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif., 44
- 10.5555/795663.796348 · DOI
- VON NEUMANN J., 1951, Various techniques used in connection with random digits. NBS, Appl. Math. Seri., 12, 36
Cited by
Sorted by citations
Items 201–300 of 322
Entropy collapse in mobile sensors: The hidden risks of sensor-based security
Shepherd, C., & Hurley, E. A. J. (2025) · Journal of Information Security and Applications · doi:10.1016/j.jisa.2025.104272 · Cited by 5
More efficient privacy amplification with less random seeds
Hayashi, M., & Tsurumaru, T. (2015) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2015.7282763 · Cited by 5
Chattopadhyay, E. (2020) · ACM SIGACT News · doi:10.1145/3406678.3406688 · Cited by 5
Usable Human Authentication: A Quantitative Treatment
Blocki, J. (2014) · Cited by 5
Tsirelson Polytopes and randomness generation
Bierhorst, P., & Zhang, Y. (2020) · New Journal of Physics · doi:10.1088/1367-2630/aba30d · Cited by 6
Computational Complexity Since 1980
Impagliazzo, R. (2005) · Lecture notes in computer science · doi:10.1007/11590156_2 · Cited by 5
Can every randomized algorithm be derandomized?
Impagliazzo, R. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132571 · Cited by 5
Aggarwal, D., Boddu, N. G., Jain, R., & Obremski, M. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3313149 · Cited by 6
Reconstructive Dispersers and Hitting Set Generators
Umans, C. (2005) · Lecture notes in computer science · doi:10.1007/11538462_39 · Cited by 5
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
Hirahara, S., Lu, Z., & Nanashima, M. (2024) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs61266.2024.00030 · Cited by 4
Molotkov, S. N. (2020) · Journal of Experimental and Theoretical Physics · doi:10.1134/s1063776120020065 · Cited by 4
Leone, N., Azzini, S., Mazzucchi, S., Moretti, V., Sanna, M., Borghi, M., Piccoli, G., Bernard, M., Ghulinyan, M., & Pavesi, L. (2023) · Photonics Research · doi:10.1364/prj.488875 · Cited by 4
Improved Real‐Time Post‐Processing for Quantum Random Number Generators
Qian, L., Sun, X., Zhang, X., & Zhou, H. (2024) · Advanced Quantum Technologies · doi:10.1002/qute.202400025 · Cited by 4
List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument
Dwork, C., Shaltiel, R., Smith, A., & Trevisan, L. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24638-1_6 · Cited by 4
Self-citationComputational Notions of Quantum Min-EntropyPreprint
Chen, Y.-H., Chung, K.-M., Lai, C., Vadhan, S., & Wu, X. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1704.07309 · Cited by 11
Efficient methods for one-shot quantum communicationPreprint
Anshu, A. (2020) · arXiv (Cornell University) · doi:10.14288/1.0388334 · Cited by 4
Derandomization and Group TestingPreprint
Cheraghchi, M. (2010) · arXiv (Cornell University) · Cited by 4
Optimization of experimental quantum randomness expansion
Piveteau, A., Seguinard, A., Mironowicz, P., & Bourennane, M. (2025) · Physical Review Applied · doi:10.1103/hc3f-3pbw · Cited by 6
Simple extractors via constructions of cryptographic pseudo-random generators
Zimand, M. (2009) · Theoretical Computer Science · doi:10.1016/j.tcs.2009.10.020 · Cited by 3
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
Li, J., Pyne, E., & Tell, R. (2024) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs61266.2024.00095 · Cited by 3
Set-Codes with Small Intersections and Small Discrepancies
Gabrys, R., Dau, S. H., Colbourn, C. J., & Milenković, O. (2020) · SIAM Journal on Discrete Mathematics · doi:10.1137/19m1241106 · Cited by 3
Extracting randomness and dependencies via a matrix polarization
Abbe, E. A. (2011) · Cited by 3
On Obtaining Pseudorandomness from Error-Correcting Codes
Kalyanaraman, S., & Umans, C. (2006) · Lecture notes in computer science · doi:10.1007/11944836_12 · Cited by 3
Randomness extractors -- applications and constructions
Wigderson, A. (2009) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.fsttcs.2009.2340 · Cited by 3
Zero-Fixing Extractors for Sub-Logarithmic Entropy
Cohen, G., & Shinkar, I. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-47672-7_28 · Cited by 3
Authenticated Key Exchange from Ideal Lattices.
Zhang, J., Zhang, Z., Ding, J., & Snook, M. (2014) · Cited by 3
Quantified Derandomization: How to Find Water in the Ocean
Tell, R. (2022) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000108 · Cited by 3
Set Families with Low Pairwise IntersectionPreprint
Beideman, C., & Blocki, J. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1404.4622 · Cited by 3
Mathematical foundations of modern cryptography: computational complexity perspectivePreprint
Goldwasser, S. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0212055 · Cited by 4
Faster Spectral Sparsification in Dynamic StreamsPreprint
Kapralov, M., Mousavifar, A., Musco, C., Musco, C., & Nouri, N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.12165 · Cited by 3
Two-Source Extractors Secure Against Quantum AdversariesPreprint
Kasher, R., & Kempe, J. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1005.0512 · Cited by 3
Leakage-Resilient Non-Malleable Secret Sharing in Non-compartmentalized ModelsPreprint
Lin, F., Cheraghchi, M., Guruswami, V., Safavi-Naini, R., & Wang, H. (2019) · arXiv (Cornell University) · doi:10.4230/lipics.itc.2020.7 · Cited by 3
New constructions of WOM codes using the Wozencraft ensemblePreprint
Shpilka, A. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1110.6590 · Cited by 3
Password Authenticated Key Exchange
Jarecki, S. (2022) · Wiley eBooks · doi:10.1002/9781394188369.ch10 · Cited by 3
Better short-seed extractors against quantum knowledge
Ben-Aroya, A., & Ta‐Shma, A. (2010) · Cited by 3
On the Complexity of Constructing Pseudorandom Functions (Especially when They Don’t Exist)
Miles, E., & Viola, E. (2013) · Journal of Cryptology · doi:10.1007/s00145-013-9161-x · Cited by 2
Statistical Evaluation of a Physical Random Number Generator
Perminov, N. S., Bannik, O. I., Gilyazov, L. R., Melnik, K. S., & Tarankova, D. Y. (2019) · Bulletin of the Russian Academy of Sciences Physics · doi:10.3103/s1062873819030365 · Cited by 2
Son İşlem Algoritmaları İçin Web Tabanlı Yazılım Suiti Geliştirilmesi
Yosunlu, D., & Avaroğlu, E. (2021) · European Journal of Science and Technology · doi:10.31590/ejosat.1008063 · Cited by 2
Molotkov, S. N. (2022) · Laser Physics · doi:10.1088/1555-6611/ac5ccc · Cited by 2
Progress in Computational Complexity Theory
Cai, J., & Zhu, H. P. (2005) · Journal of Computer Science and Technology · doi:10.1007/s11390-005-0735-4 · Cited by 2
Reconstructive Dispersers and Hitting Set Generators
Umans, C. (2008) · Algorithmica · doi:10.1007/s00453-008-9266-z · Cited by 2
On randomness extraction in AC0
Goldreich, O., Viola, E., & Wigderson, A. (2015) · Conference on Computational Complexity · doi:10.5555/2833227.2833257 · Cited by 2
Set-Codes with Small Intersections and Small Discrepancies
Gabrys, R., Dau, S. H., Colbourn, C. J., & Milenković, O. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849651 · Cited by 2
Towards Efficient LPN-Based Symmetric Encryption
Bogos, S., Korolija, D., Locher, T., & Serge Vaudenay, B. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-78375-4_9 · Cited by 2
Randomness Extraction in AC0 and with Small LocalityPreprint
Cheng, K., & Li, X. (2016) · arXiv (Cornell University) · doi:10.4230/lipics.approx-random.2018.37 · Cited by 2
Miller, C. A., & Shi, Y. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.0489 · Cited by 2
Practical randomness and privacy amplificationPreprint
Foreman, C., Wright, S., Edgington, A., Berta, M., & Curchod, F. J. (2020) · arXiv (Cornell University) · Cited by 2
More Efficient Privacy Amplification with Non-Uniform Random Seeds via Dual Universal Hash Function.Preprint
Hayashi, M., & Tsurumaru, T. (2013) · arXiv (Cornell University) · Cited by 2
ВИБІР ДЖЕРЕЛА ВИПАДКОВОСТІ ДЛЯ КОМП’ЮТЕРНОГО МОДЕЛЮВАННЯ
Щербина, Ю., Казакова, Н., Фразе-Фразенко, О. О., Лаптєв, О. А., & Собчук, А. (2023) · Science-based technologies · doi:10.18372/2310-5461.59.17944 · Cited by 1
Liu, Y., & Pass, R. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-01855-7_20 · Cited by 1
100 Gbit/s Secure and Real-Time Vacuum Fluctuation Based Quantum Random Number Generator
Bomhals, A., Bruynsteen, C., Meysmans, C., Vandierendonck, A., & Yin, X. L. (2026) · Journal of Lightwave Technology · doi:10.1109/jlt.2026.3665249 · Cited by 1
Is there a canonical network for network information theory?
Effros, M., & Langberg, M. (2014) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2014.6970797 · Cited by 1
Two-Source Randomness Extractors for Elliptic Curves for Authenticated Key Exchange
Ciss, A. A., & Sow, D. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-55589-8_6 · Cited by 1
Computational Extractors and Pseudorandomness.
Dachman-Soled, D., Gennaro, R., Krawczyk, H., & Malkin, T. (2011) · Cited by 1
On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing
Aggarwal, D., Chung, E., Obremski, M., & Ribeiro, J. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-22318-1_12 · Cited by 1
On Explicit Constructions of Designs
Liu, X., & Mubayi, D. (2022) · The Electronic Journal of Combinatorics · doi:10.37236/10513 · Cited by 1
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
Hirahara, S. (2023) · SIAM Journal on Computing · doi:10.1137/19m124705x · Cited by 1
Expander-Based Cryptography Meets Natural Proofs
Oliveira, I. C., Santhanam, R., & Tell, R. (2022) · Computational Complexity · doi:10.1007/s00037-022-00220-x · Cited by 1
Randomness evaluation of LD phase noise for use as a continuous-variable random-number generator
Tomaru, T. (2019) · OSA Continuum · doi:10.1364/osac.2.002554 · Cited by 1
Can't touch this: unconditional tamper evidence from short keys
van der Vecht, B., Coiteux-Roy, X., & Škorić, B. (2022) · Quantum Information and Computation · doi:10.26421/qic22.5-6-1 · Cited by 1
Two-sources Randomness Extractors for Elliptic CurvesPreprint
Ciss, A. A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1404.2226 · Cited by 1
List Decoding and Pseudorandom Constructions
Guruswami, V. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-77224-8_1 · Cited by 1
Extracting Computational Entropy and Learning Noisy Linear Functions
Lee, C.-J., Lu, C.-J., & Tsai, S. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2158897 · Cited by 1
Extracting Computational Entropy and Learning Noisy Linear Functions
Lee, C.-J., Lu, C.-J., & Tsai, S. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02882-3_34 · Cited by 1
Quantum-Proof Extractors: Optimal up to Constant FactorsPreprint
Chung, K.-M., Cohen, G., Vidick, T., & Wu, X. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.04194 · Cited by 1
Xu, F. (2015) · TSpace (University of Toronto) · Cited by 1
Quantum hashing is maximally secure against classical leakagePreprint
Huang, C., & Shi, Y. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1701.01091 · Cited by 1
Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends.Preprint
Ben-Aroya, A., Doron, D., & Ta‐Shma, A. (2018) · Electronic colloquium on computational complexity · Cited by 1
Deterministic Sparse Fourier Transform with an ell_infty GuaranteePreprint
Li, Y., & Nakos, V. (2019) · arXiv (Cornell University) · doi:10.4230/lipics.icalp.2020.77 · Cited by 1
Short seed extractors against quantum storagePreprint
Ta‐Shma, A. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0808.1994 · Cited by 1
Better short-seed quantum-proof extractorsPreprint
Ben-Aroya, A., & Ta‐Shma, A. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1004.3737 · Cited by 1
Explicit Designs and ExtractorsPreprint
Chattopadhyay, E., & Goodman, J. (2020) · arXiv (Cornell University) · Cited by 1
Chapter 8 Notes and References
Lőrinczi, J., Hiroshima, F., & Betz, V. (2011) · De Gruyter eBooks · doi:10.1515/9783110203738.455 · Cited by 1
Quantum-Resilient Randomness Extraction
Renner, R. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20728-0_5
Error correcting codes: local testing, list decoding, and applications
Zuckerman, D., & Patthak, A. C. (2007)
Randomness extractors and data storage
Gabizon, A., & Shaltiel, R. (2014) · IEEE Convention of Electrical and Electronics Engineers in Israel · doi:10.1109/eeei.2014.7005791
Deterministic Extractors for Independent-Symbol Sources
Lee, C.-J., Lu, C.-J., & Tsai, S. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2079012
Vadhan, S. (2010)
Random Query Answering with the Crowd
Virgilio, R. D., & Maccioni, A. (2015) · Journal on Data Semantics · doi:10.1007/s13740-015-0051-2
Multi-sources Randomness Extraction over Finite Fields and Elliptic CurvePreprint
Tchapgnouo, H. B., & Ciss, A. A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.00433
Tentative Collection of Reading Material
Goldreich, O. (2011)
Lecture 2: Pseudorandom Generators and Extractors
Dell, H., van Melkebeek, D., & Pappas, N. (2013)
The Computational Complexity of Randomness
Watson, T. W. (2013) · eScholarship (California Digital Library)
(2006) · I.B.Tauris eBooks · doi:10.5040/9780755625963.0007
A Modular Framework for Quantum-Proof Randomness Extractors
Liu, Y., Guo, J.-S., & Cui, J. (2016) · International Journal of Theoretical Physics · doi:10.1007/s10773-016-3137-1
Practical Issues in Quantum Cryptography
Xu, F. (2012) · TSpace (University of Toronto)
Two-sources randomness extractors in finite fields and in elliptic curves
Tchapgnouo, H. B., Ciss, A. A., Sow, D., & Kolyang, D. T. (2017) · Revue Africaine de la Recherche en Informatique et Mathématiques Appliquées · doi:10.46298/arima.1446
Set-Codes with Small Intersections and Small DiscrepanciesPreprint
Gabrys, R., Dau, S. H., Colbourn, C. J., & Milenković, O. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.05559
Invertible Extractors and Wiretap ProtocolsPreprint
Cheraghchi, M., Didier, F., & Shokrollahi, A. (2009) · arXiv (Cornell University)
Simple extractors via constructions of cryptographic pseudo-random generatorsPreprint
Zimand, M. (2005) · arXiv (Cornell University)
Randomness Extractors -- An Exposition
Dai, W. (2016) · Rose-Hulman Scholar (Rose–Hulman Institute of Technology)
On the use of randomness extractors for practical committee selection
Zheng, Z. (2020) · UVic’s Research and Learning Repository (University of Victoria)
Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors.
Cramer, R., Dodis, Y., Fehr, S., Padró, C., & Wichs, D. (2008)
Seed Protecting Extractors.Preprint
Cohen, G., Doron, D., & Samocha, S. (2020) · Electronic colloquium on computational complexity
Classical Computation in the Quantum World
Huang, J. (2019) · Deep Blue (University of Michigan)
A note on explicit constructions of designsPreprint
Liu, X., & Mubayi, D. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.05347
Private Weakly-Random Sequences from Human Heart Rate for Quantum Amplification
Stankiewicz, M., Horodecki, K., Sakarya, O., & Makowiec, D. (2021) · Entropy · doi:10.3390/e23091182
Zhang, J., & Zhang, Z. (2020) · Springer eBooks · doi:10.1007/978-981-15-8427-5_6
Metadata
- Authors
- Trevisan, L.
- Affiliations
- University of California, Berkeley (US)
- Corresponding author
- Luca Trevisan
- ORCID
- Luca Trevisan
- Venue
- Journal of the ACM
- Published
- 2001-07
- Volume
- 48
- Issue
- 4
- Pages
- 860-879
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W1967175855
- Cited by
- 324
- References
- 49
- Citations by year
- 2026: 7 · 2025: 7 · 2024: 10 · 2023: 9 · 2022: 16 · 2021: 8 · 2020: 25 · 2019: 14 · 2018: 9 · 2017: 13 · 2016: 17 · 2015: 9 · 2014: 16 · 2013: 16 · 2012: 21
- FWCI
- 9.54
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Journal of the ACM (publishedVersion)
- Archivio istituzionale della Ricerca - Bocconi (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Coding theory and cryptography
- Keywords
- extractors, pseudorandom generators, weak randomness, explicit constructions, error-correcting codes, randomness extraction, pseudorandomness
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
