Unicyclic strong permutations

DOI10.1007/S12095-019-00384-4MaRDI QIDQ2179491zbMATH OpenOpenAlexWikidataFDO

Authors Claude Gravel, David Thomson, Daniel Panario

Publication date 12 May 2020

Published in Cryptography and Communications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.03551

zbMATH Keywords

algebraic degreeBoolean functionsdifferential uniformityfinite fieldspermutationsWalsh spectra

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Boolean functions (94D10)

Abstract: In this paper, we study some properties of a certain kind of permutation $sigma$ over $mathbb{F}_2^n$, where $n$ is a positive integer. The desired properties for $sigma$ are: (1) the algebraic degree of each component function is $n-1$; (2) the permutation is unicyclic; (3) the number of terms of the algebraic normal form of each component is at least $2^{n-1}$. We call permutations that satisfy these three properties simultaneously unicyclic strong permutations. We prove that our permutations $sigma$ always have high algebraic degree and that the average number of terms of each component function tends to $2^{n-1}$. We also give a condition on the cycle structure of $sigma$. We observe empirically that for $n$ even, our construction does not provide unicylic permutations. For $n$ odd, $nleq11$, we conduct an exhaustive search of all $sigma$ given our construction for specific examples of unicylic strong permutations. We also present some empirical results on the difference tables and linear approximation tables of $sigma$.

Recommendations

• On the constructions of n-cycle permutations
• More constructions of n-cycle permutations
• Permutations of finite fields with prescribed properties
• More low differential uniformity permutations over \(\mathbb{F}_{2^{2 k}}\) with \(k\) odd
• 4-uniform permutations with null nonlinearity

Cites work

• A spectral characterization of correlation-immune combining functions
• Analytic combinatorics
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
• Differential cryptanalysis of DES-like cryptosystems
• Generating random permutations by coin tossing: classical algorithms, new analysis, and modern implementation
• Generators and irreducible polynomials over finite fields
• Handbook of finite fields
• scientific article; zbMATH DE number 1682693 (Why is no real title available?)
• scientific article; zbMATH DE number 5862915 (Why is no real title available?)
• scientific article; zbMATH DE number 16479 (Why is no real title available?)
• scientific article; zbMATH DE number 1394292 (Why is no real title available?)
• Primitive Polynomials Over Finite Fields
• The generation of random permutations on the fly
• Vectorial Boolean functions for cryptography

Cited in

(3)

• Tangent-Chebyshev maps over finite fields: new properties and functional graphs
• scientific article; zbMATH DE number 697804 (Why is no real title available?)
• Feedback linearly extended discrete functions

This page was built for publication: Unicyclic strong permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2179491)