A CRITICAL ANALYSIS OF MODELS FOR FAULT-TOLERANT AND SECURE COMPUTATION

摘要

We consider the problem of fault-tolerant dependable computation with multiple inputs. Although the traditional model assumes that the number of faults is relatively small when the enemy has limited resources, this assumption is unreasonable when some faults may be interdependent. Indeed, a computation system may have several replicated components and the adversary may exploit a common weakness of these so as to cause simultaneous failure. In this paper we introduce models for secure distributed computation with multiple inputs that tolerate dependent faults. In particular, we consider AND/OR graphs with colored vertices and show that they can be used to model dependable computations with an appropriate level of abstraction. We then apply this model to show that fault-tolerant dependable computation with multiple inputs can only be achieved if an appropriate number of color-disjoint solution subgraphs is found. Finding such subgraphs is NP-hard. This is in contrast to the problem of dependable computation with single inputs that requires finding vertex-disjoint paths, for which there is a polynomial time algorithm.