This is the second of a two part blog on commutative encryption.
Part one was Using Encryption to Block Spam.

In part one, I showed a commutative encryption scheme.  In that scheme, the encryption is not a substitution cypher, but a transposition cypher.   In cryptology it is a useful fiction to describe messages as if all messages begin as ordinary text, made up of alphanumeric chunks.  Historically, that was the case, but in this digital age a 'message' can be anything that might be sent as a file across a network.  That file could be anything from a simple text email to a video, a DVD image or a complete data backup.

In part one, a method was described for the transposition of components of a message in the dimensions formed by conversion of a 1-dimensional stream into a multi-dimensional array.  This is a commutative encryption method, meaning that the order in which the parties add or remove encryption does not matter.  The parties generate and retain random keys; no key exchange is needed.  The problems of key distribution and commutative encryption are solved, but the appearance of a problem remains.   I shall try to show that it is, in fact, a matter of appearance only.

Two conversers, Alice and Bob, exchange a message via alternate application and removal of encryption schemes.  Alice encrypts a message M as  M_A.  Bob overcrypts it as M_AB.  Alice decrypts her component and returns M_B.  Bob decrypts M_B to reveal M, the original message.  The encryption keys are destroyed.

The message M is passed between them as M_A M_AB M_B.  An eavesdropper, Carol, is assumed to gain access to these three messages.  It would appear that a simple comparison of the three variants of the message will reveal the code.  Two factors allow the code to remain secure despite this apparent weakness: the randomness of the key and the computing speed required by an eavesdropper.

 In order to exchange a first message, Alice and Bob must already have a common protocol.  If it is assumed that Carol has access to this protocol, it must be arranged that knowledge of the protocol gives an eavesdropper no significant advantage.  Let us suppose that a computer chip or program is used such that a computer will always boot, or default to an array of 10 x 10 x 10 x 10 bits.  The only decision available to Alice is whether to encrypt in the odd or the even dimensions of this array.

Suppose that Alice randomly chooses to encrypt odd.  She generates two random substitution keys and creates a message M_A odd.  If she receives a return message encrypted with B odd, she will detect the clash.  The error is detected by comparing the original message M_A with the message M_AB.   Alice returns an error message followed by a new M_A generated from new keys.  It is vital not to re-use any keys.

Carol intercepts  M_A and  uses two computers to try to crack the code from odd and even dimension pairs.  However, the two dimensions encrypted by Alice were encrypted by substitution of location according to a randomly generated key.  In each of two  'layers' there are 10 strips which may have been shuffled using a single use key.  There are 10! ways in which each layer was shuffled, giving 3025 different and equally likely arrangements for the strips in the original message.  These strips are a single bit, not byte, in width  so there is no clue to be had as to which decode might be more likely.  The only option for Carol is to intercept message M in the two forms M_A and M_B  whence, by a comparison attack, the original message M is obtained.  Meanwhile, Bob has decrypted M_B  and has sent a new message.

Suppose that a series of initial messages is exchanged by which a new protocol is agreed for each subsequent message.  These new protocols define which communicator is to encrypt odd, and which even.  More importantly, they specify new array dimensions and stream format.  Suppose an array is sent of 8 x 7 x 11 x 5 x 13.  Carol intercepts a stream of  40040 bits of data.  Carol has two options.  The one choice is a brute force attack to test all possible byte-wise arrangements which might generate the original array, then a test of all possible array formats, followed by a comparison of  M_A and M_B for each format.  The other choice is to crack the previous message to determine the agreed format.

Conclusion:

Alice and Bob must include a new protocol ( array format and stream format ) with every message sent, in order to maintain security.  Carol, the eavesdropper, in order to succeed, must break every successive code as fast as it is transmitted, otherwise the computational requirement for cracking any particular code in real time without its antecedent is excessive.  Without prior knowledge of the protocol it is computationally infeasible for an eavesdropper to recover the stream format and array format from at least two of three messages M_A M_AB M_B in order to break the cypher by a comparison of messages.

In practice, if such a method were used for human communications, whether by radio, text or email, 'Alice' and 'Bob' would be computer chips or software, and the human user would be entirely unaware of the encryption process.  Also, a first protocol need not be a default.  The first messages might be an exchange using a different, more computationally intensive method by which the first commutative encryption protocol is exchanged.

Footnote:
I may write further on the whole concept of the  'security' of nations, goods, the person and, perhaps,  the psyche if this article attracts sufficient interest.