At 11:32 AM 5/8/96, Raph Levien wrote: <SNIP>

One encouraging consequence of this model is that densely connected subgraphs can result in highly trusted keys even if p itself is quite small. In a clique of size k, the trust is (very) roughly 1-(1-p)^k. For example, if p is a mere 50%, then in a clique of size 10, each key in the clique is trusted with a probability of 99.9%. This computation is (I think) known as the network reachability problem, and is probably quite hard to evaluate. In practice, you'd probably want to compute upper and lower bounds instead,

Let's see if we can come up with a model that preserves this property of giving high trust values to densely connected keys, yet is also highly resistant to (some plausible model) of attacks against the Web of trust.

Raph

I like this. The most obvious attack on key signatures is to cross sign a huge number of bogus keys, is of no benefit. As the density of this bugus-clique increases, it comes closer and closer to acting as a single entity for trust calculations. Then your trust calculation for any key in the clique is simply your trust of the real key which signed all the bogus ones. It should be no time at all before most reputable key signers cut all links to that key. Another nice property of this calculation of probability is that it automatically drops off exponentially with the number of links (at least along any one chain). We need to think about how much we want multiplicity of paths to bolster our trust. Here is the scenario I want to avoid: Mallet creates a large number of keys: A, B, C[...]. C is a large set of keys. A is the Key Mallet uses publicly. It has a few signatures. B is the key Mallet uses to sign keys who's trust he wants to boost. In addition to signing B with A, Mallet also signes all the C[i] with A, and signs B with all the C[i]. This multiplicity of paths should not boost the trust in any key which is reached through this complex. In general it may be difficult to decipher which paths you want to follow in multiply (and cyclically) connected paths. I suppose one approach to this would be to pick various ways of calculating trust, and see if anyone can come up examples to attacks to exploit them. -Lance ---------------------------------------------------------- Lance Cottrell loki@obscura.com PGP 2.6 key available by finger or server. Mixmaster, the next generation remailer, is now available! http://www.obscura.com/~loki/Welcome.html or FTP to obscura.com "Love is a snowmobile racing across the tundra. Suddenly it flips over, pinning you underneath. At night the ice weasels come." --Nietzsche ----------------------------------------------------------