Re: Good enough for crypto?

From: Scott Wilber (swilber_at_comscire.com)
Date: 12/06/03 

Date: 5 Dec 2003 15:33:50 -0800

"r.e.s." <r.s@XXmindspring.com> wrote in message news:<ODMzb.28621$n56.26511@newsread1.news.pas.earthlink.net>...
> "Scott Wilber" wrote ...
> >"r.e.s." wrote ...
> >>"Scott Wilber" wrote ...
> >>>"r.e.s." wrote ...
> >>>>"Scott Wilber" wrote ...
> >>>>>"r.e.s." wrote ...
> >>>>>>"Scott Wilber" wrote ...
>
> >>>>>>> The autocorrelation function of a non-deterministic sequence will
> >>>>>>> always decrease with increasing order. The decrease will either be
> >>>>>>> monotonic or the function will oscillate, and the amplitude of the
> >>>>>>> oscillations will decrease monotonically. This is proved by proving
> >>>>>>> the behavior of the generalized autocorrelation function of the
> >>>>>>> random process, including its measurement device - something I will
> >>>>>>> not try to show in this setting.
> >>>>>>>
> >>>>>>> To the best of my knowledge, this theorem on non-deterministic
> >>>>>>> sequences is original and has never been published before. But,
> >>>>>>> its a big world and if anyone has seen this before, I would like to
> >>>>>>> know.
>
> >>>>>> (To Scott:)
> >>>>>>
> >>>>>> Your "theorem" isn't true, as this counterexample shows:
> >>>>>> Y_i = a*X_0 + b*X_(i+1) (a,b <> 0) (i = 0, 1, 2, ...),
> >>>>>> where X_0, X_1, X_2, ... are nondegenerate iid on {0,1}.
> >>>>>> The autocorrelation function for the Y-sequence is
> >>>>>> R(0) = 1, R(k)(k > 0) = 1/(1 + b**2/a**2) = constant.
> >>>>>
> >>>>> The theorem relates specifically and only to non-deterministic
> >>>>> sequences as is clearly stated. No inference may be made from this
> >>>>> concerning deterministic generators.
> >>>>
> >>>> Eh? The Y-sequence *is* non-deterministic.
> >>>>
> >>> Perhaps I missed the invention of algorithimic true random number
> >>> generators. What is the source of entropy in this generator?
> >>
> >> Your snideness is uncalled for.
> >> Do you understand what nondegenerate iid random variables are?
> >
> > If you thought my response was snide and you didn't like it, why do
> > you think it is OK to reply in the same way?
>
> I *didn't* reply the same way. Your reference to a sum of iid
> random variables first as being deterministic, and then again
> as being an "algorithmic TRNG", suggested you really didn't
> understand what they are, so I asked -- directly.
>
> > Your iid sequence is a mathematical abstraction. A real, physical
> > generator, which is what I am referring to, does not spit out iid
> > random variables. The theorem relates to either continuous numbers,
> > or more typically to binary digits directly produced by a hardware
> > true random number generator. The ACF of this real sequence of bits
> ^^^^
> > can be fully described and hence its behavior over all orders.
>
> You say "this" real sequence, but of course there is no specific
> sequence of bits. An ACF relates to a *mathematical abstraction*
> -- a probabilistic model for such sequences -- otherwise theorems
> & proofs don't even pertain.
>
> You stated a would-be theorem about the autocorrelation functions
> of non-deterministic sequences, without otherwise qualifying those
> sequences. The counter-example is to what you stated.
>
> This is reminiscent of discussions that confuse a "theoretical" OTP
> with its "realizations" in practice.
>
> --r.e.s.

Please educate me. Why is the Y-sequence non-deterministic and where
do the iid random variables come from? Again, what is their source of
entropy?

BTW, a theoretical ACF is not a probabilistic model, but is an exact
equation that will predict the measured values of the modeled system.
It is only the measurements that are probabilistically distributed,
and this distribution will converge to the predicted values if the
model is accurate.

Scott

Relevant Pages

  • Re: Good enough for crypto?
    ... >> Do you understand what nondegenerate iid random variables are? ... Your reference to a sum of iid ... You say "this" real sequence, but of course there is no specific ...
    (sci.crypt)
  • Asymptotics of Abs( Sum of sequence of rand var)
    ... I am interested in the asymptotics of the absolute value of the sum of a sequence of random variables ... Define X1...Xn iid with all moments finite ...
    (sci.math)
  • Re: How Chapman-Kolmogorov implies Markov ??
    ... Perhaps the notation "f_i" is supposed to imply there is ... something equivalent about all of these random variables, ... concept, that we index the index set iself, or else write a finite ... sequence in it, explicitly using the integers as our indices. ...
    (sci.physics)
  • Re: How Chapman-Kolmogorov implies Markov ??
    ... something equivalent about all of these random variables, ... concept, that we index the index set iself, or else write a finite ... sequence in it, explicitly using the integers as our indices. ... engineer his intentions through the ambiguities, ...
    (sci.physics)
  • Re: Basic Doubts regarding sequence of Random Variables and Stochastic Process?
    ... I have couple of basic doubts regarding sequence of random variables/ ... discrete time stochastic process defined ... A = set of all sequence of Random Variables on some probability ...
    (sci.math)