Some results concerning cryptographically significant mappings over GF(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

In this paper we investigate the existence of permutation polynomials of the form F(x) = x ^d  + L(x) over GF(2 ⁿ ), L being a linear polynomial. The results we derive have a certain impact on the long-term open problem on the nonexistence of APN permutations over GF(2 ⁿ ), when n is even. It is shown that certain choices of exponent d cannot yield APN permutations for even n. When n is odd, an infinite class of APN permutations may be derived from Gold mapping x ³ in a recursive manner, that is starting with a specific APN permutation on GF(2 ^k ), k odd, APN permutations are derived over GF(2 ^k+2i ) for any i ≥ 1. But it is demonstrated that these classes of functions are simply affine permutations of the inverse coset of the Gold mapping x ³. This essentially excludes the possibility of deriving new EA-inequivalent classes of APN functions by applying the method of Berveglieri et al. (approach proposed at Asiacrypt 2004, see [3]) to arbitrary APN functions.     

On the duals of certain d-dimensional dual hyperovals in

Let d2. A construction of d-dimensional dual hyperovals in PG(2d+1,2) using quadratic APN functions was discovered by Yoshiara in [S. Yoshiara, Dimensional dual hyperovals associated with quadratic APN functions, Innov. Incidence Geom., in press]. In this note, we prove that the duals of the d-dimensional dual hyperovals in PG(2d+1,2) constructed from quadratic APN functions are also d-dimensional dual hyperovals in PG(2d+1,2) if, and only if, d is even. Some examples are presented.     

Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions

We survey the properties of two parameters introduced by C. Ding and the author for quantifying the balancedness of vectorial functions and of their derivatives. We give new results on the distribution of the values of the first parameter when applied to F + L, where F is a fixed function and L ranges over the set of linear functions: we show an upper bound on the nonlinearity of F by means of these values, we determine then the mean of these values and we show that their maximum is a nonlinearity parameter as well, we prove that the variance of these values is directly related to the second parameter. We briefly recall the known constructions of bent vectorial functions and introduce two new classes obtained with Gregor Leander. We show that bent functions can be used to build APN functions by concatenating the outputs of a bent (n, n/2)-function and of some other (n, n/2)-function. We obtain this way a general infinite class of quadratic APN functions. We show that this class contains the APN trinomials and hexanomials introduced in 2008 by L. Budaghyan and the author, and a class of APN functions introduced, in 2008 also, by Bracken et al.; this gives an explanation of the APNness of these functions and allows generalizing them. We also obtain this way the recently found Edel?CPott cubic function. We exhibit a large number of other sub-classes of APN functions. We eventually design with this same method classes of quadratic and non-quadratic differentially 4-uniform functions.     

Notes on APN functions, semibiplanes and dimensional dual hyperovals

Two geometric objects, incidence graphs of semibiplanes and dimensional dual hyperovals, are respectively associated with APN and quadratic APN functions. From Proposition 2 (resp. Proposition 5), two APN (resp. quadratic APN) functions are CCZ (resp. extended affine) equivalent if and only if the associated graphs (resp. dimensional dual hyperovals) are isomorphic. The former graphs for almost bent functions are distance regular graphs by Proposition 4. The structures of automorphism groups of these geometric objects are investigated in Proposition 3 and Lemma 7. In particular, (Edel and Pott, Adv Math Commun 3:59–81 (2009), Question 2) is negatively answered.     

On the classification of APN functions up to dimension five

We classify the almost perfect nonlinear (APN) functions in dimensions 4 and 5 up to affine and CCZ equivalence using backtrack programming and give a partial model for the complexity of such a search. In particular, we demonstrate that up to dimension 5 any APN function is CCZ equivalent to a power function, while it is well known that in dimensions 4 and 5 there exist APN functions which are not extended affine (EA) equivalent to any power function. We further calculate the total number of APN functions up to dimension 5 and present a new CCZ equivalence class of APN functions in dimension 6.     

A New Characterization of Semi-bent and Bent Functions on Finite Fields*

We present a new characterization of semi-bent and bent quadratic functions on finite fields. First, we determine when a GF(2)-linear combination of Gold functions Tr(x²ⁱ+1) is semi-bent over GF(2ⁿ), n odd, by a polynomial GCD computation. By analyzing this GCD condition, we provide simpler characterizations of semi-bent functions. For example, we deduce that all linear combinations of Gold functions give rise to semi-bent functions over GF(2^p) when p belongs to a certain class of primes. Second, we generalize our results to fields GF(pⁿ) where p is an odd prime and n is odd. In that case, we can determine whether a GF(p)-linear combination of Gold functions Tr(x^pi+1) is (generalized) semi-bent or bent by a polynomial GCD computation. Similar to the binary case, simple characterizations of these p-ary semi-bent and bent functions are provided. Parts of this paper were presented at the 2002 IEEE International Symposium on Information Theory [10]     

On the symmetric properties of APN functions

We study the symmetric properties of APN functions as well as the structure and properties of the range of an arbitrary APN function. We prove that there is no permutation of variables that preserves the values of an APN function. Upper bounds for the number of symmetric coordinate Boolean functions in an APN function and its coordinate functions invariant under a cyclic shift are obtained. For n ≤ 6, some upper bounds for the maximal number of identical values of an APN function are given and a lower bound is found for different values of an arbitrary APN function of n variables.     

On quadratic APN functions and dimensional dual hyperovals

In this paper we characterize the d-dimensional dual hyperovals in PG(2d + 1, 2) that can be obtained by Yoshiara’s construction (Innov Incid Geom 8:147–169, 2008) from quadratic APN functions and state a one-to-one correspondence between the extended affine equivalence classes of quadratic APN functions and the isomorphism classes of these dual hyperovals.     

Minimal infeasible constraint sets in convex integer programs

In this paper we investigate certain aspects of infeasibility in convex integer programs, where the constraint functions are defined either as a composition of a convex increasing function with a convex integer valued function of n variables or the sum of similar functions. In particular we are concerned with the problem of an upper bound for the minimal cardinality of the irreducible infeasible subset of constraints defining the model. We prove that for the considered class of functions, every infeasible system of inequality constraints in the convex integer program contains an inconsistent subsystem of cardinality not greater than 2 ⁿ , this way generalizing the well known theorem of Scarf and Bell for linear systems. The latter result allows us to demonstrate that if the considered convex integer problem is bounded below, then there exists a subset of at most 2 ⁿ −1 constraints in the system, such that the minimum of the objective function subject to the inequalities in the reduced subsystem, equals to the minimum of the objective function over the entire system of constraints.     

A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities

In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions, we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent nonsmooth equation H(u,x)=0, where H:ℜ ²ⁿ →ℜ ²ⁿ , u∈ℜ ⁿ is a parameter variable and x∈ℜ ⁿ is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z ^k =(u ^k ,x ^k )} such that the mapping H(·) is continuously differentiable at each z ^k and may be non-differentiable at the limiting point of {z ^k }. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the proposed methods for particularly chosen smoothing functions are very promising. Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999     

More constructions of APN and differentially 4-uniform functions by concatenation

We study further the method of concatenating the outputs of two functions for designing an APN or a differentially 4-uniform (n, n)-function for every even n. We deduce several specific constructions of APN or differentially 4-uniform (n, n)-functions from APN and differentially 4-uniform (n/2, n/2)-functions. We also give a construction of quadratic APN functions which includes as particular cases a previous construction by the author and a more recent construction by Pott and Zhou.     

A matrix approach for constructing quadratic APN functions

A one to one correspondence is given between quadratic homogeneous APN functions and a special kind of matrices which we call as QAM’s. By modifying the elements of a known QAM, new quadratic APN functions can be constructed. Based on the nice mathematical structures of the QAM’s, an efficient algorithm for constructing quadratic APN functions is proposed. On \(\mathbb {F}_{2^7}\) , we have found 471 new CCZ-inequivalent quadratic APN functions, which is 20 times more than the number of the previously known ones. Before this paper, It is only found 23 classes of CCZ-inequivalent APN functions on \(\mathbb {F}_{2^8}\) . With the method of this paper, we have found 2,252 new CCZ-inequivalent quadratic APN functions, and this number is still increasing.     

Multipliers of periodic orbits of quadratic polynomials and the parameter plane

We prove a result about an extension of the multiplier of an attracting periodic orbit of a quadratic map as a function of the parameter. This has applications to the problem of geometry of the Mandelbrot and Julia sets. In particular, we prove that the size of p/q-limb of a hyperbolic component of the Mandelbrot set of period n is O(4 ⁿ /p), and give an explicit condition on internal arguments under which the Julia set of corresponding (unique) infinitely renormalizable quadratic polynomial is not locally connected. In memory of my grandmother Esfir Garbuz     

Bounds on the degree of APN polynomials: the case of x ?1?+?g(x)

In this paper we consider APN functions ${f:\mathcal{F}_{2^m}\to \mathcal{F}_{2^m}}$ of the form f(x) = x ^?1 + g(x) where g is any non ${\mathcal{F}_{2}}$ -affine polynomial. We prove a lower bound on the degree of the polynomial g. This bound in particular implies that such a function f is APN on at most a finite number of fields ${\mathcal{F}_{2^m}}$ . Furthermore we prove that when the degree of g is less than 7 such functions are APN only if m ?? 3 where these functions are equivalent to x ³.     

On a series of Hadamard matrices of order 2 t and the maximal excess of Hadamard matrices of order 22t

In this paper we give a new series of Hadamard matrices of order 2 ^t . When the order is 16, Hadamard matrices obtained here belong to class II, class V or to class IV of Hall's classification [3]. By combining our matrices with the matrices belonging to class I, class II or class III obtained before, we can say that we have direct construction, namely without resorting to block designs, for all classes of Hadamard matrices of order 16.Furthermore we show that the maximal excess of Hadamard matrices of order 2^2t is 2^3t , which was proved by J. Hammer, R. Levingston and J. Seberry [4]. We believe that our matrices are inequivalent to the matrices used by the above authors. More generally, if there is an Hadamard matrix of order 4n ² with the maximal excess 8n ³, then there exist more than one inequivalent Hadamard matrices of order 2^2t n ² with the maximal excess 2^3t n ³ for anyt 2.     

Indefinite higher Riesz transforms

Stein’s higher Riesz transforms are translation invariant operators on L ²(R ⁿ ) built from multipliers whose restrictions to the unit sphere are eigenfunctions of the Laplace–Beltrami operators. In this article, generalizing Stein’s higher Riesz transforms, we construct a family of translation invariant operators by using discrete series representations for hyperboloids associated to the indefinite quadratic form of signature (p,q). We prove that these operators extend to L ^r -bounded operators for 1<r<∞ if the parameter of the discrete series representations is generic.     

A note on a problem of Brocard-Ramanujan

The Brocard-Ramanujan problem pertains to the Diophantine equation n!+1=m ². Using the quadratic reciprocity law, we prove the existence of many infinite families of positive integers n such that n!+1 is not a perfect square, and we give several simple criteria for n!+1 to be a non-square.      

Universal octonary diagonal forms over some real quadratic fields

In this paper, we will prove there are infinitely many integers n such that n ²— 1 is square-free and admits universal octonary diagonal quadratic forms. Received: November 2, 1998.     

Admissible Orders of Jordan Loops

A commutative loop is Jordan if it satisfies the identity x²(yx) = (x²y)x. Using an amalgam construction and its generalizations, we prove that a nonassociative Jordan loop of order n exists if and only if n≧ 6 and n≠ 9. We also consider whether powers of elements in Jordan loops are well‐defined, and we construct an infinite family of finite simple nonassociative Jordan loops. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 103–118, 2009     

Converse Sturm–Hurwitz–Kellogg theorem and related results

We prove that if Vⁿ is a Chebyshev system on the circle and f is a continuous real-valued function with at least n + 1 sign changes then there exists an orientation preserving diffeomorphism of S¹ that takes f to a function L²-orthogonal to V. We also prove that if f is a function on the real projective line with at least four sign changes then there exists an orientation preserving diffeomorphism of that takes f to the Schwarzian derivative of a function on . We show that the space of piecewise constant functions on an interval with values ± 1 and at most n + 1 intervals of constant sign is homeomorphic to n-dimensional sphere. To V. I. Arnold for his 70th birthday