Paper 2015/436

On the Resistance of Prime-variable Rotation Symmetric Boolean Functions against Fast Algebraic Attacks

Yusong Du, Baodian Wei, Fangguo Zhang, and Huang Zhang

Abstract

Boolean functions used in stream ciphers should have many cryptographic properties in order to help resist different kinds of cryptanalytic attacks. The resistance of Boolean functions against fast algebraic attacks is an important cryptographic property. Deciding the resistance of an n-variable Boolean function against fast algebraic attacks needs to determine the rank of a square matrix over finite field GF(2). In this paper, for rotation symmetric Boolean functions in prime n variables, exploiting the properties of partitioned matrices and circulant matrices, we show that the rank of such a matrix can be obtained by determining the rank of a reduced square matrix with smaller size over GF(2), so that the computational complexity decreases by a factor of n to the power omega for large n, where omega is approximately equal to 2.38 and is known as the exponent of the problem of computing the rank of matrices.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Boolean functions
Contact author(s)
duyusong @ mail sysu edu cn
History
2015-05-07: received
Short URL
https://ia.cr/2015/436
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/436,
      author = {Yusong Du and Baodian Wei and Fangguo Zhang and Huang Zhang},
      title = {On the Resistance of Prime-variable Rotation Symmetric Boolean Functions against Fast Algebraic Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2015/436},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/436}},
      url = {https://eprint.iacr.org/2015/436}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.