# Re: Computational secure entropy extraction

**From:** Ernst Lippe (*ernstl-at-planet-dot-nl_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 <ernstl-at-planet-dot-nl@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 m-bit distiller D(k,x) takes strings k,x of specified fixed length n1
*

*>> and n2 respectively as inputs and produces an m-bit string.
*

*>>
*

*>> D is (h1,h2,t,epsilon)-secure if given that k is drawn from any
*

*>> distribution with min-entropy h1, and x is drawn independently from any
*

*>> distribution with min-entropy 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 min-entropy
*

*> 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 ]