Re: Computational secure entropy extraction
From: Ernst Lippe (ernstlatplanetdotnl_at_ignore.this)
Date: 10/28/04
 Next message: Skybuck Flying: "trying to predict next rand value"
 Previous message: Skybuck Flying: "rand() on linux ?"
 In reply to: Anton Stiglic: "Re: Computational secure entropy extraction"
 Next in thread: David Wagner: "Re: Computational secure entropy extraction"
 Reply: David Wagner: "Re: Computational secure entropy extraction"
 Reply: David Wagner: "Re: Computational secure entropy extraction"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Thu, 28 Oct 2004 22:18:15 +0200
On Thu, 28 Oct 2004 07:45:17 0700, Anton Stiglic wrote:
> Ernst Lippe <ernstlatplanetdotnl@ignore.this> wrote in message
> news:<pan.2004.10.27.11.56.00.42480@ignore.this>...
>> Somewhere hidden in the /dev/random thread was a nice discussion about
>> distilling entropy from an unknown distribution. One of the main topics
>> was if there existed some universal entropy distiller that could be used
>> on all input distributions. With a information theoretical definition of
>> security such an animal does not exist. But the situation becomes a lot
>> more interesting when we have two different and independently
>> distributed inputs and use a computational security approach.
>>
>> One of the questions that David Wagner asked was if it was possible to
>> show that there existed a universal entropy distiller with two
>> independent inputs that was computationally secure. I believe that under
>> certain conditions the answer is "yes".
>>
>> An mbit distiller D(k,x) takes strings k,x of specified fixed length n1
>> and n2 respectively as inputs and produces an mbit string.
>>
>> D is (h1,h2,t,epsilon)secure if given that k is drawn from any
>> distribution with minentropy h1, and x is drawn independently from any
>> distribution with minentropy h2, no attack running in time at most t
>> can distinguish D(k,x) from uniform with advantage better than epsilon.
>>
>> I will only consider the case where k contains maximum entropy, i.e.
>> where h1 = n1. In a certain sense this is the optimal case, if it is not
>> possible to securely extract entropy under these conditions "secure
>> entropy distillation" is certainly not possible.
>
> There has been allot of work done in this area, notably by David
> Zuckerman, with information theoretical results. Are you aware of these
> results?
I have tried to read some of his papers, but from what I can
see his approach uses an information theoretical perspective (because
it considers all possible input distributions, instead of only
the ones that could effectively found by an adversary).
> If you have long enaugh random string, you can always use it to pick a
> universal hash function and hash the other distribution that does not have
> full entropy (IIRC this is related to the leftover hash lemma).
>
> What I would like to see is an extractor that doesn't need any true
> randomness, and that can smooth out a distribution that has n minentropy
> to a uniform distribution of n bits or something close to that.
> Computational setting would be fine (doesn't have to be information
> theoretical...), as long as the assumptions are reasonable (not just
> saying that SHA1 acts like a random oracle...).
It seems that you are objecting to my requirement that k should have
maximal entropy (i.e. h1=n1).
It turns out that this was completely unnecessary for this
simple analysis (I needed it for another analysis that
I have not posted yet).
The adversary constructs a set Tk of k values and Tx of x values, where
Tk = 2^h1 and Tx = 2^h2.
Suppose that the adversary has examined A combinations in the cartesian product
Tx X Tk and that H of them are hits. Then the advantage
epsilon = (H  A 2^(m)) 2^(h1  h2)
Because A >= H we have epsilon <= H*(1  2^(m)) 2^(h1  h2)
and consequently H >= epsilon 2^(h1 + h2) / (1  2^(m)). But in order to
get H hits the adversary has to examine at least H * 2^m elements, so we get
t >= epsilon 2^(h1 + h2 + m) / (1  2^(m))
This is the same result that I got in my previous post.
Ernst Lippe
 Next message: Skybuck Flying: "trying to predict next rand value"
 Previous message: Skybuck Flying: "rand() on linux ?"
 In reply to: Anton Stiglic: "Re: Computational secure entropy extraction"
 Next in thread: David Wagner: "Re: Computational secure entropy extraction"
 Reply: David Wagner: "Re: Computational secure entropy extraction"
 Reply: David Wagner: "Re: Computational secure entropy extraction"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
