Thesis Abstract
Title of PhD Thesis: Novel Applications of Chaos Theory to Coding and Cryptography
Abstract:
From decimal expansion of real numbers to complex behaviour in biological systems, Chaos is ubiquitous. Non-linear dynamics or Chaos theory has shown much promise for Communications in recent years owing to desirable properties of non-linear dynamical systems such as Ergodicity, sensitive dependence on initial conditions and good pseudo-random properties in spite of low algorithmic complexity. The central theme of this thesis is a non-linear dynamical systems' approach to Communications (Coding and Cryptography). The thesis is divided into two parts.
Part I deals with applications of Chaos to Noiseless Coding (Entropy Coding) and Noisy Coding (Error Correction and Detection). Stochastic sources are embedded into 1-dimensional chaotic dynamical systems known as Generalized Luröth Series (GLS) which are generalized number systems. This embedding allows the application of symbolic dynamics to coding. A new proof of Kraft-McMillan inequality and its converse for prefix-free codes is provided using symbolic dynamics on GLS. Huffman coding, the famous lossless data compression algorithm is re-discovered as successive source approximation using GLS. GLS-coding, a new source coding algorithm which achieves Shannon's entropy rate for stochastic sources is proposed. GLS-coding turns out to be a generalization of Arithmetic Coding, the popular data compression algorithm used in JPEG2000, the international standard for still image compression, and in MPEG-4 Advanced Video Coding, the international standard for video compression.
Sensitive dependence on initial conditions, the hallmark of chaos, results in poor noise resistance of GLS-coding. By designing GLS-codes on a Cantor set, error detection while decoding is incorporated. Repetition codes, the most basic error detection/correction codes are also interpreted as codes on a Cantor set whose fractal dimension is equal to the rate of the code. Two new methods for multiplexing of discrete chaotic signals using GLS-coding in the presence of noise is presented, and is shown to overcome limitations of existing methods.
Part II of this thesis deals with applications of Chaos to Cryptography. It is proved that the length of the One-Time Pad, the only perfectly secure classical cryptographic system, need not be as long as the encrypted message, as it had generally been believed. One-Time Pad encryption is interpreted as randomized GLS-coding on the binary map and its dual, switched by the random pad. Classical Cryptography is thus bridged with Chaotic Cryptography through perfect secrecy systems interpreted as randomized GLS-coding.
Joint coding and encryption is beneficial in resource constrained applications requiring security while compression of bulky data is a necessity. A framework for joint coding and encryption is developed, by means of a generalization of GLS (Skew-nGLS) which is Lebesgue measure preserving and exhibits Robust Chaos. A recent discovery in Chaos theory – Robust Chaos – is characterized by absence of attracting periodic orbits in a neighbourhood of the parameter space. A generalization of the Logistic map that exhibits Robust Chaos is proposed for the first time and a pseudo-random number generator based on switching of Robust Chaos maps is shown to pass stringent statistical tests of randomness.