## CryptoDB

### Subhamoy Maitra

#### Publications

**Year**

**Venue**

**Title**

2016

TOSC

Significantly Improved Multi-bit Differentials for Reduced Round Salsa and ChaCha
Abstract

ChaCha and Salsa are two software oriented stream ciphers that have attracted serious attention in academic as well as commercial domain. The most important cryptanalysis of reduced versions of these ciphers was presented by Aumasson et al. in FSE 2008. One part of their attack was to apply input difference(s) to investigate biases after a few rounds. So far there have been certain kind of limited exhaustive searches to obtain such biases. For the first time, in this paper, we show how to theoretically choose the combinations of the output bits to obtain significantly improved biases. The main idea here is to consider the multi-bit differentials as extension of suitable single-bit differentials with linear approximations, which is essentially a differential-linear attack. As we consider combinations of many output bits (for example 19 for Salsa and 21 for ChaCha), exhaustive search is not possible here. By this method we obtain very high biases for linear combinations of bits in Salsa after 6 rounds and in ChaCha after 5 rounds. These are clearly two rounds of improvement for both the ciphers over the existing works. Using these biases we obtain several significantly improved cryptanalytic results for reduced round Salsa and ChaCha that could not b obtained earlier. In fact, with our results it is now possible to cryptanalyse 6-round Salsa and 5-round ChaCha in practical time.

2015

EPRINT

2015

EPRINT

2015

EPRINT

2012

CHES

2010

EPRINT

A Combinatorial Analysis of HC-128
Abstract

We show that the knowledge of any one of the two internal state arrays of HC-128 along with the knowledge of 2048 keystream words is sufficient
to construct the other state array completely in $2^{42}$ time complexity. Though our analysis does not lead to any attack on HC-128, it reveals a structural insight into the cipher. In the process, we theoretically establish certain combinatorial properties of HC-128 keystream generation algorithm. We also suggest a modification to HC-128 that takes care of the recently known cryptanalytic results with little reduction in speed.

2010

EPRINT

Some Applications of Lattice Based Root Finding Techniques
Abstract

In this paper we present some problems and their solutions exploiting
lattice based root finding techniques.
In CaLC 2001, Howgrave-Graham proposed a method to find the Greatest
Common Divisor (GCD) of two large integers when one of the integers is
exactly known and the other one is known approximately. In this paper, we present three applications of the technique. The first one is
to show deterministic polynomial time equivalence between factoring
$N$ ($N = pq$, where $p > q$ or $p, q$ are of same bit size) and knowledge of $q^{-1} \bmod p$. Next, we consider the problem of finding smooth integers in a short interval. The third one is to factorize $N$ given a multiple of the decryption exponent in RSA.
In Asiacrypt 2006, Jochemsz and May presented a general strategy
for finding roots of a polynomial. We apply that technique for solving the following two problems. The first one is to factorize $N$ given an
approximation of a multiple of the decryption exponent in RSA. The second one is to solve the implicit factorization problem given three RSA moduli considering certain portions of LSBs as well as MSBs of one set of three secret primes are same.

2009

EPRINT

Deterministic Polynomial-Time Equivalence of Computing the CRT-RSA Secret Keys and Factoring
Abstract

Let $N = pq$ be the product of two large primes. Consider CRT-RSA with
the public encryption exponent $e$ and private decryption exponents $d_p, d_q$. It is well known that given any one of $d_p$ or $d_q$ (or both) one can factorize $N$ in probabilistic poly$(\log N)$ time with success probability almost equal to 1. Though this serves all the practical purposes, from theoretical point of view, this is not a deterministic polynomial time algorithm. In this paper, we present a lattice based deterministic poly$(\log N)$ time algorithm that uses both $d_p, d_q$ (in addition to the public information $e, N$) to factorize $N$.

2008

EPRINT

Analysis of RC4 and Proposal of Additional Layers for Better Security Margin
Abstract

In this paper, the RC4 Key Scheduling Algorithm (KSA) is theoretically studied to reveal non-uniformity in the expected number of times each value of the permutation is touched by the indices $i, j$. Based on our analysis and the results available in literature regarding the existing weaknesses of RC4, few additional layers over the RC4 KSA and RC4 Pseudo-Random Generation Algorithm (PRGA) are proposed. Analysis of the modified cipher (we call it RC4$^+$) shows that this new strategy avoids existing weaknesses of RC4.

2008

EPRINT

Revisiting Wiener's Attack -- New Weak Keys in RSA
Abstract

In this paper we revisit Wiener's method (IEEE-IT, 1990) of continued fraction (CF) to find new weaknesses in RSA. We consider RSA with $N = pq$, $q < p < 2q$, public encryption exponent $e$ and private decryption exponent $d$. Our motivation is to find out when RSA is insecure given $d$ is $O(n^\delta)$, where we are mostly interested in the range $0.3 \leq \delta \leq 0.5$. We use both the upper and lower bounds on $\phi(N)$ and then try to find out what are the cases when $\frac{t}{d}$ is a convergent in the CF expression of
$\frac{e}{N - \frac{3}{\sqrt{2}} \sqrt{N} + 1}$.
First we show that the RSA keys are weak when $d = N^\delta$ and
$\delta < \frac{3}{4} - \gamma - \tau$, where $2q - p = N^\gamma$ and $\tau$ is a small value based on certain parameters. This presents additional results over the work of de Weger (AAECC 2002). We also discuss how the idea of Boneh-Durfee (Eurocrypt 1999) works better to find weak keys beyond the bound
$\delta < \frac{3}{4} - \gamma - \tau$. Further we show that, the RSA
keys are weak when $d < \frac{1}{2} N^\delta$ and $e$ is
$O(N^{\frac{3}{2}-2\delta})$ for $\delta \leq \frac{1}{2}$. Using similar idea we also present new results over the work of Bl{\"o}mer and May (PKC 2004).

2008

EPRINT

RSA Cryptanalysis with Increased Bounds on the Secret Exponent using Less Lattice Dimension
Abstract

We consider RSA with $N = pq$, $q < p < 2q$, public encryption exponent $e$ and private decryption exponent $d$. Boneh and Durfee (Eurocrypt 1999, IEEE-IT 2000) used Coppersmith's method (Journal of Cryptology, 1997) to factorize $N$ using $e$ when $d < N^{0.292}$, the theoretical bound. However, the experimental bound that has been reached so far is only $N^{0.280}$ for 1000 bits integers (and less for higher number of bits). The basic idea relied on LLL algorithm, but the experimental bounds were constrained by large lattice dimensions. In this paper we present theoretical results and
experimental evidences to extend the bound of $d$ for which RSA is weak. This requires the knowledge of a few most significant bits of $p$ (alternatively these bits need to be searched exhaustively). We provide experimental results to highlight that the problem can be solved with low lattice dimensions in practice. Our results outperform the existing experimental results by increasing the bounds of $d$ and also we provide clear evidence that RSA with 1000 bit $N$ and $d$ of the order of $N^{0.3}$ can be cryptanalysed in practice from the knowledge of $N, e$.

2007

EPRINT

Construction of Rotation Symmetric Boolean Functions with Maximum Algebraic Immunity on Odd Number of Variables
Abstract

In this paper we present a theoretical construction of Rotation Symmetric Boolean Functions (RSBFs) on odd number of variables with maximum possible \ai and further these functions are not symmetric.
Our RSBFs are of better nonlinearity than the existing theoretical
constructions with maximum possible \ai. To get very good nonlinearity, which is important for practical cryptographic design, we generalize our construction to a construction cum search technique in the RSBF class. We find 7, 9, 11 variable RSBFs with maximum possible \ai having nonlinearities 56, 240, 984 respectively with very small amount of search after our basic construction.

2007

EPRINT

Balanced Boolean Function on 13-variables having Nonlinearity strictly greater than the Bent Concatenation Bound
Abstract

Very recently, Kavut and Yucel identified 9-variable Boolean functions having nonlinearity 242, which is currently the best known. However, any of these functions do not contain any zero in the Walsh spectrum and that is why they cannot be made balanced. We use these functions to construct 13-variable balanced Boolean function having nonlinearity
$2^{13-1} - 2^{\frac{13-1}{2}} + 2 = 4034$ which is strictly greater than the bent concatenation bound. This is the first demonstration of balanced Boolean functions on odd number of variables having nonlinearity strictly greater than the bent concatenation bound for number of input variables less than 15.

2007

EPRINT

RC4 State Information at Any Stage Reveals the Secret Key
Abstract

A theoretical analysis of the RC4 Key Scheduling Algorithm (KSA) is presented in this paper, where the nonlinear operation is swapping among the permutation bytes. Explicit formulae are provided for the probabilities with which the permutation bytes at any stage of the KSA are biased to the secret key. Theoretical proofs of these formulae have been left open since Roos's work (1995). Based on this analysis, an algorithm is devised to recover the $l$ bytes (i.e., $8l$ bits, typically $5 \leq l \leq 16)$ secret key from the permutation after any round of the KSA with constant probability of success. The search requires $O(2^{4l})$ many operations which is the square root of the exhaustive key search complexity $2^{8l}$. Moreover, given the state information, i.e., (a) the permutation, (b) the number of bytes generated (which is related to the index $i$) and (c) the value of the index $j$, after any number of rounds in Pseudo-Random Generation Algorithm (PRGA) of RC4, one can deterministically get back to the permutation after the KSA and thereby extract the keys efficiently with a constant probability of success. Finally, a generalization of the RC4 KSA is analyzed corresponding to a class of update functions of the indices involved in the swaps. This reveals an inherent weakness of shuffle-exchange kind of key scheduling.

2007

EPRINT

New Form of Permutation Bias and Secret Key Leakage in Keystream Bytes of RC4
Abstract

Consider the permutation $S$ in RC4. Roos pointed out in 1995 that after the Key Scheduling Algorithm (KSA) of RC4, the initial bytes of the permutation, i.e., $S[y]$ for small values of $y$ are biased towards some linear combination of secret key bytes. In this paper, for the first time we show that the bias can be observed in $S[S[y]]$ too. Based on this new form of permuatation bias after the KSA and other related results, a complete framework is presented to show that many keystream output bytes of RC4 are significantly biased towards several linear combinations of the secret key bytes. The results do not assume any condition on the secret key. We find new biases in the initial as well as in the 256-th and 257-th keystream output bytes. For the first time biases at such later stages are discovered without any knowledge of secret key bytes. We also identify that these biases propagate further once the information for the index $j$ is revealed.

2007

EPRINT

On Non-Randomness of the Permutation after RC4 Key Scheduling
Abstract

Here we study a weakness of the RC4 Key Scheduling Algorithm (KSA) that has already been noted by Mantin and Mironov. Consider the RC4 permutation $S$ of $N$ (usually 256) bytes and denote it by $S_N$ after the KSA. Under reasonable assumptions we present a simple proof that each permutation byte after the KSA is significantly biased (either positive or negative) towards many values in the range $0, \ldots, N-1$. These biases are independent of the secret key and thus present an evidence that the permutation after the KSA can be distinguished from random permutation without any assumption on the secret key. We also present a detailed empirical study over Mantin's work when the theoretical formulae vary significantly from experimental results
due to repetition of short keys in RC4. Further, it is explained how these results can be used to identify new distinguishers for RC4 keystream.

2007

EPRINT

Idempotents in the Neighbourhood of Patterson-Wiedemann Functions having Walsh Spectra Zeros
Abstract

In this paper we study the neighbourhood of $15$-variable Patterson-Wiedemann (PW) functions, i.e., the functions that differ by a small Hamming distance from the PW functions in terms of truth table representation. We exploit the idempotent structure of the PW functions and interpret them as Rotation Symmetric Boolean Functions (RSBFs). We present techniques to modify these RSBFs to introduce zeros in the Walsh spectra of the modified functions with minimum reduction in nonlinearity. Our technique demonstrates 15-variable balanced and $1$-resilient functions with currently best known nonlinearities 16272 and 16264 respectively. In the process, we find functions for which the autocorrelation spectra and algebraic immunity parameters are best known till date.

2006

EPRINT

Balanced Boolean Functions with (more than) Maximum Algebraic Immunity
Abstract

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.

2006

EPRINT

Notion of Algebraic Immunity and Its evaluation Related to Fast Algebraic Attacks
Abstract

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

Reducing the Number of Homogeneous Linear Equations in Finding Annihilators
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.

2006

EPRINT

There exist Boolean functions on $n$ (odd) variables having nonlinearity $> 2^{n-1} - 2^{\frac{n-1}{2}}$ if and only if $n > 7$
Abstract

For the first time we find Boolean functions on 9 variables having nonlinearity 241, that remained as an open question in literature for almost three decades. Such functions are discovered using a suitably modified steepest-descent based iterative heuristic search in the class of rotation symmetric Boolean functions (RSBFs). This shows that there exist Boolean functions on $n$ (odd) variables having nonlinearity $> 2^{n-1} - 2^{\frac{n-1}{2}}$ if and only if $n > 7$. Using the same search method, we also find several other important functions and we study the autocorrelation, propagation characteristics and resiliency of the RSBFs (using proper affine transformations, if required). The results show that it is possible to get balanced Boolean functions on $n=10$ variables having autocorrelation spectra with maximum absolute value $< 2^{\frac{n}{2}}$, which was not known earlier. In certain cases the functions can be affinely transformed to get first order propagation characteristics. We also obtain 10-variable functions having first order resiliency and nonlinearity 492 which was posed as an open question in Crypto 2000.

2006

EPRINT

Enumeration of 9-variable Rotation Symmetric Boolean Functions having Nonlinearity > 240
Abstract

The existence of $9$-variable Boolean functions having nonlinearity
strictly greater than $240$ has been shown very recently (May 2006)
by Kavut, Maitra and Y{\"u}cel. The functions with nonlinearity 241 have been identified by a heuristic search in the class of Rotation Symmetric Boolean Functions (RSBFs). In this paper we efficiently perform the exhaustive search to enumerate the 9-variable RSBFs having nonlinearity $> 240$ and found that there are such functions with nonlinearity 241 only and there is no RSBF having nonlinearity $> 241$. Our search enumerates $8 \times 189$ many 9-variable RSBFs having nonlinearity 241. We further show that there are only two functions which are different up to the affine equivalence. Towards the end we explain the coding theoretic significance of these functions.

2005

EPRINT

Results on Rotation Symmetric Bent Functions
Abstract

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

Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity
Abstract

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.

2004

EPRINT

Crosscorrelation Spectra of Dillon and Patterson-Wiedemann type Boolean Functions
Abstract

In this paper we study the additive crosscorrelation spectra between
two Boolean functions whose supports are union of certain cosets.
These functions on even number of input variables have been introduced by Dillon and we refer to them as Dillon type functions. Our general result shows that the crosscorrelation spectra between any two Dillon type functions are at most $5$-valued. As a consequence we find that the crosscorrelation spectra between two Dillon type bent functions on $n$-variables are at most $3$-valued with maximum possible absolute value at the nonzero points being $\leq 2^{\frac{n}{2}+1}$. Moreover, in the same line, the autocorrelation spectra of Dillon type bent functions at different decimations is studied. Further we demonstrate that these results can be used to
show the existence of a class of polynomials for which the absolute
value of the Weil sum has a sharper upper bound than the Weil bound.
Patterson and Wiedemann extended the idea of Dillon for
functions on odd number of variables. We study the crosscorrelation
spectra between two such functions and then use the results for the
calculating the autocorrelation spectra too.

2004

EPRINT

Plateaued Rotation Symmetric Boolean Functions on Odd Number of Variables
Abstract

The class of Rotation Symmetric Boolean Functions (RSBFs) has received serious attention recently in searching functions of cryptographic significance. These functions are invariant under circular translation of indices. In this paper we study such functions on odd number of variables and interesting combinatorial properties related to Walsh spectra of such functions are revealed. In particular we concentrate on plateaued functions (functions with three valued Walsh spectra) in this class and derive necessary conditions for existence of balanced rotation symmetric plateaued functions. As application of our result we show the non existence of 9-variable, 3-resilient RSBF with nonlinearity 240 that has been posed as an open question in FSE 2004. Further we show how one can make efficient search in the space of RSBFs based on our theoretical results and as example we complete the search for unbalanced 9-variable, 3rd order correlation immune plateaued RSBFs with nonlinearity 240.

2003

EPRINT

Direct Sum of Non Normal and Normal Bent Functions Always Produces Non Normal Bent Functions
Abstract

Prof. Claude Carlet has pointed out an error in Theorem 1 of the
paper. The error could not be recovered for the time being.
Thus the statement presented in the title of the paper
is not proved.

2003

EPRINT

Minimum Distance between Bent and 1-resilient Boolean Functions
Abstract

In this paper we study the minimum distance between the set of bent functions and the set of 1-resilient Boolean functions and present a lower bound on that. The bound is proved to be tight for functions up to $10$ input variables. As a consequence, we present a strategy to modify the bent functions, by toggling some of its outputs, in getting a large class of $1$-resilient functions with very good nonlinearity and autocorrelation. In particular, the technique is applied upto $12$-variable functions and we show that the construction provides a large class of $1$-resilient functions reaching currently best known nonlinearity and achieving very low autocorrelation values which were not known earlier. The technique is sound enough to theoretically solve some of the mysteries of $8$-variable, $1$-resilient functions with maximum possible nonlinearity. However, the situation becomes complicated from $10$ variables and above, where
we need to go for complicated combinatorial analysis with trial and error using computational facility.

2003

EPRINT

Patterson-Wiedemann Construction Revisited
Abstract

In 1983, Patterson and Wiedemann constructed Boolean functions on
$n = 15$ input variables having nonlinearity strictly greater than
$2^{n-1} - 2^{\frac{n-1}{2}}$. Construction of Boolean functions on
odd number of variables with such high nonlinearity was not known earlier and also till date no other construction method of such functions are known. We note that the Patterson-Wiedemann construction can be understood in terms of interleaved sequences as introduced by Gong in 1995 and subsequently these functions can be described as repetitions of a particular binary string. As example we elaborate the cases for $n = 15, 21$. Under this framework, we map the problem of finding Patterson-Wiedemann functions into a problem of solving a system of linear inequalities over the set of integers and provide
proper reasoning about the choice of the orbits. This, in turn, reduces the search space. Similar analysis also reduces the complexity of calculating autocorrelation and generalized nonlinearity for such functions. In an attempt to understand the above construction from the group theoretic view point, we characterize the group of all $GF(2)$-linear transformations of $GF(2^{ab})$ which acts on $PG(2,2^a)$.

2000

EPRINT

New Directions in Design of Resilient Boolean Functions
Abstract

There has been a recent upsurge of research in the design of resilient
Boolean functions for use in stream cipher systems. The existing
research concentrates on maximum degree resilient functions and tries
to obtain as high nonlinearity as possible. In sharp contrast to this
approach we identify the class of functions with {\em provably best}
possible trade-off among the parameters: number of variables,
resiliency, nonlinearity and algebraic degree. We first prove a
sharper version of McEliece theorem for Reed-Muller codes as applied
to resilient functions, which also generalizes the well known
Xiao-Massey characterization. As a consequence a nontrivial upper
bound on the nonlinearity of resilient functions is obtained. This
result coupled with Siegenthaler's inequality naturally leads to
the notion of provably best resilient functions. We further show that
such best functions can be constructed by the Maiorana-McFarland
like technique. In cases where this method fails, we provide new ideas
to construct best functions. We also briefly discuss efficient
implementation of these functions in hardware.

2000

EPRINT

Highly Nonlinear Balanced Boolean Functions with very good Autocorrelation Property
Abstract

Constructing highly nonlinear balanced Boolean functions with very good
autocorrelation property is an interesting open question. In this direction
we use the measure $\Delta_f$ for a function $f$ proposed by Zhang and
Zheng (1995). We provide balanced functions $f$ with currently best known
nonlinearity and $\Delta_f$ values together. Our results for 15-variable
functions disprove the conjecture proposed by Zhang and Zheng (1995),
where our constructions are based on modifications of
Patterson-Wiedemann (1983) functions. Also we propose a simple
bent based construction technique to get functions with very good
$\Delta_f$ values for odd number of variables. This construction has
a root in Kerdock Codes. Moreover, our construction on even number
of variables is a recursive one and we conjecture (similar to Dobbertin's
conjecture (1994) with respect to nonlinearity) that this provides
minimum possible value of $\Delta_f$ for a function $f$ on even number
of variables.

2000

EPRINT

New Constructions of Resilent and Correlation Immune Boolean Functions achieving Upper Bounds on Nonlinearity
Abstract

Recently weight divisibility results on resilient and correlation
immune Boolean functions have received a lot of attention. These
results have direct consequences towards the upper bound on nonlinearity
of resilient and correlation immune Boolean functions of certain order.
Now the clear benchmark in the design of resilient Boolean functions
(which optimizes Sigenthaler's inequality) is to provide results
which attain the upper bound on nonlinearity. Here we construct a
7-variable, 2-resilient Boolean function with nonlinearity 56. This
solves the maximum nonlinearity issue for 7-variable functions with
any order of resiliency. Using this 7-variable function, we also
construct a 10-variable, 4-resilient Boolean function with nonlinearity
480. Construction of these two functions were justified as important
open questions in Crypto 2000. Also we provide methods to generate an
infinite sequence of Boolean functions on $n = 7 + 3i$ variables
$(i \geq 0)$ with order of resiliency $m = 2 + 2i$, algebraic degree
$4 + i$ and nonlinearity $2^{n-1} - 2^{m+1}$, which were not known
earlier. We conclude with a few interesting construction results
on unbalanced correlation immune functions of 5 and 6 variables.

2000

EPRINT

Correlation Immune Boolean Functions with Very High Nonlinearity
Abstract

Here we provide a construction method for unbalanced, first order
correlation immune Boolean functions on even number of variables
$n \geq 6$. These functions achieve the currently best known
nonlinearity $2^{n-1} - 2^{\frac{n}{2}} + 2^{\frac{n}{2} - 2}$ .
Then we provide a simple modification of these functions to get
unbalanced correlation immune Boolean functions on even number of
variables $n$, with nonlinearity
$2^{n-1} - 2^{\frac{n}{2}} + 2^{\frac{n}{2} - 2} - 2$ and maximum
possible algebraic degree $n-1$. Moreover, we present a detailed
study on the Walsh spectra of these functions.

#### Program Committees

- FSE 2019
- FSE 2018
- FSE 2017
- FSE 2014
- Eurocrypt 2013
- FSE 2013
- Asiacrypt 2013
- FSE 2012

#### Coauthors

- Avishek Adhikari (1)
- Anubhab Baksi (2)
- Subhadeep Banik (2)
- Kaushik Chakraborty (1)
- Arka Rai Choudhuri (1)
- John A. Clark (1)
- Deepak Kumar Dalai (6)
- Sourav Das (1)
- Prakash Dey (1)
- Pramit Dey (1)
- Sugata Gangopadhyay (3)
- Kishan Chand Gupta (2)
- Martin Hell (1)
- Thomas Johansson (1)
- Selçuk Kavut (2)
- Selçuk Kavut (1)
- P. H. Keskar (1)
- Soumen Maity (2)
- Alexander Maximov (1)
- Bodhisatwa Mazumdar (1)
- Willi Meier (3)
- Debdeep Mukhopadhyay (1)
- Enes Pasalic (1)
- Goutam Paul (10)
- Shashwat Raizada (1)
- Santanu Sarkar (11)
- Palash Sarkar (6)
- Sumanta Sarkar (6)
- Sourav Sen Gupta (3)
- Rohit Srivastava (1)
- Pantelimon Stanica (1)
- Melek D. Yücel (2)