Relaxed Locally Correctable Codes in Computationally Bounded
Channels

arXiv:1803.05652v1 [] 15 Mar 2018

Jeremiah Blocki∗

Venkata Gandikota†

Elena Grigorescu‡

Samson Zhou§

March 16, 2018

Abstract
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. The
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. The first such constructions are due to Ostrovsky, Pandey and Sahai
(ICALP 2007) who build private locally decodable codes under the assumption that one-way
functions exist, and in the setting where the sender and receiver share a private key.
We study variants of locally decodable and locally correctable codes in computationally
bounded, adversarial channels, under the much weaker assumption that collision-resistant hash
functions exist, and with no public-key or private-key cryptographic setup. 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 compare favorably with existing schemes built under much stronger cryptographic assumptions, and
with their classical analogues in the computationally unbounded, Hamming channel.
Our constructions crucially employ collision-resistant hash functions and local expander
graphs, extending ideas from recent cryptographic constructions of memory-hard functions.

1

Introduction

Classically, an error-correcting code is a tuple (Enc, Dec) of encoding and decoding algorithms employed by a sender to encode messages, and by a receiver to decode them, after potential corruption
by a noisy channel during transmission. Specifically, the sender encodes a message m of k symbols
∗

Department of Computer Science, Purdue University, West Lafayette, IN. Email: jblocki@purdue.edu.
Department of Computer Science, Johns Hopkins University, Baltimore, MD. Email: gv@jhu.edu.
‡
Department of Computer Science, Purdue University, West Lafayette, IN. Research supported by NSF CCF1649515. Email: elena-g@purdue.edu.
§
Department of Computer Science, Purdue University, West Lafayette, IN. Research supported in part by NSF
CCF-1649515. Email: samsonzhou@gmail.com.
†

1

from an alphabet Σ into a codeword c of block-length n consisting of symbols over the same alphabet, via Enc : Σk → Σn . The receiver uses Dec : Σn → Σk to recover the message from a received
word w ∈ Σn , a corrupted version of some Enc(m). Codes over the binary alphabet Σ = {0, 1}
are preferred in practice. The quantities of interest in designing classical codes are the information
rate, defined as k/n, and the error rate, which is the tolerable fraction of errors in the received
word. Codes with both large information rate and large error rate are most desirable.
In modern uses of error-correcting codes, one may only need to recover small portions of the
message, such as a single bit. In such settings, the decoder may not need to read the entire received
word w ∈ Σn , but only read a few bits of it. Given an index i ∈ [n] and oracle access to w, a
local decoder must make only q = o(n) queries into w, and output the bit mi . Codes that admit
such fast decoders are called locally decodable codes (LDCs) [KT00, STV99]. The parameter q is
called the locality of the decoder. A related notion is that of locally correctable codes (LCCs). LCCs
are codes for which the local decoder with oracle access to w must output bits of the codeword
c, instead of bits of the message m. LDCs and LCCs have widespread applications in many areas
of theoretical computer science, including private information retrieval, probabilistically checkable
proofs, self-correction, fault-tolerant circuits, hardness amplification, and data structures (e.g.,
[BFLS91, LFKN92, BLR93, BK95, CKGS98, CGdW13, ALRW17]). See surveys [Tre04, Gas04].
However, constructions of such codes suffer from apparently irreconcilable tension between locality
and rate: existing codes with constant locality have slightly subexponential blocklength [Yek08,
Efr12, DGY11], and codes of linear blocklength have slightly subpolynomial query complexity
[KMRS17]. See surveys by Yekhanin [Yek12] and by Kopparty and Saraf [KS16].
Ben-Sasson et al. [BGH+ 06] propose the notion of relaxed locally decodable codes (RLDCs) that
remedies the dramatic tradeoffs of classical LDCs. In this notion the decoding algorithm is allowed
to output ⊥ sometimes, to signal that it does not know the correct value; however, it should not
output an incorrect value too often. More formally, given i ∈ [k] and oracle access to the received
word w assumed to be relative close to some codeword c = Enc(m) ∈ Σn , the local decoder (1)
outputs mi if w = c; (2) outputs either mi or ⊥ with probability 2/3, otherwise; (3) the set of
indices i such that the decoder outputs mi (the correct value) with probability 2/3 is of size > ρ · k
for some constant ρ > 0. The relaxed definition allows them to achieve RLDCs with constant query
complexity and blocklength n = k1+ǫ .
Recently, Gur et al. [GRR18] introduce the analogous notion of relaxed locally correctable codes
(RLCCs). In particular, upon receiving a word w ∈ Σn assumed to be close to some codeword c,
the decoder: (1) outputs ci if w = c; (2) outputs either ci or ⊥ with probability 2/3, otherwise; and
(3) the set of indices i such that the decoder outputs ci with probability 2/3 is of size ρ · k, for some
ρ > 0. In fact, [GRR18] omits condition (3) in their definition, since the first two conditions imply
the 3rd, for codes with constant locality that can withstand a constant fraction of error [BGH+ 06].
The reduction from [BGH+ 06], however, does not maintain the asymptotic error rate, and in
particular, in the non-constant query complexity regime, the error rate becomes subconstant. Since
our results work in the ω(1)-query regime, we will build codes that achieve the 3rd condition as well
(for constant error rate). The results in [GRR18] obtain significantly better parameters for RLCCs
than for classical LCCs; namely, they construct RLCCs with constant query complexity, polynomial
block length, and constant error rate, and RLCCs with quasipolynomial query complexity, linear
blocklength (constant rate), with the caveat that the error rate is subconstant. These results
immediately extend to RLDCs, since their codes are systematic, meaning that the initial part of
the encoding consists of the message itself.

2

Computationally bounded, adversarial channels In this work we study RLDCs and RLCCs
in the more restricted, yet natural, computationally bounded adversarial channel, introduced by
Lipton [Lip94]. All the above constructions of local codes assume a channel that may introduce a
bounded number of adversarial errors, and the channel has as much time as it needs to decide what
positions to corrupt. This setting corresponds to Hamming’s error model, in which codes should
be resilient to any possible error pattern, as long as the number of corruptions is bounded. Hence,
codes built for the Hamming channel are safe for data transmission, but the drastic requirements
lead to coding limitations. By contrast, in his foundational work, Shannon proposes a weaker,
probabilistic channel in which each symbol is corrupted independently, with some fixed probability.
In [Lip94], Lipton argues that many reasonable channels stand somewhere in between these two
extremes, and one may assume that in reality adversaries are computationally bounded, and can
be modeled as polynomial time probabilistic (PPT) algorithms. Variants of this model have been
initially studied for classical error-correcting codes [Lip94, DGL04, MPSW05, GS16] to show better
error rate capabilities than in the Hamming model.
Ostrovsky et al. [OPS07] introduce the study of “private” locally decodable codes against computationally bounded channels, and build codes with constant information and error rates over the
binary alphabet, which can correct every message bit using only a small (superconstant) number
of queries to the corrupted word. Their results assume the existence of one-way functions, and
require that the encoding and decoding algorithms share a secret key that is not known to the
channel. Hemenway and Ostrovky [HO08] and Hemenway et al. [HOSW11] construct public-key
LDCs assuming the existence of Φ-hiding schemes [CMS99] and of IND-CPA secure cryptosystems,
respectively.
By contrast, our constructions of RLDCs and RLCCs do not require the sender and receiver to exchange cryptographic keys. Instead our constructions are based on the existence of collision-resilient
hash functions, a standard cryptographic assumption. Because the parameters of a collisionresistant hash function are public, any party (sender/receiver/attacker) is able to compute it.

2

Our Contributions

We start by defining the version of relaxed locally correctable codes that is relevant for our model.
We remark that our codes are systematic as well, and therefore the results also apply to the RLDCs
analogue.
Since these codes interact with an adversarial channel, the strength of the codes is not only
measured in its error correction and locality capabilities (as is the case for RLCCs/RLDCs in the
Hamming channel), but also in the security they provide against the channel. We present these
codes while describing how they interact with the channel, in order to make the analogy with the
classical setting. We use the notation Enc and Dec to denote encoding and decoding algorithms.
Definition 2.1 A local code is a tuple (Gen, Enc, Dec) of probabilistic algorithms such that
• Gen(1λ ) takes as input security parameter λ and generates a public seed s ∈ {0, 1}∗ . This
public seed s is fixed once and for all.
• Enc takes as input the public seed s and a message x ∈ Σk and outputs a codeword c = Enc(s, x)
with c ∈ Σn .

3

• Dec takes as input the public seed s, an index i ∈ [n], and is given oracle access to a word
w ∈ Σn . Decw (s, i) outputs a symbol b ∈ Σ (which is supposed to be the value of the closest
codeword to w at position i)
We say that the (information) rate of the code (Gen, Enc, Dec) is k/n. We say that the code is
efficient if Gen, Enc, Dec are all probabilistic polynomial time (PPT) algorithms.
Definition 2.2 A computational adversarial channel A with error rate τ is an algorithm that
interacts with a local code (Gen, Enc, Dec) of rate k/n in rounds, as follows. In each round of the
execution, given a security parameter λ,
(1) Generate s ← Gen(1λ ); s is public, so Enc, Dec, and A have access to s
(2) The channel A on input s hands a message x to the sender.
(3) The sender computes c = Enc(s, x) and hands it back to the channel (in fact the channel can
compute c without this interaction).
(4) The channel A corrupts at most τ n entries of c to obtain a word w ∈ Σn ; w is given to the
receiver’s Dec with query access, together with a challenge index i ∈ [n]
(5) The receiver outputs b ← Decw (s, i).
(6) We define A(s)’s probability of fooling Dec on this round to be pA,s = Pr[b 6∈ {⊥, ci }], where
the probability is taken only over the randomness of the Decw (s, i). We say that A(s) is
γ-successful at fooling Dec if pA,s > γ. We say that A(s) is ρ-successful at limiting Dec if
|GoodA,s | < ρ·n, where GoodA,s ⊆ [n] is the set of indices j such that Pr[Decw (s, j) = cj ] > 32 .
We use FoolA,s (γ, τ, λ) (resp. LimitA,s (ρ, τ, λ)) to denote the event that the attacker was γsuccessful at fooling Dec (resp. ρ-successful at limiting Dec) on this round.
We now define our secure RLCC codes against computational adversarial channels.
Definition 2.3 ((Computational) Relaxed Locally Correctable Codes (CRLCC)) A local
code (Gen, Enc, Dec) is a (q, τ, ρ, γ, µ(·))-CRLCC against a class A of adversaries if Decw makes at
most q queries to w and satisfies the following:
(1) For all public seeds s if w ← Enc(s, x) then Decw (s, i) outputs b = (Enc(s, x))i .
(2) For all A ∈ A we have Pr[FoolA,s (γ, τ, λ)] ≤ µ(λ), where the randomness is taken over the
selection of s ← Gen(1λ ) as well as A’s random coins.
(3) For all A ∈ A we have Pr[LimitA,s (ρ, τ, λ)] ≤ µ(λ), where the randomness is taken over the
selection of s ← Gen(1λ ) as well as A’s random coins.
When µ(λ) = 0 and A is the set of all (computationally unbounded) channels we say that
the code is a (q, τ, ρ, γ)-RLCC. When µ(·) is a negligible function and A is restricted to the set
of all probabilistic polynomial time (PPT) attackers we say that the code is a (q, τ, ρ, γ)-CRLCC
(computational relaxed locally correctable code).
We say that a code that satisfies conditions 1 and 2 is a Weak CRLCC, while a code satisfying
conditions 1, 2 and 3 is a Strong CRLCC code.
4

We construct Weak and Strong CRLCCs against PPT adversaries, under the assumption that
Collision-Resistant Hash Functions (CRHF) exist. Briefly, a CRHF function is a pair (GenH, H) of
probabilistic polynomial time (PPT) algorithms, where GenH takes as input a security parameter
1λ and outputs a public seed s ∈ {0, 1}∗ ; the function H : {0, 1}∗ × Σ∗ → Σℓ(λ) , takes as input
the seed s and a long enough input that is hashed into a string of length ℓ(λ). We note that H is
deterministic upon fixing s. The value ℓ(λ) is the length of the hash function. (GenH, H) is said to
be collision-resistant if for all PPT adversaries that take as input the seed s generated by Gen(1λ ),
the probability that they produce a collision pair (x, x′ ), i.e. such that H(s, x) = H(s, x′ ) and
x 6= x′ , is negligible in 1λ .
Theorem 2.4 Assuming the existence of a collision-resistant hash function (GenH, H) with length
ℓ(λ), there exist constants 0 < τ, ρ, γ < 1 and a negligible function µ, such that there exists a
constant rate (ℓ(λ) · polylog n, τ, ρ, γ, µ(·))-Weak CRLCC of blocklength n over the binary alphabet.
In particular, if ℓ(λ) = polylog λ and λ ∈ Θ(n) then the code is a (polylog n, τ, ρ, γ, µ(·))-Weak
CRLCC.
We note that in the above constructions the codes withstand a constant error rate. The classical RLCCs of [GRR18] achieve (log n)O(log log n) query complexity, constant information rate, but
subconstant error rate, in the Hamming channel.
In order to obtain Strong CRLCC we need further technical insights, that builds upon the
Weak CRLCCs. Our Strong CRLCCs have the same parameters, with only a polylog n loss in query
complexity.
Theorem 2.5 Assuming the existence of a collision-resistant hash function (GenH, H) with length
ℓ(λ), there exist constants 0 < τ, ρ, γ < 1 and a negligible function µ, such that there exists a
constant rate (polylog n, τ, ρ, γ, µ(·))-Strong CRLCC of blocklength n over the binary alphabet. In
particular, if ℓ(λ) = polylog λ and λ ∈ Θ(n) then the code is a (polylog n, τ, ρ, γ, µ(·))-Strong CRLCC.
Our constructions are systematic, so they immediately imply the existence of CRLDCs with the
same parameters.

2.1

Technical Ingredients

At a technical level our construction uses two main building blocks: local expander graphs and
collision resistant hash functions.
Local Expander Graphs Intuitively, given a graph G = (V, E) and distinguished subsets A, B ⊆
V of nodes such that A and B are disjoint and |A| = |B| we say that the pair (A, B) contains a
δ-expander if for all X ⊆ A and Y ⊆ B with |X| > δ|A| and |Y | > δ|B| there is an edge
connecting X and Y i.e., (X × Y ) ∩ E 6= ∅. A δ-local expander is a directed acyclic graph (DAG)
G with n nodes V (G) = {1, . . . , n} with the property that for any radius r > 0 and any node
v ≥ 2r the sets A = {v − 2r + 1, . . . , v − r} and B = {v − r + 1, . . . , v} contain a δ-expander.
For any constant δ > 0 it is possible to construct a δ-local expander with the property that
indeg(G) ∈ O (log n) and outdeg(G) ∈ O (log n) i.e. no node is has more that O (log n) incoming or
outgoing edges [EGS75, ABP18].
Local expanders have several nice properties that have been recently exploited in the design
and analysis of secure memory hard functions [ABH17, ABP17, BZ17, ABP18]. For example, these
5

graphs are maximally depth-robust [ABP18]. Even if we delete a large number of nodes S ⊆ V the
graph still contains a directed path of length n − (1 + ǫ) |S| for some small constant ǫ dependent
on δ — the constant ǫ can approach 0 as δ approaches 0 [ABP18]. More specifically, if we delete a
large number of nodes S
 ⊆ V at least n − (1 + ǫ) |S| of the nodes have the property that they are
2−α
α-good (with ǫ = α ) with respect to the deleted set S and any pair of α-good nodes u and v
are connected by a directed path (provided that δ is sufficiently small) — a node v is α-good with
respect to S if for any radius r < v we have at most αr nodes in S ∩ [v − r + 1, v] and for any radius
r ≤ n − v + 1 we have at most αr nodes in S ∩ [v, v + r − 1].
Suppose that each node is colored red or green and that we are only allowed to query each node to
obtain its color. If we let S denote the set of red nodes then we can develop an efficient randomized
testing algorithm to check if a node v is α-good or not. The tester will make O (polylog n) queries
and, with high probability, will accept any node v that is α1 -good and will reject any node w that
is not α2 -good for any constants α2 > 4 · α1 . Intuitively, for each r ∈ {21 , 22 , . . . , 2log n } the tester
will sample O (polylog n) nodes in the intervals [v, r − 1] and [v − r + 1, v] to make sure that the
fraction of red nodes is at most 2α1 . If the tester determines that a node v is at least α2 -good for an
appropriately small constant α2 then there is a long directed path of length at least n − (1 + ǫ)|S|
containing all α2 -good nodes and in particular containing v. Furthermore, if v < 3n/4 then v has
at least n/4 − (1 + ǫ)|S| descendants in this path.
Collision Resistant Hash Functions Our constructions employ collision resistant hash functions as a building block. While most of the recent progress on memory hard functions in cryptography combines local expanders (depth-robust graphs) with random oracles (e.g., see [AS15,
AT17, ABP18]), we stress that we do not need to work in the random oracle model1 . Indeed, our
constructions only assume the existence of collision resistant hash functions.
Weak CRLCCs We first explain our construction of Weak CRLCCs, which involves labeling a
δ-local expander with k nodes. In particular, given an input word x = (x1 , . . . , xk ) (broken up into
bit strings of length ℓ(λ)) and a k node local expander graph G, the label of node v is computed
as ℓv,s = H (s, xv ◦ ℓv1 ,s ◦ · · · ◦ ℓvd ,s ) ∈ {0, 1}ℓ(λ) , where ℓv1 ,s , . . . , ℓvd ,s are the labels of the parents
v1 , . . . , vd of node v, and ◦ denotes string concatenation. When ℓ(λ) ∈ O (polylog λ) we will select
λ ∈ O (n) to ensure that ℓ(λ) ∈ O (polylog n). We use the notation Enc and Dec for the encoding
and decoding of our construction, while we use ECC and ECCD to denote the efficient encoding
and decoding algorithms for a good binary code with constant rate and relative distance (e.g.,
[Jus72, SS96]) which can decode efficiently from some constant fractions of errors.
We first apply ECC to x1 , . . . , xk to obtain codewords c1 , . . . , ck ∈ {0, 1}O(ℓ(λ)) where ci =
ECC(xi ). Also, for v ∈ [k] we let cv+k = ECC(ℓv,s ) which is the encoding of the label corresponding
to the node v in G. The final output is c = (c1 , . . . , c2k−1 , c2k , c2k+1 , . . . , c3k ) where c2k+1 = . . . =
c3k = c2k consists of k copies of the last codeword c2k . The final word is an n bit message with
n = O (3kℓ (λ)). By repeating this last codeword k times we ensure that it is not possible for the
attacker to irreparably corrupt the final label ℓk,s .
Given a (possibly corrupted) codeword c′ produced by a PPT attacker A we let x′ = (x′1 , . . . , x′k )
with x′i = ECCD(c′i ) (possibly ⊥) and we let ℓ′v,s = ECCD(c′v+k ) for v ∈ [k] and ℓ′k,s,j = ECCD(c′2k+j )
1
The random oracle model is a source of some controversy among cryptographers [KM07, Men12, Gol06, KM15]
with some arguing that the framework can be used to develop cryptographic protocols that are efficient and secure [BR93], while others argue that the methodology is flawed e.g. [BL13, KM15].

6

for each j ∈ [k]. We say that a node v is green if it is locally consistent i.e.,

ℓ′v,s = H s, x′v ◦ ℓ′v1 ,s ◦ . . . ◦ ℓ′vd ,s ,

otherwise we say that the node is red. We first show that if a green node has the correct label
ℓ′v,s = ℓv,s then it must be the case that x′v = xv and ℓ′vi ,s = ℓvi ,s for each i ≤ d — otherwise
A would have found a hash collision! If a graph contains too many red nodes then this is easily
detectable by random sampling and our weak local decoder is allowed to output ⊥ if it detects any
red nodes. Our local decoder will first obtain the final label ℓk,s by random sampling some labels
from ℓ′k,s,1, . . . , ℓ′k,s,k and checking to make sure each of these labels is equal to ℓ′k,s . If this check
passes then with high probability we must have ℓ′k,s = ℓk,s since the attacker cannot corrupt too
many of these labels. Second, our local decoder will test to make sure that the last node k is at least
α2 -good. If this node is not α2 -good then we must have found a red node and our weak decoder
may output ⊥; otherwise the last node serves as an anchor point. In particular, since since label
ℓk,s = ℓ′k,s in this case collision resistance now implies that for any α2 -good node v then we must
have x′v = xv and ℓv,s = ℓ′v,s since v must be connected to the node k by a green path.
Strong CRLCCs The reason that the previous construction fails to yield a strong CRLCCs is
that it is possible for an attacker to change every node to a red-node by tampering with at most
O (k · ℓ(λ)/ log k) bits. In particular, since the δ-local expander G has outdegree O (log k) an
attacker who tampers with just O (ℓ(λ)) bits could tamper with one of the labels so that x′v 6= xv .
Now for every w ∈ [k] s.t. G contains the directed edge (v, w) the node w will be red and there are
up to O (log k) = O (log n) such nodes w.
We address this issue by first applying
a degree reduction gadget to our family {Gt }∞
t=1 of δ-local


k
expanders, where t = O ℓ(λ)·log
k , to obtain a new family of DAGs as follows: First, we replace
every node u ∈ [t] from Gt with a chain u1 , . . . , um of m = O (log t) nodes — we will refer to node
u ∈ [t] as the meta-node for this group. The result is a new graph with k = m · t nodes. Each of
the nodes u1 , . . . , um−1 will have constant indegree and constant outdegree. However, for i < m
we include the directed edges (ui , ui+1 ) and (ui , um ) — the node um will have indeg(um ) ∈ Θ(m).
Furthermore, if we have an edge (u, v) in Gt then we will add an edge of the (um , vj ) for some
j < m — this will be done in such a way that maintains indeg(vj ) ≤ 2 for each j < m. Therefore,
the node um will have outdeg(um ) ∈ Θ(log t). We now note that if the label ℓ′um ,s = ℓum ,s and the
node um is green then, by collision resistance, it must be the case that ℓ′ui ,s = ℓui ,s and x′ui = xui
for every ui with i ≤ m.
With this observation in mind we tweak our last construction by grouping the values ℓvi ,s and
xvi into groups of size m ∈ O (log t) before applying the error correcting code. In particular, given
our input word x divided into k = m · t distinct ℓ(λ)-bit strings xvi for i ≤ m and v ≤ t, our
final output will consist of c = (c1 , . . . , c3t ) where ci = ECC(x(i−1)m+1 , . . . , xim ) for i ≤ t and
cv+t = ECC (ℓv1 ,s ◦ . . . ◦ ℓvm ,s ) and c2t+1 = . . . = c3t = c2t consists of t copies of c2t . The final
codeword c will have length n ∈ O (tm · ℓ(λ)) = O (k · ℓ(λ)) bits. By grouping blocks together we
get the property that an attacker that wants to alter an individual label ℓvi ,s must pay to flip at
least Ω (ℓ(λ) · m) bits of cv+t . Thus, the attacker is significantly restricted in the way he can tamper
with the labels e.g., the attacker cannot tamper with one label in every group.
We now define a meta-node u ∈ [t] containing u1 , . . . , um , to be green if (1) node um is green, and
(2) at least 2m/3 of the nodes u1 , . . . , um are green. Even if we flip a (sufficiently small) constant
fraction of the bits in c we can show that most of the meta-nodes must be green — in fact, most of

7

these meta-nodes must also be α2 -good. In particular, there are only two ways to turn a meta-node
u red: (1) by paying to flip O (ℓ(λ) · m) bits in cu or cu+t , and (2) by corrupting at least m/3 other
meta-nodes w such that the directed edge (w, u) is in Gt . Finally, we are able to argue that, by
collision resistance, if a meta-node u ∈ [t] is green and the meta-node u is correct (i.e., x′uj = xuj
and ℓ′uj ,s = ℓuj ,s for each j ≤ m) and if we have the directed edge (w, u) in Gt then the label ℓ′wm ,s
must also be correct (thus, if the meta-node w is green then the meta-node must be correct). As
long as the number of red nodes S is sufficiently small. It follows that any α2 -good meta-node
u < 3t/4 is connected to at least t/4 − (1 + ǫ)|S| green meta-nodes. Since the attacker does not
have the budget to corrupt all t/4 − (1 + ǫ)|S| of these meta-nodes it follows that the meta-node u
must be correct. Once we determine that a meta-node u is correct (x′uj = xuj and ℓ′uj ,s = ℓuj ,s for
each j ≤ m) we can easily recover cu = ECC(x′u1 ◦ . . . ◦ x′um ) and/or cu+t = ECC(ℓ′u1 ,s ◦ . . . ◦ ℓ′um ,s ) 2 .

3

Related work

Classical LDCs/LCCs and relaxed variants in the Hamming channel The current best
constructions for LDCs/LCCs can achieve any constant rate R < 1, any constant relative distance
Hamming distance between codewords) δ < 1 − R, and query complexity
 √ (i.e., minimum

log
n
log
log
n
O 2
[KMRS17]. In the constant query complexity regime, for q ≥ 3, the best codes
achieve blocklength subexponential in the message length [Yek08, Efr12, DGY11]. For q = 2,
Kerenidis and deWolf [KdW04] show an exponential in k lower bound for the blocklength of any
LDC.
A notion similar to RLDCs, called Locally Decode/Reject code, was studied by Moshkovitz
and Raz [MR10] in the context of building better PCPs. The notion concerns decoding batches of
coordinates jointly, and it allows as output a list of possible messages. In the context of simplifying
the proofs in [MR10], a related notion of decodable PCPs was studied in [DH09].
Non-local codes in computationally bounded channels In their initial works in the computationally bounded channel, Lipton [Lip94] and Ding, Gopalan and Lipton [DGL04] obtain errorcorrecting codes uniquely decodable (in the classical, global setting) with error rates beyond what
is possible in the adversarial Hamming channel. Their model requires that the sender and receiver share a secret random string, unknown to the channel. This is a strong cryptographic
assumption, as the model is unsuitable to common settings such as message broadcast. Micali
et al. [MPSW05] address this drawback by proposing public-key error-correcting codes against computationally bounded channels. Their model is based on the observation that if one starts with a
code that is list-decodable, encoding messages using a secret key and digitally signing them, one
can prevent a PPT channel from producing valid signatures, while allowing the receiver to pick
the unique message from the list with a valid signature. In follow-up work, Guruswami and Smith
[GS16] removes the public-key setup, and obtains optimal rate error-correcting codes for channels
that can be described by simple circuits. Their channels are either “oblivious”, namely the error is
independent of the actual message being sent, or they are describable by polynomial size circuits.
Their results are based on the idea that the sender can choose a permutation and a “blinding
2

If we want to recover c2t+j we can simply draw r ∈ O (polylog k) samples s1 , . . . , sr from the set c2t , . . . , c3t ,
decode to obtain y1 , . . . , yr with yj = ECCD(sj ), take a majority vote to obtain ymaj and output ECC(ymaj ).

8

factor” that are then embedded into the codeword together with the message. The channel cannot
distinguish the hidden information since it operates with low complexity, while the receiver can.
LDCs in computationally bounded channels The notion of LDCs over computationally
bounded channels was introduced in [OPS07], where the authors define private LDCs. In these
constructions the sender and the receiver share a private key. They obtain codes of constant rate
and O (polylog λ) query complexity, where λ is the security parameter. Hemenway and Ostrovsky

[HO08] build LDCs in the public-key model, and obtain codes of constant rate, and O λ2 locality.
Hemenway et al. [HOSW11] improve on these results and obtain public-key LDCs with constant
rate, constant error rate and O (λ) locality, which work under a weaker cryptographic assumption
than that of [HO08].

4

Preliminaries

We use the notation [n] to represent the set {1, 2, . . . , n}. For any x, y ∈ Σn , let dist(x) denote the
Hamming weight of x, i.e. the number of non-zero coordinates of x. Let dist(x, y) = dist(x − y)
denote the Hamming distance between the vectors x and y. For any vector x ∈ Σn , let x[i] be the
ith coordinate of x. We also let x ◦ y denote the concatenation of x with y.
We denote a directed acyclic graph G with n vertices labelled in topological order by G =
([n], E). A node v ∈ V has indegree δ = indeg(v) if there exist δ incoming edges δ = |(V × {v})∩ E|.
Thus, we say that graph G has indegree δ = indeg(G) if the maximum indegree of any node of G
is δ. A node with indegree 0 is called a source node and a node with no outgoing edges is called a
sink. A node v ∈ V has outdegree δ = outdeg(v) if there exist δ outgoing edges δ = |(V × {v}) ∩ E|.
Thus, we say that graph G has outdegree δ = outdeg(G) if the maximum outdegree of any node of
G is δ. Finally, we say that graph G has degree δ = deg(G) if the maximum degree of any node of
G is δ, or equivalently maxv∈V outdeg(v)+ indeg(v) = δ. We use parentsG (v) = {u ∈ V : (u, v) ∈ E}
to denote the parents of a node v ∈ V . We will often consider graphs obtained from other graphs
by removing subsets of nodes. Therefore if S ⊂ V , then we denote by G − S the DAG obtained
from G by removing nodes S and incident edges.
Let C be a (n, k) code that maps any k-length message over alphabet Σ to a unique n-length
codeword over alphabet Σ. We say n is the block length of the code, and k/n is the information
rate. Let Enc : Σk → Σn denote the encoding map of C. We define the minimum distance of C to
be the quantity minc1 ,c2∈C dist(c1 , c2 ) and the relative minimum distance of C to be the quantity
minc1 ,c2∈C dist(cn1 ,c2 ) .
We shall use Enc and Dec to refer to the encoding and decoding algorithms of our construction,
and ECC and ECCD to refer to the encoding and decoding algorithms for a binary code CJ with
constant rate and relative distance. We will use Justesen codes [Jus72] in what follows.
Theorem 4.1 [Jus72] For any 0 < R < 1, there exist binary linear codes of rate R, that are
efficiently decodable from ∆J (R) fraction of errors, where ∆J (R) is a function that only dependents
on R.
In particular, we use ECC and ECCD to denote the efficient encoding and decoding algorithms
of a Justesen binary linear code of rate R = 14 , and we let ∆J = ∆J (1/4) in the construction that
follows.
9

Collision Resistant Hash Functions (CRHF)
Our code constructions involve the use of collision-resistant hash functions. We use the following
definitions from Katz and Lindell [KL14].
Definition 4.2 [KL14, Definition 4.11] A hash function with alphabet Σ and blocklength ℓ(.) is a
pair Π = (GenH, H) of probabilistic polynomial time algorithms satisfying:
• GenH is a probabilistic algorithm which takes as input a security parameter 1λ and outputs a
public seed s ∈ {0, 1}∗ , where the security parameter 1λ is implicit in the string s.
• H is a deterministic algorithm that takes as input a seed s and a string Σ∗ and outputs a
string H(s, x) ∈ Σℓ(λ) .
A collision resistant hash function can be defined using the following experiment for a hash function
Π = (GenH, H), an adversary A, and a security parameter λ:
The collision-finding experiment Hash − collA,Π (λ):
(1) s ← GenH(1λ )
(2) (x, x′ ) ← A(s)
(3) The output of the experiment is 1 if and only if A successfully finds a collision, i.e.
x 6= x′ and H(s, x) = H(s, x′ ).
Then this experiment implicitly defines a collision resistant hash function.
Definition 4.3 [KL14, Definition 4.12] A hash function Π = (GenH, H) is collision resistant if
for all probabilistic polynomial time adversaries A there exists a negligible function negl such that
Pr [Hash − collA,Π (λ) = 1] ≤ negl(λ).

Background on δ-Local Expander Graphs
We now begin to describe the underlying DAGs in our code construction. We first define the class
of graphs δ-expanders and δ-local expanders.
Definition 4.4 Let δ > 0. A bipartite graph G = (U, V, E) is called a δ-expander if for all M1 ⊆ U ,
M2 ⊆ V such that |M1 | ≥ δ|U | and |M2 | ≥ δ|V |, there exists an edge e ∈ M1 × M2 .
Definition 4.5 Let δ > 0 and G = ([n], E) be a directed acyclic graph. G is called a δ-local
expander if for every vertex x ∈ [n] and every r ≤ min{x, n − x}, the bipartite graph induced by
U = [x, . . . , x + r − 1] and V = [x + r, . . . , x + 2r − 1] is a δ-expander.
Theorem 4.6, due to Alwen et al. [ABP18], states that δ-local expanders exist with degree O (log n).
Theorem 4.6 [ABP18] For any n > 0, δ > 0, there exists a δ-local expander G = ([n], E) with
indegree O (log n) and outdegree O (log n).
10

The construction of Alwen et al. [ABP18] is probabilistic. In particular, they show that there is a
random distribution over DAGs such that any sample from this distribution is a δ-local expander
with high probability. The randomized construction of Alwen et al. [ABP18] closely follows an
earlier construction of Erdos et al. [EGS75] 3 .
We now list some properties of the δ-local expander graphs shown in [ABP18]. We will use
these properties to construct the Dec algorithm for the CRLCC scheme.
Definition 4.7 (α-good node) Let G = ([n], E) be a DAG and let S ⊆ [n] be a subset of vertices.
Let 0 < c < 1. We say v ∈ [n] − S is α-good under S if for all r > 0:
|[v − r + 1, v] ∩ S| ≤ αr,

|[v, v + r − 1] ∩ S| ≤ αr.

Intuitively, we can view the subset S to be a set of “deleted” vertices. A vertex in the remaining
graph is called α-good if at most α fraction of vertices in any of its neighborhood are contained
in the deleted set. In our case, we will ultimately define S to be the nodes with the inconsistent
labels.
The following result of [ABP18] shows that in any DAG G, even if we deleted a constant fraction
of vertices, there still remain a constant fraction of vertices that are α-good.
Lemma 4.8 (Lemma 4.4 in [ABP18]) Let G = ([n], E) be a directed acyclic graph. For any
S ⊂ [n] and any 0 < α < 1, at least n − |S| 2−α
nodes in G − S are α-good under S.
α

Alwen et al. [ABP18] also show that in a δ-local expander graph G any two α-good vertices in
G − S are connected.

Lemma 4.9 (Lemma 4.3 in [ABP18]) Let G = ([n], E) be a δ-local expander, S ⊆ [n] and
0 ≤ α ≤ 1. If δ < min((1 − α)/2, 1/4), then any two α-good vertices u, v ∈ G − S are connected in
G − S.

5

Construction of Weak-CRLCC

In this section we overview the construction of a constant rate weak-CRLCC scheme. In order to
show the existence of a CRLCC scheme, we need to construct the PPT algorithms
Gen, Enc and Dec.

λ
Our construction will use a CRHF Π = (GenH, H). In particular, Gen 1 simply runs GenH 1λ
to output the public seed s.
The Enc algorithm uses the CRHF to create labels for the vertices of a δ-local expander. We
now define the recursive labeling process for the vertices of any given DAG G using H.
Definition 5.1 (Labeling)
Let Σ = {0, 1}ℓ(λ) . Given a directed acyclic graph G = ([k], E), a

λ
seed s ← GenH 1 for a collision resistant hash function H : {0, 1}∗ → {0, 1}ℓ(λ) , and a message
x = (x1 , x2 , · · · , xk ) ∈ Σk we define the labeling of graph G with x, labG,s : Σk → Σk as labG,s (x) =
(ℓ1,s , ℓ2,s , · · · , ℓk,s ), where
(
H(s, xv ),
indeg(v) = 0
ℓv,s =
H(s, xv ◦ ℓv1 ,s ◦ · · · ◦ ℓvd ,s ), 0 < indeg(v) = d,
3

While Alwen et al. [ABP18] only analyze the indegree of this construction it is trivial to see that the outdegree is
also O (log n) since the construction of Erdos et al. [EGS75] overlays multiple bipartite expander graphs on top of the
nodes V = [n]. Each bipartite expander graph has indeg, outdeg ∈ O (1) and each node is associated with O (log n)
expanders.

11

where v1 , . . . , vd are the parents of vertex v in G, according to some predetermined topological order.
We omit the subscripts G, s when the dependency on the graph G and public hash seed H is clear
from context.

5.1

Enc Algorithm


In this section we describe the Enc algorithm which takes as input a seed s ← Gen 1λ and
a message x ∈ {0, 1}k , and returns a codeword c ∈ {0, 1}n . For a security parameter λ, let
H : {0, 1}∗ → {0, 1}ℓ(λ) be a CRHF (see Definition 4.3). We will assume that Enc has access to H. In
this section we also let ECC : {0, 1}ℓ(λ) → {0, 1}4·ℓ(λ) be a standard binary code with message length
ℓ(λ) and block length 4 · ℓ(λ) (such as Justesen code [Jus72]) and let ECCD : {0, 1}4·ℓ(λ) → {0, 1}ℓ(λ)
be the decoder that efficiently decodes from ∆J fraction of errors.
Let s ← Gen(1λ ). Let k′ = k/ℓ(λ) and for δ = 1/100, let G = ([k′ ], E) be a δ-local expander
graph with indegree O (log k′ ).
Enc(s, x):
Input: x = (x1 , · · · , xk′ ) ∈ {0, 1}k where each xi ∈ {0, 1}ℓ(λ) and k = k′ · ℓ(λ).
Output: c = (c1 , · · · , c3k′ −1 ) ∈ {0, 1}n where each ci ∈ {0, 1}4·ℓ(λ) and n = 4(3k′ − 1) · ℓ(λ)

• Let labG,s (x) = ℓ1,s , · · · , ℓk′ ,s be the labeling of the graph G with input x and seed s.
• The codeword c consists of the group-wise encoding of message x, followed by the encoded
labeling of the graph using ECC, followed by k′ − 1 copies of encoded ℓk′ .


c = (ECC(x1 ), · · · , ECC(xk′ ), ECC(ℓ1,s ), · · · , ECC(ℓk′ ,s ), ECC ℓk′ ,s , · · · , ECC ℓk′ ,s ) .
|
{z
}
k ′ −1 times

...
ECC(ℓ1,s )

ECC(ℓ2,s )

ECC(ℓ3,s )

ECC(ℓ4,s )

ECC(ℓk′ ,s )

ECC(ℓ5,s )

ECC(ℓk′ ,s )

ECC(ℓk′ ,s )

ECC(ℓk′ ,s )

k′ − 1
Fig. 1: An example of an encoding with an underlying graph with k′ = k/ℓ(λ) nodes
The parameter δ = 1/100 is arbitrary, and simply chosen to satisfy Lemma 4.9. Also, note that
the codeword length is n = 4 · (3k′ − 1) · ℓ(λ) over the binary alphabet {0, 1}, where ℓ(λ) is the
length of the output of the CRHF H and the original message had length k = k′ · ℓ(λ). Therefore,
the rate nk of CRLCC scheme obtained from Enc is Θ(1).

5.2

Dec Algorithm

In this section, we detail a randomized algorithm Dec : {0, 1}n × [n] → {⊥} ∪ {0, 1} for Enc :
{0, 1}k → {0, 1}n described in Section 5.1. We assume Dec has access to the same public seed s
12

used by Enc as well as the δ-local expander used by Enc. We focus on the key ideas first and then
provide the formal description of Dec. The notion of a green node is central to Dec.
′
Given a word (corrupted codeword) w = (w1 , . . . , w3k′ −1 ) ∈ ({0, 1}4·ℓ(λ) )3k −1 we define x′i =
ECCD(wi ) ∈ {0, 1}ℓ(λ) for i ≤ k′ and ℓ′v,s = ECCD(wk′ +v ) for v ≤ k′ and ℓ′k′ ,s,i = ECCD(w2k′ +i ) for
i < k′ .
Definition 5.2 (Green/red node) We say that a node v ∈ [k′ ] with parents v1 , . . . , vd is green if
the label ℓ′v,s is consistent with the hash of its parent labels i.e., ℓ′v,s = H(s, xv ◦ℓ′v1 ,s ◦ℓ′v2 ,s ◦· · ·◦ℓ′vd ,s ).
A node that is not green is a red node.
We say that a node v is correct if ℓ′v,s = ℓv,s and x′v = xv . Lemma 5.3 highlights one of the key
reasons why green nodes are significant in our construction.
Lemma 5.3 Suppose that node v is green and correct (i.e., ℓ′v,s = ℓv,s ) and suppose that there is
a directed path from node u to node v consisting entirely of green nodes. Then either the node u is
also correct (i.e., ℓ′u,s = ℓu,s ) or the PPT adversary has produced a hash collision.
Proof : If node v is green, then by definition ℓ′v,s = H(s, x′v ◦ ℓ′v1 ,s ◦ · · · ◦ ℓ′vd ,s ) where v1 , . . . , vd are
the parents of node v. Moreover, if ℓ′v,s is unaltered, then ℓ′v,s = ℓv,s = H(s, xv ◦ℓv1 ,s ◦ℓv2 ,s ◦· · ·◦ℓvd ,s ).
Thus,
H(s, xv ◦ ℓv1 ,s ◦ ℓv2 ,s ◦ · · · ◦ ℓvd ,s ) = H(s, x′v ◦ ℓ′v1 ,s ◦ · · · ◦ ℓ′vd ,s ).
Either xv = x′v and ℓvj ,s = ℓ′vj ,s for each j ∈ [d] or we have found a hash collision. In particular,
let vj be the node that lies on the green path from u to v. Assuming we have no hash collision the
node vj is correct and green. We can extend the same argument inductively to argue that node u
must be correct.

Our local decoder will output ⊥ if it ever detects any red nodes (Note that when the codeword
is not corrupted we will have 0 red nodes).
We now consider two cases. Case 1: The input index i ≥ 8k − 4ℓ(λ). This corresponds to a bit
query within the last k′ blocks. From the construction of the code, we know that the last k′ blocks
of the encoding are the same, i.e. c2k′ +j = c2k′ for all 1 ≤ j ≤ k′ . In this case, Decw simply queries
O (log k′ ) blocks in [2k′ , 3k′ − 1], finds the decodes them to the nearest codeword and returns the
majority codeword. Since the adversary cannot corrupt many blocks beyond decoding radius, the
majority will return the correct block with high probability. See Section 5.2.1 for the formal proof.
Case 2: If the input index i < 8k − 4ℓ(λ), Decw uses the properties of the δ-local expander
′
graph to detect whether the corresponding label has been tampered
m or not. Let i denote the index
l
i
mod k′ . We check to make sure
of the node in G associated with the queried bit i i.e., i′ = 4·ℓ(λ)

that (1) the node k′ is at least α-good, and (2) the node i′ is also α-good. If either check fails then
we will output ⊥. Otherwise, by Lemma 5.3 the node i′ must be correct (with high probability)
since (1) there is a green path connecting any two α-good nodes in a δ-local expander, and (2) the
node k′ must be correct (with high probability).
The core part of the Decw then is the probabilistic procedure to verify that a node v is α-good.
First, it is clear that there is a deterministic procedure IsGreenw (v) that checks whether a given
node v ∈ [k′ ] is green or not in O (log n) coordinate queries to w (see Lemma 5.5 for the formal
statement). Now in order to verify if a node v is α-good, we need to estimate the fraction of
green nodes in any neighborhood of it. This is achieved by designing a tester that accepts v if it is
13

α/4-good with respect to the set S of red nodes and rejects with high probability if v is not α-good
(formalized in Lemma 5.6).
The key observation behind Lemma 5.6 is that it suffices to check that [v, v + 2j − 1] ∩ S ≤
α · 2j /4 for each j ≤ log k′ and that [v − 2j + 1, v] ∩ S ≤ α · 2j /4 for each j ≤ log k′ . For each j we
can sample r = O (polylog k′ ) random nodes in each of the intervals [v − 2j + 1, v] and [v, v + 2j − 1]
and use the subroutine IsGreen to count the number of red (resp. green) nodes in each interval. If
for every j ≤ log k′ the number of red nodes is both intervals at most α · 2j /2 we accept. Otherwise,
we reject.
We now proceed to formalize the decoder Dec for the Weak-CRLCC described above.
5.2.1

Query Procedure for i ≥ 8k − 4ℓ(λ)

In this section, we describe the procedure for recovering a coordinate for input i ≥ 8k − 4ℓ(λ).
We show that regardless of the underlying graph, any adversary that can change at most ∆4J k
coordinates of a codeword obtained from Enc, cannot prevent relaxed local correction for a query
on the last k′ blocks.
Consider the following algorithm Decw
1 (s, i) for any i ≥ 8k − 4ℓ(λ):
Decw
1 : Input : Index i ∈ [n] such that i ≥ 8k − 4ℓ(λ).
 3 
k
(1) Sample Θ log
blocks {wt } of w for t between 2k′ and 3k′ uniformly at random.
ℓ(λ)

(2) Decode each of the queried blocks wt to the corrected codeword, ct := ECC(ECCD(wt )).
(could possibly be a ⊥ if ECCD fails to decode).
(3) Let cmaj = majority{ct } be the codeword of ECC which occurs majority of the times in
Step (2) above.
(4) Output symbol (i mod 4ℓ(λ)) of cmaj .

3
We show in Lemma 5.4 that Pr [Decw
1 (s, i) = c[i]] ≥ 1 − negl(n) and uses at most O log n
queries.



Lemma 5.4 Let Enc be as described in Section 5.1. For any 8k − 4ℓ(λ) ≤ i ≤ n, Decw
1 does the
following:
(1) For any x ∈ {0, 1}k and c = Enc(s, x), it holds that Decc1 (s, i) = c[i].
(2) For any x ∈ {0, 1}k , c = Enc(s, x) and w ∈ {0, 1}n generated by any PPT adversary such that
dist(c, w) ≤ ∆4J k , it holds that
Pr [Decw
1 (s, i) = c[i]] ≥ 1 −

3
Moreover, Decw
1 makes at most O log n queries to w.

Proof :
symbol.

1
2
nlog n

.

First, note that for any codeword obtained from Enc, Dec1 will always output the correct

14

Let w be the received word which is obtained by altering at most ∆4J k coordinates of some
codeword c obtained from Enc, i.e., 0 < dist(c, w) ≤ ∆4J k . From Enc, we know that the last k′
blocks of any codeword are exactly the same. Since dist(c, w) ≤ ∆4J k , at most 14 fraction of these
blocks are modified in more than ∆J fraction of their coordinates. Therefore, at least 43 fraction
of the last k′ blocks can be corrected to a unique codeword closest to them. Thus, each query
3
finds an correct codeword block with probability
at least 4 . Then by standard Chernoff bounds,

3

k
queries are correct is at least 1 − e−Ω(s) , where
the probability that the majority of the Θ log
ℓ(λ)
 3 
k
is the number of sampled blocks.
s = Θ log
ℓ(λ)
 3 
k
Since Dec1 queries O log
blocks each of length 4ℓ(λ) bits, the complexity of Dec1 is at most
ℓ(λ)


3
3
O log k = O log n .


5.2.2

Query Procedure for i < 8k − 4ℓ(λ)

In this section, we describe the algorithm for recovering a coordinate for input i < 8k−4ℓ(λ). Before
we describe the algorithm, we need a few definitions and properties of the code we constructed in
Section 5.1.
Recall that for a codeword obtained from Enc, the first k′ blocks of length 4ℓ(λ) each, corresponds to the encoding of the message symbols, and the next k′ blocks correspond to the encoding
of labels of the nodes of a fixed δ-local expander graph G = ([k′ ], E) generated using the k′ message
blocks.
In the next lemma, we describe an algorithm which verifies whether a given node of G is green
with respect to the labels obtained from the received vector w ∈ {0, 1}n . Recall from the definition
of a green node that we need to query only the labels of the parents of a given vertex v to verify
if it is green. Since the indegree of G is O (log k′ ), we can check if a particular node is green by
making at most O (log k′ ) block queries to w. We now formalize the verification procedure.
Lemma 5.5 Let G = ([k′ ], E) be δ-local expander with indegree O (log k′ ) used by Enc and let
w = (w1 , . . . , w3k′ −1 ) ∈ {0, 1}n be the corrupted word obtained from the PPT adversary. There
exists an algorithm IsGreen that uses O (ℓ(λ) log (n/ℓ(λ))) coordinate queries to w and outputs
whether a given node v ∈ [k′ ] of G is green or not.
Proof :

We claim the following algorithm achieves the desired properties:

IsGreen: Input: Node v ∈ [k′ ] of G with indegree d = O (log k′ ).
(1) Query and decode the blocks wk′ +vj for vj ∈ parentsG (v). Let ℓ′k′ +vj := ECCD(wk′ +vj ).
Return ‘Red’ if ECCD fails on any input.
(2) Query and decode the block wv . Let x′v := ECCD(wv ). Return ‘Red’ if ECCD fails.
(3) If ECCD(wk′ +v ) = H(s, x′v ◦ wk′ +v1 ◦ wk′ +v2 ◦ · · · ◦ wk′ +vd ), where vj ∈ parentsG (v) for
j ∈ [d], then output ‘Green’
(4) Else output ‘Red’.

15

IsGreen outputs whether or not the label of node v, i.e. ECCD(wk′ +v ), is green by querying at
most O (log k′ ) blocks of w. Since each block is 4ℓ(λ) bits long, and k′ = k/ℓ(λ) = O (n/ℓ(λ)), the
number of bits queried is equivalently O (ℓ(λ) log (n/ℓ(λ))).

Let w ∈ {0, 1}n be the received word obtained from the PPT adversary. Let S ⊆ [k′ ] be the
set of red nodes of G with respect to its labeling obtained from w. Let 0 < α < 1. Recall from
Definition 4.7 that we call a node i ∈ [k ′ ] of G to be α-good under the set S ⊆ [k′ ] if for all r > 0,
the number of nodes of S in any r-sized neighborhood of i is at most α·r. We now give an algorithm
to locally verify if a given node of G is α-good with high probability.



n
Lemma 5.6 For any α < 34 , there exists a procedure that makes O ℓ(λ) log3+ǫ ℓ(λ)
coordinate
queries to w and for any node i ∈ [k′ ] of G does the following:
• Accepts if i is

α
4 -good

under S with probability 1 − negl(n).

• Rejects if i is not α-good under S with probability 1 − negl(n).
Proof :

Consider the following algorithm IsGood, where S is defined to be the set of red nodes:

IsGood: Input: Node i ∈ [k′ ] of G, α < 34 , space parameter ǫ > 0.
(1) If i is not green, then Reject.
(2) For every p ∈ {1, . . . , log k′ } do:
• Sample log1+ǫ k′ nodes U1p ⊆ [i − 2p + 1, i] and U2p ⊆ [i, i + 2p − 1].
• If the fraction of red nodes in U1p or U2p is larger than 34 α, then Reject.
(3) Accept otherwise.

Note that IsGood samples at most O log2+ǫ k′ nodes of G and for each of those nodes, we
check if it is green. Using Algorithm IsGreen described in Lemma 5.5, we can verify if a node is
green using only O (log k′ ) block queries to w. Therefore the number of coordinates of w queried
by IsGood is at most O ℓ(λ) log3+ǫ (n/ℓ(λ)) .
If the node i is red, then i ∈ S and therefore by definition it is not α-good for any α. On the
other hand, if i is α/4-good, then we know that for any r-sized neighborhoods of i, i.e [i − r + 1, i]
and [i, i + r − 1] have at most α · r/4 red nodes. In particular, for all p ∈ [log k′ ], the neighborhoods
U1p = [i − 2p + 1, i] and U2p = [i, i + 2p − 1] contain at most α · 2p−2 red nodes. So on sampling
log1+ǫ k′ nodes uniformly at random from these intervals of size 2p , the probability that we sample
1+ǫ ′
at least 43 α log1+ǫ k′ red nodes is at most e−13α log (k )/12 . Taking a union bound over all log k′
intervals, IsGood accepts any α/4-good node with probability at least 1 − negl(k′ ) = 1 − negl(n) for
ℓ(λ) = polylog n.
We now show that any node which is not α-good under S is not α/4-good for some interval of
size 2p , p > 0. Therefore, IsGood rejects any node which is not α-good with probability at least
1 − negl(k′ ). If node i is not α-good under S, then there exists a neighborhood I of i such that
the number of red nodes in I is at least α|I|. Let R(X) denote the number of red nodes for some
∗
∗
subset X ⊆ V . Let U1 ⊆ I ⊆ U2 where |U1 | = 2p and |U2 | = 2p +1 for some integer p∗ > 0. Then
∗

∗

R(U2 ) ≥ R(I) ≥ α|I| ≥ α|U1 | = α · 2p ≥
16

α p∗ +1
·2
.
4

where the inequality (*) results from i not being α-good.



Let (w, i, x) be the challenge provided by any PPT adversary such that dist(c, w) ≤ τ , where
c = Enc(x). Recall that using Algorithm Dec1 we can successfully correct any index i ≥ 8k − 4ℓ(λ).
Therefore, to design Dec2 , we assume the correctness of node k′ using Dec1 . The procedure Dec2
first checks whether nodes i and node k′ are α-good for some α < 3/4. If they are both α-good,
then by Lemma 4.9 there is a path of green nodes connecting i and node k′ . Node k′ now serves as
an anchor point by being both α-good and correct due to the repetition code, so then Lemma 5.3
implies node i is also unaltered. We now formalize this and describe Dec2 in Lemma 5.7.
Lemma 5.7 Let Enc be as described in Section 5.1. For any 1 ≤ i < 8k − 4ℓ(λ), there exists a
procedure Dec2 with the following properties:
(1) For any x ∈ {0, 1}k and c = Enc(s, x), Decc2 (s, i) = c[i].
(2) For any x ∈ {0, 1}k , c = Enc(s, x) and w ∈ {0, 1}n generated by any PPT adversary such that
dist(c, w) ≤ ∆4J k ,
Pr [Decw
2 (s, i) ∈ {c[i], ⊥}] ≥ 1 − negl(n).

Moreover, Dec2 makes at most O ℓ(λ) log3+ǫ (n/ℓ(λ)) queries to input w for any constant ǫ > 0.
Proof :

We claim the following procedure has the desired properties.

Decw
2 : Input: Index i < 8k − 4ℓ(λ).
(1) Let S be the set of red nodes of G with respect to the labels obtained from w.
(2) Let α < 43 .
(3) Reconstruct the label of k′ -th node, ℓk′ ,s using a call to Dec1 .
m
l
i
mod k′ are α-good under S, then return
(4) If node k′ of G with label ℓk′ ,s and node 4·ℓ(λ)
wi ,
(5) Else return ⊥.

First we show that the query complexity of Dec2 is at most O ℓ(λ) log3+ǫ (n/ℓ(λ)) . Observe that
Dec1 described in Lemma 5.4 uses majority decoding
 to reconstruct the entire block w2k′ +j , for any
0 ≤ j ≤ k′ − 1. Moreover, it uses at most O log3 n coordinate queries to w in order to reconstruct
any of the last k′ blocks with 1 − negl(n). Therefore we can assume that after Step (3), the label
ℓk′ ,s of G is correct with very high probability. Also, using the procedure described in Lemma
5.6,

we can check if both the nodes k′ and i are α-good using at most O ℓ(λ) log3+ǫ (n/ℓ(λ)) queries
for any ǫ > 0. Therefore the query complexity of Dec2 is O ℓ(λ) log3+ǫ (n/ℓ(λ)) .
To show (1), observe that if w is a codeword produced by Enc, then the label ℓk′ ,s is reconstructed
correctly with probability 1 by Dec1 in the first step. Also since S = ∅, all the nodes of G are
α-good. Therefore, Dec2 always returns the correct codeword symbol.
Now, if w is any string produced by a PPT adversary such that 0 < dist(c, w) ≤ ∆4J k , then from
the analysis of Dec1 in Lemma 5.4, we know that ℓk′ ,s is reconstructed correctly with probability
at least 1 − negl(n). If both nodes i and k′ of G are α-good under S, then by Lemma 4.9, we know
17

that there exists a path in G from node i to node k′ in G which consists of only green nodes. So,

node i is a green ancestor of node k′ . The correctness of wi then follows from Lemma 5.3.
We now combine the two correctors described above to obtain our local corrector Dec as follows:
Decw : Input : Index i.
(1) If i ≥ 8k − 4ℓ(λ), return Decw
1 (s, i)
(2) Else return Decw
2 (s, i).
Lemma 5.8 Let Enc be as described in Section 5.1. For any i ∈ [n], Dec does the following:
(1) For any x ∈ {0, 1}k and c = Enc(s, x), Decc (s, i) = c[i].
(2) For any x ∈ {0, 1}k , c = Enc(s, x) and w ∈ {0, 1}n generated by any PPT adversary such that
dist(c, w) ≤ ∆4J k ,
Pr [Decw (s, i) ∈ {c[i], ⊥}] ≥ 1 − negl(n).

Moreover, Dec makes at most O ℓ(λ) log 3+ǫ (n/ℓ(λ)) queries to input w for any constant ǫ > 0.

Proof :
The proof follows from Lemma 5.7 and Lemma 5.4. Since n = (3k′ − 1) · 4ℓ(λ), any
query on an index i < 8k − 4ℓ(λ) is handled by Lemma 5.7 while a query on an index i ≥ 8k − 4ℓ(λ)
uses at most O ℓ(λ) log3+ǫ (n/ℓ(λ)) queries, the
is handled by Lemma 5.4. Since each scenario

3+ǫ
algorithm also uses O ℓ(λ) log
(n/ℓ(λ)) queries. Note that for ℓ(λ) = polylog n, the query
complexity of the decoder is polylog n.

We now show that our construction Π = (Gen, Enc, Dec) is a CRLCC scheme.
Proof of Theorem 2.4: Gen on input a security parameter λ simulates the generator algorithm
GenH of the CRHF to output a random seed s.
Consider s ← Gen(1λ ), Enc described in Section 5.1 and the decoder Dec described in Section 5.2
above. We claim that the triple Π = (Gen, Enc, Dec) is a CRLCC scheme.
From the construction of Enc, we know that the block length of a codeword produced by Enc is
n = (3k′ − 1) · 4 · ℓ(λ) < 12k. Therefore, the information rate of the CRLCC is O (1).
From Lemma 5.8 we know that on input (w, i, x) generated by any PPT adversary such that
dist(Enc(x), w) ≤ ∆4J k , Decw queries at most O ℓ(λ) log3+ǫ (n/ℓ(λ)) coordinates of w and returns
d ∈ {Enc(x)[i], ⊥} with probability at least 1 − negl(n). Also, Dec on input any valid encoding
(Enc(x), i, x) returns Enc(x)[i] with probability 1.


6

Strong-CRLCC

In this section, we give an improved construction that locally corrects a majority of input coordinates.
The Barrier: The challenge in correcting a constant fraction
of
 the nodes in the previous

n
construction is that an adversary that is permitted to change O log n symbols can turn all nodes
red in a graph that has outdegree O (log n).
18

Key Idea: We overcome the above mentioned barrier using three ideas. First, we run the
original δ-local expander Gt through an indegree reduction gadget to obtain a new graph G with
k′ = t · m nodes in which almost every node has at most 2 incoming/outgoing edges and each node
u in Gt (called the meta-node) corresponds to m nodes u1 , . . . , um in G.
Second, we introduce the notion of green meta-node u and show that the same key properties we
used for the construction of Weak-CRLCC still hold with respect to the meta-nodes. A meta-node
u = {u1 , . . . , um } is defined to be correct if all of its corresponding nodes u1 , . . . , um are correct
(i.e., ℓ′uj ,s = ℓuj ,s and x′uj = xuj for each j ≤ m). However, we stress that the definition of a
green meta-node does not require that all uj are green. Instead we require that um is green and
most of the nodes u1 , . . . , um−1 are green. Crucially, this definition transfers the depth robustness
properties of the δ-local expander Gt to G. In particular, if a meta-node v is green and correct and
there is a directed path from u to v in Gt containing only green meta-nodes, then u must also be
correct (or we will find a hash collision).
Third, we group the labels ℓu1 ,s , . . . , ℓum ,s into blocks before encoding them using a good error
correcting code with constant rate and constant distance. This forces the attacker to flip at least
Ω (m · ℓ(λ)) bits to tamper any of the meta-nodes. In this way we can ensure that an attacker
must tamper with at least Ω (t · m · ℓ(λ)) bits to make Ω(t) meta-nodes red. Therefore, by choosing
appropriate parameters t and m, we get the Strong-CRLCC.
Metagraph
We will define the notion of a metagraph used in our approach to construct Strong-CRLCCs. For
any graph G = (V, E), let M1 , M2 , . . . Mm be a partition of the vertex set V . We call the graph
Gm = (Vm , Em ) with the following properties to be the metagraph of G.
Nodes: For every partition Mi of V , there is a unique node vi ∈ Vm . We call vi the simple node
and Mi its meta-node.
Edges: There exists an edge between vi and vj in Gm if and only if there exists an edge between u
and v in G for some u ∈ Mi and v ∈ Mj .
Graph Degree Reduction
We now describe our procedure ReduceDegree that reduces the degree of many nodes in a graph,
while simultaneously yielding a desirable meta-graph.
ReduceDegree: (Let G0 be a δ-local expander with δ = 1/100.)
Input: Graph G0 with t vertices and m = max{indeg(G0 ), outdeg(G0 )} + 1
Output: Graph G with m · t vertices.
• For each node u in G0 we add m nodes u1 , . . . , um to G. Along with each of the directed
edges (ui , ui+1 ) and (ui , um ) for i < m.
• For each directed edge (u, v) in G0 we connect the final node um to the first node vj that
currently has indegree at most 1.
Again, the choice of δ = 1/100 is only to satisfy Lemma 4.9.

19

·G· 0·

···

u

G

u1

u2

···

···

um

v

v−1

···

v1

v2

···

vm

Fig. 2: An example of a degree reduction graph

6.1

Enc Algorithm


In this section we describe the Enc algorithm which takes as input a seed s ← Gen 1λ and a message
x ∈ {0, 1}k and returns a codeword c ∈ {0, 1}n . For a security parameter λ, let H : {0, 1}∗ →
{0, 1}ℓ(λ) be a CRHF (see Definition 4.3). Recall that, ECC and ECCD denote the encoding and
decoding algorithms of a good code of rate 1/4 that can decode efficiently from ∆J fraction of
errors.


k
For t = O ℓ(λ)·log
k , let G0 = ([t], E) be a δ-local expander graph on t vertices and degree
(indegree and outdegree) m = O (log t). Let G := ReduceDegree(G0 ) be the graph with k′ :=
nodes output by the degree reducing procedure applied to G0 .

k
ℓ(λ)

Let s ← Gen(1λ )
Enc(s, x):
Input: x = (x1 , · · · , xk′ ) ∈ {0, 1}ℓ(λ)

k′

, where k = k′ · ℓ(λ)
3t−1
, where t = k′ /m and n = O (k).
Output: c = (c1 , · · · , c3t−1 ) ∈ {0, 1}4m·ℓ(λ

• Let (ℓ11 ,s , . . . , ℓ1m ,s , . . . , ℓt1 ,s . . . , ℓtm ,s ) = labG,s (x) be the labeling of the graph G with
input x using the CRHF (see Definition 5.1).
• Let U1 := (ℓ11 ,s , ℓ12 ,s , · · · , ℓ1m ,s ), . . . , Ut := (ℓt1 ,s , ℓt2 ,s , · · · , ℓtm ,s ).
• Let T1 := (x1 , x2 , . . . , xm ), . . . , Tt := (x(t−1)m+1 , x(t−1)m+2 , · · · , xtm ).
• The codeword c consists of the encoding of groups of message bits, followed by encoding
k′
using ECC of groups of labels, followed by t = m
copies of the last encoding.
c = (ECC(T1 ), ECC(T2 ), · · · , ECC(Tt ), ECC(U1 ), ECC(U2 ), · · · , ECC(Ut ),
ECC(Ut ), · · · , ECC(Ut )),
|
{z
}
t times

where ECC(Ui ) = ECC(ℓi1 ,s , . . . , ℓim ,s ) for all i ∈ [t].

Lemma 6.3 is the key lemma that did not hold for our previous construction. It states that if
for any w ∈ {0, 1}n , dist(w, c) ≤ ∆J4 ·k then the number of red meta-nodes is very small. Lemma 6.6
20

is analogous to Lemma 5.3 and asserts that if there is a green path from meta-node u to meta-node
v and v is correct then meta-node u must also be correct. It follows that any meta-node v < 4t that
is α-good must also be correct because v is connected to all other α-good meta nodes, and there
are too many α-good meta nodes for the attacker to corrupt them all. With this observation it is
relatively straightforward to extend the ideas from the previous section to build a strong Dec with
locality O (polylog n).
We also remark that it is possible to allow the rate of our code to approach 1. For example, we
can split the initial input x into chunks of size xi ∈ {0, 1}100λ so that the size of each label ℓi,s is
significantly smaller than the size of the corresponding chunk (We would also need to modify the
underlying ECC so the rate of this code is also close to 1).

6.2

Dec Algorithm

Observe that at the end of the construction, each meta-node contains exactly one node (i.e. the
final node) with indegree more than 2 (it has indegree m) and outdegree more than 2 (it has
outdegree O (m)).
The codeword c = Enc(x) consists of 3 parts. The first 4k bits correspond to the message symbols
x passed m · ℓ(λ) bits at a time through ECC. The next 4k bits correspond to t codewords ECC(Uj ),
and finally the last 4k − 4m · ℓ(λ) bits correspond to the repetitions of the final ECC codeword,
ECC(Ut ). Therefore the length of any codeword produced by Enc is O (n) since m = O (log k).
Claim 6.1 outdeg(G0 ) = Θ(log k).
Definition 6.2 We call a meta-node Mi green if both:
• At least 1 − ∆J fraction of the underlying nodes in Mi are green.
• The final node in Mi is green.
We call a meta-node red if the meta-node is not green. Similarly, we call a meta-node Mi correct if
we are able to correctly decode Mi . Observe that Mi can contain tampered nodes but still be correct.
Observe that encoding the labels of a meta node using a good code, we ensure that a meta-node
can only be corrupted by changing 4m · ℓ(λ) · ∆J bits of the meta-node or finding a hash collision:
Lemma 6.3 If dist(w, c) ≤

∆J k
4 ,

then at most

t
4

meta-nodes in G are red.

Proof : Observe that a meta-node can be made red by changing at least 4m · ℓ(λ) · ∆J bits or
by finding a hash collision. Therefore, by changing at most ∆4J k bits of a codeword, an adversary
k′
k
= 4m
can make at most 4mℓ(λ)
= 4t meta-nodes in G red.

Similar to the decoder Dec of Section 5.2, which splits the decoding procedure for the first
8k−4ℓ(λ) indices and a separate decoding procedure for the remaining indices, the current decoding
procedure has separate subroutine to handle indices corresponding to the first 2t − 1 blocks and a
separate decoding procedure for the remaining indices. In the following, we define m(i) to be the
meta-node corresponding to index i. That is,
m
l
i


l 4mℓ(λ) m, i ≤ 4k
i−4k
m(i) =
4mℓ(λ) , 4k < i ≤ 8k,



t,
i > 8k
21

6.2.1

Query Procedure for m(i) = t

In the case that m(i) = t, we run a procedure Decw
≥t (s, i) that takes advantage of the fact that any
∆J k
adversary that can change at most 4 coordinates of any codeword obtained from Enc. Thus,
the adversary cannot prevent local correction for a query on the last t groups corresponding to the
w
repetition of ECC codeword. Similar to Decw
1 in Section 5.2, the algorithm Dec≥t (s, i) randomly
samples a number of points, takes the majority of the samples, and performs decoding using ECCD.
Lemma 6.4 Let Enc be as described in Section 6.1. For any i ∈ [n] such that m(i) = t, there
exists an algorithm Decw
≥t that does the following:
(1) For any x ∈ {0, 1}k and c = Enc(s, x), Decc≥t (s, i) = c[i].
(2) For any x ∈ {0, 1}k , c = Enc(s, x) and w ∈ {0, 1}n generated by any PPT adversary such that
dist(c, w) ≤ ∆4J k ,


n
Pr Decw
≥t (s, i) = c[i] ≥ 1 − log n .
n

2
Moreover, Decw
≥t makes at most O ℓ(λ) · log n queries to input w.

Proof :

Consider the following algorithm Decw
≥t (i) for any i ∈ [n] with m(i) ≥ t:

Decw
≥t : Input : Index i ∈ [n] with m(i) ≥ t.
(1) For each 0 ≤ j < 4mℓ(λ), sample O (log n) indices of w greater than 8k − 4mℓ(λ) and
congruent to j (mod 4mℓ(λ)) uniformly at random.
(2) For each 0 ≤ j < 4mℓ(λ), choose the symbol w̃j that corresponds to the majority of the
samples from Wj .
(3) Correct the word (w̃1 , · · · , w̃4mℓ(λ) ) using ECCD and output index i (mod 4mℓ(λ)).
First, note that for any codeword obtained from Enc, Dec≥t will always output the correct symbol.
Let w be received word which is obtained by altering at most ∆4J k coordinates of some codeword
i.e, 0 < dist(c, w) ≤ ∆4J k for some codeword c obtained from Enc. We know that the last t
coordinates (mod 4mℓ(λ)) of any codeword are exactly the same, c[j] = c[j + 4mℓ(λ)] for all
j ≥ 8k − 4mℓ(λ). Since dist(c, w) ≤ ∆4J k , at most ∆8J of such coordinates j (mod 4mℓ(λ)) are
corrupted in more than 1/4 fraction of the blocks. For the remaining j, each query finds an
unmodified symbol with probability at least 1 − ∆4J . Then by standard Chernoff bounds over the
O (log n) random queries for each j (mod 4m), the probability that the majority of the O log2 n
1
queries are unmodified is at least 1 − nlog
n . Then by a simple union bound, the probability that
n
the majority of the symbols in meta-node Mt are corrected is at least 1 − nlog
n.
Since Dec≥t makes
O
(log
n)
queries
for
each
of
the
m·ℓ(λ)
congruence
classes
and m = O (log n),

then O ℓ(λ) · log2 n queries are made in total.


22

6.2.2

Query Procedure for m(i) < t

Observe from the construction that G0 is the metagraph of G Since G0 is a δ-local expander, then
for any 0 < α < 1 and subset S of vertices, the metagraph G0 − S contains at least t − |S| α2 − 1
α-good nodes by Lemma 4.8. Also, from Lemma 4.9, we know that any two α-good nodes are
connected by a path in G0 − S. Thus, by letting S be the set of all red meta-nodes, any two
α-good meta-nodes in G0 are connected by a path of green meta-nodes. We use these observations
to design the corrector for m(i) < t.
First, we claim the existence of a procedure to test whether a meta-node is green.
Lemma 6.5 Let w = (w1 , · · · w3t−1 ) ∈ {0, 1}n . There exists a procedure IsGreenMeta that uses
coordinate O ℓ(λ) · log2 n queries to w and checks whether a meta-node i of G0 with labels corresponding to w is green.
Proof :

We claim the following procedure satisfies the desired properties:

IsGreenMeta(i): Input : Meta-node index i ∈ [t].
(1) Check if the final node in meta-node i is green:
• Query coordinates of wt+i and retrieve (ℓ′i1 , . . . , ℓ′im ) := ECCD(wt+i ).
• Query the coordinates of wi and retrieve (x′i1 , . . . , x′im ) := ECCD(wi ).
• Check whether ℓ′im = H(s, x′im ◦ ℓ′i1 ◦ · · · ◦ ℓ′im−1 ) for the final node im in meta-node
i, where i1 , . . . , im−1 are the parents of im , which are all in meta-node i.
• If ℓ′im is not consistent, then output ‘Red’.
(2) For each node ij in meta-node i, check whether ij is green:
• Let ij−1 (in meta-node i) and p(j)r (in meta-node p(j)) be the parents of ij .
• Query wt+r and retrieve ℓ′p(j)r using ECCD(wt+p(j) ).
• Check whether ℓ′ij = H(s, x′ij ◦ ℓ′ij−1 ◦ ℓ′p(j)r ).
(3) If at least 1 − ∆J of the nodes in meta-node i are green, then output ‘Green’.
(4) Else, output ‘Red’.
Recall from Definition 6.2 that a green meta-node first requires that at least 1−∆J of the underlying
nodes in meta-node i are green. Since a node is green if its label is consistent with the labels of
its parents, then the procedure IsGreenMeta properly recognizes whether at least 1 − ∆J of the
underlying nodes in i are green after decoding using ECCD. Secondly, a green meta-node requires
that the final node in i is green. In this case, the final node im has m − 1 parents, and again
the procedure recognizes whether ℓ′im = H(s, x′im ◦ ℓ′i1 ◦ · · · ◦ ℓ′im−1 ) after obtaining the labels using
ECCD.

To see that the IsGreenMeta does at most O ℓ(λ) · log2 n coordinate queries, we observe that
in Step (1), we query two blocks of w each of length 4mℓ(λ) bits. Also, in Step (2), for each of the
m − 1 nodes in the meta-node i we queryone additional block
 of w to check if it is green. Therefore
the total query complexity is O m2 ℓ(λ) = O ℓ(λ) · log2 n .

23

We now introduce the algorithm for recovering a coordinate for input i whose meta-node m(i)
is less than t.
Decw
<t : Input : Index i ∈ [n] with m(i) < t of G,

1
2

< α < 34 , space parameter ǫ > 0.

(1) If meta-node m(i) is not green, then return ⊥.
(2) For every p ∈ {1, . . . , log t} do:
• Sample log1+ǫ k meta-nodes U1p ⊆ [i − 2p + 1, i] and U2p ⊆ [i, i + 2p − 1].
• Use the procedure IsGreenMeta to check the fraction of red meta-nodes in U1p or
U2p .
• If the fraction of red meta-nodes in U1p or U2p is larger than 34 α, then return ⊥.
(3) Otherwise, compute ECCD(wm(i) ) if i ≤ 4k or, ECCD(wt+m(i) ) if i > 4k and return the i
(mod 4mℓ(λ))-th coordinate.
We crucially use the following lemma to prove the correctness of Dec<t procedure given in Lemma 6.7.
Lemma 6.6 The meta-node parents of a meta-node v of G0 that is green and correct must also be
correct unless a hash collision was found.
Proof :
Let v ∈ [t] be a meta-node that is green and correct and let u be a green meta-node
parent of v in the metagraph G0 . Let the nodes in v be v1 , . . . , vm and the nodes in u be u1 , . . . , um .
Let (x′v1 , . . . , x′vm ) := ECCD(wv ) and ℓ′ = (ℓ′v1 , . . . , ℓ′vm ) := ECCD(wt+v ). If v is green and correct,
then ℓ′vt ,s = ℓvt ,s and x′vt = xvt for each 1 ≤ t ≤ m − 1. Let vu be the node of v connected to u so
that ℓ′vu ,s = H(s, x′vu ◦ ℓ′vu−1 ,s ◦ · · · ℓ′vum ,s ). Similarly, ℓvu ,s = H(s, xvu ◦ ℓvu−1 ,s ◦ · · · ℓvum ,s ), so the
label for um must be correct.
Since u is green, then ℓ′um ,s = H(s, x′um ◦ ℓ′u1 ,s ◦ · · · ◦ ℓ′um−1 ,s ). Similarly, ℓ′um ,s = H(s, xum ◦ ℓu1 ,s ◦
· · · ◦ ℓum−1 ,s ). Assuming no hash collisions are found, then xum = x′um and ℓ′ut ,s = ℓut ,s for each
1 ≤ t ≤ m − 1, so u is both green and correct (after decoding using ECCD).

We now justify the correctness of the Dec<t procedure.
Lemma 6.7 Let Enc be as described in Section 6.1. For any i ∈ [n] such that m(i) < t, Dec<t
does the following:
(1) For any x ∈ {0, 1}k and c = Enc(s, x), Decc<t (s, i) = c[i].
(2) For any x ∈ {0, 1}k , c = Enc(s, x) and w ∈ {0, 1}n generated by any PPT adversary such that
dist(c, w) ≤ ∆4J ,
Pr [Decw
<t (s, i) ∈ {c[i], ⊥}] ≥ 1 − negl(n).

4+ǫ
Moreover, Decw
n queries to input w.
<t makes at most O ℓ(λ) · log

Proof :
First we show that the query complexity of Dec<t is at most O log4+ǫ n . Observe
that we query log t indices p. For each p, we sample log1+ǫ k meta-nodes to test whether the meta-
nodes are green. The IsGreenMeta procedure checks if a meta-node is green using O ℓ(λ) · log2 n
coordinate queries to w. Therefore, the total number of queries is O ℓ(λ) · log4+ǫ n .
24

Note that if w is a codeword produced by Enc, then the meta-node m(i) containing index i is
reconstructed correctly by Dec<t by ECCD(wm(i) ) or ECCD(wm(i)+t ) accordingly. Therefore, Dec<t
always returns the correct codeword symbol.
On the other hand, if w is any string produced by a PPT adversary such that 0 < dist(c, w) ≤
∆J k
4 , then Dec<t first checks whether the meta-node m(i) containing i is α-good. Recall that G0
is a δ-local expander by construction. Thus if meta-node m(i) is α-good under the set of red
meta-nodes S, then by Lemma 4.9, that there exists a path in G0 from meta-node m(i) to a later
meta-node that is α-good that consists of only green nodes. Hence, node m(i) is a green ancestor of
a green and correct meta-node. The correctness of w[i] then follows by applying a simple induction
on Lemma 6.6. We can without loss of generality assume that the last meta-node i.e. t is correct
and green using the Dec≥t described in Section 6.2.1. Therefore, we know the existence of such a
later node which is green and correct.

Combining the two decodersin Section 6.2.1 and Section 6.2.2, we get a decoder for CRLCC which
uses at most O ℓ(λ) · log2 n = polylog n for ℓ(λ) = polylog n. Now we show that we indeed get a
Strong-CRLCC and the decoder does not return a ⊥ for majority of the coordinate queries.
w
Lemma 6.8 Let Dec be defined by running Decw
<t on inputs i ∈ [n] where m(i) < t and Dec≥t on
inputs i such that m(i) = t. Then

1
Pri [Decw (s, i) 6= c[i]] > .
4
′

k
Proof : Recall from Lemma 6.3 that the number of red meta-nodes is at most 4m
. By Lemma 4.8

′
′
k
2
k
the number of α-good nodes in G0 is at least m − 4m α − 1 . Thus, there exists α < 1 so that the
7k ′
number of α-good nodes in G0 is greater than 12m
. Since the adversary can only corrupt a small
constant fraction of coordinates of the codeword, then by a simple Pigeonhole argument there is
an α-good meta-node j that is also correct, for j > 4t . Therefore, each index i such that m(i) ≤ 4t
that is in an α-good meta node has a descendant that is both α-good and correct. Hence, applying

an induction on Lemma 6.6 shows that i is correctable.

References
[ABH17]

Joël Alwen, Jeremiah Blocki, and Ben Harsha. Practical graphs for optimal sidechannel resistant memory-hard functions. In Bhavani M. Thuraisingham, David Evans,
Tal Malkin, and Dongyan Xu, editors, ACM CCS 17, pages 1001–1017. ACM Press,
October / November 2017. 2.1

[ABP17]

Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Depth-robust graphs and their
cumulative memory complexity. In Jean-Sébastien Coron and Jesper Buus Nielsen,
editors, EUROCRYPT 2017, Part II, volume 10211 of LNCS, pages 3–32. Springer,
Heidelberg, May 2017. 2.1

[ABP18]

Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Sustained space complexity. In
Advances in Cryptology - EUROCRYPT - 37th Annual International Conference on the
Theory and Applications of Cryptographic Techniques, Proceedings, 2018. (to appear).
2.1, 2.1, 4, 4.6, 4, 4, 4.8, 4, 4.9, 3
25

[ALRW17] Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, and Erik Waingarten. Optimal
hashing-based time-space trade-offs for approximate near neighbors. In Proceedings
of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA
2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 47–66, 2017. 1
[AS15]

Joël Alwen and Vladimir Serbinenko. High parallel complexity graphs and memoryhard functions. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th ACM STOC,
pages 595–603. ACM Press, June 2015. 2.1

[AT17]

Joël Alwen and Björn Tackmann. Moderately hard functions: Definition, instantiations,
and applications. In Yael Kalai and Leonid Reyzin, editors, TCC 2017, Part I, volume
10677 of LNCS, pages 493–526. Springer, Heidelberg, November 2017. 2.1

[BFLS91]

László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium
on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 21–31,
1991. 1

[BGH+ 06] Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan.
Robust pcps of proximity, shorter pcps, and applications to coding. SIAM J. Comput.,
36(4):889–974, 2006. A preliminary version appeared in the Proceedings of the 36th
Annual ACM Symposium on Theory of Computing (STOC). 1
[BK95]

Manuel Blum and Sampath Kannan. Designing programs that check their work. J.
ACM, 42(1):269–291, 1995. 1

[BL13]

Daniel J. Bernstein and Tanja Lange. Non-uniform cracks in the concrete: The power
of free precomputation. In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013,
Part II, volume 8270 of LNCS, pages 321–340. Springer, Heidelberg, December 2013. 1

[BLR93]

Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci., 47(3):549–595, 1993. 1

[BR93]

Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for
designing efficient protocols. In V. Ashby, editor, ACM CCS 93, pages 62–73. ACM
Press, November 1993. 1

[BZ17]

Jeremiah Blocki and Samson Zhou. On the depth-robustness and cumulative pebbling
cost of Argon2i. In Yael Kalai and Leonid Reyzin, editors, TCC 2017, Part I, volume
10677 of LNCS, pages 445–465. Springer, Heidelberg, November 2017. 2.1

[CGdW13] Victor Chen, Elena Grigorescu, and Ronald de Wolf. Error-correcting data structures.
SIAM J. Comput., 42(1):84–111, 2013. 1
[CKGS98] Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. Private information
retrieval. J. ACM, 45(6):965–981, 1998. 1
[CMS99]

Christian Cachin, Silvio Micali, and Markus Stadler. Computationally private information retrieval with polylogarithmic communication. In Advances in Cryptology - EUROCRYPT ’99, International Conference on the Theory and Application of Cryptographic
26

Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding, pages 402–414, 1999.
1
[DGL04]

Yan Ding, Parikshit Gopalan, and Richard Lipton. Error correction against computationally bounded adversaries. Manuscript, 2004. 1, 3

[DGY11]

Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. Matching vector codes. SIAM J.
Comput., 40(4):1154–1178, 2011. 1, 3

[DH09]

Irit Dinur and Prahladh Harsha. Composition of low-error 2-query pcps using decodable
pcps. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS
2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 472–481, 2009. 3

[Efr12]

Klim Efremenko. 3-query locally decodable codes of subexponential length. SIAM J.
Comput., 41(6):1694–1703, 2012. 1, 3

[EGS75]

Paul Erdös, Ronald L. Graham, and Endre Szemeredi. On sparse graphs with dense
long paths. Technical report, Stanford University, Stanford, CA, USA, 1975. 2.1, 4, 3

[Gas04]

William I. Gasarch. A survey on private information retrieval (column: Computational
complexity). Bulletin of the EATCS, 82:72–107, 2004. 1

[Gol06]

Oded Goldreich. On post-modern cryptography. Cryptology ePrint Archive, Report
2006/461, 2006. http://eprint.iacr.org/2006/461. 1

[GRR18]

Tom Gur, Govind Ramnarayan, and Ron D. Rothblum. Relaxed locally correctable
codes. In 9th Innovations in Theoretical Computer Science Conference, ITCS, pages
27:1–27:11, 2018. 1, 2

[GS16]

Venkatesan Guruswami and Adam D. Smith. Optimal rate code constructions for
computationally simple channels. J. ACM, 63(4):35:1–35:37, 2016. 1, 3

[HO08]

Brett Hemenway and Rafail Ostrovsky. Public-key locally-decodable codes. In Advances
in Cryptology - CRYPTO 2008, 28th Annual International Cryptology Conference, Proceedings, pages 126–143, 2008. 1, 3

[HOSW11] Brett Hemenway, Rafail Ostrovsky, Martin J. Strauss, and Mary Wootters. Public key
locally decodable codes with short keys. In 14th International Workshop, APPROX,
and 15th International Workshop, RANDOM, Proceedings, pages 605–615, 2011. 1, 3
[Jus72]

Jørn Justesen. Class of constructive asymptotically good algebraic codes. IEEE Trans.
Information Theory, 18(5):652–656, 1972. 2.1, 4, 4.1, 5.1

[KdW04]

Iordanis Kerenidis and Ronald de Wolf. Exponential lower bound for 2-query locally
decodable codes via a quantum argument. J. Comput. Syst. Sci., 69(3):395–420, 2004.
3

[KL14]

Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography, Second
Edition. CRC Press, 2014. 4, 4.2, 4.3

27

[KM07]

Neal Koblitz and Alfred J. Menezes. Another look at “provable security”. Journal of
Cryptology, 20(1):3–37, January 2007. 1

[KM15]

Neal Koblitz and Alfred Menezes.
The random oracle model: A twentyyear retrospective.
Cryptology ePrint Archive, Report 2015/140, 2015.
http://eprint.iacr.org/2015/140. 1

[KMRS17] Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally
correctable and locally testable codes with sub-polynomial query complexity. J. ACM,
64(2):11:1–11:42, 2017. 1, 3
[KS16]

Swastik Kopparty and Shubhangi Saraf. Guest column: Local testing and decoding of
high-rate error-correcting codes. SIGACT News, 47(3):46–66, 2016. 1

[KT00]

Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for
error-correcting codes. In Proceedings of the Thirty-Second Annual ACM Symposium
on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 80–86, 2000. 1

[LFKN92] Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods
for interactive proof systems. J. ACM, 39(4):859–868, 1992. 1
[Lip94]

Richard J. Lipton. A new approach to information theory. In STACS, 11th Annual
Symposium on Theoretical Aspects of Computer Science, Proceedings, pages 699–708,
1994. 1, 3

[Men12]

Alfred Menezes. Another look at provable security (invited talk). In David Pointcheval
and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, page 8.
Springer, Heidelberg, April 2012. 1

[MPSW05] Silvio Micali, Chris Peikert, Madhu Sudan, and David A. Wilson. Optimal error correction against computationally bounded noise. In Theory of Cryptography, Second Theory
of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005,
Proceedings, pages 1–16, 2005. 1, 3
[MR10]

Dana Moshkovitz and Ran Raz. Two-query PCP with subconstant error. J. ACM,
57(5):29:1–29:29, 2010. A preliminary version appeared in the Proceedings of 49th
Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008). 3

[OPS07]

Rafail Ostrovsky, Omkant Pandey, and Amit Sahai. Private locally decodable codes.
In Automata, Languages and Programming, 34th International Colloquium, ICALP,
Proceedings, pages 387–398, 2007. 1, 3

[SS96]

Michael Sipser and Daniel A. Spielman. Expander codes. IEEE Trans. Information
Theory, 42(6):1710–1722, 1996. 2.1

[STV99]

Madhu Sudan, Luca Trevisan, and Salil P. Vadhan. Pseudorandom generators without
the XOR lemma (abstract). In Proceedings of the 14th Annual IEEE Conference on
Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, page 4, 1999. 1

[Tre04]

Luca Trevisan. Some applications of coding theory in computational complexity. CoRR,
cs.CC/0409044, 2004. 1
28

[Yek08]

Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length.
J. ACM, 55(1):1:1–1:16, 2008. 1, 3

[Yek12]

Sergey Yekhanin. Locally decodable codes. Foundations and Trends in Theoretical
Computer Science, 6(3):139–255, 2012. 1

29

