Paper 2023/627
Conflict Checkable and Decodable Codes and Their Applications
Abstract
Let $C$ be an errorcorrecting 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 $i$th entry is being held by the $i$th 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 conflictcheckable and conflictdecodable codes and prove the following main results: (1) (AlmostMDS conflictcheckable codes:) For every distance $d\leq n$, there exists a code that supports conflictbased errordetection whose dimension $k$ almost achieves the singleton bound, i.e., $k\geq nd+0.99$. Interestingly, the code is nonlinear, 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 $nd\leq k0.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 halfdistance:) For every distance $d\leq n$ there exists a linear code that supports conflictbased errordecoding up to half of the distance. The code's dimension $k$ ``halfmeets'' the singleton bound, i.e., $k=(nd+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 (BenOr, 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 nontrivial 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 conflictdecoder 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=(nd+3)/3$. Our construction is based on trilinear polynomials, and the algorithmic result follows by showing that the induced conflict graph is structured enough to allow efficient recovery of a maximal vertex cover. As an application of the last result, we present the first polynomialtime statistical tworound Verifiable Secret Sharing (resp., threeround general MPC protocol) that remains secure in the presence of an active adversary that corrupts up to $t<n/3.001$ of the parties. We can upgrade the resiliency threshold to $n/3$, which is known to be optimal in this setting, at the expense of increasing the computational complexity to be quasipolynomial. Previous solutions (Applebaum, Kachlon, and Patra, TCC'20) suffered from an exponentialtime complexity even when the adversary corrupts only $n/4$ of the parties.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 error correcting codesverifiable secret sharingMPCround complexity
 Contact author(s)

bennyap @ post tau ac il
elirn chalon @ gmail com  History
 20230503: approved
 20230502: received
 See all versions
 Short URL
 https://ia.cr/2023/627
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/627, author = {Benny Applebaum and Eliran Kachlon}, title = {Conflict Checkable and Decodable Codes and Their Applications}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/627}, year = {2023}, url = {https://eprint.iacr.org/2023/627} }