Conflict Checkable and Decodable Codes and Their Applications

Oded's comments

Conflict checkable codes may be viewed as an extreme relaxation of 2-query locally testable codes (LTCs), requiring that non-codewords be rejected with positive probability (rather than with probability that is lower-bounded by a function of their distance from the code). It turns out that the known limitations on 2-query LTC (i.e., both in the binary and linear case only tiny codes exist), apply also to the current relaxation. On the other hand, it is shown that there exists (non-linear) conflict-checkbale codes (over an expnentially large alphabet) that almost achieve the singleton bound. In comparison, good 2-query LTCS with constant alphabet are implicit in DELLM, but their (constant) rate does not achieve the singleton bound.

Conflict detectable codes allow to reduce error-correction to recovery from erasure failures, while the reduction uses the inconsistency relation (between pairs of locations) to identify a set of uncorrupted locations.

The original abstract

Let C be an error-correcting code over a large alphabet q of block length n, and assume that a possibly corrupted codeword c is distributively stored among n servers where the ith entry is being held by the ith server. Suppose that every pair of servers publicly announce whether the corresponding coordinates are ``consistent'' with some legal codeword or ``conflicted''. What type of information about c can be inferred from this consistency graph? Can we check whether errors occurred and if so, can we find the error locations and effectively decode? We initiate the study of conflict-checkable and conflict-decodable codes and prove the following main results:

1. (Almost-MDS conflict-checkable codes:) For every distance d leq n, there exists a code that supports conflict-based error-detection whose dimension k almost achieves the singleton bound, i.e., k geq n-d+0.99. Interestingly, the code is non-linear, and we give some evidence that suggests that this is inherent. Combinatorially, this yields an n-partite graph over [q]^n that contains q^k cliques of size n whose pairwise intersection is at most n-d leq k-0.99 vertices, generalizing a construction of Alon (Random Struct. Algorithms, '02) that achieves a similar result for the special case of triangles (n=3).
2. (Conflict Decodable Codes below half-distance:) For every distance d leq n there exists a linear code that supports conflict-based error-decoding up to half of the distance. The code's dimension k ``half-meets'' the singleton bound, i.e., k=(n-d+2)/2, and we prove that this bound is tight for a natural class of such codes. The construction is based on symmetric bivariate polynomials and is rooted in the literature on verifiable secret sharing (Ben-Or, Goldwasser and Wigderson, STOC '88; Cramer, Damg?rd, and Maurer, EUROCRYPT '00).
3. (Robust Conflict Decodable Codes:) We show that the above construction also satisfies a non-trivial notion of robust decoding/detection even when the number of errors is unbounded and up to d/2 of the servers are Byzantine and may lie about their conflicts. The resulting conflict-decoder runs in exponential time in this case, and we present an alternative construction that achieves quasipolynomial complexity at the expense of degrading the dimension to k=(n-d+3)/3. Our construction is based on trivariate polynomials, and the algorithmic result follows by showing that the induced conflict graph is structured enough to allow efficient recovery of a minimum vertex cover.

See IACR ePrint 2023/627.