Re: Good enough for crypto?

From: r.e.s. (r.s_at_XXmindspring.com)
Date: 12/04/03 

Date: Thu, 04 Dec 2003 20:17:50 GMT

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

Relevant Pages

  • Re: Good enough for crypto?
    ... > random variables first as being deterministic, ... >> Your iid sequence is a mathematical abstraction. ... It is only the measurements that are probabilistically distributed, ...
    (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)
Loading