Amortized Locally Decodable Codes for Insertions and Deletions

Block et al. give a construction of a compiler taking any Hamming $\mathrm{𝖫𝖣𝖢}$ and compiling it into an Insdel $\mathrm{𝖫𝖣𝖢}$[4]. We refer to their construction as the BBGKZ compiler. In the compiled encoding procedure, the message $𝒙$ is first encoded under the Hamming $\mathrm{𝖫𝖣𝖢}$ as codeword $𝒚,$ where $𝒚$ is then partitioned into size $\tau$ Hamming blocks $𝒚={𝒘}_1\circ \mathrm{\dots }{𝒘}_B$. Each Hamming block ${𝒘}_j$ along with its index $j$ is encoded using a constant rate Insdel code with the special property stating that the relative Hamming weight of every logarithmic-sized interval is at most $2/5$ (The Schulman-Zuckerman-code [23] satisfies this property). Lastly, each block is pre/postpended with a zero buffer $0^{\varphi \tau }$ of length $\varphi \tau$, where $\varphi \in (0,1),$ resulting in the Insdel block ${𝒘}_j^{\prime }$ and the Insdel codeword $𝒀={𝒘}_1^{\prime }\circ \mathrm{\cdots }\circ {𝒘}_B^{\prime }.$ Intuitively, the zero buffers $0^{\varphi \tau }$ help to identify the beginning/end of each block after insertions/deletions.

Then, the compiled Insdel local decoding procedure, when given oracle access to the (possibly corrupted) Insdel codeword $\widetilde{𝒀}$, attempts to simulate the Hamming decoder with access to a corrupted codeword $\widetilde{𝒚}$ that is close to the Hamming Codeword $𝒚$ in Hamming Distance. Specifically, when the Hamming decoder queries symbol $i$ of its expected oracle access to (possibly corrupted) codeword $\widetilde{𝒚}$, the Insdel decoding procedure will identify the block ${𝒘}_j$ which contains $𝒚[i]$, (attempt to) locate the corresponding padded Insdel block ${𝒘}_j^{\prime }$, undo the padding, run the Insdel decoder to recover the pre-compiled block ${𝒘}_j,$ and return the corresponding symbol $\widetilde{𝒚}[i]$. This query simulation process is facilitated by a subroutine we refer to as the RecoverBlock procedure which (attempts to) locate a particular Insdel block ${𝒘}_j^{\prime }$ in the presence of corruptions using a noisy binary search procedure.

Our first challenge in constructing amortizable Insdel $\mathrm{𝖫𝖣𝖢}$s is the observation that RecoverBlock performs asymptotically strictly more queries than the symbols it recovers. Since the codeword $𝒀$ may contain insertions and deletions, in order for RecoverBlock to locate the Hamming decoder’s queries, it performs a noisy binary search procedure and makes $O(\tau +\tau \text{polylog}(n))$ queries to recover the block corresponding to each query made by the Hamming decoder. The Hamming decoder only uses one of these symbols, but even if the decoder utilized all $\tau$ symbols from the recovered symbols, the amortized locality is still at least $O(\text{polylog}(n))$ per symbol recovered. Thus, we cannot achieve constant amortized locality by using the BBGKZ compiler as a black box.

Our insight to address this challenge is that RecoverBlock can be modified to recover a consecutive interval of blocks rather than just a single block. We refer to this modified procedure as RecoverBlocks, where on input block interval $[a,b]:=\{a,\mathrm{\dots },b\}$, RecoverBlocks will recover pre-compiled blocks ${𝒘}_a,\mathrm{\dots },{𝒘}_b$ and make at most $O((b-a+1)\tau +\tau \text{polylog}(n))$ queries. Hence, as long as $b-a+1\ge \text{polylog}(n)$, the ratio of recovered symbols to queried symbols will be constant.

We show that the modified procedure RecoverBlocks preserves correctness. That is, a majority of the (corrupted) Insdel blocks ${\widetilde{𝒘}}_j^{\prime }$ satisfy the property running the search RecoverBlocks with any interval $[a,b]$ that contains $j\in [a,b]$ will yield the original Hamming block ${𝒘}_j$ except with negligible probability. Block et al. [4] proved that the procedure RecoverBlock will correctly find any local-good block and that most blocks will be local-good as long as the number of corruptions is bounded. The main technical challenge results from an inherent mismatch for RecoverBlocks because an interval $[a,b]$ may contain a mixture of blocks that are (resp. are not) locally-good. We show that RecoverBlocks successfully recovers any local-good blocks in its interval except with negligible probability.

We prove that correctness in a similar manner to the analysis of Block et al. [4]. We also utilize the notion of local-good blocks, where if block ${𝒘}_j^{\prime }$ is $(\theta ,\gamma )$-local-good, it will have at most $\gamma \tau$ corruption with the additional desirable property that any block interval $[a,b]$ surrounding the block, i.e. $j\in [a,b]$, has at least $(1-\theta )\times |b-a+1|$ blocks that also have at most $\gamma \tau$ corruption. Utilizing analysis from [4] we can pick our parameters to ensure that at least $(1-{\delta }_h)$ fraction of our blocks are $(\theta ,\gamma )$-local good. What we prove is that if block ${𝒘}_j^{\prime }$ is $(\theta ,\gamma )$-local good and if $j\in [a,b]$ then calling RecoverBlocks for the interval $[a,b]$ will recover the original (uncorrupted) ${𝒘}_j$ with high probability along with any other $(\theta ,\gamma )$-good block in the interval $[a,b]$. Thus, for any partition $[a_1,b_1],\mathrm{\dots },[a_z,b_z]$ of $[B]$ calling RecoverBlocks with each interval $[a_i,b_i]$ would recover the corrupt (uncorrupted) ${𝒘}_j$ for at least $(1-{\delta }_h)B$ blocks. We will use this observation to reason about the correctness of our decoding procedure. Intuitively, we can view the compiled Insdel decoder as simulating the Hamming decoder with a corrupted codeword whose fractional hamming distance is at most ${\delta }_h$ from the original codeword.

The next challenge is utilizing the RecoverBlocks procedure to obtain amortized locality in the Insdel local decoding procedure. Similar to the BBGKZ compiler, our Insdel decoder with oracle access to (possibly corrupted) codeword $\widetilde{𝒀}$ simulates the compiled Hamming decoder’s oracle access to (possibly corrupted) codeword $\widetilde{𝒚}.$ Our hope is that if the underlying Hamming $\mathrm{𝖫𝖣𝖢}$ is amortizable then the compiled Insdel $\mathrm{𝖫𝖣𝖢}$ will also be amortizable. In particular, we hope to group the Hamming decoder’s queries $q_1,\mathrm{\dots },q_{\mathrm{\ell }}$ together into corresponding (disjoint) index intervals $[a_1,b_1],\mathrm{\dots },[a_p,b_p]$ such that (1) ${\sum }_i|b_i+1-a_i|=\mathrm{\Theta }(\mathrm{\ell })$, (2) $\{q_1,\mathrm{\dots },q_{\mathrm{\ell }}\}\subseteq {\bigcup }_i[a_i,b_i]$, and (3) the average size $\frac{1}{p}{\sum }_i|b_i+1-a_i|$ of each interval is large enough we can amortize over the calls to RecoverBlocks e.g., we need to ensure that the average interval size is at least $\frac{1}{p}{\sum }_i|b_i+1-a_i|=\mathrm{\Omega }(\text{polylog}n)$. Unfortunately, in general, we cannot place any such structural guarantees on the queries made by an (amortizable) Hamming $\mathrm{𝖫𝖣𝖢}$.

We address this problem by introducing the notion of a $t$-consecutive interval querying Hamming $\mathrm{𝖫𝖣𝖢}$decoder which is amortization-friendly under our Insdel compiler. Intuitively, the local decoder for a $t$-consecutive interval querying Hamming $\mathrm{𝖫𝖣𝖢}$ accesses the (possibly corrupted) codeword $\widetilde{𝒚}$ by querying for $t$-sized intervals instead of individual message symbols i.e., the decoder may submit the query $[i,i+t-1]$ and the output will be $\widetilde{𝒚}[i,i+t-1]$. In more detail the Hamming decoder takes as input an interval $[L,R]$ of message symbols we would like to recover, makes queries for $t$-sized intervals of the (possibly corrupted) codeword $\widetilde{𝒚}$ and then attempts to output $𝒙[L,R]$. Note that if the Hamming decoder makes $\mathrm{\ell }/t$ interval queries to $\widetilde{𝒚}$ this still corresponds to locality $\mathrm{\ell }$ as the total number of codeword symbols accessed is $t\times (\mathrm{\ell }/t)=\mathrm{\ell }$.

Correspondingly, when the Hamming decoder is $t$-consecutive interval querying, our Insdel decoder will make at most $2\lceil \mathrm{\ell }/t\rceil$ calls to RecoverBlocks on intervals of size $t.$ The resulting query complexity is roughly $\mathrm{\ell }\times \left(\frac{\tau {\log }^{3}n}{t}+O(1)\right)$, and so, in other words, the query complexity blow-up is by a factor of $O\left(\frac{\tau {\log }^{3}n}{t}\right)$. This implies that if there exists a $t$-consecutive interval querying Hamming decoder for $t=\mathrm{\Omega }(\tau {\log }^{3}n)$ with constant amortized locality, our compiled Insdel construction will have constant amortized locality. Thus, the primary question is whether or not it is possible to construct $t$-consecutive interval querying Hamming $\mathrm{𝖫𝖣𝖢}$s with constant amortized locality. We leave this as an open question for worst-case errors, but show that it is possible in settings where the channel is computationally/resource restricted.

We present a $t$-consecutive interval querying private-key amortized Hamming $\mathrm{𝖫𝖣𝖢}$ ($\mathrm{𝗉𝖺𝖫𝖣𝖢}$) construction with constant rate, constant amortized locality, and constant error tolerance i.e. ideal parameters. As a starting point we use the one-time private-key Hamming $\mathrm{𝖫𝖣𝖢}$ constructed by Ostrovsky et al. [21]. Blocki and Zhang show that their construction is amortizable and that their construction may be extended to multi-round secret-key reuse with cryptographic building blocks [7]. For simplicity, we focus on the single round construction, which is information-theoretically secure as long as the channel is computationally bounded.

The single round construction first generates the secret key as a randomly drawn permutation $\pi$ and a random string $𝒓.$ To encode the message $𝒙$, it is partitioned into blocks $𝒙={𝒆}_1\circ \mathrm{\dots }{𝒆}_B$ and each block ${𝒆}_j$ is encoded as ${𝒆}_j^{\prime }=\mathrm{𝖤𝗇𝖼}(𝒆)$ by a constant rate, constant error tolerance Hamming code $\mathrm{𝖤𝗇𝖼}$. Lastly, the bits of the encoded blocks are permuted by $\pi$ and the random string $𝒓$ is xor’d i.e. the resulting codeword is $𝒚=\pi ({𝒆}_1^{\prime }\circ \mathrm{\cdots }\circ {𝒆}_B^{\prime })\oplus 𝒓$. The local decoder can recover any block ${𝒆}_j$ by finding the indices of its corresponding encoded block ${𝒆}_j^{\prime }$, reversing the permutation and random masking, and running the Hamming code decoder $\mathrm{𝖣𝖾𝖼}$ to recover ${𝒆}_j.$ Unfortunately, the local decoder is not $t$-consecutive interval querying since its queries are not in a contiguous interval. The main issue is that the application of the permutation $\pi$ removes any pre-existing block structure in the codeword $𝒚$ i.e., if the local decoder wants to query for consecutive (pre-permutation) code symbols $({𝒆}_1^{\prime }\circ \mathrm{\cdots }\circ {𝒆}_B^{\prime })[s+1,s+\mathrm{\ell }]$, it would have to query $𝒚[\pi (s+1)],\mathrm{\dots },𝒚[\pi (s+\mathrm{\ell })]$, which are no longer consecutive with high probability.

A first attempt to remedy this issue is to permute at the block level instead of the bit level i.e. we draw permutation $\pi$ over $[B]$ and set the codeword instead as $𝒚=({𝒆}_{\pi (1)}^{\prime }\circ \mathrm{\cdots }\circ {𝒆}_{\pi (B)}^{\prime })\oplus 𝒓.$ While this admits contiguous access when recovering any block ${𝒆}_j$ it defeats the original purpose of the permutation. The permutation $\pi$ (and the one-time pad $𝒓$) ensure that (whp) an adversarial channel cannot produce too many corruptions in any individual block. If we permute at the block level then it is trivial for an attacker to corrupt entire blocks. In particular, the adversary could focus their entire error budget to corrupt symbols at the start of the codeword. This simple strategy will always corrupt a constant fraction of blocks ${𝒆}_j^{\prime }.$ Thus, the proposed code will not satisfy correct decoding.

Our primary insight is that we can apply the permutation at an intermediate “sub-block” granularity to ensure correctness and simultaneously support consecutive interval queries. In particular, each encoded block ${𝒆}_j^{\prime },$ for $j\in [B],$ is further partitioned into $\beta$ sub-blocks ${𝒆}_j^{\prime }=({\mathit{ϵ}}_{(j-1)\beta +1}\circ \mathrm{\cdots }\circ {\mathit{ϵ}}_{j\beta })$ and the permutation is applied over sub-blocks ${\mathit{ϵ}}_r$, for $r\in [B\beta ]$, rather than the Hamming blocks ${𝒆}_j^{\prime }$ themselves i.e. the codeword is

Intuitively, while a constant fraction of the sub-blocks ${\mathit{ϵ}}_r$ can still be corrupted with non-negligible probability, as long as the parameter $\beta$ is suitably large (e.g., $\beta =O(\text{polylog}n)$), we can ensure that, except with negligible probability, the overall error in each encoded block ${𝒆}_j^{\prime }$ will still be at most a $\delta$-fraction. Thus, except with negligible probability we can recover ${𝒆}_j$ (the uncorrupted content in block $j$) by making $\beta$ consecutive interval queries to obtain ${\mathit{ϵ}}_r$ for each $r\in [(j-1)\beta +1,j\beta ]$. This is exactly what we needed to achieve amortization with our Ideal Insdel compiler.

The above construction assumes that the sender and receiver share a secret key and only allows the sender to transmit one encoded message. However, if the channel is probabilistic polynomial time (PPT) then the construction can be extended allow for the sender to transmit multiple messages using standard cryptographic tools e.g., pseudo-random functions[21, 7]. Furthermore, if we assume stronger resource bounds on the channel (space, sequential depth etc…) then one can use cryptographic puzzles to completely eliminate the requirement for a secret key using ideas from prior works e.g., [1, 6, 3].

With the building blocks established prior, the $\mathrm{𝖺𝖫𝖣𝖢}$ Hamming-to-Insdel compiler and the consecutive interval querying, ideal Hamming $\mathrm{𝗉𝖺𝖫𝖣𝖢}$, we construct the first ideal Insdel $\mathrm{𝖺𝖫𝖣𝖢}$ within relaxed settings (private-key and resource-bounded). Naturally, we first construct a private-key, ideal Insdel $\mathrm{𝖺𝖫𝖣𝖢}$ by directly using our compiler on the $t$-consecutive interval querying, ideal Hamming $\mathrm{𝗉𝖺𝖫𝖣𝖢}$. For compiler block size $\tau$, our construction achieves constant amortized locality by setting $t=\mathrm{\Omega }(\tau {\log }^{3}n)$ as discussed previously.

The remaining challenge lies in showing that the compiler’s correctness is preserved in private-key settings. Intuitively, we argue via a reduction to the security of the underlying Hamming $\mathrm{𝗉𝖺𝖫𝖣𝖢}$. Suppose there exists a probabilistic polynomial time adversary $𝒜$ who introduces an Insdel corruption pattern into compiled codeword $𝒀$ of their chosen message $𝒙$ that causes a decoding error with non-negligible probability. Then, we can construct a probabilistic polynomial time adversary $ℬ$ who introduces a Hamming error pattern into (pre-compiled) codeword $𝒚$ by (1) using our compiler procedure to transform Hamming codeword $𝒚$ into the compiled Insdel codeword $𝒀$, (2) Giving compiled Insdel codeword $𝒀$ to adversary $𝒜$ and receiving corrupted Insdel codeword $\widetilde{𝒀}$, and finally, (3) constructing the pre-compiled codeword $\widetilde{𝒚}$ by the same simulation process done by the compiled decoder via the RecoverBlocks procedure. To streamline the reduction argument, we draw inspiration from Block and Blocki [3] and repackage our compiler into a convenient form for our reduction. All together, we have an Ideal Insdel $\mathrm{𝗉𝖺𝖫𝖣𝖢}$.

Next, we generalize the $\mathrm{𝗉𝖺𝖫𝖣𝖢}$ construction to construct an $\mathrm{𝖺𝖫𝖣𝖢}$ for resource-bounded settings ($\mathrm{𝗋𝖺𝖫𝖣𝖢}$). Similarly, our first step is constructing a $t$-consecutive interval querying Hamming $\mathrm{𝗋𝖺𝖫𝖣𝖢}$. To do this, we make use of the Hamming private-key-to-resource-bounded $\mathrm{𝖫𝖣𝖢}$ compiler by Ameri et al. [1], which was observed by Blocki and Zhang to be amortizable with only a constant blow-up to the amortized locality [7]. At a high level, their compiler makes use of a cryptographic primitive known as a cryptographic puzzle to embed the secret key within the codeword.

More specifically, cryptographic puzzles consists of two algorithms $\mathrm{𝖯𝗎𝗓𝗓𝖦𝖾𝗇}$ and $\mathrm{𝖯𝗎𝗓𝗓𝖲𝗈𝗅𝗏𝖾}.$ On input seed $𝒄$, $\mathrm{𝖯𝗎𝗓𝗓𝖦𝖾𝗇}$ outputs a puzzle $𝒁$ with solution is $𝒄$ i.e. $\mathrm{𝖯𝗎𝗓𝗓𝖲𝗈𝗅𝗏𝖾}(𝒁)=𝒄.$ The security requirement states that adversary $𝒜$ in a defined algorithm class $ℝ,$ cannot solve the puzzle $𝒁$ and cannot even distinguish between tuples $({𝒁}_0,{𝒄}_0,{𝒄}_1)$ and $({𝒁}_1,{𝒄}_0,{𝒄}_1)$ for random ${𝒄}_i$ and ${𝒁}_i=\mathrm{𝖯𝗎𝗓𝗓𝖦𝖾𝗇}({𝒄}_i).$

Then, the Hamming $\mathrm{𝗋𝖺𝖫𝖣𝖢}$ compiler takes a $\mathrm{𝗉𝖺𝖫𝖣𝖢}$ $({\mathrm{𝖦𝖾𝗇}}_{𝗉},{\mathrm{𝖤𝗇𝖼}}_{𝗉},{\mathrm{𝖣𝖾𝖼}}_{𝗉})$, and on on message $𝒙$ will (1) generate the secret key $\mathrm{𝗌𝗄}\leftarrow {\mathrm{𝖦𝖾𝗇}}_{𝗉}(1^{\lambda };𝒄)$ with some random coins $𝒄$ (2) Compute the $\mathrm{𝗉𝖺𝖫𝖣𝖢}$ encoding of the message ${𝒚}_{𝗉}\leftarrow {\mathrm{𝖤𝗇𝖼}}_{𝗉,\mathrm{𝗌𝗄}}(𝒙)$ (3) Compute an encoding ${𝒚}_{\ast }$ of the puzzle $𝒁$ using a code with low locality that recovers the entire message (known as an ${\mathrm{𝖫𝖣𝖢}}^{\ast }$) and (4) output $𝒚={𝒚}_{𝗉}\circ {𝒚}_{\ast }$. Intuitively, a resource-bounded adversary will not be able to solve the puzzle, while the $\mathrm{𝗋𝖺𝖫𝖣𝖢}$ decoder $\mathrm{𝖣𝖾𝖼}$ will have sufficient resources to solve the puzzle, recover the secret key $\mathrm{𝗌𝗄}$, and run the amortized local decoder ${\mathrm{𝖣𝖾𝖼}}_{𝗉,\mathrm{𝗌𝗄}}$.

We make an additional observation that if the compiler is instantiated with a $t$-consecutive interval querying $\mathrm{𝗉𝖺𝖫𝖣𝖢},$ then the resulting $\mathrm{𝗋𝖺𝖫𝖣𝖢}$ will also be $t$-consecutive interval querying. Thus, when applied to our amortized Hamming-to-Insdel compiler with $t=\mathrm{\Omega }(\tau {\log }^{3}n),$ we acheive constant amortized locality. Lastly, the same reduction argument as in the ideal Insdel $\mathrm{𝗉𝖺𝖫𝖣𝖢}$ construction may be used, with an additional subtle detail of allowing sufficient resources for the reduction. That is, for the class of resource-bounded channels/adversaries $ℝ$ that our Insdel $\mathrm{𝖺𝖫𝖣𝖢}$ is secure against, the underlying Hamming $\mathrm{𝖺𝖫𝖣𝖢}$ must be secure against a wider class of adversaries $\overline{ℝ}$, where $\overline{ℝ}$ include adversaries $𝒜\in ℝ$ whom can additionally compute the simulation process in the private-key reduction.

Let $x\leftarrow y$ represent a variable assignment of $x$ as $y$ and $x\stackrel{\$}{\leftarrow }X$ denote a uniform random assignment of $x$ from space $X$. Let $\circ$ denote the concatenation function. For $l\le r,$ $[l,r]:=\{l,l+1,\mathrm{\dots },r\}$ denotes an interval from $l$ to $r$ inclusive of its ends points. Similarly, $[l,r):=\{l,l+1,\mathrm{\dots },r-1\}$ denotes an interval from $l$ to $r$ exclusive of the right endpoint. Over an alphabet $\mathrm{\Sigma }$, bolded notations $𝒙$ denote vectors/words while non-bolded $x\in \mathrm{\Sigma }$ denote single symbols. For a word $𝒙$, $x[i]$ denotes the symbol of $𝒙$ at index i, while $𝒙[l,r]:=(x[l],x[l+1],\mathrm{\dots },x[r])$ denotes the subword of $𝒙$ projected to indices in interval $[l,r].$ It will also be useful to define a short-hand for retrieving symbols from “blocks" of a word $𝒙$: $𝒙{⟨i⟩}_b:=𝒙[(i-1)b+1,ib]$ for any block size $b$ and index $i.$

For any words $𝒙,𝒚\in {\mathrm{\Sigma }}^n$, $\mathrm{𝖧𝖺𝗆}(𝒙,𝒚)$ denotes the hamming distance between $𝒙$ and $𝒚$ i.e. $|\{i\in [n]:x_i\ne y_i\}|$. Further, for $𝒛\in {\mathrm{\Sigma }}^{\ast },\mathrm{𝖤𝖣}(𝒙,𝒛)$ denotes the edit distance between $𝒙$ and $𝒛$ i.e. the number of symbol insertions and deletions to transform $𝒙$ into $𝒛.$ We say $𝒙$ and $𝒚$ (resp. $𝒙$ and $𝒛$) are $\delta$-hamming-close (resp. $\delta$-edit-close) when $\mathrm{𝖧𝖺𝗆}(𝒙,𝒚)\le \delta |x|$ (resp. $\mathrm{𝖤𝖣}(𝒙,𝒛)\le 2\delta |𝒙|$).

We recall the formal definitions of an $\mathrm{𝖫𝖣𝖢}$ and an amortized $\mathrm{𝖫𝖣𝖢}$.

Throughout the paper, it will be assumed codes are over the binary alphabet i.e. $\mathrm{\Sigma }=\{0,1\}$ unless specified otherwise. The primary metrics of interest for Hamming/Insdel $\mathrm{𝖺𝖫𝖣𝖢}$s are the rate $k/n,$ amortized locality $\alpha$, and the error/edit tolerance $\delta .$

First, we fix notation consistent with the encoder definition above for the rest of the paper. We will refer to the Hamming encoding $𝒚$ in step $1$ as the Hamming encoding and the final codeword $𝒀$ as the Insdel encoding or simply as the encoding. Let $𝒙\in {\{0,1\}}^k$ be the message of size $k$ and let $𝒚={\mathrm{𝖤𝗇𝖼}}_{\text{h}}(𝒙)\in {\{0,1\}}^m$ be the Hamming encoding with size $m$. Let $B=m/\tau$ be the number of blocks. Define $\beta$ such that the rate of the overall encoding is $1/\beta$. Similarly, define ${\beta }_{\text{insdel}}$ such that the rate of the Insdel code ${𝒞}_{\text{insdel}}$ is $1/{\beta }_{\text{insdel}}$. Then, the rate of the Hamming encoding is $({\beta }_{\text{insdel}}\log B+2\varphi )/\beta .$ Let ${\delta }_{\text{h}}$ and ${\delta }_{\text{insdel}}$ be the error tolerances of the Hamming encoding and the Insdel code respectively. Let each ${𝒘}_j=𝒚{⟨j⟩}_{\tau }\in {\{0,1\}}^{\tau }$ denote Hamming block $j$. Similarly, each ${𝒘}_j^{\prime }\in {\{0,1\}}^{\beta \tau }$ denotes the Insdel block/ block $j$. Then, the overall codeword is $𝒀\in {\{0,1\}}^n$ has length $n=\beta m.$ We consider any corrupted codeword $\widetilde{𝒀}\in {\{0,1\}}^{\tilde{n}}$ such that $\mathrm{𝖤𝖣}(𝒀,\widetilde{𝒀})\le 2\delta n.$

We define the block decomposition as a mapping from codeword symbols to their blocks post corruption.

By definition, the pre-image of each block decomposition defines a partition of $[\tilde{n}]$ into $B$ intervals $\{{\varphi }^{-1}(j):j\in [B]\}.$ Each of these intervals define the block structure, where the j’th interval defines the j’th block in the corrupted codeword. In other words, for each $j\in [B]$, ${\varphi }^{-1}(j)$ are all the indices corresponding to block $j.$

As in the BBGKZ compiler, our modified decoder will rely on a noisy recovery process, where the decoder will need to locate blocks without knowing the block boundaries that have been modified by insdel errors. For any search interval $[l,r)\subseteq [\tilde{n}],$ it will be helpful to consider its corresponding block interval i.e. the smallest interval $[L,R-1]\subseteq [B]$ such that $[l,r)\subseteq [\tau L,\tau (R-1)].$ Block intervals are defined formally below.

We say a block is good if it does not have too many edit corruptions. Intuitively, good blocks will correspond to Insdel blocks that are correctly decodable, except with negligible probability.

Good blocks may be naturally extended to good intervals, where the summed edit corruptions of each block within the interval is not too much. Additionally, we constrain the number of bad blocks in any good interval.

Lastly, we define the notion of a locally good block, which captures the idea that any interval including such a block must also be good.