Paper 2006/032

Reducing the Number of Homogeneous Linear Equations in Finding Annihilators

Deepak Kumar Dalai and Subhamoy Maitra

Abstract

Given a Boolean function $f$ on $n$-variables, we find a reduced set of homogeneous linear equations by solving which one can decide whether there exist annihilators at degree $d$ or not. Using our method the size of the associated matrix becomes $\nu_f \times (\sum_{i=0}^{d} \binom{n}{i} - \mu_f)$, where, $\nu_f = |\{x | wt(x) > d, f(x) = 1\}|$ and $\mu_f = |\{x | wt(x) \leq d, f(x) = 1\}|$ and the time required to construct the matrix is same as the size of the matrix. This is a preprocessing step before the exact solution strategy (to decide on the existence of the annihilators) that requires to solve the set of homogeneous linear equations (basically to calculate the rank) and this can be improved when the number of variables and the number of equations are minimized. As the linear transformation on the input variables of the Boolean function keeps the degree of the annihilators invariant, our preprocessing step can be more efficiently applied if one can find an affine transformation over $f(x)$ to get $h(x) = f(Bx+b)$ such that $\mu_h = |\{x | h(x) = 1, wt(x) \leq d\}|$ is maximized (and in turn $\nu_h$ is minimized too). We present an efficient heuristic towards this. Our study also shows for what kind of Boolean functions the asymptotic reduction in the size of the matrix is possible and when the reduction is not asymptotic but constant.

Note: The initial title of the eprint submission was ``Towards an Efficient Algorithm to find Annihilators by Solving a Set of Homogeneous Linear Equations". This revision updates the title with a more appropriate one. This draft also incorporates editorial and technical revisions and more recent references. Further this an extended version of the draft recently accepted in SETA 2006.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. The paper has been accepted in SETA 2006
Contact author(s)
subho @ isical ac in
History
2006-07-03: last of 6 revisions
2006-01-27: received
See all versions
Short URL
https://ia.cr/2006/032
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/032,
      author = {Deepak Kumar Dalai and Subhamoy Maitra},
      title = {Reducing the Number of Homogeneous Linear Equations in Finding Annihilators},
      howpublished = {Cryptology ePrint Archive, Paper 2006/032},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/032}},
      url = {https://eprint.iacr.org/2006/032}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.