Three XOR-lemmas – an exposition. (English) Zbl 1343.68112
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 248-272 (2011).
Summary: We provide an exposition of three lemmas that relate general properties of distributions over bit strings to the exclusive-or (xor) of values of certain bit locations.
The first XOR-Lemma, commonly attributed to U. V. Vazirani (1986), relates the statistical distance of a distribution from the uniform distribution over bit strings to the maximum bias of the xor of certain bit positions. The second XOR-Lemma, due to U. V. Vazirani [“Efficiency considerations in using semi-random sources”, in: Proceedings of the 19th annual ACM symposium on theory of computing, STOC 2007. New York, NY: ACM. 160–168 (1987; doi:10.1145/28395.28413)], is a computational analogue of the first. It relates the pseudorandomness of a distribution to the difficulty of predicting the xor of bits in particular or random positions. The third Lemma, due to the author and L. A. Levin [“A hard-core predicate for all one-way functions”, in: Proceedings of the 21th annual ACM symposium on theory of computing, STOC 1989. New York, NY: ACM. 25–32 (1989; doi:10.1145/73007.73010)], relates the difficulty of retrieving a string and the unpredictability of the xor of random bit positions. The most notable XOR Lemma – that is the so-called Yao XOR Lemma – is not discussed here.
We focus on the proofs of the aforementioned three lemma. Our exposition deviates from the original proofs, yielding proofs that are believed to be simpler, of wider applicability, and establishing somewhat stronger quantitative results. Credits for these improved proofs are due to several researchers.
For the entire collection see [Zbl 1220.68005].
The first XOR-Lemma, commonly attributed to U. V. Vazirani (1986), relates the statistical distance of a distribution from the uniform distribution over bit strings to the maximum bias of the xor of certain bit positions. The second XOR-Lemma, due to U. V. Vazirani [“Efficiency considerations in using semi-random sources”, in: Proceedings of the 19th annual ACM symposium on theory of computing, STOC 2007. New York, NY: ACM. 160–168 (1987; doi:10.1145/28395.28413)], is a computational analogue of the first. It relates the pseudorandomness of a distribution to the difficulty of predicting the xor of bits in particular or random positions. The third Lemma, due to the author and L. A. Levin [“A hard-core predicate for all one-way functions”, in: Proceedings of the 21th annual ACM symposium on theory of computing, STOC 1989. New York, NY: ACM. 25–32 (1989; doi:10.1145/73007.73010)], relates the difficulty of retrieving a string and the unpredictability of the xor of random bit positions. The most notable XOR Lemma – that is the so-called Yao XOR Lemma – is not discussed here.
We focus on the proofs of the aforementioned three lemma. Our exposition deviates from the original proofs, yielding proofs that are believed to be simpler, of wider applicability, and establishing somewhat stronger quantitative results. Credits for these improved proofs are due to several researchers.
For the entire collection see [Zbl 1220.68005].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 62E99 | Statistical distribution theory |
| 68P30 | Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) |
| 68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |
Keywords:
vector spaces; Kroniker and Fourier bases; pseudorandomness; space-bounded computation; one-way functions; hard-core predicates and functionsReferences:
| [1] | Alexi, W., Chor, B., Goldreich, O., Schnorr, C.P.: RSA and Rabin Functions: Certain Parts Are As Hard As the Whole. SIAM Journ. on Computing 1988, 194–209 (1984) · Zbl 0644.94011 |
| [2] | Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple Constructions of Almost k-wise Independent Random Variables. Journal of Random Structures and Algorithms 3(3), 289–304 (1992) · Zbl 0755.60002 · doi:10.1002/rsa.3240030308 |
| [3] | Babai, L., Nisan, N., Szegedy, M.: Multiparty protocols and logspace-hard pseudorandom sequences. In: 21st STOC, pp. 1–11 (1989) · doi:10.1145/73007.73008 |
| [4] | Blum, M., Micali, S.: How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits. SIAM Journ. on Computing 1984, 850–864 (1982); Preliminary version in 23rd FOCS 1982 · Zbl 0547.68046 |
| [5] | Chor, B., Friedmann, J., Goldreich, O., Hastad, J., Rudich, S., Smolansky, R.: The Bit Extraction Problem or t-Resilient Functions. In: Proc. of the 26th IEEE Symp. on Foundation Of Computer Science (FOCS), pp. 396–407 (1985) · doi:10.1109/SFCS.1985.55 |
| [6] | Erdos, P., Spenser, J.: Probabilistic Methods in Combinatorics. Academic Press, New York (1974) |
| [7] | Goldreich, O.: Foundation of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001) · Zbl 1007.94016 · doi:10.1017/CBO9780511546891 |
| [8] | Goldreich, O.: Foundation of Cryptography: Basic Applications. Cambridge University Press, Cambridge (2004) · Zbl 1068.94011 · doi:10.1017/CBO9780511721656 |
| [9] | Goldreich, O., Goldwasser, S., Micali, S.: How to Construct Random Functions. Jour. of the ACM 33(4), 792–807 (1986) · Zbl 0596.65002 · doi:10.1145/6490.6503 |
| [10] | Goldreich, O., Levin, L.A.: Hard-core Predicates for any One-Way Function. In: 21st STOC, pp. 25–32 (1989) |
| [11] | Goldreich, O., Nisan, N., Wigderson, A.: On Yao’s XOR-Lemma. In: Goldreich, O., et al.: Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 273–301. Springer, Heidelberg (2011) · Zbl 1304.68074 |
| [12] | Goldreich, O., Rubinfeld, R., Sudan, M.: Learning polynomials with queries: the highly noisy case. SIAM J. Discrete Math. 13(4), 535–570 (2000) · Zbl 0968.68063 · doi:10.1137/S0895480198344540 |
| [13] | Goldwasser, S., Micali, S.: Probabilistic Encryption. JCSS 28(2), 270–299 (1982); Preliminary version in 14th STOC 1982 · Zbl 0563.94013 |
| [14] | Kaliski Jr., B.S.: Elliptic Curves and Cryptography: A Pseudorandom Bit Generator and Other Tools, Ph.D. Thesis, LCS, MIT (1988) |
| [15] | Levin, L.A.: One-Way Function and Pseudorandom Generators. Combinatorica 7(4), 357–363 (1987); A preliminary version in 19th STOC 1985 · Zbl 0641.68061 · doi:10.1007/BF02579323 |
| [16] | Naor, J., Naor, M.: Small-bias Probability Spaces: Efficient Constructions and Applications. In: 22nd STOC, pp. 213–223 (1990) · Zbl 0776.60014 |
| [17] | Nisan, N.: Pseudorandom Generators for Space-Bounded Computations. In: 22nd STOC, pp. 204–212 (1990) · doi:10.1145/100216.100242 |
| [18] | Rabin, M.O.: Digitalized Signatures and Public Key Functions as Intractable as Factoring, MIT/LCS/TR-212 (1979) |
| [19] | Rivest, R., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Comm. ACM 21, 120–126 (1978) · Zbl 0368.94005 · doi:10.1145/359340.359342 |
| [20] | Vazirani, U.V.: Randomness, Adversaries and Computation, Ph.D. Thesis, EECS, UC Berkeley (1986) |
| [21] | Vazirani, U.V.: Efficiency Considerations in Using Semi-random Sources. In: Proc. 19th ACM Symp. on Theory of Computing, pp. 160–168 (1987) · doi:10.1145/28395.28413 |
| [22] | Vazirani, U.V., Vazirani, V.V.: Efficient and Secure Pseudo-Random Number Generation. In: Proc. 25th IEEE Symp. on Foundation of Computer Science, pp. 458–463 (1984) · Zbl 0579.65005 · doi:10.1109/SFCS.1984.715948 |
| [23] | Yao, A.C.: Theory and Applications of Trapdoor Functions. In: Proc. of the 23rd IEEE Symp. on Foundation of Computer Science, pp. 80–91 (1982) · doi:10.1109/SFCS.1982.45 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
