Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity |
| |
Authors: | Deepak Kumar Dalai Subhamoy Maitra Sumanta Sarkar |
| |
Institution: | (1) Applied Statistics Unit, Indian Statistical Institute, 203 B T Road, Kolkata, 700 108, India |
| |
Abstract: | So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present
a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum
possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated
under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the
input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several
other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator
immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with O(n2) time and O(n) space complexity.
We use the term “Annihilator Immunity” instead of “Algebraic Immunity” referred in the recent papers 3–5, 9, 18, 19]. Please
see Remark 1 for the details of this notational change |
| |
Keywords: | Algebraic attack Algebraic degree Algebraic immunity Annihilator Annihilator immunity Balancedness Boolean functions Krawtchouk polynomials Nonlinearity Symmetric Boolean functions |
本文献已被 SpringerLink 等数据库收录! |
|