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(2n) 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 3n16 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 Theoremdecomposition of power functionsthreshold implementationsAPN
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.