×

zbMATH — the first resource for mathematics

On Yao’s XOR-lemma. (English) Zbl 1304.68074
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, 273-301 (2011).
Summary: A fundamental lemma of Yao states that computational weak-unpredictability of Boolean predicates is amplified when the results of several independent instances are XOR together. We survey two known proofs of Yao’s lemma and present a third alternative proof. The third proof proceeds by first proving that a function constructed by concatenating the values of the original function on several independent instances is much more unpredictable, with respect to specified complexity bounds, than the original function. This statement turns out to be easier to prove than the XOR-lemma. Using a result of Goldreich and Levin (1989) and some elementary observation, we derive the XOR-lemma.
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.)
94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Goldreich, O.: Foundation of Cryptography – Class Notes. Computer Science Department, Technion, Haifa, Israel (Spring 1989)
[2] Goldreich, O.: Foundation of Cryptography – Fragments of a Book, Available from ECCC (February 1995)
[3] Goldreich, O.: Foundation of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001) · Zbl 1007.94016 · doi:10.1017/CBO9780511546891
[4] Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge (2008) · Zbl 1154.68056 · doi:10.1017/CBO9780511804106
[5] Goldreich, O., Levin, L.A.: A Hard-Core Predicate for all One-Way Functions. In: 21st STOC, pp. 25–32 (1989) · doi:10.1145/73007.73010
[6] Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A Pseudorandom Generator from any One-way Function. SICOMP 28(4), 1364–1396 (1999); Combines papers of Impagliazzo et al. (21st STOC, 1989) and Håstad (22nd STOC, 1990) · Zbl 0940.68048 · doi:10.1137/S0097539793244708
[7] Impagliazzo, R.: See [8], which appeared after our first posting (1994) (manuscript)
[8] Impagliazzo, R.: Hard-core Distributions for Somewhat Hard Problems. In: 36th FOCS, pp. 538–545 (1995); This is a later version of [7] · Zbl 0938.68921
[9] Impagliazzo, R., Jaiswal, R., Kabanets, V.: Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. In: 47th FOCS, pp. 187–196 (2006) · Zbl 1200.68142 · doi:10.1109/FOCS.2006.13
[10] Impagliazzo, R., Jaiswal, R., Kabanets, V., Wigderson, A.: Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. 39(4), 1637–1665 (2010); Preliminary version in 40th STOC (2008) · Zbl 1206.68131 · doi:10.1137/080734030
[11] Impagliazzo, R., Wigderson, A.: P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In: 29th STOC, pp. 220–229 (1997) · Zbl 0962.68058
[12] Levin, L.A.: One-Way Functions and Pseudorandom Generators. Combinatorica 7(4), 357–363 (1987) · Zbl 0641.68061 · doi:10.1007/BF02579323
[13] Levin, L.A.: Average Case Complete Problems. SICOMP 15, 285–286 (1986) · Zbl 0589.68032 · doi:10.1137/0215020
[14] Nisan, N., Rudich, S., Saks, M.: Products and Help Bits in Decision Trees. In: 35th FOCS, pp. 318–329 (1994) · Zbl 0918.68026 · doi:10.1109/SFCS.1994.365683
[15] Nisan, N., Wigderson, A.: Hardness vs Randomness. JCSS 49(2), 149–167 (1994) · Zbl 0821.68057
[16] Viola, E., Wigderson, A.: Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. Theory of Computing 4(1), 137–168 (2008); Preliminary version in IEEE Conf. on Comput. Complex. (2007) · Zbl 1213.68321 · doi:10.4086/toc.2008.v004a007
[17] Yao, A.C.: Theory and Application of Trapdoor Functions. In: 23rd FOCS, 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.