Encryption via Reversible Cellular Automata

Reversibility is a condition for the second law of thermodynamics.  Cellular automata (CA) has features that parallel the second law of thermodynamics, such as reversibility.  Interestingly, most cellular CA are not reversible.  However, there are still configurations of CA that do obey the second law of thermodynamics and are reversible.  By definition, the second law of thermodynamics has the property of entropy, a measure of the disorder of a system.  In reversible systems, the entropy should increase.  Another way to look at this is, randomness of a system should increase as it evolves.

Entropy can be thought of as the ratio of heat to temperature, and entropy increases as the system absorbs heat and decreases as a system looses heat.  Heat is associated with the motion and vibration of atoms, an increase in entropy causes a random motion of the atoms.  In order for a system to be reversible, all information related to the evolution of the system will need to be retained.  Thermodynamically speaking, the information is the motion of atoms in the system, which is, the entropy of the system.  By using CA, a completely closed system can be simulated without loosing information.  The following illustrates how a CA is built from a rule-based binary structure, here rule 110 is established:


A CA is reversible if its global map is invertible.  If a CA is invertible, it is deterministic in both directions, which is a key concept for encryption.  The rule of CA that is associated with reversibility is called the inverse rule.  Over the past 20 years or so, Cryptographic techniques have become a central part of secure digital communication.  All crypto systems can be classified into two types; Private  and Public.  In symmetric key systems , both the sender and receiver use the same key to reveal the information.  The symmetric key system can be classified into two types; Block and Stream cyphers.  The Block cypher breaks the plain text into fixed length blocks and encryption is performed one black at a time.  The following diagram describes how CA is used to derive a Block cypher:


By applying a transition rule, for moving forward and backwards, and iterating for n time steps, the original configuration of the CA can be obtained.  The following diagram depicts these transitions:


Stream cyphers encrypt the plain text one-byte at a time.  Cellular automata has become an important tool in developing cryptographic systems, especially for high speed encryption, such as for mobile devices.  In the following presentation, layered reversible CA used and describes a methodology and algorithm for encryption and decryption that performs at the level of, or faster than, the Advanced Encryption Standard (AES):


One of the most important features of using reversible CA for encryption is the ability to compose highly company generators that are suitable for high speed applications.

Leave a Reply

Your email address will not be published. Required fields are marked *