From: loki@infonex.com (Lance Cottrell)
Date: Thu, 9 May 1996 20:40:48 +0800
To: Raph Levien <cypherpunks@toad.com
Subject: Re: Transitive trust and MLM
Message-ID: <adb72eeb0b021004f545@[206.170.115.3]>
MIME-Version: 1.0
Content-Type: text/plain


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
----------------------------------------------------------