International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Using Wiedemann's algorithm to compute the immunity against algebraic and fast algebraic attacks

Authors:
Frederic Didier
Download:
URL: http://eprint.iacr.org/2006/261
Search ePrint
Search Google
Abstract: We show in this paper how to apply well known methods from sparse linear algebra to the problem of computing the immunity of a Boolean function against algebraic or fast algebraic attacks. For an $n$-variable Boolean function, this approach gives an algorithm that works for both attacks in $O(n2^{n} D)$ complexity and $O(n2^n)$ memory. Here $D = \binom{n}{d}$ and $d$ corresponds to the degree of the algebraic system to be solved in the last step of the attacks. For algebraic attacks, our algorithm needs significantly less memory than the algorithm in \cite{ACGKMR06} with roughly the same time complexity (and it is precisely the memory usage which is the real bottleneck of the last algorithm). For fast algebraic attacks, it does not only improve the memory complexity, it is also the algorithm with the best time complexity known so far for most values of the degree constraints.
BibTeX
@misc{eprint-2006-21753,
  title={Using Wiedemann's algorithm to compute the immunity against algebraic and fast algebraic attacks},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / algebraic and fast algebraic attacks, algebraic immunity, Wiedemann's algorithm},
  url={http://eprint.iacr.org/2006/261},
  note={ frederic.didier@inria.fr 13364 received 4 Aug 2006},
  author={Frederic Didier},
  year=2006
}