Abstract
A Santha-Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible. In this paper, we study the generalization of SV sources for non-binary sequences. We show that unlike the binary case, deterministic randomness extraction in the generalized case is sometimes possible. We present a necessary condition and a sufficient condition for the possibility of deterministic randomness extraction. These two conditions coincide in “non-degenerate” cases.
Next, we turn to a distributed setting. In this setting the SV source consists of a random sequence of pairs \((a_1, b_1), (a_2, b_2), \ldots \) distributed between two parties, where the first party receives \(a_i\)’s and the second one receives \(b_i\)’s. The goal of the two parties is to extract common randomness without communication. Using the notion of maximal correlation, we prove a necessary condition and a sufficient condition for the possibility of common randomness extraction from these sources. Based on these two conditions, the problem of common randomness extraction essentially reduces to the problem of randomness extraction from (non-distributed) SV sources. This result generalizes results of Gács and Körner, and Witsenhausen about common randomness extraction from i.i.d. sources to adversarial sources.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Austrin, P., Chung, K.-M., Mahmoody, M., Pass, R., Seth, K.: On the impossibility of cryptography with tamperable randomness. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 462–479. Springer, Heidelberg (2014)
Beigi, S., Etesami, O., Gohari, A.: Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources (2014). arXiv:1412.6641
Beigi, S., Tse, D.: under preparation
Berger, T.: The source coding game. IEEE Trans. on Information Theory IT–17(1), 71–76 (1971)
Blum, M.: Independent unbiased coin flips from a correlated biased source - a finite state Markov chain. Combinatorica 6(2), 97–108 (1986)
Bourgain, J.: More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory (2005)
Bourgain, J.: On the construction of affine extractors. Geometric And Functional Analysis 17(1), 33–57 (2007)
Chor, B., Goldreich, O., Håstad, J., Freidmann, J., Rudich, S., Smolensky, R.: The bit extraction problem of t-resilient functions. In: Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pp. 396–407 (1985)
Chor, B., Goldreich, O.: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity. SIAM J. Comput. 17(2), 230–261 (1988)
Dobrusin, R.L.: Individual methods for transmission of information for discrete channels without memory and messages with independent components. Sov. Math. 4, 253–256 (1963)
Dvir, Z.: Extractors for varieties. Computational Complexity 21(4), 515–572 (2012)
Dvir, Z., Gabizon, A., Wigderson, A.: Extractors and rank extractors for polynomial sources. In: FOCS 2007: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 52–62 (2007)
Dobrusin, R.L.: Unified methods of optimal quantizing of messages. Sov. Math. 4, 284–292 (1963)
Fischer, M.J., Lynch, N.A.: A lower bound for the time to assure interactive consistency. Information Processing Letters 14, 183–186 (1982)
Gács, P., Körner, J.: Common information is far less than mutual information. Problems of Control and Information Theory 2(2), 119–162 (1972)
Gabizon, A., Raz, R.: Deterministic extractors for affine sources over large fields. In: Proceedings of the 46th FOCS, pp. 407–418 (2005)
Kamp, J., Rao, A., Vadhan, S., Zuckerman, D.: Deterministic extractors for small-space sources. In: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 691–700 (2006)
Nisan, N., Zuckerman, D.: Randomness is Linear in Space. Journal of Computer and System Sciences 52(1), 43–52 (1996)
Rabin, M.O.: Randomized byzantine generals. In: Proceedings of the 24th Annual Symposium on Foundations of Computer Science, pp. 403–409 (1983)
Rao, A.: Extractors for a constant number of polynomially small min-entropy independent sources. In: Proceedings of the 38th STOC, pp. 497–506 (2006)
Reingold, O., Vadhan, S., Wigderson, A.: A note on extracting randomness from Santha-Vazirani sources. Unpublished manuscript (2004)
Palaiyanur, H., Chang, C., Sahai, A.: Lossy compression of active sources. In: IEEE International Symposium on Information Theory, pp. 1977–1981 (2008)
Santha, M., Vazirani, U.: Generating quasi-random sequences from slightly-random sources. In: Proceedings of Symposium on the Foundations of Computer Science (1984). Jourdnal of Computer and System Sciences, 33(1), 75–87 (1986)
Vazirani, U.V.: Efficiency considerations in using semi-random sources. In: Proceedings of the Nineteenth STOC, pp. 160–168 (1987)
Vazirani, U.V., Vazirani, V.V.: Random polynomial time is equal to slightly-random polynomial time. In: Proc. 26th Annual IEEE Symposium on the Foundations of Computer Science, pp. 417–428 (1985)
Vazirani, U.V., Vazirani, V.V.: Sampling a population with a single semi-random source. In: Proc. 6th FST & TCS Conf. (1986)
Vadhan, S.: Pseudorandomness. Now Publishers (2012)
von Neumann, J.: Various techniques used in connection with random digits. Applied Math Series 12, 36–38 (1951)
Witsenhausen, H.S.: On sequences of pairs of dependent random variables. SIAM Journal on Applied Mathematics 28(1), 100–113 (1975)
Yao, A.C.: Some Complexity Questions Related to Distributed Computing. In: Proc. of 11th STOC, vol. 14, pp. 209–213 (1979)
Zuckerman, D.: Randomness-optimal oblivious sampling. Random Structures and Algorithms 11, 345–367 (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beigi, S., Etesami, O., Gohari, A. (2015). Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_12
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)