  Constructions of locally decodable codes (LDCs) have one of two undesirable
properties: low rate or high locality (polynomial in the length of the
message). In settings where the encoder/decoder have already exchanged
cryptographic keys and the channel is a probabilistic polynomial time (PPT)
algorithm, it is possible to circumvent these barriers and design LDCs with
constant rate and small locality. However, the assumption that the
encoder/decoder have exchanged cryptographic keys is often prohibitive. We thus
consider the problem of designing explicit and efficient LDCs in settings where
the channel is slightly more constrained than the encoder/decoder with respect
to some resource e.g., space or (sequential) time. Given an explicit function
$f$ that the channel cannot compute, we show how the encoder can transmit a
random secret key to the local decoder using $f(\cdot)$ and a random oracle
$H(\cdot)$. This allows bootstrap from the private key LDC construction of
Ostrovsky, Pandey and Sahai (ICALP, 2007), thereby answering an open question
posed by Guruswami and Smith (FOCS 2010) of whether such bootstrapping
techniques may apply to LDCs in weaker channel models than just PPT algorithms.
Specifically, in the random oracle model we show how to construct explicit
constant rate LDCs with locality of polylog in the security parameter against
various resource constrained channels.
