Cryptography with constant input locality

DOI10.1007/s00145-009-9039-0zbMath1183.94018OpenAlexW1993729573MaRDI QIDQ1037233

Yuval Ishai, Eyal Kushilevitz, Benny Applebaum

Publication date: 13 November 2009

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

Full work available at URL: https://doi.org/10.1007/s00145-009-9039-0

zbMATH Keywords

cryptography with low complexityhardness of decoding random linear codeinput localityNC\(^0\)

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Cryptography (94A60) Theory of error-correcting codes and error-detecting codes (94B99) Authentication, digital signatures and secret sharing (94A62)

Related Items (8)

Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN ⋮ A dichotomy for local small-bias generators ⋮ Reusable Two-Round MPC from LPN ⋮ Locally computable UOWHF with linear shrinkage ⋮ CPA/CCA2-secure PKE with squared-exponential DFR from low-noise LPN ⋮ TinyKeys: a new approach to efficient multi-party computation ⋮ Breaking the circuit size barrier for secure computation under quasi-polynomial LPN ⋮ Cryptography with constant input locality

Uses Software

• McEliece

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cryptography with constant input locality
• Probabilistic encryption
• One-way functions and circuit complexity
• Random oracles separate PSPACE from the polynomial-time hierarchy
• Optimization, approximation, and complexity classes
• Synthesizers and their application to the parallel construction of pseudo-random functions
• McEliece public key cryptosystems using algebraic-geometric codes
• Computationally private randomizing polynomials and their applications
• Efficient cryptographic schemes provably as secure as subset sum
• On the learnability of discrete distributions
• A minimal model for secure computation (extended abstract)
• Candidate One-Way Functions Based on Expander Graphs
• Constant depth circuits, Fourier transform, and learnability
• Proof verification and the hardness of approximation problems
• Efficient noise-tolerant learning from statistical queries
• Complete characterization of security notions for probabilistic private-key encryption
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Parallel and Concurrent Security of the HB and HB +  Protocols
• On Pseudorandom Generators with Linear Stretch in NC0
• Probabilistic checking of proofs
• Coin flipping by telephone a protocol for solving impossible problems
• On the inherent intractability of certain coding problems (Corresp.)
• A Pseudorandom Generator from any One-way Function
• On the Existence of Pseudorandom Generators
• Foundations of Cryptography
• Nonmalleable Cryptography
• Foundations of Cryptography
• Authenticating Pervasive Devices with Human Protocols
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• On ε‐biased generators in NC⁰
• The complexity of theorem-proving procedures
• Cryptography in $NC^0$
• Theory of Cryptography
• Noise-tolerant learning, the parity problem, and the statistical query model
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: Cryptography with constant input locality