Feedback linearly extended discrete functions
Preprint
Abstract
We study a new flexible method to extend linearly the graph of a non-linear, and usually not bijective, function so that the resulting extension is a bijection. Our motivation comes from cryptography. Examples from symmetric cryptography are given as how the extension was used implicitly in the construction of some well-known block ciphers. The method heavily relies on ideas brought from linear coding theory and secret sharing. We are interested in the behaviour of the composition of many extensions, and especially the space of parameters that defines a family of equations based on finite differences or linear forms. For any linear extension, we characterize entirely the space of parameters for which such equations are solvable in terms of the space of parameters that render those equations for the corresponding non-linear extended functions solvable. Conditions are derived to assess the solvability of those kind of equations in terms of the number of compositions or iterations. We prove a relation between the number of compositions and the dimensions of vector spaces that appear in our results. The proofs of those properties rely mostly on tools from linear algebra.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Differential cryptanalysis of DES-like cryptosystemsJournal of Cryptology, 1991
- A spectral characterization of correlation-immune combining functionsIEEE Transactions on Information Theory, 1988
- How to Construct Pseudorandom Permutations from Pseudorandom FunctionsSIAM Journal on Computing, 1988
- Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)IEEE Transactions on Information Theory, 1984
- On sharing secrets and Reed-Solomon codesCommunications of the ACM, 1981
- On a class of error correcting binary group codesInformation and Control, 1960