2014/05/06 by George Saad, Jared Saia, Saad, George +1 · 3 citations
Computer Science · #Blockchain Technology Applications and Security #Complexity and Algorithms in Graphs #Cryptography and Data Security #Cryptography and Security (cs.CR) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.CR #cs.DC
paper · pdf · doi:10.48550/arxiv.1405.1167
17 pages and 1 figure. It is submitted to SSS'14
openalex publication_date 2014/05/06 · arxiv created 2014/10/27 · arxiv updated 2014/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the problem of reliable multiparty computation (RC), there are n parties, each with an individual input, and the parties want to jointly compute a function f over n inputs. The problem is complicated by the fact that an omniscient adversary controls a hidden fraction of the parties. We describe a self-healing algorithm for this problem. In particular, for a fixed function f, with n parties and m gates, we describe how to perform RC repeatedly as the inputs to f change. Our algorithm maintains the following properties, even when an adversary controls up to t ≤ ((1)/(4) - ε) n parties, for any constant ε>0. First, our algorithm performs each reliable computation with the following amortized resource costs: O(m + n log n) messages, O(m + n log n) computational operations, and O(ℓ) latency, where ℓ is the depth of the circuit that computes f. Second, the expected total number of corruptions is O(t (log* m)2), after which the adversarially controlled parties are effectively quarantined so that they cause no more corruptions.