Basic theory in construction of Boolean functions with maximum possible annihilator immunity

被引:174
作者
Dalai, Deepak Kumar [1 ]
Maitra, Subhamoy [1 ]
Sarkar, Sumanta [1 ]
机构
[1] Indian Stat Inst, Appl Stat Unit, Kolkata 700108, W Bengal, India
关键词
algebraic attack; algebraic degree; algebraic immunity; annihilator; annihilator immunity; balancedness; Boolean functions; Krawtchouk polynomials; nonlinearity; symmetric Boolean functions;
D O I
10.1007/s10623-005-6300-x
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.
引用
收藏
页码:41 / 58
页数:18
相关论文
共 29 条
[1]  
[Anonymous], 1991, LECT NOTES COMPUTER
[2]  
Armknecht F, 2004, LECT NOTES COMPUT SC, V3017, P65
[3]  
Batten LM, 2004, LECT NOTES COMPUT SC, V3348, P84
[4]  
BOTEV A, 2004, P 15 INT WORKSH SYNT, P8
[5]  
BOTEV A, 2004, LOWER BOUNDS ALGEBRA
[6]  
BOTEV A, 2004, P 6 INT C DISCR MOD, P227
[7]  
BRAEKEN A, 2005, CRYPTOLOGY
[8]   Symmetric Boolean functions [J].
Canteaut, A ;
Videau, M .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (08) :2791-2811
[9]  
CANTEAUT A, 2005, WCC 2005, P1
[10]  
CARLET C, 2004, IMPROVING ALGEBRAIC