On the Generalization of Butterfly Structure

Abstract

Butterfly structure was proposed in CRYPTO 2016 [PUB16], and it cangenerate permutations over F22n from power permutations over F2n for odd n. Afterthat, a generalized butterfly structure was proposed in IEEE IT [CDP17], which cangenerate permutations over F22n from any permutation over F2n . There is also anothergeneralization which was given in [FFW17]. Up to now, three constructions based onbutterfly structure and Gold type permutations are proposed. In the present paper,we give a construction which contains the three previous constructions as special casesand also generates new permutations with good cryptographic properties. Moreover,we give a characterization of the number of solutions of a special system of linearequations in a more general way, which is useful to investigate the cryptographicproperties of quadratic functions obtained with butterfly construction based on Goldexponents.