Reversibility and Randomness |
Abstract
Contents
In terms of cellular automata, it is sufficient to show that its global function is bijective (one-to-one in both directions) to demonstrate reversibility. Conversely, demonstrating two different states that map to the same state in the next generation is enough to establish that an automaton is irreversible. Showing that there exists a "garden of eden" - i.e. a state with no possible precursor is also sufficient to establish irreversibility (Richardson, after Moore 1961). For a finite CA, identifying an initial which never recurs during the future evolution of the automata is also conclusively demonstrates irreversibility.
Firstly, irreversible random number generators fail to attain the maximum possible period for a given internal state. This is simple to prove - a generator with an internal state of size N bits has a potential period of 2^N. Any irreversible generator will have at least one initial state which never recurs in the future evolution of the automaton, so we can see that its period cannot reach 2^N. Perhaps more significantly, irreversible dynamic systems typically "leak" information. For every bit destroyed by a reversible generator, it's period is typically reduced by half. There have been a number of attempts to quantify the extent to which such systems are likely to lose the information present in their initial conditions. In general, an irreversible generator has an expected cycle length of about sqrt(S), where S is the maximum possible period for a generator with that quantity of "internal state". References for this include [V. F. Kolchin, 1986], [P. Flajolet and A. M. Odlyzko, 1989] and [S. A. Kauffman, 1990]. By contrast a reversible random number generator typically has an expected cycle of a reversible generator with S possible states has an expected cycle length of approximately S/2. This can be seen as follows: The probability of a cycle occurring does not depend on the length of the cycle - as the following table should indicate:
It therefore follows that the probability density function representing the probability of the occurrence of each cycle consists of a series of peaks at the integers from 1 - N inclusive, each with area 1 / S. Zero is not included since p(0) = 0. Given such a distribution, in theory, the expected value lies at the centre of gravity of the PDF, i.e. at: x = (S + 1) / 2. This value has received experimental confirmation. The mathematical notions about the expected period of reversible and irreversible generators presented here need to be taken with several pinches of salt. In reality, there's no reason why states should be connected together at random - and indeed, an intelligently designed generator should probably try to do better then this. It should be obvious that reversible generators can also consist entirely of cycles with very short periods, while irreversible generators can aspire to having a period of P - 1. A diagram of this should clarify things. The above equations can probably be considered as a description of how the period of an existing automata can be expected to scale as the size of its internal state changes. While reversibility is usually considered to be an all-or-nothing notion, it can also be usefully interpreted as a continuum, with irreversibility being a matter of degree. Finite irreversible automata cannot leak information forever; they must settle down into cycles where information is no longer being lost. When they do so, their operation may be considered to be - to all intents and purposes - reversible. Some automata settle down onto their attractors rapidly, while others meander around, slowly losing their precious entropy in the process before arriving at their limit-cycle.
Within the field of cellular automata itself, reversible random number generators appear less common. Possibly the first and best-known cellular automata used as a RNG, the "Wolfram-30" automata [Wolfram 1986] is not reversible. Neither of the Wolfram-90 nor the Wolfram-130 automata as used by Moshe Sipper, Marco Tomasso, Mose Zolla, and Mathieu Perrenoud [ Sipper/Tomasso/Zolla/Perrenoud] are reversible.
Rule 90 is described as being
Rule 150 can be written as:
In fact all the rules used by Sipper/Tomasso/Zolla/Perrenoud (i.e. rules, 90, 105, 150, 165) produce irreversible dynamics - and consequently the resulting automata are liable to destroy information. It is not possible - even by using different spatial combinations of these rules - to produce a reversible automata.
It was proved by Y. N. Patt [Patt, 1971] that /all/
"non-trivial" Wolfram automata are irreversible. Exhaustive search and the
1D decision procedure for reversibility were employed.
("Trivial" reversible Wolfram automata included 204, 170, 240, 51, 85, 15 -
Toffoli and Margulis were experts at the design of reversibile automata - but
their text suggests they didn't put a great deal of effort into the design of
their PRNGs. They refer to
Key: Nodes with more than one arrow going into them represent points where information is irretrievably lost.
These diagrams illustrate what you are likely to get if you connect states together randomly. Taking a seed at random, the reversible generator produces an expected period of roughly S/2, while the irreversible one has an expected period of roughly sqrt(S).
It is far from inevitable that reversible generators exhibit superior dynamics to irreversible ones:
The first has a cycle with a large period. However the chance of a randomly chosen resulting in landing on the cycle is less than 30% - and all other seeds wind up in a cycle with period three.
The second shows a generator where some seeds result in traversing every node.
In particular in cryptography - for example, if you are using a PRNG as a component of a stream-cypher - it is normally desirable to prevent one's opponent from predicting an earlier part of a PRNG-stream from the later part. One way of making creating difficulties is to ensure that information used in the earlier part of the message is not even present in the latter part - by having the information destroyed in the process of operating the PRNG. While this might sound attractive, it is important that information is being lost at the right rate. If information is destroyed at a rate of one bit per bit of cyphertext output, the system effectively reduces to a one-time pad - and you need to make sure that there are as many bits present in your seed as there are in your message. Of course if information is destroyed any faster than this then it is just going to waste. Destroying information more slowly than it is output is the potentially interesting case. If you destroy it too slowly, then any advantages of using the method can be lost. For example, the cryptanalyst may be able to work backwards through your message to the point where a bit of information is lost from the output of the RNG. Assuming the information was lost from the internal state relatively recently, he can then search backwards for it, trying all the various possibilities. After receiving confirmation from the plaintext about which of these is correct, he can then continue decoding. In irreversible systems, the rate of information loss typically decreases exponentially with time. It's consequently not terribly easy to transmit a message of any significant length without either wasting lots of bits or losing any security advantages. In conclusion, irreversibility may offer some cryptographical benefits, but there are also disadvantages: namely loss of randomness as more and more state-information is lost. Irreversibility makes it harder to predict things that have happened in the past (i.e. at an earlier point in the encryption process) but it simultaneously makes it easier to predict things that are likely to happen in the future. The utility of such an arrangement in cryptography is, at best, questionable. If exploiting the advantages without suffering from the disadvantages could be done the result would be a kind of cross between a PRNG-based stream cypher and a "one-time pad". As far as we know, the atempt has not been seriously made.
The answer seems to be in the affirmative. In an interesting paper entitled "Reversibility of 2D Cellular Automata is Undecidable" [Kari, 1990] Jarkko Kari proved a number of counter-intuitive notions about cellular automata of two dimensions and higher which use von Neumann-style neighbourhoods. In particular if follows from his proof that given a class of reversible automata using the VN neighbourhood, in general, no bound may be placed on the size of the neighbourhood required by the inverse of that automaton. Further, in general, there is no finite effective procedure for locating the inverse of such a reversible automaton, i.e. there is no algorithm for finding the inverse rule with a time complexity bounded by a computable function. This means that finding the inverse of such an automata can be made extremely difficult. If we had access to such an automata, it could be used as a component of the pseudo-random number generator. We could run it forwards in the knowledge that our opponent will have an extremely difficult time trying to find out how to run it backwards.
"One-way"automata may be applied in the field of public-key cryptography. It did not escape the notice of Jarkko Kari that the existence of the "one-way"automata he had described had potentially important implications for public-key cryptography. He wrote: "Reversible CA rules can be used to encrypt messages in a natural way: The plain text is expressed as a configuration of the CA, and the encryption is done by applying the CA rule rule for a fixed, finite number of times. The configuration obtained is the cryptotext. One may use periodic boundary conditions to make the configurations finite in size. The decryption is done simply by applying the inverse rule to the cryptotext for the same number of steps. The operations can be done very efficiently in parallel if proper hardware implementations are available.The demands made on the design of automata for use in public-key cryptography are more restrictive than those required for use in a "one way" random number generator. For the former, the inverse of the automata must be known, whereas in the latter case, a proof showing that the inverse of the transition function existed would suffice. There's a shortage of one-way functions suitable for use in public-key cryptography. In the same way that the use of elliptic curves offers a number of advantages over (say) RSA encryption, so cellular automata may offer fresh avenues.
The only worker in the area appears to be the Chinese cryptographer, [Tao Renji]. His work apparently involves finding two invertable automata, and generating a composite automata by combining them. Data is encrypted by passing the data through the composite automaton, and decrypted by passing the data through the inverses of each of the two automata that were combined. The result is a rapid system, but one that requires large keys to operate securely. This is described further in Bruce Schneier's book, Applied Cryptography. We have performed some similar work. See "Public key cryptography using cellular automata" and "Automata whose inverses have unboundedly large neighbourhoods" for more details.
Kari J.: "Reversibility of 2D Cellular Automata is Undecidable", 1990. Knuth, D. E.: "The Art of Computer Programming, Volume 2: Semi-numerical Algorithms", 1981. Kauffman, S. A.: "The Origins of Order, Self-Organisation and Selection in Evolution", 1993. Kolchin, V. F.: "Random Mappings", Optimization Software Inc., New York 1986. Margulis, N. H., and Toffoli, T.: "Cellular Automata Machines", 1987 MIT Press. Margulis, N. H., and Toffoli, T.: "Invertible Cellular Automata: A Review", 1990. Patt, Y. N.: "Injections of neighbourhood size three and four on the set of configurations from the infinite one-dimensional tesselation automata of two-state cells", unpublished, 1971. Sipper, M., Tomasso, M., Zolla M., and Perrenoud, M.: "Generating High-Quality Random Numbers In Parallel By Cellular Automata". Sipper, Moshe: "Evolution of Parallel Cellular Machines", Springer, 1997. Wolfram, S: "Random-Sequence Generation by Cellular Automata", Adv. Applied Math., 1986. |