International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at)


Deepak Kumar Dalai (#482)
Name Deepak Kumar Dalai
Personal Homepage
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
Ph.D. Supervisor(s) Subhamoy Maitra
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
To provide an update on this entry, please click .

Contact: phds (at)

[ IACR home page ] [ IACR PhDs page ] © IACR