Constructing Rotation Symmetric Boolean Functions with Maximum Algebraic Immunity on an Odd Number of Variables

Jie PENG  Haibin KAN  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E95-A   No.6   pp.1056-1064
Publication Date: 2012/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E95.A.1056
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
algebraic attack,  algebraic immunity,  nonlinearity,  invertible cyclic matrix,  rotation symmetric Boolean function,  

Full Text: PDF(280.3KB)>>
Buy this Article

It is well known that Boolean functions used in stream and block ciphers should have high algebraic immunity to resist algebraic attacks. Up to now, there have been many constructions of Boolean functions achieving the maximum algebraic immunity. In this paper, we present several constructions of rotation symmetric Boolean functions with maximum algebraic immunity on an odd number of variables which are not symmetric, via a study of invertible cyclic matrices over the binary field. In particular, we generalize the existing results and introduce a new method to construct all the rotation symmetric Boolean functions that differ from the majority function on two orbits. Moreover, we prove that their nonlinearities are upper bounded by .