On second-order nonlinearity and maximum algebraic immunity of some bent functions in \mathcal{PS}^{+}

The rth-order nonlinearity and algebraic immunity of Boolean function play a central role against several known attacks on stream and block ciphers. Since its maximum equals the covering radius of the rth-order Reed-Muller code, it also plays an important role in coding theory. The computation of exact value or high lower bound on the rth-order nonlinearity of a Boolean function is very complected/challenging problem, especially when r>1. In this article, we identify a subclass of \({\mathcal{D}}_{0}\) type bent functions constructed by modifying well known Dillon functions having sharper bound on their second-order nonlinearity. We further, identify a subclass of bent functions in \({\mathcal {PS}}^{+}\) class with maximum possible algebraic immunity. The result is proved by using the well known conjecture proposed by Tu and Deng (Des. Codes Cryptogr. 60(1):1–14, 2011). To obtain rth-order nonlinearity (r>2), that is, whole nonlinearity profile of the constructed bent functions is still an open problem.     

Improving the high order nonlinearity lower bound for Boolean functions with given algebraic immunity

Algebraic immunity is a recently introduced cryptographic parameter for Boolean functions used in stream ciphers. If pAI(f) and pAI(f⊕1) are the minimum degree of all annihilators of f and f⊕1 respectively, the algebraic immunity AI(f) is defined as the minimum of the two values. Several relations between the new parameter and old ones, like the degree, the r-th order nonlinearity and the weight of the Boolean function, have been proposed over the last few years.In this paper, we improve the existing lower bounds of the r-th order nonlinearity of a Boolean function f with given algebraic immunity. More precisely, we introduce the notion of complementary algebraic immunity defined as the maximum of pAI(f) and pAI(f⊕1). The value of can be computed as part of the calculation of AI(f), with no extra computational cost. We show that by taking advantage of all the available information from the computation of AI(f), that is both AI(f) and , the bound is tighter than all known lower bounds, where only the algebraic immunity AI(f) is used.     

On extended algebraic immunity

Algebraic immunity (AI) measures the resistance of a Boolean function f against algebraic attack. Extended algebraic immunity (EAI) extends the concept of algebraic immunity, whose point is that a Boolean function f may be replaced by another Boolean function f ^c called the algebraic complement of f. In this paper, we study the relation between different properties (such as weight, nonlinearity, etc.) of Boolean function f and its algebraic complement f ^c . For example, the relation between annihilator sets of f and f ^c provides a faster way to find their annihilators than previous report. Next, we present a necessary condition for Boolean functions to be of the maximum possible extended algebraic immunity. We also analyze some Boolean functions with maximum possible algebraic immunity constructed by known existing construction methods for their extended algebraic immunity.     

Covering Sequences of Boolean Functions and Their Cryptographic Significance

We introduce the notion of covering sequence of a Boolean function, related to the derivatives of the function. We give complete characterizations of balancedness, correlation immunity and resiliency of Boolean functions by means of their covering sequences. By considering particular covering sequences, we define subclasses of (correlation-immune) resilient functions. We derive upper bounds on their algebraic degrees and on their nonlinearities. We give constructions of resilient functions belonging to these classes. We show that they achieve the best known trade-off between order of resiliency, nonlinearity and algebraic degree.     

Exact relations between nonlinearity and algebraic immunity

We sharpen some lower bounds on the higher order nonlinearity of a Boolean function in terms of the value of its algebraic immunity and obtain new tight bounds. We prove a universal tight lower bound, which enables us to reduce the problem of estimating higher order nonlinearity to finding the dimension of certain linear subspaces in the space of Boolean functions. As a simple corollary of this result, we obtain all previously known estimates in this area. For polynomials with disjoint terms, finding the dimension of those linear subspaces reduces to a simple combinatorial inspection. We prove a tight lower bound on the second order nonlinearity of a Boolean function in terms of the value of its algebraic immunity.     

On designated-weight Boolean functions with highest algebraic immunity

Algebraic immunity has been considered as one of cryptographically significant properties for Boolean functions. In this paper, we study ∑d-1 i=0 (ni)-weight Boolean functions with algebraic immunity achiev-ing the minimum of d and n - d + 1, which is highest for the functions. We present a simpler sufficient and necessary condition for these functions to achieve highest algebraic immunity. In addition, we prove that their algebraic degrees are not less than the maximum of d and n - d + 1, and for d = n1 +2 their nonlinearities equalthe minimum of ∑d-1 i=0 (ni) and ∑ d-1 i=0 (ni). Lastly, we identify two classes of such functions, one having algebraic degree of n or n-1.     

Upsets in round robin tournaments

LetT(R) be the class of tournaments having monotone score vectorR = (r₁,…, r_n). For a givenn, upper and lower bounds are given for the minimum number and maximum number of upsets for tournaments inT(R) withR strong. The cases of equality are characterized.     

Blow-up phenomena for a system of semilinear heat equations with nonlinear boundary flux

This paper deals with the blow-up for a system of semilinear r-Laplace heat equations with nonlinear boundary flux. It is shown that, under certain conditions on the nonlinearities and data, blow-up will occur at some finite time, and when blow-up does occur upper and lower bounds for the blow-up time are obtained.     

Complexity of Nonlinear Two-Point Boundary-Value Problems

We study upper and lower bounds on the worst-case ε-complexity of nonlinear two-point boundary-value problems. We deal with general systems of equations with general nonlinear boundary conditions, as well as with second-order scalar problems. Two types of information are considered: standard information defined by the values or partial derivatives of the right-hand-side function, and linear information defined by arbitrary linear functionals. The complexity depends significantly on the problem being solved and on the type of information allowed. We define algorithms based on standard or linear information, using perturbed Newton's iteration, which provide upper bounds on the ε-complexity. The upper and lower bounds obtained differ by a factor of log log 1/ε. Neglecting this factor, for general problems the ε-complexity for the right-hand-side functions having r(r⩾2) continuous bounded partial derivatives turns out to be of order (1/ε)^1/r for standard information, and (1/ε)^1/(r+1) for linear information. For second-order scalar problems, linear information is even more powerful. The ε-complexity in this case is shown to be of order (1/ε)^1/(r+2), while for standard information it remains at the same level as in the general case.     

On the 16th Hilbert problem for limit cycles on nonsingular algebraic curves

We give an upper bound for the maximum number N of algebraic limit cycles that a planar polynomial vector field of degree n can exhibit if the vector field has exactly k nonsingular irreducible invariant algebraic curves. Additionally we provide sufficient conditions in order that all the algebraic limit cycles are hyperbolic. We also provide lower bounds for N.     

On exceptional values of entire and meromorphic functions

Letf(z) be meromorphic function of finite nonzero orderρ. Assuming certain growth estimates onf by comparing it withr ^ρ L(r) whereL(r) is a slowly changing function we have obtained the bounds for the zeros off(z) ?g (z) whereg (z) is a meromorphic function satisfyingT (r, g)=o {T(r, f)} asr → ∞. These bounds are satisfied but for some exceptional functions. Examples are given to show that such exceptional functions exist.     

Maximal values of generalized algebraic immunity

The notion of algebraic immunity of Boolean functions has been generalized in several ways to vector-valued functions and/or over arbitrary finite fields and reasonable upper bounds for such generalized algebraic immunities has been proved in Armknecht and Krause (Proceedings of ICALP 2006, LNCS, vol. 4052, pp 180–191, 2006), Ars and Faugere (Algebraic immunity of functions over finite fields, INRIA, No report 5532, 2005) and Batten (Canteaut, Viswanathan (eds.) Progress in Cryptology—INDOCRYPT 2004, LNCS, vol. 3348, pp 84–91, 2004). In this paper we show that the upper bounds can be reached as the maximal values of algebraic immunities for most of generalizations by using properties of Reed–Muller codes.      

Agard’s η-distortion function and Schottky’s theorem

The monotoneity properties of certain functions defined in terms of the η-distortion function ηκ(t) in quasiconformal theory are studied and asymptotically sharp bounds are obtained for ηκ(t), thus proving some properties of the upper bound functionK(t, r) in Schottky’s theorem on analytic functions and improving the known explicit bounds forK (t, r).     

The simultaneous diophantine approximation of values of functions satisfying certain n variable q-difference equations

In a previous paper lower bounds were obtained on the simultaneous diophantine approximation of values of certain functions which satisfy linear q-difference equations. In the present paper these results are generalized from n = 1 to n > 1 variables. In order to better see what some of these solutions “look like” the algebraic properties of certain classes of functions are investigated, particularly with regard to a type of multiplication which is analogous to the convolution product. At the end of the paper such algebraic results are also obtained for the case n = 1.     

Connection Between Polynomial Optimization and Maximum Cliques of Non-Uniform Hypergraphs

In Motzkin and Straus (Canad. J. Math 498 17, 533540 1965) provided a connection between the order of a maximum clique in a graph G and the Lagrangian function of G. In Rota Bulò and Pelillo (Optim. Lett. 500 3, 287295 2009) extended the Motzkin-Straus result to r-uniform hypergraphs by establishing a one-to-one correspondence between local (global) minimizers of a family of homogeneous polynomial functions of degree r and the maximal (maximum) cliques of an r-uniform hypergraph. In this paper, we study similar optimization problems and obtain the connection to maximum cliques for {s, r}-hypergraphs and {p, s, r}-hypergraphs, which can be applied to obtain upper bounds on the Turán densities of the complete {s, r}-hypergraphs and {p, s, r}-hypergraphs.     

Bounds for the error of linear systems of equations using the theory of moments

Consider the system, of linear equations Ax = b where A is an n × n real symmetric, positive definite matrix and b is a known vector. Suppose we are given an approximation to x, ξ, and we wish to determine upper and lower bounds for ∥ x − ξ ∥ where ∥ ··· ∥ indicates the euclidean norm. Given the sequence of vectors {r_i}_{i^k = 0}, where r_i = Ar_{i − 1} and r₀ = b − Aξ, it is shown how to construct a sequence of upper and lower bounds for ∥ x − ξ ∥ using the theory of moments.     

Boolean functions with maximum algebraic immunity: further extensions of the Carlet–Feng construction

The algebraic immunity of Boolean functions is studied in this paper. More precisely, having the prominent Carlet–Feng construction as a starting point, we propose a new method to construct a large number of functions with maximum algebraic immunity. The new method is based on deriving new properties of minimal codewords of the punctured Reed–Muller code \(\mathrm{RM}^{\star }(\lfloor \frac{n-1}{2}\rfloor ,n)\) for any n, allowing—if n is odd—for efficiently generating large classes of new functions that cannot be obtained by other known constructions. It is shown that high nonlinearity, as well as good behavior against fast algebraic attacks, is also attainable.     

Norm bounds and underestimators for unconstrained polynomial integer minimization

We consider the problem of minimizing a polynomial function over the integer lattice. Though impossible in general, we use a known sufficient condition for the existence of continuous minimizers to guarantee the existence of integer minimizers as well. In case this condition holds, we use sos programming to compute the radius of a p-norm ball which contains all integer minimizers. We prove that this radius is smaller than the radius known from the literature. Our numerical results show that the number of potentially optimal solutions is reduced by several orders of magnitude. Furthermore, we derive a new class of underestimators of the polynomial function. Using a Stellensatz from real algebraic geometry and again sos programming, we optimize over this class to get a strong lower bound on the integer minimum. Also our lower bounds are evaluated experimentally. They show a good performance, in particular within a branch and bound framework.     

One-way multiparty communication lower bound for pointer jumping with applications

In this paper we study the one-way multiparty communication model, in which every party speaks exactly once in its turn. For every k, we prove a tight lower bound of Ω(n ^1/(k?1)}) on the probabilistic communication complexity of pointer jumping in a k-layered tree, where the pointers of the i-th layer reside on the forehead of the i-th party to speak. The lower bound remains nontrivial even for k = (logn)^1/2?? parties, for any constant ? > 0. Previous to our work a lower bound was known only for k =3 (Wigderson, see [7]), and in restricted models for k>3 [2},24,18,4,13]. Our results have the following consequences to other models and problems, extending previous work in several directions. The one-way model is strong enough to capture general (not one-way) multiparty protocols with a bounded number of rounds. Thus we generalize two problem areas previously studied in the 2-party model (cf. [30,21,29]). The first is a rounds hierarchy: we give an exponential separation between the power of r and 2r rounds in general probabilistic k-party protocols, for any k and r. The second is the relative power of determinism and nondeterminism: we prove an exponential separation between nondeterministic and deterministic communication complexity for general k-party protocols with r rounds, for any k,r. The pointer jumping function is weak enough to be a special case of the well-studied disjointness function. Thus we obtain a lower bound of Ω(n ^1/(k?1)) on the probabilistic complexity of k-set disjointness in the one-way model, which was known only for k = 3 parties. Our result also extends a similar lower bound for the weaker simultaneous model, in which parties simultaneously send one message to a referee [12]. Finally, we infer an exponential separation between the power of any two different orders in which parties send messages in the one-way model, for every k. Previous results [29, 7] separated orders based on who speaks first. Our lower bound technique, which handles functions of high discrepancy over cylinder intersections, provides a “party-elimination” induction, based on a restricted form of a direct-product result, specific to the pointer jumping function.     

A new exact exponential penalty function method and nonconvex mathematical programming

A new exact penalty function method, called the l₁ exact exponential penalty function method, is introduced. In this approach, the so-called the exponential penalized optimization problem with the l₁ exact exponential penalty function is associated with the original optimization problem with both inequality and equality constraints. The l₁ exact exponential penalty function method is used to solve nonconvex mathematical programming problems with r-invex functions (with respect to the same function η). The equivalence between sets of optimal solutions of the original mathematical programming problem and of its associated exponential penalized optimization problem is established under suitable r-invexity assumption. Also lower bounds on the penalty parameter are given, for which above these values, this result is true.