**Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity**

*Deepak Kumar Dalai and Subhamoy Maitra and Sumanta Sarkar*

**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(n^2)$ time and $O(n)$ space complexity.

**Category / Keywords: **secret-key cryptography / Algebraic Attack, Algebraic Degree, Algebraic Immunity,

**Date: **received 15 Jul 2005, last revised 15 Jul 2005

**Contact author: **subho at isical ac in

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20050720:062842 (All versions of this report)

**Short URL: **ia.cr/2005/229

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]