Paper 2016/671

Efficient probabilistic algorithm for estimating the algebraic properties of Boolean functions for large $n$

Yongzhuang Wei, Enes Pasalic, Fengrong Zhang, and Samir Hod\v zić

Abstract

Although several methods for estimating the resistance of a random Boolean function against (fast) algebraic attacks were proposed, these methods are usually infeasible in practice for relative large input variables $n$ (for instance $n\geq 30)$ due to increased computational complexity. An efficient estimation the resistance of Boolean function (with relative large input variables $n$) against (fast) algebraic attacks appears to be a rather difficult task. In this paper, the concept of partial linear relations decomposition is introduced, which decomposes any given nonlinear Boolean function into many linear (affine) subfunctions by using the disjoint sets of input variables. Based on this result, a general probabilistic decomposition algorithm for nonlinear Boolean functions is presented which gives a new framework for estimating the resistance of Boolean function against (fast) algebraic attacks. It is shown that our new probabilistic method gives very tight estimates (lower and upper bound) and it only requires about $O(n^22^n)$ operations for a random Boolean function with $n$ variables, thus having much less time complexity than previously known algorithms.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Stream ciphersfast algebraic attackstime complexityalgebraic immunity.
Contact author(s)
walker_wei @ msn com
zhfl203 @ cumt edu cn
History
2016-07-06: received
Short URL
https://ia.cr/2016/671
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/671,
      author = {Yongzhuang Wei and Enes Pasalic and Fengrong Zhang and Samir Hod\v zić},
      title = {Efficient probabilistic algorithm for estimating the algebraic properties  of Boolean functions for large $n$},
      howpublished = {Cryptology ePrint Archive, Paper 2016/671},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/671}},
      url = {https://eprint.iacr.org/2016/671}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.