From: IN%"eli+@GS160.SP.CS.CMU.EDU" 13-MAY-1996 19:59:41.90

EALLENSMITH@ocelot.Rutgers.EDU writes:

...

The different paths going through those different signatures will be correlated/non-independent, yes.... but that isn't the problem unless you're considering multiple paths (in a more complicated version).

To determine key validity, you do have to consider all paths. If a single trusted path to the bad key exists, the attacker wins.

Hmm.... a useful distinction in this is between multiple paths with no common elements except the beginning and end and ones with common elements. The sections of the ones with common elements that have no common elements can probably be treated as a subset of the larger path - a virtual link, if you will - with its values (trustworthiness et al) determined by the paths contained within it.

...

IIRC, there have been some sociological studies showing that _everyone_ is linked through 6 or so people.

Milgram's "small world" experiments used a much looser sort of "link" than we want here. It would be certainly interesting to know how large a difference this makes.

Milgram? Thanks, I'll check for that name.

It's true that you don't need to talk to everybody. The problem is that I might want to talk to people whom I don't know personally, but know by reputation, or by function ("DEA Rat Hotline" -- well, maybe not).

I'm not disputing that... just that you don't need to be able to go through the web to reach everyone who's got a key. Admittedly, the subsection of people who have keys are more likely (through being more technologically sophisticated et al, on average) to be useful to contact than those who don't. -Allen