Three XOR-Lemmas — An Exposition

DOI10.1007/978-3-642-22670-0_22zbMath1343.68112OpenAlexW2231779562MaRDI QIDQ3088188

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_22

zbMATH Keywords

vector spacespseudorandomnessone-way functionsspace-bounded computationhard-core predicates and functionsKroniker and Fourier bases

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (14)

Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN ⋮ The Range of Topological Effects on Communication ⋮ A dichotomy for local small-bias generators ⋮ Extractors for varieties ⋮ On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions ⋮ On secret sharing, randomness, and random-less reductions for secret sharing ⋮ Affine extractors over prime fields ⋮ Improved Extractors for Recognizable and Algebraic Sources ⋮ Improving the Hadamard extractor ⋮ QUAD: A Practical Stream Cipher with Provable Security ⋮ Optimal Amplification of Noisy Leakages ⋮ Placing conditional disclosure of secrets in the communication complexity universe ⋮ Pseudorandom generators from regular one-way functions: new constructions with improved parameters ⋮ Leakage-resilient key exchange and two-seed extractors

Cites Work

• Unnamed Item
• Unnamed Item
• Probabilistic encryption
• One way functions and pseudorandom generators
• Learning Polynomials with Queries: The Highly Noisy Case
• On Yao’s XOR-Lemma
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• RSA and Rabin Functions: Certain Parts are as Hard as the Whole
• Simple Constructions of Almost k-wise Independent Random Variables
• A method for obtaining digital signatures and public-key cryptosystems
• Foundations of Cryptography
• Foundations of Cryptography

This page was built for publication: Three XOR-Lemmas — An Exposition