Chaotic Measures and Dynamical Systems

  The assertion that hash functions and chaotic iterators share some of the same desired properties was put forth by Heileman et al., [1993], where it was suggested that a chaotic iterator which exhibits sensitive dependence on initial conditions might also perform well as a hash function. The authors introduced the notion that hash functions can be transformed into chaotic iterators in the real domain, allowing some measures from the field of nonlinear dynamics to be applied. This was done by converting the hash functions to iterators in the continuous domain, and then calculating the continuous Lyapunov exponent of the resulting iterator. The results showed that the corresponding double hashing iterator had a positive Lyapunov exponent in the real domain, indicating that this iterator has sensitive dependence on initial conditions. Similar tests for linear probing indicated that it had a zero Lyapunov exponent, or no sensitive dependence on initial conditions.

A general form for a dynamical system is given by the first order recurrence relation

 

where the constant c is the initial condition, and . The function f generally must be nonlinear to generate complex behavior. This simple system is called an iterator. It is well-known that for some choices of even simple f in equation (7), a system that exhibits extremely complex behavior can be obtained. One such form of behavior is referred to as chaos. While a universally accepted definition of chaos does not exists, it is generally agreed that one characteristic is sensitive dependence on initial conditions, coupled with bounded behavior [Peitgen et al.,1992].

• Lyapunov Exponent
• Integer Lyapunov Exponent
• Integer Lyapunov Evaluation
• Entropy