On Diffusion Layers of SPN Based Format Preserving Encryption Schemes: Format Preserving Sets Revisited

In Inscrypt 2016, Chang et al. proposed a new family of substitution-permutation (SPN) based format preserving encryption algorithms in which a non-MDS (Maximum Distance Separable) matrix was used in its diffusion layer. In the same year in Indocrypt 2016 Gupta et al., in their attempt to provide a reason for choosing non-MDS over MDS matrices, introduced an algebraic structure called format preserving sets (FPS). They formalised the notion of this structure with respect to a matrix both of whose elements are coming from some finite field F-q. Many interesting properties of format preserving sets S subset of F-q with respect to a matrix M(F-q) were derived. Nevertheless, a complete characterisation of such sets could not be derived. In this paper, we fill that gap and give a complete characterisation of format preserving sets when the underlying algebraic structure is a finite field. Our results not only generalise and subsume those of Gupta et al., but also obtain some of these results over a more generic algebraic structure viz. ring R. We obtain a complete characterisation of format preserving sets over rings when the sets are closed under addition. Finally, we provide examples of format preserving sets of cardinalities 103 and 263 with respect to 4 x 4 MDS matrices over some rings which are not possible over any finite field.