Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Boolean functions, Algebraic immunity, Fast algebraic attacks

Date: received 29 Aug 2012

Contact author: meicheng liu at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20120903:125739 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]