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
Niels Möller (nisse@lysator.liu.se)
21 Oct 1998 16:44:42 +0200
Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> 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}.
You're right, it doesn't exclude that. But what is important is that
it *does* excludes cycles. This is how:
Look at an infinite sequence of symbols or blocks, for instance
ABCQWERTYQWERTYQWERTY...
Now shift this sequence L (L = 6) positions, and compare with the original
sequence
ABCQWERTYQWERTYQWERTY...
ABCQWERTYQWERTYQWERTY...
You see that the two copies match exactly, except for a finite number
of symbols at the start. The interesting thing is that the sequence
has a cycle *if and only if* there is some L>0 so that you can shift
it L steps and have such a perfect match (except for a finite number
of symbols at the start).
The property that Shimir exploits implies that however you shift the
sequence (try L = i-j), whenever there is a match at one position,
there will never (or more precisely, as long as the counters don't
wrap around) be a match also at the next position. Therefore, the kind
of perfect match described above is impossible, and there can be no
cycles.
It should not be too difficult to write a formal proof that the
property ((x_i = x_j and i != j) => x{i+1} != x{j+1}) makes cycles
impossible, but I hope that the above sketch is clear enough.
/Niels
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:22