I'm really glad to see this thread. I think this is a problem that is well worth thinking about. I think what is really called for is a model of when keys are likely to be bogus, and when signatures, etc., are likely to be correct. Before going into the math, I'll go through some examples. Any key that's "well connected" in the MIT keyring is likely to be good. Specifically, if it's signed by lots of people, and each of those people is reachable from my trust root, then I'm pretty much willing to believe the key is good. Unfortunately, there are a fair number of reasons why a key may be bad. A really _cool_ thing to do with a compromised machine would be to sign a big bunch of bogus keys. Given how easy it is to compromise a machine, this is a very real worry. I don't know if this attack has been realized yet, but it's best to assume it could be and will be. Another weakness is the "clueless user" who signs keys gotten from the Net, or otherwise not properly verified. I don't claim to know all of the vulnerabilities, but I do think it would be a good idea to quantify them before designing a key distribution system. Hal calls into question the value of signed keys. To me, this points to the pressing need for better manual verification of keys, by communicating secure hashes through the phone and on physical channels, including business cards. These channels are more secure than the Net, are more convenient for all but the most hardcore net.heads, and would actually work quite well, I think. But I do think it would be nice to have access to "probably good" keys for casual e-mail. With luck, a densely connected Web of manually obtained keys can serve as a good foundation for the latter. Now for the mathematical model. Signatures can bind keys to e-mail addresses, or act as assertions that the signed public key is trusted to transitively sign other keys. Let's assume that each signature has a certain probability p of being good, and a 1-p probability of being bogus, and that all probabilities are independent. These are probably bad assumptions in the real world, but that's the difference between theory and practice. Now we can actually evaluate the probability of a given key being good. Consider a Monte Carlo process in which each edge in the graph is present with probability 1-p. For each run, we determine whether the recipient's public key (actually the binding between public key and recipient's e-mail address) is reachable from our trust root. The probability over a large number of runs is (given our assumptions) the probability of the key being good. 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