M. Burmester, Y. Desmedt, and Y. Wang (USA)
Dependable computation, fault tolerance, security
We consider the problem of fault-tolerant dependable com putation 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. In deed, 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 com putation 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 depend able computations with an appropriate level of abstraction. We then apply this model to show that fault-tolerant de pendable 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 computa tion with single inputs that requires finding vertex-disjoint paths, for which there is a polynomial time algorithm.
Important Links:
Go Back
