research-article

Guest Column: A Recipe for Constructing Two-Source Extractors

Author:

Eshan ChattopadhyayAuthors Info & Claims

ACM SIGACT News, Volume 51, Issue 2

Pages 38 - 57

https://doi.org/10.1145/3406678.3406688

Published: 16 June 2020 Publication History

Abstract

Randomness is a valuable resource in computation. Randomness is used to run various Monte Carlo simulations of complex systems such as the stock market or weather prediction systems. Various randomized algorithms have been discovered that often vastly outperform known deterministic counterparts (see [MR10] for examples). Cryptography is another area that crucially relies on access to random bits, and it is known that various basic cryptographic primitives fail to be secure if the quality of the randomness used is poor [DOPS04]. However natural sources of randomness are typically defective. This leads to the following basic question: \Can we efficiently produce truly random bits given access to defective sources of randomness?"

References

[1]

[AGM03] Noga Alon, Oded Goldreich, and Yishay Mansour. Almost k-wise independence versus k-wise independence. Information Processing Letters, 88(3):107{110, 2003.

Digital Library

[2]

[AL93] Mikl_os Ajtai and Nathan Linial. The inuence of large coalitions. Combinatorica, 13(2):129{145, 1993.

[3]

[BACD+18] Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, and Amnon Ta-Shma. A new approach for constructing low-error, two-source extractors. In 33rd Computational Complexity Conference (CCC 2018). Schloss Dagstuhl-Leibniz- Zentrum fuer Informatik, 2018.

[4]

[BACDTS19] Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. Two-source condensers with low error and small entropy gap via entropy-resilient functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.

[5]

[BADTS16] Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. Explicit two-source extractors for near-logarithmic min-entropy. In Electronic Colloquium on Computational Complexity (ECCC), volume 23, page 88, 2016.

[6]

[BBCM95] Charles H Bennett, Gilles Brassard, Claude Cr_epeau, and Ueli M Maurer. Generalized privacy ampli_cation. IEEE Transactions on Information Theory, 41(6):1915{ 1923, 1995.

[7]

[BBR88] Charles H Bennett, Gilles Brassard, and Jean-Marc Robert. Privacy ampli_cation by public discussion. SIAM journal on Computing, 17(2):210{229, 1988.

[8]

[BIW06] Boaz Barak, Russell Impagliazzo, and Avi Wigderson. Extracting randomness using few independent sources. SIAM Journal on Computing, 36(4):1095{1118, 2006.

Digital Library

[9]

[Blu86] Manuel Blum. Independent unbiased coin ips from a correlated a _nite state Markov chain. Combinatorica, 6(2):97{108, 1986.

Digital Library

[10]

[BOL85] Michael Ben-Or and Nathan Linial. Collective coin ipping, robust voting schemes and minima of Banzhaf values. In 26th Annual Symposium on Foundations of Com- puter Science (FOCS), pages 408{416. IEEE, 1985.

[11]

[Bou05] Jean Bourgain. More on the sum-product phenomenon in prime _elds and its applications. International Journal of Number Theory, 1(01):1{32, 2005.

[12]

[Bra10] Mark Braverman. Polylogarithmic independence fools AC0 circuits. Journal of the ACM (JACM), 57(5):1{10, 2010.

[13]

[CG88] Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):230{ 261, 1988.

Digital Library

[14]

[CGL16] Eshan Chattopadhyay, Vipul Goyal, and Xin Li. Non-malleable extractors and codes, with their many tampered extensions. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 285{298, 2016.

Digital Library

[15]

[CL16] Eshan Chattopadhyay and Xin Li. Explicit non-malleable extractors, multi-source extractors, and almost optimal privacy ampli_cation protocols. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 158{167. IEEE, 2016.

[16]

[Coh16a] Gil Cohen. Local correlation breakers and applications to three-source extractors and mergers. SIAM Journal on Computing, 45(4):1297{1338, 2016.

[17]

[Coh16b] Gil Cohen. Making the most of advice: New correlation breakers and their applications. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 188{196. IEEE, 2016.

[18]

[Coh16c] Gil Cohen. Non-malleable extractors { New tools and improved constructions. In 31st Conference on Computational Complexity (CCC 2016). Schloss Dagstuhl-Leibniz- Zentrum fuer Informatik, 2016.

[19]

[Coh17] Gil Cohen. Towards optimal two-source extractors and ramsey graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1157{ 1170, 2017.

Digital Library

[20]

[Coh19] Gil Cohen. Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs. SIAM Journal on Computing, pages STOC16{30{STOC16{67, 2019.

Digital Library

[21]

[CRS14] Gil Cohen, Ran Raz, and Gil Segev. Nonmalleable extractors with short seeds and applications to privacy ampli_cation. SIAM Journal on Computing, 43(2):450{476, 2014.

[22]

[CZ19] Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. Annals of Mathematics, 189(3):653{705, 2019.

[23]

[DKSS13] Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan. Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. SIAM Journal on Computing, 42(6):2305{2328, 2013.

[24]

[DLWZ14] Yevgeniy Dodis, Xin Li, Trevor D Wooley, and David Zuckerman. Privacy ampli_cation and nonmalleable extractors via character sums. SIAM Journal on Computing, 43(2):800{830, 2014.

[25]

[DOPS04] Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, and Amit Sahai. On the (im)possibility of cryptography with imperfect randomness. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 196{205. IEEE, 2004.

[26]

[DP07] Stefan Dziembowski and Krzysztof Pietrzak. Intrusion-resilient secret sharing. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 227{237. IEEE, 2007.

[27]

[DW09] Yevgeniy Dodis and Daniel Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. In Proceedings of the forty-_rst annual ACM sym- posium on Theory of computing, pages 601{610, 2009.

Digital Library

[28]

[DW11] Zeev Dvir and Avi Wigderson. Kakeya sets, new mergers, and old extractors. SIAM Journal on Computing, 40(3):778{792, 2011.

Digital Library

[29]

[Erd47] P. Erd}os. Some remarks on the theory of graphs. Bull. Amer. Math. Soc., 53(4):292{ 294, 04 1947.

[30]

[GUV09] Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced expanders and randomness extractors from Parvaresh{Vardy codes. Journal of the ACM (JACM), 56(4):1{34, 2009.

[31]

[Kar71] A.A. Karatsuba. On a certain arithmetic sum. Soviet Math Dokl., 12, 1172--1174, 1971.

[32]

[Kar91] AA Karatsuba. The distribution of values of Dirichlet characters on additive sequences. In Doklady Acad. Sci. USSR, volume 319, pages 543{545, 1991.

[33]

[KKL89] Je_ Kahn, Gil Kalai, and Nathan Linial. The inuence of variables on Boolean functions. Citeseer, 1989.

[34]

[Lew19] Mark Lewko. An explicit two-source extractor with min-entropy rate near 4=9. Math- ematika, 65(4):950{957, 2019.

[35]

[Li11] Xin Li. Improved constructions of three source extractors. In 2011 IEEE 26th Annual Conference on Computational Complexity, pages 126{136. IEEE, 2011.

[36]

[Li13] Xin Li. Extractors for a constant number of independent sources with polylogarithmic min-entropy. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 100{109. IEEE, 2013.

[37]

[Li15a] Xin Li. Non-malleable condensers for arbitrary min-entropy, and almost optimal protocols for privacy ampli_cation. In Theory of Cryptography Conference, pages 502{531. Springer, 2015. [Li15b] Xin Li. Three-source extractors for polylogarithmic min-entropy. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 863{882. IEEE, 2015.

[38]

[Li16] Xin Li. Improved two-source extractors, and a_ne extractors for polylogarithmic entropy. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 168{177. IEEE, 2016.

[39]

[Li17] Xin Li. Improved non-malleable extractors, non-malleable codes and independent source extractors. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1144{1156, 2017.

Digital Library

[40]

[Li19] Xin Li. Non-malleable extractors and non-malleable codes: Partially optimal constructions. In 34th Computational Complexity Conference, CCC 2019, July 18--20, 2019, New Brunswick, NJ, USA, pages 28:1{28:49, 2019.

[41]

[LRVW03] Chi-Jen Lu, Omer Reingold, Salil Vadhan, and Avi Wigderson. Extractors: Optimal up to constant factors. In Proceedings of the thirty-_fth annual ACM symposium on Theory of computing, pages 602{611, 2003.

[42]

[Mau92] Ueli M Maurer. Protocols for secret key agreement by public discussion based on common information. In Annual International Cryptology Conference, pages 461{ 470. Springer, 1992.

[43]

[Mek17] Raghu Meka. Explicit resilient functions matching Ajtai-Linial. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1132{1148. SIAM, 2017.

[44]

[MR10] Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Chapman & Hall/CRC, 2010.

Digital Library

[45]

[MU02] Elchanan Mossel and Christopher Umans. On the complexity of approximating the VC dimension. Journal of Computer and System Sciences, 65(4):660{671, 2002.

Digital Library

[46]

[MW97] Ueli Maurer and Stefan Wolf. Privacy ampli_cation secure against active adversaries. In Annual International Cryptology Conference, pages 307{321. Springer, 1997.

[47]

[NZ96] Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43{52, 1996.

Digital Library

[48]

[Ram30] Frank P. Ramsey. On a problem of formal logic. Proceedings of the London Mathe- matical Society, Series 2, 30:264{286, 1930.

[49]

[Rao09] Anup Rao. Extractors for low-weight a_ne sources. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 95{101. IEEE, 2009.

[50]

[Raz05] Ran Raz. Extractors with weak random seeds. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 11{20, 2005.

Digital Library

[51]

[Sha04] Ronen Shaltiel. Recent developments in explicit constructions of extractors. In Current Trends in Theoretical Computer Science: The Challenge of the New Century, Vol. 1: Algorithms and Complexity, pages 189{228. World Scienti_c, 2004. [SV86] Miklos Santha and Umesh V Vazirani. Generating quasi-random sequences from semi-random sources. Journal of computer and system sciences, 33(1):75{87, 1986.

[52]

[Tre01] Luca Trevisan. Extractors and pseudorandom generators. Journal of the ACM, 48(4):860{879, 2001.

Digital Library

[53]

[Uma99] Christopher Umans. Hardness of approximating _p 2 minimization problems. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 465{474. IEEE, 1999.

[54]

[Vad12] Salil P Vadhan. Pseudorandomness. Foundations and Trends R in Theoretical Com- puter Science, 7(1{3):1{336, 2012.

[55]

[Vio14] Emanuele Viola. Extractors for circuit sources. SIAM Journal on Computing, 43(2):655{672, 2014.

[56]

[vN51] J. von Neumann. Various techniques used in connection with random digits. Applied Math Series, 12:36{38, 1951. Notes by G.E. Forsythe, National Bureau of Standards. Reprinted in Von Neumann's Collected Works, 5:768--770, 1963.

[57]

[WZ93] Avi Wigderson and David Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications. In Proceedings of the twenty-_fth annual ACM symposium on Theory of computing, pages 245{251, 1993.

Digital Library

[58]

[Zuc90] David Zuckerman. General weak random sources. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 534{543. IEEE, 1990.

[59]

[Zuc96] David Zuckerman. On unapproximable versions of NP-complete problems. SIAM Journal on Computing, 25(6):1293{1304, 1996.

Digital Library

[60]

[Zuc97] David Zuckerman. Randomness-optimal oblivious sampling. Random Structures & Algorithms, 11(4):345{367, 1997.

[61]

[Zuc06] David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 681{690, 2006.

Digital Library

Cited By

Chattopadhyay E(2022)Recent Advances in Randomness ExtractionEntropy10.3390/e2407088024:7(880)Online publication date: 26-Jun-2022
https://doi.org/10.3390/e24070880
Chattopadhyay ELiao JLeonardi SGupta A(2022)Extractors for sum of two sourcesProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3519963(1584-1597)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3519963
Goldreich OWigderson A(2022)Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00035(269-275)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00035

Guest Column: A Recipe for Constructing Two-Source Extractors
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic reasoning algorithms
2. Theory of computation

Recommendations

Extractors with weak random seeds
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing
We show how to extract random bits from two or more independent weak random sources in cases where only one source is of linear min-entropy and all other sources are of logarithmic min-entropy. Our main results are as follows:
- A long line of research, ...
Guest column: from randomness extraction to rotating needles

The finite field Kakeya problem deals with the way lines in different directions can overlap in a vector space over a finite field. This problem came up in the study of certain Euclidean problems and, independently, in the search for explicit randomness ...
Pseudo-Random Pattern Generator Design for Column-Matching BIST
DSD '07: Proceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools

This paper discusses possibilities for a choice of a pseudorandom pattern generator that is to be used in combination with the column-matching based built-in self-test design method. The pattern generator should be as small as possible, whereas patterns ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGACT News

ACM SIGACT News Volume 51, Issue 2

June 2020

85 pages

ISSN:0163-5700

DOI:10.1145/3406678

Editor:
Stephen Fenner
University of South Carolina

Issue’s Table of Contents

Copyright © 2020 Copyright is held by the owner/author(s).

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 June 2020

Published in SIGACT Volume 51, Issue 2

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
108
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)4

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chattopadhyay E(2022)Recent Advances in Randomness ExtractionEntropy10.3390/e2407088024:7(880)Online publication date: 26-Jun-2022
https://doi.org/10.3390/e24070880
Chattopadhyay ELiao JLeonardi SGupta A(2022)Extractors for sum of two sourcesProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3519963(1584-1597)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3519963
Goldreich OWigderson A(2022)Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00035(269-275)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00035

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents