International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Balanced Boolean Functions with (more than) Maximum Algebraic Immunity

Authors:
Deepak Kumar Dalai
Subhamoy Maitra
Download:
URL: http://eprint.iacr.org/2006/434
Search ePrint
Search Google
Abstract: In this correspondence, construction of balanced Boolean functions with maximum possible algebraic (annihilator) immunity (AI) is studied with an additional property which is necessary to resist fast algebraic attack. The additional property considered here is, given an $n$-variable ($n$ even) balanced function $f$ with maximum possible AI $\frac{n}{2}$, and given two $n$-variable Boolean functions $g, h$ such that $fg = h$, if $\deg(h) = \frac{n}{2}$, then $\deg(g)$ must be greater than or equal to $\frac{n}{2}$. Our results can also be used to present theoretical construction of resilient Boolean functions having maximum possible AI.
BibTeX
@misc{eprint-2006-21925,
  title={Balanced Boolean Functions with (more than) Maximum Algebraic Immunity},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Algebraic Attacks, Annihilators, Boolean Functions, Fast Algebraic Attacks.},
  url={http://eprint.iacr.org/2006/434},
  note={ deepak_r@isical.ac.in 13472 received 20 Nov 2006},
  author={Deepak Kumar Dalai and Subhamoy Maitra},
  year=2006
}