## CryptoDB

### Deepak Kumar Dalai

#### Publications

Year
Venue
Title
2006
EPRINT
It has been noted recently that algebraic (annihilator) immunity alone does not provide sufficient resistance against algebraic attacks. In this regard, given a Boolean function $f$, just checking the minimum degree annihilators of $f, 1+f$ is not enough and one should check the relationsips of the form $fg = h$, and a function $f$, even if it has very good algebraic immunity, is not necessarily good against fast algebraic attack, if degree of $g$ becomes very low when degree of $h$ is equal to or little greater than the algebraic immunity of $f$. In this paper we theoretically study the two currently known constructions having maximum possible algebraic immunity from this viewpoint. To the end, we also experimentally study some cryptographically significant functions having good algebraic immunity.
2006
EPRINT
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.
2006
EPRINT
In this correspondence, construction of balanced Boolean functions with maximum possible algebraic (annihilator) immunity (AI) is studied with an additional property which is necessary to resist fast algebraic attack. The additional property considered here is, given an $n$-variable ($n$ even) balanced function $f$ with maximum possible AI $\frac{n}{2}$, and given two $n$-variable Boolean functions $g, h$ such that $fg = h$, if $\deg(h) = \frac{n}{2}$, then $\deg(g)$ must be greater than or equal to $\frac{n}{2}$. Our results can also be used to present theoretical construction of resilient Boolean functions having maximum possible AI.
2005
FSE
2005
EPRINT
In this paper we analyze the combinatorial properties related to the Walsh spectra of rotation symmetric Boolean functions on even number of variables. These results are then applied in studying rotation symmetric bent functions.
2005
EPRINT
So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions,one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with $O(n^2)$ time and $O(n)$ space complexity.

#### Coauthors

Kishan Chand Gupta (2)
Subhamoy Maitra (6)
Sumanta Sarkar (1)