[6868] in cryptography@c2.net mail archive
neighborhood namespace
daemon@ATHENA.MIT.EDU (Wei Dai)
Thu Mar 30 15:18:55 2000
Date: Thu, 30 Mar 2000 04:46:52 -0800
From: Wei Dai <weidai@eskimo.com>
To: cypherpunks@openpgp.net, cryptography@c2.net
Message-ID: <20000330044652.N29936@eskimo.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
I have a new idea for solving the name-to-key binding problem in
public-key cryptography: allow multiple conflicting names that point to
different keys (or in general arbitrary files or objects) in a global
namespace, then use collaborative filtering to select the one that's most
relevant to a particular user. It's like a secure version of Google, or
PGP's web-of-trust taken one step further.
To use the system a user first defines his immediate neighborhood (a set
of name,key pairs called Named Entities) with at least one neighbor (he
has to obtain this through some other method). For each of his immediate
neighbors, he sets two real number attributes (collectively called his
Belief about that neighbor):
Acceptance - how much he believes the key belongs to the name (zero is
neutral, negative if he believes it's an attempt at impersonation)
Reliance - how much he trusts certificates signed by the key
His Beliefs are signed and published to a certificate server (assume for
the moment there is a central certificate server that everyone uses). Now
using his Beliefs and those of his neighbors and his neighbors' neighbors
etc., we recursively compute for him two real number attributes for each
Named Entity (collectively called the Named Entity's Reputation in the
user's extended neighborhood):
Popularity - this will be used to rank conflicting names
Trust - a measure of how much the neighbors trust the Entity's
certificates
The algorithm for doing this computation is recursively defined as
follows:
Popularity(source, target) := Reputation(source, target, {source})
Popularity(source, target, excludedSet) :=
source's Acceptance of target + sum over all Named Entities e in source's
immediate neighbor that's not in excludedSet, Discount(source's Reliance
of e, Popularity(e, target, excludedSet U {e}))
Computing Trust is similar, just replace Acceptance above with Reliance.
This algorithm has a very bad worst case running time, but I
think it is practical for typical Belief graphs, especially if
appropriate pruning of the recursion tree is done when
the intermediate value computed will be too deeply discounted to matter
much to the final result. The Discount function is tentatively defined as
follows, in C code. The idea is to map value from the reals to the
interval (-reliance, +reliance).
static double Discount(double reliance, double value)
{
double r = 1 - pow(2, -reliance);
if (value <= 0)
return log(1-(1-pow(2, value))*r)/log(2);
else
return log(1/(1-(1-pow(2, -value))*r))/log(2);
}
With this system in place, when you search for a key by using, say, the
name Bob, and even though there might be millions of legitimate keys out
there named Bob, and millions more that are impersonation attempts, you
will automaticly get a list that are mostly likely to be the real Bob
you're looking for. If you enter a more complete name the system can
just pick the most Popular key with that name and skip presenting you
with a list. It should be even easier than email address.
I hope this idea will finally make public-key cryptography easy enough
for most people to use on a daily basis, and I believe it can also be
used to solve the kind of namespace problem that FreeNet, for example, is
facing.
