Fast tensor transforms and ring-valued orthogonal matrices: an application to cryptography

Abstract

We present a generalization of the Fast Fourier and fast Walsh transform algorithms to tensor products of $n$ arbitrary $q\times q$ matrices over a commutative ring, reducing the cost of applying such a tensor product from $q^{2n}$ to $n{q}^n$ ring operations. We then give an explicit construction of square orthogonal matrices over a commutative unitary ring, starting from a prescribed first row, and specialize this construction to $\mathbb{Z}/256\mathbb{Z}$. Combining these two ingredients, we propose a symmetric cryptosystem in which the secret key determines~$n$ orthogonal matrices over $\mathbb{Z}/256\mathbb{Z}$ whose tensor product encrypts a block of $q^n$ bytes; encryption and decryption both exploit the fast tensor product algorithm. We give three examples of implementations.