TAILIEUCHUNG - Weight and nonlinearity of Boolean functions

In this paper we analyze the weight and the nonlinearity of various types of Boolean functions. We give some general results related to rotation symmetric Boolean functions, and in particular, we prove partially a conjecture stated by Cusick and Stanica in. | Turk J Math 36 (2012) , 520 – 529. ¨ ITAK ˙ c TUB doi: Weight and nonlinearity of Boolean functions Lavinia Corina Ciungu Abstract In this paper we analyze the weight and the nonlinearity of various types of Boolean functions. We give some general results related to rotation symmetric Boolean functions, and in particular, we prove partially a conjecture stated by Cusick and St˘ anic˘ a in [3]. Key Words: Hamming weight, nonlinearity, balanced functions, affine equivalence, rotation symmetric 1. Introduction Boolean functions have many applications in coding theory and cryptography. A detailed account of the latter applications can be found in the book [2]. If we define Vn to be the vector space of dimension n over the finite field GF (2) = {0, 1} , then an n variable Boolean function f(x1 , x2, ., xn) = f(x) is a map from Vn to GF (2). Every Boolean function f(x) has a unique polynomial representation (usually called the algebraic normal form [2, p. 6]), and the degree of f is the degree of this polynomial. A function of degree ≤ 1 is said to be affine, and if the constant term is 0 such a function is called linear. We let Bn denote the set of all Boolean functions in n variables, with addition and multiplication done modulo 2 . If we list the 2n elements of Vn as v0 = (0, ., 0), v1 = (0, ., 0, 1), . in lexicographic order, then the 2n -vector (f(v0 ), f(v1 ), ., f(v2n−1 )) is called the truth table of f . The weight (also called Hamming weight) wt(f) of f is defined to be the number of 1 s in the truth table for f . In many cryptographic uses of Boolean functions, it is important that the truth table of each function f has an equal number of 0 s and 1 s; in that case, we say that the function f is balanced. The distance d(f, g) between 2 Boolean functions f and g is defined by d(f, g) = wt(f + g), where the polynomial addition is done modulo 2 . An important concept in cryptography is the nonlinearity N (f) defined by N (f) = min wt(f

• Toán học
• Hamming weight
• Nonlinearity of Boolean functions
• Balanced functions
• Affine equivalence
• Rotation symmetric