In our analogy, we view the entities involved as nodes (vertices) in a (possibly directed) graph and a secure link between two entities is expressed as a (possibly labeled) edge (arc) between them. A secure link may correspond to a physically secure link or to a shared key obtained without the help of a third party. We call the graph the "security graph".
As in network reliability we will discuss two models for trust, a deterministic one and a probabilistic one. To start discussing our viewpoint about trust we start with an example. Assume that the entities are {A,B,C,D} and that all pairs of entities, but (A,D), have received each other's public key without the help of a third party. This means that D has full trust in B RELATIVE to the authenticity of B's public key and a similar relative trust exists between D and C. However when D wants to obtain a certificate of A's public key then the relative trusts in B and C does not imply that B and C can be trusted relative to this certificate. In our deterministic model, we define trust relative to two entities as being a Boolean expression induced from the security graph, i.e. B OR C. This means that if D wants to obtain A's public key, D needs to trust that B and C will never be both dishonest.
To define, in general, relative trust for our deterministic model we say that the trust in a path is 1 if the path has length one, else it is the logical AND of all the intermediate nodes. Trust between n_i and n_j is the logical OR of all the trust in simple paths between n_i and n_j.
We now discuss some of the results this model implies. First, the BAN principle of transitivity of trust implies that a single path between sender and receiver is used to obtain the public key (of the sender or of the receiver). Our trust model says that if one of the nodes in this single path becomes corrupt, the security vanishes, as has been observed before by several researchers. Secondly, if multiple paths exist between entities it is better to use these simultaneously. For authenticity this means sending the same information in parallel. These facts can easily be formalized using our probabilistic model.
In our probabilistic model we give to each vertex in the security graph a probability of being trustworthy. If these probabilities are all independent, the Boolean expression transforms easily into a probability. Note that in this model this probability will always be 1 if (n_i,n_j) is an edge. Note that in Beth-Borcherding-Klein (ESORICS '94) it has been observed that trust between two entities should decrease when these are farther apart (see also PGP for a more primitive variant of this approach). This goal is naturally achieved in our model.
If the model is not a probabilistic, but threshold one (i.e. there are at maximum u-1 dishonest entities), then it makes only sense to use disjoint paths simultaneously and u-connected graphs are the solution.
An alternative probabilistic model in which we allocate the probability to an edge and not to a vertex is also well known in network reliability and its advantages/disadvantages in the context of trust will be briefly discussed.
For PRIVACY simultaneous use of paths implies using the one-time path for each OR in the Boolean expression (more generally using threshold schemes).
For more information, contact desmedt@cs.uwm.edu.