Re: new /dev/random

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 10/11/04 

Date: Mon, 11 Oct 2004 20:48:50 +0000 (UTC)

Paul Rubin wrote:
>How's this: an n-bit distiller D(k,x) takes strings k,x of specified
>fixed length, and produces an n-bit string.
>
>D is (h1,h2,epsilon)-secure if,
> Given k is drawn from any distribution with min-entropy h1, and
> x is drawn independently from any distribution with min-entropy h2,
> (min-entropy(D(k,x))) > (n-epsilon).

Sounds very promising.

My version would be a slight tweak:

D is (h1,h2,epsilon)-secure if,
   Given k is drawn from any distribution with min-entropy h1, and
   x is drawn independently from any distribution with min-entropy h2,
   then D(k,x) is indistinguishable from uniform except with
   advantage at most epsilon.

We could also consider a computational security variant:
D is (h1,h2,t,epsilon)-secure if [...] no attack running in time at
most t can distinguish D(k,x) from uniform with advantage better than
epsilon.

Next, I'm trying to figure out whether it is plausible that there
exists a deterministic function D that satisfies the above requirements.
It seems very plausible to me. At least, I can't think of any universal
counterexample (in contrast to the case where you draw from just one
distribution, where there is a universal counterexample).

It would be interesting if there is any function one can prove to meet
this requirement. (Kind of a generalization of 2-universal hashing.)

Another question would be whether a random oracle meets this notion.
(Obviously, one should allow the distributions to depend on the
random oracle D.)

Relevant Pages

  • Re: An inference/estimation question
    ... each pair drawn (he tells you how he is generating your data, ... the distribution his raw observations are drawn from). ... so you have lost all information on symmetry. ...
    (sci.stat.math)
  • Re: Augmenting a sample from unbounded distribution, until no values are above or below threshold.
    ... I am working on a problem where I require a sample of numbers drawn from a distribution that has no bounds. ... The issue is that some values that may be drawn from these distributions do not make any sense for the task I am working on. ... Also, any number lying outside the 'threshold of realism' I cannot just set to threshold values, because that would not be realistic either. ...
    (comp.soft-sys.matlab)
  • Re: An inference/estimation question
    ... the distribution his raw observations are drawn from). ... You can see that the result has to be centered on zero, ... so you have lost all information on symmetry. ...
    (sci.stat.math)
  • Re: new /dev/random
    ... > x is drawn independently from any distribution with min-entropy h2, ... is indistinguishable from uniform except with advantage at most, hmmm, ...
    (sci.crypt)
  • Re: new /dev/random
    ... > Given k is drawn from any distribution with min-entropy h1, ... > distinguish Dfrom uniform with advantage better than epsilon. ... success rate for the attacker, e.g. an attacker should only be able to achieve ...
    (sci.crypt)