Re: Poisson numbers for random keyspace assignment

[tcmay@got.net (Timothy C. May)]

At 2:49 AM 8/31/95, MONTY HARDER wrote:
>                  [Great statistical summary deleted]

Thanks. Two other people sent me e-mail saying the odds of a keyspace chunk
being left uncovered are 1/e, so this part is pretty well known. (With an
expectation of "1" of course, as I noted. Interestingly, this was the same
formula we used at Intel to figure out chip yields: "What's the probability
that a chip will have zero defects given that m defects are the "expected"
number?")

I wanted to explain the derivation in more detail than just saying 1/e,
especially for the more interesting cases where the keyspace gets more
coverage. (Where the m = expected value is more than 1.)

>TC> * For opportunistic attacks on keys in challenges, the odds are 95% that a
>TC> key will be found with only twice the total effort (or time) using a
>TC> totally random method of picking up keyspace to search.
>
>  The odds can be improved somewhat by scaling the granularity of the
>sweep to the size of the sweep. (Align larger chunks on large-chunk
>boundaries, eliminating the chance of overlap with other large chunks.)

Indeed, this is an effect to consider. That is, each searcher is
(presumably) not overlapping, so the results I reported are sort of a bound
on the actual numbers. At one end, with lots of searchers doing very small
fractions of the total, the results are pure Poisson. At the other end,
with a searcher covering most or all of the keyspace, then of course the
results are those of nonrandom search. Practically speaking, with dozens or
hundreds of searchers, the Poisson results produce accurate enough
estimates.

>  The best advantage of the random method is that it allows people to
>participate completely anonymously, as there is nothing to report save
>the Eureka!, and that can be done through a remailer anyway. When the
>challenge is solved, everyone can stop cracking.

A very good point! Anonymous cracking has many advantages.


--Tim May

---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
Corralitos, CA              | knowledge, reputations, information markets,
Higher Power: 2^756839      | black markets, collapse of governments.
"National borders are just speed bumps on the information superhighway."