Preliminary noteThe system described here is broken. Don't pay it too much attention.
HistoryThe basic idea of using a cellular automata for public key cryptography was originally developed by the Chinese cryptographer, Tao Renji, in the 1980s.We have developed our own system on paper. Since there appears to be no convenient way to access Tao's work from here, the relationship between our system and his is not yet clear to us. Our system does appear to share many of the reported properties of Tao's work.
DescriptionThe basic idea involves generating two finite invertable non-uniform cellular automata. At least one of the automata should contain a significant number of non-linear components. The two automata are combined, to form a third automata which is then published as the public key.Combining the two automata is done by creating a third automata which is equivalent to applying them in sequence. This is done by algebraic combination, and expanding out the resulting terms. The domain of the resulting automata is likely to be larger than that of either of its components. To encrypt data, it is passed through the published automata and then subjected to diffusion. In order to decrypt, the diffusion is reversed then the inverses of the two private automata are applied consecutively. The diffusion used can be simple and unkeyed - it's not intended to be a source of strength in the basic scheme. Automata such as the ones on display (as Java applets) at Hexagonal Engineering's diffusion page appear suitable. The "one-way" element of the operation relies on the difficulty in finding the inverse of the public automata. It can be difficult to factor a composite automata into its component parts, in much the same way that it is difficult to factor the product of two large primes. In order to help ensure that finding the inverse of the public automata is difficult, at least one of the component automata is generated in a manner that guarantees that the inverse function has an unboundedly large domain. See our monograph on this subject for a construction method which produces this type of automata. The two automata should be applied in "opposite directions" along their "construction paths" in order to maximise the radius of the inverse of the public automata. Individual cells of at least one of the automata should contain key-dependent non-linear components.
More detailsWe have not yet implemented this system.It's virtue is likely to be that it will offer extremely rapid performance. Encryption is likely to be somewhat faster than decryption, due to the fact that at least one automata's inverses will consist of a large number of serial operations. It is likely to have large keysizes. It will be a challenge to see how much the description of the public automata can be effectively compressed without introducing weaknesses. No attempts have been made here yet to quantify how hard the problem of decomposing the public automata into its component parts presents.
FAPKC BibliographyThose references to the original work we know of are listed here.
|