Notion of Algebraic Immunity and Its evaluation Related to Fast Algebraic Attacks

Deepak Kumar Dalai; Kishan Chand Gupta; Subhamoy Maitra

Paper 2006/018

Notion of Algebraic Immunity and Its evaluation Related to Fast Algebraic Attacks

Deepak Kumar Dalai, Kishan Chand Gupta, and Subhamoy Maitra

Abstract

It has been noted recently that algebraic (annihilator) immunity alone does not provide sufficient resistance against algebraic attacks. In this regard, given a Boolean function $f$, just checking the minimum degree annihilators of $f, 1+f$ is not enough and one should check the relationsips of the form $fg = h$, and a function $f$, even if it has very good algebraic immunity, is not necessarily good against fast algebraic attack, if degree of $g$ becomes very low when degree of $h$ is equal to or little greater than the algebraic immunity of $f$. In this paper we theoretically study the two currently known constructions having maximum possible algebraic immunity from this viewpoint. To the end, we also experimentally study some cryptographically significant functions having good algebraic immunity.

Note: A few data in Table 1 are corrected. In Section 3, there are some minor editorial modifications.

Metadata

Available format(s): PDF PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Contact author(s): subho @ isical ac in
History: 2006-02-08: last of 3 revisions; 2006-01-17: received; See all versions
Short URL: https://ia.cr/2006/018
License: CC BY

BibTeX

@misc{cryptoeprint:2006/018,
      author = {Deepak Kumar Dalai and Kishan Chand Gupta and Subhamoy Maitra},
      title = {Notion of Algebraic Immunity and Its evaluation Related to Fast Algebraic Attacks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/018},
      year = {2006},
      url = {https://eprint.iacr.org/2006/018}
}