Constructing Orthogonal Latin Squares from Linear Cellular Automata
This work addresses a cryptographic problem for designing secret sharing schemes, but it appears incremental as it builds on existing methods for cellular automata and combinatorial designs.
The authors tackled the problem of generating orthogonal Latin squares for cryptographic applications, specifically threshold secret sharing schemes, by proving that two linear cellular automata produce orthogonal Latin squares if and only if the polynomials of their local rules are relatively prime.
We undertake an investigation of combinatorial designs engendered by cellular automata (CA), focusing in particular on orthogonal Latin squares and orthogonal arrays. The motivation is of cryptographic nature. Indeed, we consider the problem of employing CA to define threshold secret sharing schemes via orthogonal Latin squares. We first show how to generate Latin squares through bipermutive CA. Then, using a characterization based on Sylvester matrices, we prove that two linear CA induce a pair of orthogonal Latin squares if and only if the polynomials associated to their local rules are relatively prime.