Re: new /dev/random

From: Paul Rubin (//phr.cx_at_NOSPAM.invalid)
Date: 10/12/04 

Date: 11 Oct 2004 16:34:33 -0700

daw@taverner.cs.berkeley.edu (David Wagner) writes:
> 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.

OK. Maybe something more is needed for both versions though:

D is (h1,h2,epsilon)-secure if for any n, the ensemble

  {D(k,x1), D(k,x2), ..., D(k,xn)}

is indistinguishable from uniform except with advantage at most, hmmm,
maybe epsilon*n^c for some c. Otherwise D might ignore x (Michael
Amling gave an example) and be perfectly secure through one query and
useless afterwards, not what we want for a distiller. The different
x_i's don't have to come from the same distribution. The distribution
of x_i must have min-entropy >= h2, but it can depend on the values
actually drawn for x1,...,x_(i-1). k is still independent of all the x_i.

This is kind of messy--got a cleaner way of saying it? Perhaps it's
not needed at all, if we can combine previous D(k,x_i)'s to find
D(k,x_(i+1)) preserving D's security, i.e. something like CFB mode.

> 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.

Maybe for the computational variant there's also some kinds of
distributions you don't have to worry about. But D also has to be
efficiently computable. So we're back to cryptography.

> 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.

Yeah, I agree, at least for the unbounded case, there's some hope of
proving something. For the computational case, it sounds as hard as
proving there are secure ciphers, i.e. very difficult.

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, ... zero; ... Can one show that Dis fairly close to uniform, as long ...
    (sci.crypt)
  • Re: new /dev/random
    ... > x is drawn independently from any distribution with min-entropy h2, ... Another question would be whether a random oracle meets this notion. ...
    (sci.crypt)