Abstract Recently, many cryptographic primitives such as homomorphic encryption (HE), multi-party computation (MPC) and zero-knowledge (ZK) protocols have been proposed in the literature which operate on the prime field $${\mathbb {F}}_p$$ F p for some large prime p. Primitives that are designed using such operations are called arithmetization-oriented primitives. As the concept of arithmetization-oriented primitives is new, a rigorous cryptanalysis of such primitives is yet to be done. In this paper, we investigate arithmetization-oriented APN functions. More precisely, we investigate APN permutations in the CCZ-classes of known families of APN power functions over the prime field $${\mathbb {F}}_p$$ F p . Moreover, we present a class of binomial permutation having differential uniformity at most 5 defined via the quadratic character over finite fields of odd characteristic. Computationally it is confirmed that the latter family contains new APN permutations for some small parameters. We conjecture it to contain an infinite subfamily of APN permutations.

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 $$\mathbb {F}_{2^n}$$ F 2 n . We prove the existence of a decomposition of the inverse using quadratic and linear power permutations for all permutations when $$2^n-1$$ 2 n - 1 is a prime, and we prove the non-existence of such decompositions for power permutations of differential uniformity strictly lower than 16 when 4|n. We also prove that any permutation admits a decomposition into quadratic power permutations and affine permutations of the form $$ax+b$$ a x + b if $$4 \not \mid n$$ 4 ∤ n . 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 $$x^7$$ x 7 and affine permutations.

Functions with good cryptographic properties which are used as S-boxes in the design of block ciphers have a fundamental importance to the security of these ciphers since they determine the resistance to various kinds of cryptanalytic attacks. Almost Perfect Nonlinear (APN) functions provide the best possible resistance to differential cryptanalysis, which is one of the most efficient cryptographic attacks against block ciphers known to date. Furthermore, APN permutations are of particular interest in practice since many cipher designs require the S-box to be a permutation. In this paper, we present a low-complexity hardware architecture for the TU-decomposition of APN permutations, showing how Dillon’s APN permutation can be decomposed in this way as a practically relevant example. The TU-decomposition of an m-bit permutation is based on the use of two$m/2$-bit keyed permutations (T and U) to reduce the complexity of the original permutation. Dillon’s permutation on 6 bits is the only known APN permutation on an even number of bits, so its study is of fundamental interest. We present hardware theoretical complexities and experimental results obtained from FPGA and ASIC implementations for the proposed TU-decomposition hardware architecture. These complexities and results are compared with other hardware architectures given in the literature for the same function. From the comparisons, it can be observed that the TU-decomposition architecture presented here greatly outperforms other hardware approaches with respect to area, delay and area$\times $delay complexities.

Threshold implementation is a method based on secret sharing to secure cryptographic ciphers (and in particular S-boxes) against differential power analysis side-channel attacks which was proposed by Nikova, Rechberger, and Rijmen in 2006. Until now, threshold implementations were only constructed for specific types of functions and some small S-boxes, but no generic construction was ever presented. In this paper, we present the first universal threshold implementation with$t+2$shares that is applicable to any bijective S-box, where$t$is its algebraic degree (or is larger than the algebraic degree). While being universal, our construction is also optimal with respect to the number of shares, since the theoretically smallest possible number,$t+1$, is not attainable for some bijective S-boxes. Our results enable low latency secure hardware implementations without the need for additional randomness. In particular, we apply this result to find two uniform sharings of the AES S-box. The first sharing is obtained by using the threshold implementation of the inversion in$\mathbb {F}_{2^{8}}$and the second by using two threshold implementations of two cubic power permutations that decompose the inversion. Area and performance figures for hardware implementations are provided.

The six infinite families of power APN functions are among the oldest known instances of APN functions, and it has been conjectured in 2000 that they exhaust all possible power APN functions. Another long-standing open problem is that of the Walsh spectrum of the Dobbertin power family, which is still unknown. Those of Kasami, Niho and Welch functions are known, but not the precise values of their Walsh transform, with rare exceptions. One promising approach that could lead to the resolution of these problems is to consider alternative representations of the functions in questions. We derive alternative representations for the infinite APN monomial families. We show how the Niho, Welch, and Dobbertin functions can be represented as the composition$x^{i} \circ x^{1/j}$of two power functions, and prove that our representations are optimal, i.e. no two power functions of lesser algebraic degree can be used to represent the functions in this way. We investigate compositions$x^{i} \circ L \circ x^{1/j}$for a linear polynomial$L$, show how the Kasami functions in odd dimension can be expressed in this way with$i=j$being a Gold exponent and compute all APN functions of this form for$n \le 9$and for$L$with binary coefficients, thereby showing that our theoretical constructions exhaust all possible cases. We present observations and data on power functions with exponent$\sum _{i = 1}^{k-1} 2^{2ni} - 1$which generalize the inverse and Dobbertin families. We present data on the Walsh spectrum of the Dobbertin function for$n \le 35$, and conjecture its exact form. As an application of our results, we determine the exact values of the Walsh transform of the Kasami function at all points of a special form. Computations performed for$n\leq 21$show that these points cover about 2/3 of the field.

Abstract In this work we give several generalizations of the isotopic shift construction, introduced recently by Budaghyan et al. (IEEE Trans Inform Theory 66:5299–5309, 2020), when the initial function is a Gold function. In particular, we derive a general construction of APN functions which covers several unclassified APN functions for $$n=8$$ n = 8 and produces fifteen new APN functions for $$n=9$$ n = 9 .

Almost perfect nonlinear (APN) functions over fields of characteristic 2 play an important role in cryptography, coding theory and, more generally, mathematics and information theory. In this paper we deduce a new method for constructing APN functions by studying the isotopic equivalence, concept defined for quadratic planar functions in fields of odd characteristic. In particular, we construct a family of quadratic APN functions which provides a new example of an APN mapping over${\mathbb F}_{2^{9}}$and includes an example of another APN function$x^{9}+ \mathop {\mathrm {Tr}}\nolimits (x^{3})$over${\mathbb F}_{2^{8}}$, known since 2006 and not classified up to now. We conjecture that the conditions for this family are satisfied by infinitely many APN functions.

We investigate the differential properties of a vectorial Boolean function G obtained by modifying an APN function F . This generalizes previous constructions where a function is modified at a few points. We characterize the APN-ness of G via the derivatives of F, and deduce an algorithm for searching for APN functions whose values differ from those of F only on a given set U ⊆ F2n. We introduce a value ΠFassociated with any F, which is invariant under CCZ-equivalence. We express a lower bound on the distance between a given APN function F and the closest APN function in terms of ΠF. We show how ΠFcan be computed efficiently for F quadratic. We compute ΠFfor all known APN functions over F2n. up to n ≤ 8. his is the first new CCZ-invariant for APN functions to be introduced within the last ten years. We derive a mathematical formula for this lower bound for the Gold function F (x) = x3, and observe that it tends to infinity with n. Finally, we describe how to efficiently find all sets U such that, taking G(x) = F (x) + v for x ∈ U and G(x) = F (x) for x ∉ U,G(x) is APN.

The binomial B(x) = x3+βx36(where β is primitive in F22) over F210 is the first known example of an Almost Perfect Nonlinear (APN) function that is not CCZ-equivalent to a power function, and has remained unclassified into any infinite family of APN functions since its discovery in 2006. We generalize this binomial to an infinite family of APN quadrinomials of the form x3+a(x2i+1)2k+bx3·2m+c(x2i+m+2m)2kfrom which B(x) can be obtained by setting a = β, b = c = 0, i = 3, k = 2. We show that for any dimension n = 2m with m odd and 3 + m,setting(a, b, c)=(β, β2, 1) and i =m -2 or i = (m - 2)-1mod n yields an APN function, and verify that for n = 10 the quadrinomials obtained in this way for i = m - 2 and i = (m - 2)-1mod n are CCZ-inequivalent to each other, to B(x), and to any other known APN function over F210.

CCZ-equivalence is the most general currently known equivalence relation for functions over finite fields preserving planarity and APN properties. However, for the particular case of quadratic planar functions isotopic equivalence is more general than CCZ-equivalence. A recent construction method for APN functions over fields of even characteristic, so-called isotopic shift construction, was instigated by the notion of isotopic equivalence. In this paper we discuss possible applications of the idea of isotopic shift for the case of planar functions. We show that, surprisingly, some of the known planar functions are actually isotopic shifts of each other. This confirms practically the pertinence of the notion of isotopic shift not only for APN functions but also for planar maps.

We study the problem of existence of APN functions of algebraic degree n over F2n. We characterize such functions by means of derivatives and power moments of the Walsh transform. We deduce several non-existence results which imply, in particular, that for most of the known APN functions F over F2n. the function x2n-1+ F(x) is not APN, and changing a value of F in a single point then results in non-APN functions. This leads us to conjectures that an APN function modified in one point cannot remain APN and that there exists no APN function of algebraic degree n.

We study the problem of existence of APN functions of algebraic degree n over F2n. We characterize such functions by means of derivatives and power moments of the Walsh transform. We deduce some non-existence results which mean, in particular, that for most of the known APN functions F over F2nthe function x2n-1+ F(x) is not APN, and changing a value of F in a single point results in non-APN functions.

In this paper, we discover that univariate form of a Niho bent function is a sum of functions having the form of a Leander-Kholosha bent function taken with particular coefficients from F*(2n) for every term. We know that the Niho bent functions are related to o-polynomials. The power terms in the univariate Niho bent function can be derived by working, in a first step, on each monomial of the corresponding o-polynomial separately, and in a second step, adding them to obtain the global expression. This allows, knowing the monomials in an o-polynomial, to obtain the power terms of the polynomial representing corresponding bent function. However, the coefficients are not calculated explicitly. The explicit form is given for the bent functions obtained from quadratic and cubic o-polynomials. We also calculate the algebraic degree of any bent function in the Leander-Kholosha class.

In this paper, we extend the class of Niho bent function consisting of 2rterms discovered by Leander and Kholosha. The extension is achieved by inserting coefficients of the power terms in the original function. Doing this, we obtain relation to all the existing quadratic o-monomials. We also calculate the algebraic degree of any function in the extended class.

In this paper, most of the known infinite classes of generalized bent functions are analyzed for their relation to the completed Maiorana-McFarland class. This is done using the criterion based on second-order derivatives of a function. In particular, it is shown that, unlike in the binary case, not all quadratic bent functions are EA-equivalent to a function of the Maiorana-McFarland type. This is the first attempt to rise this problem for the generalized bent functions.

This paper consists of two main contributions. First, the Niho bent function consisting of 2rexponents (discovered by Leander and Kholosha) is studied. The dual of the function is found and it is shown that this new bent function is not of the Niho type. Second, all known univariate representations of Niho bent functions are analyzed for their relation to the completed Maiorana-McFarland classM. In particular, it is proven that two families do not belong to the completed classM. The latter result gives a positive answer to an open problem whether the classHof bent functions introduced by Dillon in his thesis of 1974 differs from the completed classM.

In 1998, the second author, Charpin and Zinoviev characterized APN and AB (n, n)-functions by means of associated 2n-variable Boolean functions. In particular, they proved that a function F is AB if and only if the associated Boolean function γFis bent. This observation leads to potentially new bent functions associated to the known AB functions, or at least gives new insight on known bent functions. However, up to now, representations of γFare known only for Gold AB power functions and determining γFfor the rest of AB functions is an open problem. In the present paper we determine γFfor most of the known families of APN and AB functions.

We observe that the CCZ-equivalence of bent vectorial functions over $${{\bf F}_2^n}$$ (n even) reduces to their EA-equivalence. Then we show that in spite of this fact, CCZ-equivalence can be used for constructing bent functions which are new up to EA-equivalence and therefore to CCZ-equivalence: applying CCZ-equivalence to a non-bent vectorial function F which has some bent components, we get a function F′ which also has some bent components and whose bent components are CCZ-inequivalent to the components of the original function F. Using this approach we construct classes of nonquadratic bent Boolean and bent vectorial functions.

A method for constructing differentially 4-uniform quadratic hexanomials has been recently introduced by J. Dillon. We give various generalizations of this method and we deduce the constructions of new infinite classes of almost perfect nonlinear quadratic trinomials and hexanomials from F22mto F22m. We check for m = 3 that some of these functions are CCZ-inequivalent to power functions.

This paper introduces the first found infinite classes of almost perfect nonlinear (APN) polynomials which are not Carlet-Charpin-Zinoviev (CCZ)-equivalent to power functions (at least for some values of the number of variables). These are two classes of APN binomials from F2nto F2n(for n divisible by 3, resp., 4). We prove that these functions are extended affine (EA)-inequivalent to any power function and that they are CCZ-inequivalent to the Gold, Kasami, inverse, and Dobbertin functions when n ges 12. This means that for n even they are CCZ-inequivalent to any known APN function. In particular, for n = 12,20,24, they are therefore CCZ-inequivalent to any power function.

We exhibit an infinite class of almost perfect nonlinear quadratic polynomials from F2nto F2n(n ges 12, n divisible by 3 but not by 9). We prove that these functions are EA-inequivalent to any power function and that they are CCZ-inequivalent to any Gold function. In a forthcoming full paper, we shall also prove that at least some of these functions are CCZ-inequivalent to any Kasami function

New infinite classes of almost bent and almost perfect nonlinear polynomials are constructed. It is shown that they are affine inequivalent to any sum of a power function and an affine function