From: frantz@netcom.com (Bill Frantz)
Date: Tue, 9 Jul 1996 10:34:06 +0800
To: cypherpunks@toad.com
Subject: Re: NYT/CyberTimes on CWD article
Message-ID: <199607082221.PAA27343@netcom8.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


At  3:01 PM 7/6/96 -0800, Norman Hardy wrote:
>At 9:17 AM 7/6/96, Declan McCullagh wrote:
>>"We are writers, not crytographers."
>>
>>-Declan
>....
>This seems to be an application for Bloom filters.
>See page bottom of page 561 in Knuth's "Searching and Sorting", First Edition.
>(Vol 3 of Art of Computer Programming)
>
>With a Bloom filter you can hide which URLs you reject yet quickly rejecting
>particular URLs.
>
>Compute SHA(URL) yielding 160 bits. Divide that into 16 ten bit quantities
>b[i], for 0<=i< 10.
>Reject the access if P[b[i]] = 1 for each i. P is an array of 1024 bits
>computed by someone
>with the index prohibitorum. (pardon my Latin)
>
>Yes, this excludes 1/1024 "falsely accused" URLs, but you get the idea.

As Norm knows, we used this algorithm to provide a label search function
(What Unix people use grep for) for an IBM OS back in the 1970s.  SHA is
probably overkill for the hash function, but you need something better than
a barber poll hash.


-------------------------------------------------------------------------
Bill Frantz       | The Internet may fairly be | Periwinkle -- Consulting
(408)356-8506     | regarded as a never-ending | 16345 Englewood Ave.
frantz@netcom.com | worldwide conversation.    | Los Gatos, CA 95032, USA