  Error-correcting codes that admit local decoding and correcting algorithms
have been the focus of much recent research due to their numerous theoretical
and practical applications. An important goal is to obtain the best possible
tradeoffs between the number of queries the algorithm makes to its oracle (the
locality of the task), and the amount of redundancy in the encoding (the
information rate).
  In Hamming's classical adversarial channel model, the current tradeoffs are
dramatic, allowing either small locality, but superpolynomial blocklength, or
small blocklength, but high locality. However, in the computationally bounded,
adversarial channel model, proposed by Lipton (STACS 1994), constructions of
locally decodable codes suddenly exhibit small locality and small blocklength,
but these constructions require strong trusted setup assumptions e.g.,
Ostrovsky, Pandey and Sahai (ICALP 2007) construct private locally decodable
codes in the setting where the sender and receiver already share a symmetric
key.
  We study variants of locally decodable and locally correctable codes in
computationally bounded, adversarial channels, in a setting with no public-key
or private-key cryptographic setup. The only setup assumption we require is the
selection of the public parameters (seed) for a collision-resistant hash
function. Specifically, we provide constructions of relaxed locally correctable
and relaxed locally decodable codes over the binary alphabet, with constant
information rate, and poly-logarithmic locality.
  Our constructions, which compare favorably with their classical analogues in
the computationally unbounded Hamming channel, crucially employ
collision-resistant hash functions and local expander graphs, extending ideas
from recent cryptographic constructions of memory-hard functions.
