Self-Healing Computation
This addresses the challenge of secure and efficient distributed computing for systems like blockchain or cloud networks, though it appears incremental as it builds on existing RC frameworks.
The paper tackles the problem of reliable multiparty computation (RC) in the presence of an adversary controlling up to a fraction of parties, by introducing a self-healing algorithm that performs repeated computations as inputs change, achieving amortized costs of O(m + n log n) messages and operations, O(ℓ) latency, and limiting total corruptions to O(t (log* m)^2).
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 \leq (\frac{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(\ell)$ latency, where $\ell$ 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.