[ Changed 12th November 1996 ]
Reliability against failures from faulty links in an open network is usually assured by employing a network which has an appropriate topology. Security is assured by authenticating (and/or encrypting) the exchanged messages. For this, however, a certain degree of trust among the participating entities is needed. `Trusted paths' can be regarded as edges of a graph which we call the security graph. Usually it is assumed that this graph is almost complete, and that the entities are aware of its topology. In our scenario this is not the case.
We link trust with reliability, by analyzing the security graph. There are two models, a deterministic one in which the relative trust in a path is a Boolean expression, and a probabilistic one in which the vertices are assigned probabilities, and the trust in a path is a probability associated with the Boolean expression. We then discuss the `consensus problem' in the new scenario.
The talk is based on recent work with Yvo Desmedt. It is related to earlier work by Beth-Borcherding-Klein, Maurer and Reiter-Stubblebine, but differs in some important respects.