I just noticed that a paper was published at the RSA conference with
concepts that might be relevant to the PGP web of trust.
http://discovery.csc.ncsu.edu/~pning/pubs/robust-keyrings.pdf
Improving Robustness of PGP Keyrings by Conflict Detection, by Q Jiang
et al of North Carolina State University.
One concept they discuss is the use of redundancy in the WoT. This idea
goes back to PGP 2; you can mark introducers as partially trusted,
and then if you have two chains of trust leading to the same key, both
partial, this can add up to full validity. We extended this internally
in later versions of PGP to support full probabilistic calculation based
on a paper by Ueli Maurer.
However a problem with this is that if a user has two keys, both marked
as partially trusted, and both sign a third key, that key can end up
as fully valid, even though only one user signed it. Internally at
PGP.com we discussed this years ago and thought about providing a way
to indicate that one or more keys were controlled by the same user,
but the UI would be so complex that we gave up on it. (Ironically,
the sample keyring we distributed at one point had two keys on it by the
same person, with both keys signing other keys on the keyring, so we were
setting up a situation which practically begged for this flaw to show up.)
The new paper does not use a probabilistic model, but rather assumes
that users are either malicious or reliable. It attempts to distinguish
the two by detecting conflicts, where the same identity is bound to
two different keys. It takes such a conflict as evidence of malicious
behavior and uses graph theory to try to figure out which keys are the
malicious ones. These can then be eliminated from the WoT and then the
resulting signatures are taken to be correct.
There is a large literature on trust issues in WoT-like structures.
I'll see if I can find an up-to-date bibliography on the subject, or
perhaps someone here knows of one.
Hal Finney