Deepak Kumar Dalai (#482)

Name
Deepak Kumar Dalai

Personal Homepage
http://www.niser.ac.in/~deepak

Topic of his/her doctorate.
On Some Necessary Conditions of Boolean Functions to Resist Algebraic Attacks

Category
secret-key cryptography

Keywords
boolean functions, algebraic immunity

Year of completion
2006

Abstract
In this thesis we discuss on some properties of Boolean functions that are necessary for resistance against algebraic and fast algebraic attacks. It is well known that the algebraic degree $d$ of a Boolean function $f(x_1,\ldots,x_n)$, on $n$ variables, should not be low if it has to be used as a primitive in a cryptosystem. Recently, it has been noted that a necessary condition in resisting algebraic attack is the function $f$ should not have a relation $fg = h$, where $g, h$ are nonzero $n$-variable Boolean functions of low degree. This condition boils down to the situation that the function $f$ should not have relations like $f h_1 = 0$ or $(1+f) h_2 = 0$, where $h_1, h_2$ are nonzero $n$-variable Boolean functions
of low degree. The function $h_1$ (respectively $h_2$) is called the annihilator of $f$ (respectively $1+f$). The notation ${\cal AI}_n(f)$ is used
to denote the minimum degree of the annihilators of $f$ or $1+f$. This is well known as ``Algebraic Immunity" of the function $f$ in literature. There are evidences that algebraic immunity is not a sufficient condition to resist against all kinds of (fast) algebraic attacks, but clearly it is one of the most important necessary conditions. It is known
that ${\cal AI}_n(f) \leq \lceil \frac{n}{2} ceil$.
Good nonlinearity is an important property for a Boolean function to be used in a cryptosystem. We present a fundamental relationship between algebraic
immunity and nonlinearity of a Boolean function. We first relate the weight of a function with its algebraic immunity and then extend the result to show that if $nl(f) < \sum_{i=0}^{d} \binom{n}{i}$, then ${\cal AI}_n(f) \leq d+1$. Thus while choosing a function with good algebraic immunity, the nonlinearity of the function is lower bounded. Given a Boolean function, we have also studied the number of
linearly independent annihilators at the lowest possible degree.Further we have studied some existing constructions of cryptographically significant Boolean functions in terms of their algebraic immunity.
As there was no known construction of Boolean function with maximum possible algebraic immunity, we concentrated on that problem. So far, the attempt in designing Boolean functions with required algebraic immunity was only ad-hoc, i.e., the functions were designed keeping in mind the other cryptographic criteria, and then it has been checked whether it can provide good algebraic immunity too. For the first time, we present a construction method to generate Boolean functions on $n$ variables with
highest possible algebraic immunity $\lceil \frac{n}{2} ceil$. The construction is iterative in nature, i.e., we start from a function on one or two variables and then using them we continue to build the functions on higher number of variables step by step.
Further we tried to concentrate on the basic theory that how a function with maximum possible algebraic immunity can be constructed. We considered the $n$-variable functions $f, f_1, f_2$. The functions $f_1, f_2$ are such that they have no annihilator having degree $< \lceil \frac{n}{2} ceil$.
Then one can construct a function $f$ with the maximum possible algebraic immunity $\lceil \frac{n}{2} ceil$ where $supp(f) \supseteq supp(f_2)$ and $supp(1+f) \supseteq supp(f_1)$. We applied this strategy to get functions with maximum possible algebraic immunity and specifically
concentrated on the symmetric Boolean functions with such property. The algebraic degree and nonlinearity of these symmetric functions are studied in detail.
It has been revealed that Boolean functions with maximum possible algebraic immunity may be weak against fast algebraic attacks. It may very well
happen that given a Boolean function $f$ with
${\cal AI}_n(f) = \lceil \frac{n}{2} ceil$, one can get a functions $g, h$ with $\deg(h) = \lceil \frac{n}{2} ceil$ and $\deg(g)$ very low. The low degree of $g$ makes the function $f$ vulnerable against certain kinds of fast algebraic attacks. This motivates us to analyse the functions $f$ with maximum possible algebraic immunity to check the degree of $g$ under such a scenario. We study the different functions (produced by our constructions, and also other functions) to check this property and identify when the situation is encouraging and when it is not.
Given a Boolean function $f$ on $n$-variables, a set of homogeneous linear equations can be formed, by solving which one can decide whether there exist annihilators at degree $d$ or not. We analyse how the number of homogeneous linear equations can be reduced
and show that the reduction can be significant if one can find an affine transformation over $f(x)$ to get $h(x) = f(Bx+b)$ such that $|\{x | h(x) = 1, wt(x) \leq d\}|$ is maximized. We present an efficient
heuristic towards this. Our study also shows for what kind of Boolean functions the asymptotic reduction is possible and when the reduction is not asymptotic but constant. Our method helps in theoretically understanding the structure of the set of homogeneous linear equations used to find the annihilators.

Last Change
2011-04-20 08:13:34