Welcome to the resource topic for 2006/032
Title:
Reducing the Number of Homogeneous Linear Equations in Finding Annihilators
Authors: Deepak Kumar Dalai, 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.
ePrint: https://eprint.iacr.org/2006/032
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .