Paper 2012/498

On the immunity of Boolean functions against fast algebraic attacks using bivariate polynomial representation

Meicheng Liu and Yin Zhang and Dongdai Lin

Abstract

In the last decade, algebraic and fast algebraic attacks are regarded as the most successful attacks on LFSR-based stream ciphers. Since the notion of algebraic immunity was introduced, the properties and constructions of Boolean functions with maximum algebraic immunity have been researched in a large number of papers. However, it is unclear whether these functions behave well against fast algebraic attacks. In this paper, we study the immunity of Boolean functions against fast algebraic attacks using bivariate polynomial representation. Based on bivariate polynomial representation, we present a sufficient and necessary condition for a Boolean function to achieve good immunity against fast algebraic attacks, propose an efficient method for estimating the immunity of a large class of Boolean functions, including the functions of Q. Jin et al., and prove that the functions of D. Tang et al. achieve (almost) optimal immunity against fast algebraic attacks.