[11466] in cryptography@c2.net mail archive
Re: Extracting uniform randomness from noisy source
daemon@ATHENA.MIT.EDU (Paul Crowley)
Mon Aug 12 10:37:30 2002
To: John Kelsey <kelsey.j@ix.netcom.com>
Cc: daw@mozart.cs.berkeley.edu (David Wagner),
cryptography@wasabisystems.com
From: Paul Crowley <paul@ciphergoth.org>
Date: 12 Aug 2002 10:56:50 +0100
In-Reply-To: John Kelsey's message of "Sun, 11 Aug 2002 16:45:52 -0400"
OK, here's an attempt at a formal definition of how secure a keyed
hash function is for entropy collection.
Here's the game. Our attacker selects an algorithm MUNGE which takes
an unbounded stream of random bits as input and generates random
strings as output. We then select a key K and reveal it to the
attacker. We take a secret unbounded stream, feed it to MUNGE, and
hash the output, using the key K. The attacker then makes as many
guesses about the output as they want until they get it exactly right.
The hash function is (H,t,p)-secure for entropy collection if for any
choice of attacker such that the entropy of the output of MUNGE is H
or greater and the total work of the attacker (including MUNGE) is
bounded by t, then the probability of a correct guess is p.
I suspect you can do without the key in an asymptotic model, but I'm
not so sure in the concrete model.
--
__ Paul Crowley
\/ o\ sig@paul.ciphergoth.org
/\__/ http://www.ciphergoth.org/
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com
