Revisiting linearly extended discrete functions - Gravel Claude; Panario Daniel (Journal of Mathematical Cryptology)
The authors introduced a new family of cryptographic schemes in a previous research article, which includes many practical encryption schemes, such as the Feistel family. Given a finite field of order qq, any n>m≥0n\gt m\ge 0, the authors described a new way to extend discrete functions with domain size qmq^{m} and range size qn−mq^{n-m} to a permutation over qnq^{n} elements using theory from linear error correcting codes. The authors previously showed that the knowledge about the differentials and correlations of the resulting permutation reduces solely to those of the extended discrete function. We show how the perfect secrecy of extended nonlinear functions transfers to the family of bijective linear extensions. We investigate how the concrete security of the family of nonlinear functions relates to the family of permutations obtained by such a type of linear extension. We also explore how the interplay between the entropy and the total variation distance (near-perfect secrecy with unbounded adversary) affects the mixing rate (number of iterations of the feedback linear extensions) with respect to the uniform distribution of the permutations over qnq^{n} elements. We give a new proof that a distribution close to the uniform distribution has a large entropy.