Re: The Cost of Snakeoil

Ben Laurie (ben@algroup.co.uk)
Sun, 26 Jul 1998 21:08:17 +0100

• Next message: Werner Koch: "Re: RNG in a Smart Card"
• Previous message: Peter Gutmann: "Re: Any KEA implementations out there?"
• Maybe in reply to: Ray Arachelian: "Any KEA implementations out there?"

David Wagner wrote:
> Claim. The intersection of I' and J will be non-empty with
> good probability.
> Proof. An easy application of the birthday paradox: I' and J
> are random, with |I'| = |J| = 2^{28}, so the probability
> of an empty intersection is
> (1 - 2^{-56})^{2^{56}} ~ e^{-1} ~ .368.
> This failure probability can be easily made exponentially
> small by increasing the size of |I'| and |J| by a constant
> factor.
>
> Does that seem right? I could well be doing something wrong.

Hmmm ... I can't think of any obvious flaw with this argument, except
that the probability of an empty intersection is surely
(1-2^(-28))^(2^28), which is just a detail.

Nice one.

Cheers,

Ben.

-- 
Ben Laurie            |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant  |Fax:   +44 (181) 735 0689|http://www.apache.org/
and Technical Director|Email: ben@algroup.co.uk |
A.L. Digital Ltd,     |Apache-SSL author     http://www.apache-ssl.org/
London, England.      |"Apache: TDG" http://www.ora.com/catalog/apache/
WE'RE RECRUITING! http://www.aldigital.co.uk/recruit/

• Next message: Werner Koch: "Re: RNG in a Smart Card"
• Previous message: Peter Gutmann: "Re: Any KEA implementations out there?"
• Maybe in reply to: Ray Arachelian: "Any KEA implementations out there?"