You are looking at a specific version 20130819:111146 of this paper. See the latest version.

Paper 2013/273

Computing the Rank of Incidence Matrix and the Algebraic Immunity of Boolean Functions

Deepak Kumar Dalai

Abstract

The incidence matrix between a set of monomials and a set of vectors in $\F_2$ has a great importance in the study of coding theory, cryptography, linear algebra, combinatorics. The rank of these matrices are very useful while computing algebraic immunity($\ai$) of Boolean functions in cryptography literature~\cite{MPC04,DGM04}. Moreover, these matrices are very sparse and well structured. Thus, for aesthetic reason finding the rank of these matrices is also very interesting in mathematics. In this paper, we have reviewed the existing algorithms with added techniques to speed up the algorithms and have proposed some new efficient algorithms for the computation of the rank of incidence matrix and solving the system of equations where the co-efficient matrix is an incidence matrix. Permuting the rows and columns of the incidence matrix with respect to an ordering, the incidence matrix can be converted to a lower block triangular matrix, which makes the computation in quadratic time complexity and linear space complexity. Same technique is used to check and computing low degree annihilators of an $n$-variable Boolean functions in faster time complexity than the usual algorithms. Moreover, same technique is also exploited on the Dalai-Maitra algorithm in~\cite{DM06} for faster computation. On the basis of experiments, we conjecture that the $\ai$ of $n$-variable inverse S-box is $\lfloor\sqrt{n}\rfloor + \lceil\frac{n}{\lfloor\sqrt{n}\rfloor}\rceil-2$. We have also shown the skepticism on the existing fastest algorithm in~\cite{ACGKMR06} to find $\ai$ and lowest degree annihilators of a Boolean function.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown status
Keywords
Boolean functionalgebraic immunityrank of matrixLU-decomposition
Contact author(s)
deepak @ niser ac in
History
2013-08-19: revised
2013-05-14: received
See all versions
Short URL
https://ia.cr/2013/273
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.