Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:22
Adam Back (aba@dcs.ex.ac.uk)
Wed, 21 Oct 1998 15:02:11 +0100
Mok-Kong Shen writes:
> Niels Möller wrote:
> > In the eurocrypt-98 rump session, Adi Shamir proposed the following
> > construction:
> >
> > Given some pseudorandom function F (iirc, Shamir used a hash function,
> > but the same should apply to a block cipher with a fixed (secret)
> > key), construct a sequence by iterating
> >
> > x_0 = some secret seed value
> > x_{i+1} = F(x_i) + i (where + is addition or bitwise xor).
> >
> > This simple construction guarantees that there are no short cycles,
> > because if i != j, then x_i = x_j implies x_{i+1} != x_{j+1}. The
> > sequence can't repeat until the counter wraps around.
>
> I haven't yet understood the stuff. The above does not seem to
> exclude the possibility of, say, x_{i+2} = x_{j+2}.
I doesn't exclude the possibililty of repeats in the output from the
generator. But then it shouldn't exclude reapeats because then it
would be biased, each iteration restricting the number of possible
outputs.
But what it does do is ensure that if the RNG state does end up in a
previously seen state, that the generator will not produce the same
sequence following that state as it did the last time it was in this
state. (Because i will be different to last time).
Consider the simpler x_0 = some secret seed value; x_{i+1} = F(X_i).
With this generator if x_i ever gets to be the same as x_j, you will
have a cycle. Shamir's proposal stops this, simply. I like it.
Adam
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:22