From: Bill Stewart <stewarts@ix.netcom.com>
Date: Sun, 3 Mar 1996 09:20:55 +0800
To: "marcus (m.d.) leech" <mleech@bnr.ca>
Subject: Re: Web of Trust vs other models
Message-ID: <199603030054.QAA28602@ix7.ix.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


At 09:48 AM 3/1/96 -0500, you wrote:
>There are a pool of 1 million keys.  Each of those keys is signed by between
>  two and 5 other randomly chosen keys in the pool.  
>  Each signature implies a trust relation between the key and the signer.
>Given that, determine mean, min, and max path lengths for purposes of
>  "certification".
>Has anyone done this experiment?

Probably been done, though not necessarily in a PGP context. 
The problem is equivalent to analyzing a randomly selected directed graph,
and some Operations Research or CS grad student has probably done it.

Meanwhile, Don Kitchen at one point collected all the data off the
MIT keyserver for analysis, which is a much different problem than
random signatures.  I found that the chain from some middle point,
such as Phil Zimmermann's or Derek Atkins's key was about 12-14 levels
deep, averaging about 6, which compares interestingly with the
default PGP depth limit of4.  From my key, it was pretty deep,
especially since my certification from Phil Karn was from one of
his older keys, which is why I asked Derek to sign my key...

#--
#				Thanks;  Bill
# Bill Stewart, stewarts@ix.netcom.com / billstewart@attmail.com +1-415-442-2215
# http://www.idiom.com/~wcs     Pager +1-408-787-1281