On Decompositions of Permutations in Quadratic Functions

Samuele Andreoli; Enrico Piccione; Lilya Budaghyan; Pantelimon Stănică; Svetla Nikova

Paper 2023/1632

On Decompositions of Permutations in Quadratic Functions

Samuele Andreoli

, University of Bergen

Enrico Piccione

, University of Bergen

Lilya Budaghyan

, University of Bergen

Pantelimon Stănică

, Naval Postgraduate School

Svetla Nikova

, KU Leuven, University of Bergen

Abstract

The algebraic degree of a vectorial Boolean function is one of the main parameters driving the cost of its hardware implementation. Thus, finding decompositions of functions into sequences of functions of lower algebraic degrees has been explored to reduce the cost of implementations. In this paper, we consider such decompositions of permutations over . We prove the existence of decompositions using quadratic and linear power permutations for all permutations when is a prime, and we prove the non-existence of such decompositions for power permutations of differential uniformity strictly lower than when . We also prove that any permutation admits a decomposition into quadratic power permutations and affine permutations of the form if . Furthermore, we prove that any permutation admits a decomposition into cubic power permutations and affine permutations. Finally, we present a decomposition of the PRESENT S-Box using the power permutation and affine permutations.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: power function vectorial Boolean function decomposition permutation
Contact author(s): samuele andreoli @ uib no
enrico piccione @ uib no
lilya budaghyan @ uib no
pstanica @ nps edu
svetla nikova @ esat kuleuven be
History: 2023-10-23: approved; 2023-10-20: received; See all versions
Short URL: https://ia.cr/2023/1632
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1632,
      author = {Samuele Andreoli and Enrico Piccione and Lilya Budaghyan and Pantelimon Stănică and Svetla Nikova},
      title = {On Decompositions of Permutations in Quadratic Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1632},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1632}
}