research-article

Extractors for sumset sources

Authors:

Eshan Chattopadhyay,

Xin LiAuthors Info & Claims

STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

Pages 299 - 311

https://doi.org/10.1145/2897518.2897643

Published: 19 June 2016 Publication History

Abstract

We propose a new model of weak random sources which we call sumset sources. A sumset source X is the sum of C independent sources, with each source on n bits source having min-entropy k. We show that extractors for this class of sources can be used to give extractors for most classes of weak sources that have been studied previously, including independent sources, affine sources (which generalizes oblivious bit-fixing sources), small space sources, total entropy independent sources, and interleaved sources. This provides a unified approach for randomness extraction.

A known extractor for this class of sources, prior to our work, is the Paley graph function introduced by Chor and Goldreich, which works for the sum of 2 independent sources, where one has min-entropy at least 0.51n and the other has logarithmic min-entropy. To the best of our knowledge, the only other known construction is from the work of Kamp, Rao, Vadhan and Zuckerman, which can extract from the sum of exponentially many independent sources.

Our main result is an explicit extractor for the sum of C independent sources for some large enough constant C, where each source has polylogarithmic min-entropy. We then use this extractor to obtain improved extractors for other well studied classes of sources including small-space sources, affine sources and interleaved sources.

References

[1]

B. Barak, R. Impagliazzo, and A. Wigderson. Extracting randomness using few independent sources. SIAM J. Comput., 36(4):1095–1118, Dec. 2006.

Digital Library

[2]

B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson. Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. J. ACM, 57(4), 2010.

Digital Library

[3]

B. Barak, A. Rao, R. Shaltiel, and A. Wigderson. 2-source dispersers for n o(1) entropy, and Ramsey graphs beating the Frankl-Wilson construction. Annals of Mathematics, 176(3):1483–1543, 2012.

[4]

E. Ben-Sasson and S. Kopparty. Affine dispersers from subspace polynomials. SIAM J. Comput., 41(4):880–914, 2012.

[5]

E. Ben-Sasson and N. Zewi. From affine to two-source extractors via approximate duality. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 2011.

Digital Library

[6]

M. Blum. Independent unbiased coin flips from a correlated biased source ˜ Na finite state markov chain. Combinatorica, 6(2):97–108, 1986.

Digital Library

[7]

J. Bourgain. More on the sum-product phenomenon in prime fields and its applications. IJNT, 01(01):1–32, 2005.

[8]

J. Bourgain. On the construction of affine extractors. GAFA Geometric And Functional Analysis, 17(1):33–57, 2007.

[9]

E. Chattopadhyay. Explicit two-source extractors and resilient functions. In STOC, 2016.

Digital Library

[10]

E. Chattopadhyay, V. Goyal, and X. Li. Non-malleable extractors and codes, with their many tampered extensions. In STOC, 2016.

Digital Library

[11]

E. Chattopadhyay and D. Zuckerman. New extractors for interleaved sources. Technical Report TR15-151, ECCC, 2015.

[12]

B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17(2):230–261, 1988.

Digital Library

[13]

B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich, and R. Smolensky. The bit extraction problem of t-resilient functions (preliminary version). In FOCS, pages 396–407, 1985.

Digital Library

[14]

G. Cohen. Local correlation breakers and applications to three-source extractors and mergers. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, 2015.

Digital Library

[15]

E. Demenkov and A. S. Kulikov. An elementary proof of a 3n - o(n) lower bound on the circuit complexity of affine dispersers. In Proceedings of the 36th International Conference on Mathematical Foundations of Computer Science, MFCS’11, pages 256–265, Berlin, Heidelberg, 2011. Springer-Verlag.

Digital Library

[16]

Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Comput., 38:97–139, 2008.

Digital Library

[17]

Y. Dodis and D. Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. In STOC, pages 601–610, 2009.

Digital Library

[18]

S. Dziembowski and K. Pietrzak. Intrusion-resilient secret sharing. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’07, pages 227–237, Washington, DC, USA, 2007. IEEE Computer Society.

Digital Library

[19]

M. G. Find, A. Golovnev, E. Hirsch, and A. Kulikov. A better-than-3n lower bound for the circuit complexity of an explicit function. Technical Report TR15-166, ECCC, 2015.

[20]

A. Gabizon and R. Raz. Deterministic extractors for affine sources over large fields. Combinatorica, 28(4):415–440, 2008.

Digital Library

[21]

A. Gabizon, R. Raz, and R. Shaltiel. Deterministic extractors for bit-fixing sources by obtaining an independent seed. SIAM J. Comput., 36(4):1072–1094, 2006.

Digital Library

[22]

V. Guruswami, C. Umans, and S. P. Vadhan. Unbalanced expanders and randomness extractors from Parvaresh–Vardy codes. J. ACM, 56(4), 2009.

Digital Library

[23]

Y. Kalai, X. Li, and A. Rao. 2-source extractors under computational assumptions and cryptography with defective randomness. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pages 617–628, 2009.

Digital Library

[24]

Y. T. Kalai, X. Li, A. Rao, and D. Zuckerman. Network extractor protocols. In FOCS, pages 654–663, 2008.

Digital Library

[25]

J. Kamp, A. Rao, S. P. Vadhan, and D. Zuckerman. Deterministic extractors for small-space sources. Journal of Computer and System Sciences, 77:191–220, 2011.

Digital Library

[26]

J. Kamp and D. Zuckerman. Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. Siam Journal on Computing, 36:1231–1247, 2007.

Digital Library

[27]

X. Li. A new approach to affine extractors and dispersers. In Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on, pages 137–147, June 2011.

Digital Library

[28]

X. Li. Extractors for a constant number of independent sources with polylogarithmic min-entropy. In FOCS, pages 100–109, 2013.

Digital Library

[29]

X. Li. New independent source extractors with exponential improvement. In STOC, pages 783–792, 2013.

Digital Library

[30]

X. Li. Extractors for affine sources with polylogarithmic entropy. Technical Report TR15-121, ECCC, 2015.

[31]

X. Li. Improved constructions of two-source extractors. Technical Report TR15-125, ECCC, 2015.

[32]

X. Li. Three-source extractors for polylogarithmic min-entropy. In FOCS, 2015.

Digital Library

[33]

U. Maurer and S. Wolf. Privacy amplification secure against active adversaries. In Advances in Cryptology — CRYPTO ’97, volume 1294, pages 307–321, Aug. 1997.

Digital Library

[34]

N. Nisan and D. Zuckerman. Randomness is linear in space. J. Comput. Syst. Sci., 52(1):43–52, 1996.

Digital Library

[35]

A. Rao. Extractors for a constant number of polynomially small min-entropy independent sources. SIAM J. Comput., 39(1):168–194, 2009.

Digital Library

[36]

A. Rao. Extractors for low-weight affine sources. In CCC, 2009.

Digital Library

[37]

R. Raz. Extractors with weak random seeds. In STOC, pages 11–20, 2005.

Digital Library

[38]

R. Raz, O. Reingold, and S. Vadhan. Extracting all the randomness and reducing the error in Trevisan’s extractors. JCSS, 65(1):97–128, 2002.

Digital Library

[39]

R. Raz and A. Yehudayoff. Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. Journal of Computer and System Sciences, 77:167–190, 2011.

Digital Library

[40]

R. Shaltiel. Dispersers for affine sources with sub-polynomial entropy. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 247–256, 2011.

Digital Library

[41]

L. Trevisan. Extractors and pseudorandom generators. J. ACM, pages 860–879, 2001.

Digital Library

[42]

L. Trevisan and S. P. Vadhan. Extracting Randomness from Samplable Distributions. In IEEE Symposium on Foundations of Computer Science, pages 32–42, 2000.

Digital Library

[43]

E. Viola. Extractors for circuit sources. SIAM J. Comput., 43(2):655–672, 2014.

[44]

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.

[45]

A. Yehudayoff. Affine extractors over prime fields. Combinatorica, 31(2):245–256, 2011.

Digital Library

Cited By

Chattopadhyay ELiao J(2023)Hardness against Linear Branching Programs and MoreProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.9(1-27)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.9
Aggarwal DChung EObremski MRibeiro J(2023)On Secret Sharing, Randomness, and Random-less Reductions for Secret SharingTheory of Cryptography10.1007/978-3-031-22318-1_12(327-354)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-22318-1_12
Chattopadhyay E(2022)Recent Advances in Randomness ExtractionEntropy10.3390/e2407088024:7(880)Online publication date: 26-Jun-2022
https://doi.org/10.3390/e24070880
Show More Cited By

Index Terms

Extractors for sumset sources
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
  2. Probability and statistics
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Explicit two-source extractors and resilient functions
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

We explicitly construct an extractor for two independent sources on n bits, each with polylogarithmic min-entropy. Our extractor outputs one bit and has polynomially small error. The best previous extractor, by Bourgain, required each source to have ...
New extractors for interleaved sources
CCC '16: Proceedings of the 31st Conference on Computational Complexity

We study how to extract randomness from a C-interleaved source, that is, a source comprised of C independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields:

For some δ > 0, c > 0,...
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, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

June 2016

1141 pages

ISBN:9781450341325

DOI:10.1145/2897518

General Chair:
Daniel Wichs
Northeastern, USA
,
Program Chair:
Yishay Mansour
Tel Aviv

Copyright © 2016 ACM.

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]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 June 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '16

Sponsor:

SIGACT

STOC '16: Symposium on Theory of Computing

June 19 - 21, 2016

MA, Cambridge, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
172
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chattopadhyay ELiao J(2023)Hardness against Linear Branching Programs and MoreProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.9(1-27)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.9
Aggarwal DChung EObremski MRibeiro J(2023)On Secret Sharing, Randomness, and Random-less Reductions for Secret SharingTheory of Cryptography10.1007/978-3-031-22318-1_12(327-354)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-22318-1_12
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
Chattopadhyay EGoodman J(2022)Improved Extractors for Small-Space Sources2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00066(610-621)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00066
Chattopadhyay EGoodman JGoyal VLi XMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Extractors for adversarial sources via extremal hypergraphsProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384339(1184-1197)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384339
Chattopadhyay ELi X(2020)Non-malleable Codes, Extractors and Secret Sharing for Interleaved Tampering and Composition of TamperingTheory of Cryptography10.1007/978-3-030-64381-2_21(584-613)Online publication date: 9-Dec-2020
https://doi.org/10.1007/978-3-030-64381-2_21
Chattopadhyay ELi XHatami HMcKenzie PKing V(2017)Non-malleable codes and extractors for small-depth circuits, and affine functionsProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055483(1171-1184)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055483
Chattopadhyay EZuckerman DWichs DMansour Y(2016)Explicit two-source extractors and resilient functionsProceedings of the forty-eighth annual ACM symposium on Theory of Computing10.1145/2897518.2897528(670-683)Online publication date: 19-Jun-2016
https://dl.acm.org/doi/10.1145/2897518.2897528
Li X(2016)Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2016.26(168-177)Online publication date: Oct-2016
https://doi.org/10.1109/FOCS.2016.26

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 Table of Contents