Input locality and hardness amplification

DOI10.1007/s00145-011-9117-yzbMath1291.94059OpenAlexW2031699542MaRDI QIDQ1946597

Alon Rosen, Andrej Bogdanov

Publication date: 15 April 2013

Published in: Journal of Cryptology (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.190.4593

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items (4)

Expander-based cryptography meets natural proofs ⋮ A dichotomy for local small-bias generators ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Expander-Based Cryptography Meets Natural Proofs

Cites Work

• Unnamed Item
• The computational complexity of universal hashing
• Public-key cryptography from different assumptions
• Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
• Cryptography with Constant Input Locality
• On the Security of Goldreich’s One-Way Function
• On the Existence of Pseudorandom Generators
• The rank of sparse random matrices over finite fields
• Theory of Cryptography
• On the Power of the Randomized Iterate
• Noise-tolerant learning, the parity problem, and the statistical query model
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Input locality and hardness amplification