On Yao’s XOR-Lemma

DOI10.1007/978-3-642-22670-0_23zbMath1304.68074OpenAlexW2294870549MaRDI QIDQ3088189

Noam Nisan, Avi Wigderson, Oded Goldreich

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_23

zbMATH Keywords

one-way functionsdirect product lemmahard-core predicateshard-core regionsYao's XOR lemma

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Statistical distribution theory (62E99) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (34)

The Range of Topological Effects on Communication ⋮ A strong direct product theorem for quantum query complexity ⋮ Improved hardness amplification in NP ⋮ Derandomized parallel repetition theorems for free games ⋮ Nonuniform Indistinguishability and Unpredictability Hardcore Lemmas: New Proofs and Applications to Pseudoentropy ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ Hardness amplification within NP against deterministic algorithms ⋮ Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Candidate trapdoor claw-free functions from group actions with applications to quantum protocols ⋮ A tight computational indistinguishability bound for product distributions ⋮ Query complexity in errorless hardness amplification ⋮ A note on the relation between XOR and selective XOR lemmas ⋮ Distributed Merkle's puzzles ⋮ Unnamed Item ⋮ Magic Adversaries Versus Individual Reduction: Science Wins Either Way ⋮ The value of help bits in randomized and average-case complexity ⋮ Parallel and Concurrent Security of the HB and HB +  Protocols ⋮ Basing Weak Public-Key Cryptography on Strong One-Way Functions ⋮ Degradation and Amplification of Computational Hardness ⋮ Hardness amplification within NP ⋮ Parallel and concurrent security of the HB and \(HB^{+}\) protocols ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Upper and Lower Bounds on the Power of Advice ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ Query Complexity in Errorless Hardness Amplification ⋮ Three XOR-Lemmas — An Exposition ⋮ Weak Oblivious Transfer from Strong One-Way Functions ⋮ Advice Lower Bounds for the Dense Model Theorem ⋮ Chernoff-type direct product theorems ⋮ A Hardcore Lemma for Computational Indistinguishability: Security Amplification for Arbitrarily Weak PRGs with Optimal Stretch ⋮ Randomness vs time: Derandomization under a uniform assumption ⋮ Direct Sum Testing ⋮ Average-case rigidity lower bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• One way functions and pseudorandom generators
• Hardness vs randomness
• Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification
• Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
• Average Case Complete Problems
• Products and Help Bits in Decision Trees
• A Pseudorandom Generator from any One-way Function
• Foundations of Cryptography
• Computational Complexity

This page was built for publication: On Yao’s XOR-Lemma