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 nonbinary sequences. We show that unlike the binary setup of Santha and Vazirani, deterministic randomness extraction in the generalized case is sometimes possible. In particular, if the adversary has access to
s “nondegenerate” dice that are
c-sided and can choose one die to throw based on the previous realizations of the dice, then deterministic randomness extraction is possible if
s<c. We present a necessary condition and a sufficient condition for the possibility of deterministic randomness extraction. These two conditions complement each other in the nondegenerate cases. Next, we turn to a distributed setting. In this setting the SV source consists of a random sequence of pairs
(a1,b1),(a2,b2),… distributed between two parties, where the first party receives
ai's and the second one receives
bi'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 (nondistributed) SV sources. This result generalizes results of Gács and Körner, and Witsenhausen about common randomness extraction from independently and identically distributed sources to adversarial sources.
A direct analysis of the task of randomness amplification from Santha-Vazirani sources using the violation of the chained Bell inequality is performed in terms of the convex combination of no-signaling boxes required to simulate quantum violation of the inequality. This analysis is used to find the exact threshold value of the initial randomness parameter from which perfect randomness can be extracted in the asymptotic limit of a large number of measurement settings. As a byproduct, we provide a tool for the analysis of randomness amplification protocols, namely a general characterization of the probability distributions of bits generated by Santha-Vazirani sources, which are shown to be mixtures of specific permutations of Bernoulli distributions with a parameter defined by the source.
We revisit the impossibility of a variety of cryptographic tasks including privacy and differential privacy with imperfect randomness. For traditional notions of privacy, such as security of encryption, commitment or secret sharing schemes, dramatic impossibility results are known [MP90,DOPS04] for several concrete sources R, including a (seemingly) very “nice and friendly” Santha-Vazirani (SV) source. Moreover, Bosley and Dodis [BD07] gave strong evidence that many traditional privacy tasks (e.g., encryption) inherently require an “extractable” source of randomness. The common interpretation of these negative results is that privacy is impossible even with “very structured” imperfect sources. Somewhat surprisingly, Dodis et al. [DLMV12] put a slight dent in this belief, by showing that non-trivial differential privacy is possible with the SV sources. This suggested a qualitative gap between traditional and differential privacy, and left open the question if differential privacy is possible with more realistic (i.e., less structured) sources than the SV sources. Motivated by solving this question, we introduce a new, modular framework for showing strong impossibility results for (either traditional or differential) privacy under a general imperfect source R. In particular, we introduce natural and easy-to-understand concepts of expressiveness and separability of a given imperfect source R, and show the following results: – Low levels of expressiveness generically imply strong impossibility results for both traditional and differential privacy. – Separability implies expressiveness; NON-separability is equivalent to “weak bit extraction”. – While the separability of some concrete (e.g., SV) sources R was implicitly known, we show new separability results for several important sources, including general “block sources”. As direct corollaries of these general results, we get the following corollaries: – Existing, but quantitatively improved, impossibility results for traditional privacy, but under a wider variety of sources R. – First impossibility results for differential privacy. Although, unsurprisingly, these results (barely) miss the highly structured SV sources, they come back extremely quickly once the source becomes slightly more realistic (e.g., a realistic “block source”). – Any imperfect source allowing (either traditional or differential) privacy admits a certain type of deterministic bit extraction. (This result is incomparable to the result of [BD07].) Overall, we believe our results provide an intuitive, modular and unified picture elucidating the (im)possibility of privacy with general imperfect sources.