Decomposition of Permutations in a Finite Field

Svetla Nikova; Ventzislav Nikov; Vincent Rijmen

Paper 2018/103

Decomposition of Permutations in a Finite Field

Svetla Nikova, Ventzislav Nikov, and Vincent Rijmen

Abstract

We describe a method to decompose any power permutation, as a sequence of power permutations of lower algebraic degree. As a result we obtain decompositions of the inversion in $GF (2^{n})$ for small $n$ from $3$ up to $16$ , as well as for the APN functions, when $n = 5$ . More precisely, we find decompositions into quadratic power permutations for any $n$ not multiple of $4$ and decompositions into cubic power permutations for $n$ multiple of $4$ . Finally, we use the Theorem of Carlitz to prove that for $3 \leq n \leq 16$ any $n$ -bit permutation can be decomposed in quadratic and cubic permutations.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Carlitz Theorem decomposition of power functions threshold implementations APN
Contact author(s): svetla nikova @ esat kuleuven be
History: 2020-11-02: last of 2 revisions; 2018-01-29: received; See all versions
Short URL: https://ia.cr/2018/103
License: CC BY

BibTeX

@misc{cryptoeprint:2018/103,
      author = {Svetla Nikova and Ventzislav Nikov and Vincent Rijmen},
      title = {Decomposition of Permutations in a Finite Field},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/103},
      year = {2018},
      url = {https://eprint.iacr.org/2018/103}
}