On algebraic immunity and annihilators

Xian Mo Zhang*, Josef Pieprzyk, Yuliang Zheng

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

11 Citations (Scopus)

Abstract

Algebraic immunity AI(f) defined for a boolean function f measures the resistance of the function against algebraic attacks. Currently known algorithms for computing the optimal annihilator of f and AI(f) are inefficient. This work consists of two parts. In the first part, we extend the concept of algebraic immunity. In particular, we argue that a function f may be replaced by another boolean function fc called the algebraic complement of f. This motivates us to examine AI(fc). We define the extended algebraic immunity of f as AI*(f) = min[AI(f),AI(fc)}. We prove that 0 < AI(f) - AI*(f) < 1. Since AI(f) - AI*(f) = 1 holds for a large number of cases, the difference between AI(f) and AI* (f) cannot be ignored in algebraic attacks. In the second part, we link boolean functions to hypergraphs so that we can apply known results in hypergraph theory to boolean functions. This not only allows us to find annihilators in a fast and simple way but also provides a good estimation of the upper bound on AI*(f).

Original languageEnglish
Title of host publicationInformation Security and Cryptology - ICISC 2006: 9th International Conference, Proceedings
EditorsMin Surp Rhee, Byoungcheon Lee
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Pages65-80
Number of pages16
Volume4296 LNCS
ISBN (Print)3540491120, 9783540491125
Publication statusPublished - 2006
EventICISC 2006: 9th International Conference on Information Security and Cryptology - Busan, Korea, Republic of
Duration: 30 Nov 20061 Dec 2006

Other

OtherICISC 2006: 9th International Conference on Information Security and Cryptology
CountryKorea, Republic of
CityBusan
Period30/11/061/12/06

    Fingerprint

Cite this

Zhang, X. M., Pieprzyk, J., & Zheng, Y. (2006). On algebraic immunity and annihilators. In M. S. Rhee, & B. Lee (Eds.), Information Security and Cryptology - ICISC 2006: 9th International Conference, Proceedings (Vol. 4296 LNCS, pp. 65-80). Berlin; Heidelberg: Springer, Springer Nature.