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:

In STOC 1989, Rabin and Ben-Or (RB) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with statistical (information-theoretic) security in the presence of an active (aka Byzantine) rushing adversary that controls up to half of the parties. We study the round complexity of general secure multiparty computation and several related tasks in the RB model.

Abstract. Suppose that you wish to sample a random graph [Formula: see text] over [Formula: see text] vertices and [Formula: see text] edges conditioned on the event that [Formula: see text] does not contain a “small” [Formula: see text]-size graph [Formula: see text] (e.g., clique) as a subgraph. Assuming that most such graphs are [Formula: see text]-free, the problem can be solved by a simple rejected-sampling algorithm (that tests for [Formula: see text]-cliques) with an expected running time of [Formula: see text]. Is it possible to solve the problem in a running time that does not grow polynomially with [Formula: see text]? In this paper, we introduce the general problem of sampling a “random looking” graph [Formula: see text] with a given edge density that avoids some arbitrary predefined [Formula: see text]-size subgraph [Formula: see text]. As our main result, we show that the problem is solvable with respect to some specially crafted [Formula: see text]-wise independent distribution over graphs. That is, we design a sampling algorithm for [Formula: see text]-wise independent graphs that supports efficient testing for subgraph-freeness in time [Formula: see text], where [Formula: see text] is a function of [Formula: see text] and the constant [Formula: see text] in the exponent is independent of [Formula: see text]. Our solution extends to the case where both [Formula: see text] and [Formula: see text] are [Formula: see text]-uniform hypergraphs. We use these algorithms to obtain the first probabilistic construction of constant-degree polynomially unbalanced expander graphs whose failure probability is negligible in [Formula: see text] (i.e., [Formula: see text]). In particular, given constants [Formula: see text], we output a bipartite graph that has [Formula: see text] left nodes and [Formula: see text] right nodes with right-degree of [Formula: see text] so that any right set of size at most [Formula: see text] expands by factor of [Formula: see text]. This result is extended to the setting of unique expansion as well. We observe that such a negligible-error construction can be employed in many useful settings and present applications in coding theory (batch codes and low-density parity-check codes), pseudorandomness (low-bias generators and randomness extractors), and cryptography. Notably, we show that our constructions yield a collection of polynomial-stretch locally computable cryptographic pseudorandom generators based on Goldreich’s one-wayness assumption resolving a central open problem in the area of parallel-time cryptography (e.g., Applebaum, Ishai, and Kushilevitz [ SIAM J. Comput., 36 (2006), pp. 845–888] and Ishai et al. [ Proceedings of the 40 th Annual ACM Symposium on Theory of Computing, ACM, 2008, pp. 433–442]).

In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with perfect (information-theoretic and error-free) security at the presence of an active (aka Byzantine) rushing adversary that controls up to n/3 of the parties. We study the round complexity of general secure multiparty computation in the BGW model. Our main result shows that every functionality can be realized in only four rounds of interaction, and that some functionalities cannot be computed in three rounds. This completely settles the round-complexity of perfect actively-secure optimally-resilient MPC, resolving a long line of research. Our lower-bound is based on a novel round-reduction technique that allows us to lift existing three-round lower-bounds for verifiable secret sharing to four-round lower-bounds for general MPC. To prove the upper-bound, we develop new round-efficient protocols for computing degree-2 functionalities over large fields, and establish the completeness of such functionalities. The latter result extends the recent completeness theorem of Applebaum, Brakerski and Tsabary (TCC 2018, Eurocrypt 2019) that was limited to the binary field.

Suppose that you wish to sample a random graph G over n vertices and m edges conditioned on the event that G does not contain a “small" t-size graph H (e.g., clique) as a subgraph. Assuming that most such graphs are H-free, the problem can be solved by a simple rejected-sampling algorithm (that tests for t-cliques) with an expected running time of nO(t). Is it possible to solve the problem in running time that does not grow polynomially with nt? In this paper, we introduce the general problem of sampling a “random looking'' graph G with a given edge density that avoids some arbitrary predefined t-size subgraph H. As our main result, we show that the problem is solvable with respect to some specially crafted k-wise independent distribution over graphs. That is, we design a sampling algorithm for k-wise independent graphs that supports efficient testing for subgraph-freeness in time f(t) · ncwhere f is a function of t and the constant c in the exponent is independent of t. Our solution extends to the case where both G and H are d-uniform hypergraphs. We use these algorithms to obtain the first probabilistic construction of constant-degree polynomially-unbalanced expander graphs whose failure probability is negligible in n (i.e., n-ω(1)). In particular, given constants d>c, we output a bipartite graph that has n left nodes, ncright nodes with right-degree of d so that any right set of size at most nΩ(1)expands by factor of Ω(d). This result is extended to the setting of unique expansion as well. We observe that such a negligible-error construction can be employed in many useful settings, and present applications in coding theory (batch codes and LDPC codes), pseudorandomness (low-bias generators and randomness extractors) and cryptography. Notably, we show that our constructions yield a collection of polynomial-stretch locally-computable cryptographic pseudorandom generators based on Goldreich's one-wayness assumption resolving a central open problem in parallel-cryptography (cf., Applebaum-Ishai-Kushilevitz, FOCS 2004; and Ishai-Kushilevitz-Ostrovsky-Sahai, STOC 2008).