On the Multiplicative Complexity of Quasi-Quadratic Boolean Functions

摘要

The multiplicative complexity μ(f) of Boolean function f(x_1,..., x_n) is the smallest number of AND gates in the circuits of basis {&, ⊕, 1} such that each circuit executes function/. Boolean function f(x_1, ..., x_n) is quasi-quadratic if it can be presented as φ(x_1, ..., x_k) ⊕ q(x_1,..., x_n), where φ is an arbitrary function, q is a quadratic function (i.e., a function of degree), k ≤ n. This work is concerned with the multiplicative complexity of quasi-quadratic functions with k = 3 and arbitrary n. We prove that if f(x_1,..., x_n) is a quasi-quadratic Boolean function where k = 3, n ≥ k, then μ(f) ≤ 「(n + 1)/2」, where 「a」 denotes the smallest integer not less than α. In addition, we describe the family of quasi-quadratic Boolean functions f_n(x_1, ...,x_n),k = 3, n = 5, 6,..., for which we prove that μ(f_n) =「(n + 1 )/2」.