Detecting and Correcting Computationally Bounded Errors: A Simple Construction Under Minimal Assumptions

Standard deterministic codes cannot achieve better parameters against (non-uniform) computationally bounded channels beyond what they achieve for computationally unbounded channels, and in particular, they cannot go beyond the Singleton bound. This is because a worst-case message and error pattern for which detection/correction fails can simply be hard-coded as non-uniform advice to an efficient adversary. To overcome this limitation, we therefore consider codes $(\mathrm{Enc},\mathrm{Dec})$, where the encoding procedure $\mathrm{Enc}$ takes additional randomness as input. We consider two variants. In the basic variant of randomized codes, fresh randomness $r$ for the encoding algorithm is chosen each time on the fly and is unknown to the adversary ahead of time. The adversary chooses a worst-case message $m$, gets the resulting randomized codeword $c\leftarrow \mathrm{Enc}(m;r)$ for a fresh random $r$, and then chooses the error $e$ as an arbitrary efficiently computable function of the codeword. We also consider a stronger variant called self-seeded codes, where the randomness $r$ of the encoding algorithm is fixed once and for all and known to the adversary a priori. That is, the adversary gets the randomness $r$ and then uses it to adaptively choose the message $m$ (which fully defines the codeword $c=\mathrm{Enc}(m;r)$) along with the error $e$. In both cases, the fractional Hamming weight of $e$ is bounded by the error tolerance $\rho$. Error detection ensures that with overwhelming probability the resulting erroneous codeword $c^{\prime }=c+e$ decodes to $m$ when there are no errors, and decodes to either $m$ or $\perp$ when there are errors. Error correction ensures that with overwhelming probability $c^{\prime }$ decodes to $m$.

The main technical difference between randomized and self-seeded codes is adaptivity: in the former the message $m$ to be encoded is chosen by the adversary before the randomness $r$ is chosen, while in the latter the message $m$ can adaptively depend on $r$.¹¹1Randomized codes may also be secret-coin, where the adversary never sees the full randomness $r$. However, our construction will be public-coin and the randomness $r$ can be easily recovered from the codeword $c$. Self-seeded codes allow us to fix the randomness for the code once and for all as a public seed, and afterwards the code is fully deterministic. Moreover, the seed can be chosen by the encoder unilaterally without any coordination with the decoder. For example, different software manufacturers can individually choose their own seeds to be used by the encoding algorithms in their software, while allowing for interoperability with the decoders implemented by other manufacturers without any coordination. Self-seeded codes should be contrasted to the notion of seeded codes in [3], which required a shared random seed as a common trusted setup between the encoder and decoder. Self-seeded codes are the strongest notion and directly imply the seemingly incomparable notions of randomized codes and seeded codes.

We show that any randomized code that goes beyond the Singleton bound with error detection tolerance $\rho >1-R$ or error correction tolerance $\rho >(1-R)/2$ implies one-way functions, while any such seeded (and therefore also self-seeded) code implies collision-resistant hash functions.

We construct randomized and self-seeded codes going beyond the Singleton bound, with essentially optimal parameters for both error detection and error correction, under the above respective minimal assumptions.

Recall that, in the case of error-detection, the Singleton bound says that the relative error tolerance $\rho \le 1-R$ necessarily degrades as the rate improves when considering worst-case errors; in contrast, for computationally bounded errors, our result simultaneously achieves the best possible error tolerance $\rho \approx 1$ and rate $R\approx 1$. In the case of error correction, the Singleton bound says the maximal error tolerance is $\rho \le (1-R)/2$ for worst-case errors, while for computationally bounded errors our result achieves twice as large error tolerance $\rho \approx 1-R$, subject to the upper limit .

Our achieved parameters are essentially optimal, up to the arbitrarily small constant $\epsilon$. This is clear for error detection, where we get the best possible rate $R\approx 1$ and error tolerance $\rho \approx 1$ simultaneously. For error-correction, one cannot tolerate $\rho \ge 1/2$ fraction of errors since an efficient adversarial channel can modify 1/2 the codeword positions to a fresh encoding of a different message, causing decoding to fail with probability at least $1/2$.²²2The works of [11, 12] overcome this limitation by having a stateful and secret keyed encoding procedure to ensure that an adversarial channel cannot generate/reuse valid codewords. Moreover, one cannot have rate $R>1-\rho$ since zeroing out the first $\rho$ fraction of positions of the codeword would remove information about the message, causing decoding to fail.

We remark that, not only are one-way functions and collision-resistant hash functions the minimal assumptions needed to achieve the above results, they are considered some of the most standard and well-studied cryptographic assumptions/primitives. In particular, one-way functions are a minimal assumption necessary for essentially any non-trivial task in cryptography and are implied by all concrete cryptographic hardness assumptions. Collision-resistant hash functions are not known to be implied by one-way function, but can be constructed from essentially every concrete cryptographic hardness assumption, such as hardness of factoring, discrete logarithms, learning with errors, etc.

The closest related prior work of [3] achieves essentially the same parameters as our work, but only for the weaker notion of seeded codes, which require trusted setup, and only by assuming a strong form of “two-input correlation-intractable hash functions”, which we do not know how to instantiate under any standard cryptographic hardness assumption. Our result for self-seeded codes yields a stronger primitive under significantly weaker minimal assumptions. Comparing the notions of randomized, seeded and self-seeded codes, it is clear that self-seeded codes are the strongest notion easily implying the other two, while randomized and seeded codes are seemingly incomparable. Interestingly, since we show that any non-trivial seeded codes imply collision-resistant hashing, which in turn implies self-seeded codes, we show that seeded and self-seeded codes are equivalent in terms of the needed assumptions.

While we stated separate results for error-detection and error-correction above, we can also simultaneously achieve a non-trivial combination of correction and detection. In particular, we can augment the previous theorem statement with the following:

For any constants and , there is a code over a constant-sized alphabet with rate $R=1-{\rho }_c-\epsilon$ that simultaneously uniquely corrects from a ${\rho }_c$ fraction of errors and detects a ${\rho }_d=1-{\rho }_c-\epsilon$ fraction of errors.

The above implies both of the previously stated results for error detection (by setting ${\rho }_c=0$) and error correction (by ignoring ${\rho }_d$). However simultaneous error correction and detection is an interesting property, which is more than the sum of its parts. It gives a single decoding procedure that either outputs a message or $\perp$ (error detection symbol) and is guaranteed to uniquely recover the correct message if the error rate is $\le {\rho }_c$ and to never output the wrong message as long as the error rate is $\le {\rho }_d$. We can envision scenarios where correcting a small fraction of errors (e.g., ${\rho }_c=.1$) may suffice. Our result show that for such instances, we can have a code with a correspondingly large rate (e.g., $R\approx .9$) while simultaneously being able to detect a much larger fraction of errors (e.g., ${\rho }_d\approx .9$) at no additional cost.

We note that our results hold for large constant-size alphabets, but do not extend to the case of a binary alphabet. Giving optimal results for binary codes that detect/correct computationally bounded errors under minimal assumptions remains an interesting open problem. The results of [3] for seeded error correcting codes using a strong form of correlation intractable hash functions extend to the binary case and show that one can uniquely decode computationally bounded errors with essentially the same parameters as list-decoding for worst-case errors. It remains an open problem to achieve such results for randomized or self-seeded codes under any assumptions, and/or to to get provably secure seeded codes under standard cryptographic hardness assumptions.

We start with a naive construction of self-seeded error-detection codes that requires a sub-exponentially large alphabet size, and then show how to reduce the alphabet size to some (large) constant. Let $\mathscr{H}={\{h_r:{\{0,1\}}^k\to {\{0,1\}}^{\lambda }\}}_{r\in {\{0,1\}}^{\lambda }}$ be a collision-resistant hash function family with output length $\lambda$ (security parameter), which we can think of as $\lambda =k^{\alpha }$ for some small constant $\alpha >0$. Given a random public seed $r\leftarrow {\{0,1\}}^{\lambda }$, no polynomial-time adversary can find two messages $m\ne m^{\prime }$ such that $h_r(m)=h_r(m^{\prime })$.

The encoding algorithm $\mathrm{Enc}(m;r)$ takes a message $m\in {\{0,1\}}^k$ and parses it as $n=k/w$ symbols $m=(m_1,\mathrm{\dots },m_n)$ over an alphabet ${\mathrm{\Sigma }}_{\mathrm{data}}={\{0,1\}}^w$ for some large $w=O(\lambda )$. It then “folds in” the seed $r$ and hash of the message $h_r(m)$ into each message symbol to yield the codeword

interpreted as $n$ symbols over the larger alphabet $\mathrm{\Sigma }={\{0,1\}}^{w+2\cdot \lambda }$. The decoding algorithm $\mathrm{Dec}(c^{\prime })$ gets

which gives a candidate message $m^{\prime }=(m_1^{\prime },\mathrm{\dots },m_n^{\prime })$. It checks that the second part of each codeword symbol has the same common seed value $r_1^{\prime }=\mathrm{\cdots }=r_n^{\prime }$ and that the third part of each symbol has the same common hash value $y_i^{\prime }=h_{r_i^{\prime }}(m^{\prime })$; if so it outputs $m^{\prime }$ else $\perp$. The code achieves rate $R=w/(w+2\lambda )\approx 1$ by choosing a sufficiently large $w=O(\lambda )$. Moreover, it achieves error-tolerance $\rho =1-1/n$. Unless the adversary changes every symbol of the codeword $c$, or finds a collision, decoding is guaranteed to output the correct message $m$ or $\perp$. To see this, assume at least one symbol of the codeword remains unchanged and decoding outputs $m^{\prime }\ne m$ for some $m^{\prime }\ne \perp$. Then it must be the case that $r_i^{\prime }=r,y_i^{\prime }=h_r(m^{\prime })=h_r(m)$ for all $i$ and therefore the this gives a collision $m\ne m^{\prime }$ such that $h_r(m)=h_r(m^{\prime })$.

We reduce the alphabet size to a constant by applying a standard error-correcting code $({\mathrm{Enc}}_{\mathrm{ctrl}},{\mathrm{Dec}}_{\mathrm{ctrl}})$ over a constant sized alphabet to the small “control” value $(r,h_r(m))$. In particular, for some constants $w>v$, we use a code with alphabet ${\mathrm{\Sigma }}_{\mathrm{ctrl}}={\{0,1\}}^v$ such that ${\mathrm{Enc}}_{\mathrm{ctrl}}:{\{0,1\}}^{2\lambda }\to {\mathrm{\Sigma }}_{\mathrm{ctrl}}^n$ maps a $2\lambda$-bit message to a codeword of length $n=k/w$. The corresponding rate of the code is very small $R_{\mathrm{ctrl}}=O(\lambda /k)=o(1)$, but we will want large distance ${\delta }_{\mathrm{ctrl}}\approx 1$. Such codes can be constructed by concatenating Reed-Solomon codes with a brute-force inner code over the alphabet ${\mathrm{\Sigma }}_{\mathrm{ctrl}}$ (see Theorem 13). We do not need efficient error-decoding for now, but only require an efficient way to recognize and valid codewords and invert them without errors. The encoding algorithm of our self-seeded code $\mathrm{Enc}(m;r)$ first computes $c_{\mathrm{ctrl}}=(c_{\mathrm{ctrl},1},\mathrm{\dots },c_{\mathrm{ctrl},n})={\mathrm{Enc}}_{\mathrm{ctrl}}((r,h_r(m)))\in {\mathrm{\Sigma }}_{\mathrm{ctrl}}^n$. It interprets $m\in {\{0,1\}}^k$ as $m=(m_1,\mathrm{\dots },m_n)\in {\mathrm{\Sigma }}_{\mathrm{data}}^n$ consisting of $n=k/w$ symbols over the alphabet ${\mathrm{\Sigma }}_{\mathrm{data}}={\{0,1\}}^w$ and then “folds” the two vectors together to yield the final codeword

interpreted as $n$ symbols in over the alphabet $\mathrm{\Sigma }={\mathrm{\Sigma }}_{\mathrm{data}}\times {\mathrm{\Sigma }}_{\mathrm{ctrl}}={\{0,1\}}^{v+w}$. The decoding algorithm $\mathrm{Dec}(c^{\prime })$ gets

and recovers a candidate message $m^{\prime }=(m_1^{\prime },\mathrm{\dots },m_n^{\prime })$ as well as a candidate $c_{\mathrm{ctrl}}^{\prime }=(c_{\mathrm{ctrl},1}^{\prime },\mathrm{\dots },c_{\mathrm{ctrl},n}^{\prime })$. It checks that $c_{\mathrm{ctrl}}^{\prime }$ is a valid codeword and if so recovers $(r^{\prime },y^{\prime })$ such that $c_{\mathrm{ctrl}}^{\prime }={\mathrm{Enc}}_{\mathrm{ctrl}}(r^{\prime },y^{\prime })$. If $c_{\mathrm{ctrl}}^{\prime }$ is not a valid codeword or $h_{r^{\prime }}(m^{\prime })\ne y^{\prime }$, it outputs $\perp$ else it outputs $m^{\prime }$. Note that this generalizes the previous naive idea with a sub-exponentially large alphabet, which corresponds to using a repetition code for the control code. The rate of the overall code is $R=w/(w+v)$ which can be made arbitrarily close to $1$ by choosing a sufficiently large constant $w>v$. The error-tolerance is $\rho ={\delta }_{\mathrm{ctrl}}\approx 1$. In particular, if $c^{\prime }$ is within distance $\rho$ of $c$ and $c_{\mathrm{ctrl}}^{\prime }$ is a valid codeword then it must be the case that $c_{\mathrm{ctrl}}^{\prime }=c_{\mathrm{ctrl}}$ and hence $r^{\prime }=r,y^{\prime }=h_r(m)$. In this case, the only way that that decoding can output some $m^{\prime }\ne m$ is if the values form a hash collision $h_r(m^{\prime })=h_r(m)$.

To achieve error-correction, we use essentially the same construction as before, but additionally encode the data $m$ using an efficiently list-decodable error-correcting code $({\mathrm{Enc}}_{\mathrm{data}},{\mathrm{Dec}}_{\mathrm{data}})$ over a constant size alphabet ${\mathrm{\Sigma }}_{\mathrm{data}}={\{0,1\}}^w$ for some large constant $w$. For any constant we want this code to have rate $R_{\mathrm{data}}\approx 1-\rho$ and to be list-decodable from a $\rho$ fraction of errors. This can be accomplished using the codes of [5]. Moreover, we will now want the code $({\mathrm{Enc}}_{\mathrm{ctrl}},{\mathrm{Dec}}_{\mathrm{ctrl}})$ to efficiently uniquely decode from $\rho$ errors, which can be achieved with the same parameters as previously. Our self-seeded code $\mathrm{Enc}(m;r)$ computes $c_{\mathrm{ctrl}}=(c_{\mathrm{ctrl},1},\mathrm{\dots },c_{\mathrm{ctrl},n})={\mathrm{Enc}}_{\mathrm{ctrl}}((r,h_r(m)))\in {\mathrm{\Sigma }}_{\mathrm{ctrl}}^n$ as before, and also $c_{\mathrm{data}}=(c_{\mathrm{data},1},\mathrm{\dots },c_{\mathrm{data},n})={\mathrm{Enc}}_{\mathrm{data}}(m)\in {\mathrm{\Sigma }}_{\mathrm{data}}^n$. It then “folds” the two codewords together to yield the final codeword

where $\mathrm{\Sigma }={\mathrm{\Sigma }}_{\mathrm{data}}\times {\mathrm{\Sigma }}_{\mathrm{ctrl}}={\{0,1\}}^{v+w}$. The decoding algorithm $\mathrm{Dec}(c^{\prime })$ gets

It applies list-decoding on the data part $c_{\mathrm{data}}^{\prime }$ of the received value $c$ to recover a polynomial list of candidate messages $\{m^{(i)}\}={\mathrm{Dec}}_{\mathrm{data}}(c_{\mathrm{data}}^{\prime })$. It also uniquely decodes $(r^{\prime },y^{\prime })={\mathrm{Dec}}_{\mathrm{ctrl}}(c_{\mathrm{ctrl}}^{\prime })$. Then it outputs the first value $m^{(i)}$ such that $h_{r^{\prime }}(m^{(i)})=y^{\prime }$, or outputs $\perp$ if none is found or if either of the decoding procedures fail. The rate of the overall code is $R=R_{\mathrm{data}}\cdot (w+v)/w\approx 1-\rho$ by choosing sufficiently large constants $w>v$. To analyze the error-correction, first observe that if the received value $c^{\prime }$ within relative distance $\rho$ of $c=\mathrm{Enc}(m;r)$ then, by the correctness of list-decoding of the “data code”, the correct message $m$ will be in the decoded list with $m=m^{(i)}$ for some $i$, and by the correctness of unique decoding of the “control code” we have $(r^{\prime },y^{\prime })=(r,h_r(m))$. So the only way that error correction can fail is if there is another $m^{(j)}\ne m$ in the list such that $h_r(m^{(j)})=h_r(m)$, but this gives a collision on the hash function.

Our constructions of randomized codes with error-detection and error-correction are identical to the above constructions of self-seeded codes, but instead of requiring the hash family $h_r$ to be collision-resistant, we only need it to be a universal one-way hash function (UOWHF). A UOWHF ensures that a polynomial time adversary that selectively chooses a message $m$ first and then gets the seed $r$ cannot find a collision $m^{\prime }\ne m$ such that $h_r(m)=h_r(m^{\prime })$ except with negligible probability. Such UOWHFs can be constructed from one-way functions [13, 16]. Recall that the only difference between self-seeded and randomized codes is whether the encoded message $m$ can be chosen adaptivley depending on the randomness $r$ or selectively before $r$ is chosen, which exactly matches the difference between collision-resistant hash functions and UOWHFs.

We show that self-seeded codes beating the Singleton bound, with error-detection tolerance $\rho >1-R$ or error-correction tolerance $\rho >(1-R)/2$, imply collision-resistant hash functions (CRHFs). Start by considering a self-seeded error-detection code $(\mathrm{Enc},\mathrm{Dec})$ with error-detection tolerance $\rho$. We claim that for every fixed subset $S$ of $1-\rho$ fraction of codeword positions, the function $h_r(m)=\mathrm{Enc}(m;r)[S]$ that outputs the codeword symbols of $\mathrm{Enc}(m;r)$ in the positions indexed by $S$ is collision-resistant. In particular, if there is an efficient adversary that, given $r$, can find a collision $m\ne m^{\prime }$ such that $h_r(m)=h_r(m^{\prime })$, it means that $\mathrm{Enc}(m;r)$ and $\mathrm{Enc}(m^{\prime };r)$ are at distance and therefore such an adversary can break error detection by choosing the message $m$ and modifying $\mathrm{Enc}(m;r)$ to $\mathrm{Enc}(m^{\prime };r)$. Moreover, if the rate of the code exceeds the Singleton bound with $R>1-\rho$, then the functions $h_r$ are compressing, making them CHRFs. To get the analogous result for error-correction, we simply note that $\rho$-error-correction implies $(2\rho )$-error-detection. In particular, if an efficient adversary given $r$ can find two messages $m_0\ne m_1$ such that $\mathrm{Enc}(m_0;r)$ and $\mathrm{Enc}(m_1;r)$ are within relative distance $2\rho$ then it can find a “midpoint” $c^{\prime }$ which is at relative distance $\rho$ from both $\mathrm{Enc}(m_0;r)$ and $\mathrm{Enc}(m_1;r)$. For one of $b\in \{0,1\}$, modifying $\mathrm{Enc}(m_b;r)$ to $c^{\prime }$ necessarily causes decoding to output the incorrect message $m_{1-b}$.

We also show that randomized error-detection and error-correction codes beating the Singleton bound imply one-way functions. The argument is somewhat different from above since we don’t want to assume that $\mathrm{Enc}(m;r)$ reveals $r$ in the full. Instead, we rely on the fact that, if one-way functions don’t exist, then we can efficiently sample “almost uniform” inverses of any efficient function [9]. Consider a random codeword $c=\mathrm{Enc}(m;r)$ for a random message $m$ and randomness $r$. For any subset $S$ of $1-\rho$ fraction of codeword positions we can efficiently find an almost uniform inverse $(m^{\prime },r^{\prime })$ of the function $f(m,r)=\mathrm{Enc}(m;r)[S]$ that outputs the codeword symbols in positions $S$. This means that $c=\mathrm{Enc}(m;r)$ and $c^{\prime }=\mathrm{Enc}(m^{\prime };r^{\prime })$ agree on the positions in $S$ and therefore have relative distance $\le \rho$. If the rate of the code exceeds the Singleton bound with $R>1-\rho$, then there is a non-negligible probability that $m\ne m^{\prime }$ since $f$ loses information about $m$. Therefore the channel that changes $c$ to $c^{\prime }$ is efficient and defeats error detection by introducing $\rho$-fraction errors. Similarly the channel that changes a random subset of $\rho /2$ positions outside of $S$ from $c$ to $c^{\prime }$ defeats error correction since decoding is almost as likely to output $m^{\prime }$ as $m$.

The Hamming distance between $x,y\in {[q]}^n$ is $\mathrm{\Delta }(x,y)=|\{i:x_i\ne y_i\}|$. The relative Hamming distance between $x,y\in {[q]}^n$ is $\delta (x,y)=\frac{\mathrm{\Delta }(x,y)}{n}$.

The statistical distance (also known as, variation distance) of two distributions $P$ and $Q$ over a discrete domain $X$ is defined by $\text{SD}(P,Q)={\max }_{S\subseteq X}|P(S)-Q(S)|$.

We will also use the following lemma about average min-entropy:

Average min-entropy gives a bound on the probability that an adversary that gets the value of $Y$ will guess the value of $X$ in a single attempt. We will use the following useful lemma that connects average min-entropy and min-entropy.

We will also use the classical result of Impagliazzo and Luby on distributional one-way functions implying one-way functions.