The monoidal nature of the Feistel-Toffoli construction

Abstract

The Feistel-Toffoli construction of a bijective Boolean function out of an arbitrary one, a fundamental tool in reversible computing and in  cryptography, has recently been analyzed (see [12]) to be a special instance of the construction of a monoid homomorphism from the  X-fold cartesian power of a monoid M into the endomorphism monoid of the free M-set over the set X. It is the purpose of this note to  show that this construction itself is in fact a genuine monoidal one. The generalization of the Feistel-Toffoli construction to internal  categories in arbitrary finitely complete categories of [12] then becomes a special instance of this monoidal description.