On the Structure of Format Preserving Sets in the Diffusion Layer of Block Ciphers

In 2016, Chang et al. proposed a Format Preserving Encryption (FPE) scheme over a finite field and used an MDS matrix in the diffusion layer of the scheme for optimal diffusion. Later that year, Gupta et al. defined an algebraic structure named Format Preserving Set (FPS) is the diffusion layer of an FPE scheme. In 2018, Barua et al. showed that it is not possible to construct an FPS over a finite field in the diffusion layer of an FPE scheme if the cardinality of the set is not a power of prime. They extended the search of FPS over a finite commutative ring <inline-formula> <tex-math notation="LaTeX">$\mathcal {R}$ </tex-math></inline-formula> and showed that if an FPS <inline-formula> <tex-math notation="LaTeX">$S \subseteq \mathcal {R}$ </tex-math></inline-formula> is closed under addition then it gets module structure over some subring of <inline-formula> <tex-math notation="LaTeX">$\mathcal {R}$ </tex-math></inline-formula>. Moreover, in this case, the only possible cardinalities of FPS are some power of the cardinalities of subrings when the module is free. The purpose of this article is twofold. Firstly, we show that it is possible to construct format preserving sets over a finite commutative ring which are not closed under addition. Secondly, we search for format preserving sets and MDS matrices over torsion modules. We provide examples of format preserving sets of cardinalities 26 and 52 over torsion modules and rings. These cardinalities are interesting because they correspond to the set of English alphabets, without and with capitalization. By considering a finite Abelian group as a torsion module over a PID, we show that a matrix <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math></inline-formula> with entries from the PID is MDS if and only if <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math></inline-formula> is MDS under the projection map on the same Abelian group.