From: Bill Stewart <stewarts@ix.netcom.com>
Date: Mon, 4 Mar 1996 06:14:01 +0800
To: Laurence Lundblade <lgl@qualcomm.com>
Subject: Re: A brief comparison of email encryption protocols
Message-ID: <199603030038.QAA06274@ix2.ix.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


At 09:01 AM 2/29/96 -0800,  Laurence Lundblade <lgl@qualcomm.com> wrote:
.....CME wrote....
>>Like X.509, my certs have an Issuing-name and a Subject-name -- but
>>they're both cryptographic hashes of public keys.  You can take a portion
>>of those hashes [e.g., low order 12 bits] and use it to index a hash table
>>of certificates or keys.  The cert is more general than X.509 -- that is,
......
>Isn't using a hash as the identifier replicating the key distribution
>problem that PGP has or are you including some other data that can be used
>to look up the cert?  I think a problem occurs when you have 20 billion of
>these certs (two for every person in the year 2010 or such).  A simple hash
>into a table isn't going to cut it because you a single database (with
>replication?) isn't going to be possible.  Some hierarchical lookup like
>DNS is going to be needed. The look ups are needed to check for revocation.

There's a name collision on the word "hash" here.  Carl was using both
hashes in the same sentence.  A "cryptographic hash" is a strongly one-way
mapping from an input string (in this case a public key) to a number.
A hash table is a data structure that uses a mapping from an input string
to a number to decide where to put things.  An MD5 cryptographic hash
function used on PGP public keys (e.g. to get the fingerprint) is
64 bits long, so there may be a few collisions if there are 2**34 keys
out there; if things scale to that point, PGP 4.1.3 need to use SHA for
fingerprints instead (or in addition).  Carl is proposing using a 
hash table (indexed by a hash-table hash of the cryptographic hash)
to store public keys; that's a separate problem, though of course if you
want to store 20 billion keys in one place, there are better data structures
than simple hash tables.

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