The invertibility of the XOR of rotations of a binary word

Abstract

We prove the following result regarding operations on a binary word whose length is a power of two: computing the exclusive-or of a number of rotated versions of the word is an invertible (one-to-one) operation if and only if the number of versions combined is odd. (This result is not new; there is at least one earlier proof, due to Thomsen [Cryptographic hash functions, PhD thesis, Technical University of Denmark, 28 November 2008]. Our proof may be new.)

Keywords:

• invertibility
• exclusive-or
• rotation
• binary words
• circulant matrix

2010 AMS Subject Classification :

• 11C99

Acknowledgements

I would like to thank Lars Knudsen, Niels Ferguson, Louay M. J. Bazzi and Sanjoy K. Mitter for helpful comments and suggestions.