Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity

Recent research shows that the class of rotation symmetric Boolean functions is potentially rich in functions of cryptographic significance. In this paper, based on the knowledge of compositions of an integer, we present two new kinds of construction of rotation symmetric Boolean functions having optimal algebraic immunity on either odd variables or even variables. Our new functions are of much better nonlinearity than all the existing theoretical constructions of rotation symmetric Boolean functions with optimal algebraic immunity. Further, the algebraic degree of our rotation symmetric Boolean functions are also high enough.     

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.     

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.     

Multiplicative relations with conjugate algebraic numbers

We study what algebraic numbers can be represented by a product of algebraic numbers conjugate over a fixed number field K in fixed integer powers. The problem is nontrivial if the sum of these integer powers is equal to zero. The norm of such a number over K must be a root of unity. We show that there are infinitely many algebraic numbers whose norm over K is a root of unity and which cannot be represented by such a product. Conversely, every algebraic number can be expressed by every sufficiently long product in algebraic numbers conjugate over K. We also construct nonsymmetric algebraic numbers, i.e., algebraic numbers such that no elements of the corresponding Galois group acting on the full set of their conjugates form a Latin square. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 7, pp. 890–900, July, 2007.     

Exact solutions and mixing in an algebraic dynamical system

Let be an n×n matrix with entries a_ij in the field . We consider two involutive operations on these matrices: the matrix inverse I: ^–1 and the entry-wise or Hadamard inverse J: a_ij a _ij ^–1 . We study the algebraic dynamical system generated by iterations of the product J. I. We construct the complete solution of this system for n 4. For n = 4, it is obtained using an ansatz in theta functions. For n 5, the same ansatz gives partial solutions. They are described by integer linear transformations of the product of two identical complex tori. As a result, we obtain a dynamical system with mixing described by explicit formulas.Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 143, No. 1, pp. 131–149, April, 2005.     

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.      

Exact and traveling-wave solutions for convection-diffusion-reaction equation with power-law nonlinearity

Based on the simplest equation method, we propose exact and traveling-wave solutions for a nonlinear convection-diffusion-reaction equation with power law nonlinearity. Such equation can be considered as a generalization of the Fisher equation and other well-known convection-diffusion-reaction equations. Two important cases are considered. The case of density-independent diffusion and the case of density-dependent diffusion. When the parameters of the equation are constant, the Bernoulli equation is used as the simplest equation. This leads to new traveling-wave solutions. Moreover, some wavefront solutions can be derived from the traveling-wave ones. The case of time-dependent velocity in the convection term is studied also. We derive exact solutions of the equations by using the Riccati equation as simplest equation. The exact and traveling-wave solutions presented in this paper can be used to explain many biological and physical phenomena.     

Linear algebraic groups and countable Borel equivalence relations

If is an equivalence relation on a standard Borel space , then we say that is Borel reducible to if there is a Borel function such that . An equivalence relation on a standard Borel space is Borel if its graph is a Borel subset of . It is countable if each of its equivalence classes is countable. We investigate the complexity of Borel reducibility of countable Borel equivalence relations on standard Borel spaces. We show that it is at least as complex as the relation of inclusion on the collection of Borel subsets of the real line. We also show that Borel reducibility is -complete. The proofs make use of the ergodic theory of linear algebraic groups, and more particularly the superrigidity theory of R. Zimmer.

     

Additive and multiplicative relations connecting conjugate algebraic numbers

We investigate the problem of finding for which sets of integers a₁,…, a_k either of the equations Σ_{i = 1}^k a_iα_i = 0 or Π_{i = 1}^k α_i^a_i = 1 has a non-trivial solution in (not necessarily distinct) conjugate algebraic numbers α₁,…, α_k. The problem turns out to be connected with the existence of certain latin squares having zero determinant.     

Homological equivalence relations on an algebraic curve

We study the collection of homological equivalence relations on a fixed curve. We construct a moduli space for pairs consisting of a curve of genus g and a homological equivalence relation of degree n on the curve, and a classifying set for homological equivalence relations of degree n on a fixed curve, modulo automorphisms of the curve. We identify a special type of homological equivalence relations, and we characterize the special homological equivalence relations in terms of the existence of elliptic curves in the Jacobian of the curve.     

Unbounded self-adjoint operators connected by algebraic relations

Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 41, No. 12, pp.1664–1668, December, 1989.     

Linear relations among algebraic solutions of differential equations

For any univariate polynomial with coefficients in a differential field of characteristic zero and any integer, q, there exists an associated nonzero linear ordinary differential equation (LODE) with the following two properties. Each term of the LODE lies in the differential field generated by the rational numbers and the coefficients of the polynomial, and the qth power of each root of the polynomial is a solution of this LODE. This LODE is called a qth power resolvent of the polynomial. We will show how one can get a resolvent for the logarithmic derivative of the roots of a polynomial from the αth power resolvent of the polynomial, where α is an indeterminate that takes the place of q. We will demonstrate some simple relations among the algebraic and differential equations for the roots and their logarithmic derivatives. We will also prove several theorems regarding linear relations of roots of a polynomial over constants or the coefficient field of the polynomial depending upon the (nondifferential) Galois group. Finally, we will use a differential resolvent to solve the Riccati equation.     

Exact solutions of an integro-differential equation with quadratically cubic nonlinearity

Exact solutions of a nonlinear integro-differential equation with quadratically cubic nonlinear term are found. The equation governs, in particular, stationary shock wave propagation in relaxing media. For the exponential kernel the shapes of both compression and rarefaction shocks having a finite width of the front are calculated. For media with limited “memorizing time” the difference relation permitting the construction of wave profile by the mapping method is derived. The initial equation is rather general. It governs the evolution of nonlinear waves in real distributed systems, for example, in biological tissues, structurally inhomogeneous media and in some meta-materials.     

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.     

On the affine equivalence relation between two classes of Boolean functions with optimal algebraic immunity

Recently, two classes of Boolean functions with optimal algebraic immunity have been proposed by Carlet et al. and Wang et al., respectively. Although it appears that their methods are very different, it is proved in this paper that the two classes of Boolean functions are in fact affine equivalent. Moreover, the number of affine equivalence classes of these functions is also studied.     

Exact completion of path categories and algebraic set theory: Part I: Exact completion of path categories

We introduce the notion of a “category with path objects”, as a slight strengthening of Kenneth Brown's classical notion of a “category of fibrant objects”. We develop the basic properties of such a category and its associated homotopy category. Subsequently, we show how the exact completion of this homotopy category can be obtained as the homotopy category associated to a larger category with path objects, obtained by freely adjoining certain homotopy quotients. In a second part of this paper, we will present an application to models of constructive set theory. Although our work is partly motivated by recent developments in homotopy type theory, this paper is written purely in the language of homotopy theory and category theory, and we do not presuppose any familiarity with type theory on the side of the reader.