## CryptoDB

### Sumanta Sarkar

#### Affiliation: TCS Innovation Labs

#### Publications

**Year**

**Venue**

**Title**

2016

TOSC

Lightweight Diffusion Layer: Importance of Toeplitz Matrices
Abstract

MDS matrices are used as building blocks of diffusion layers in block ciphers, and XOR count is a metric that estimates the hardware implementation cost. In this paper we report the minimum value of XOR counts of 4 × 4 MDS matrices over F24 and F28 , respectively. We give theoretical constructions of Toeplitz MDS matrices and show that they achieve the minimum XOR count. We also prove that Toeplitz matrices cannot be both MDS and involutory. Further we give theoretical constructions of 4 × 4 involutory MDS matrices over F24 and F28 that have the best known XOR counts so far: for F24 our construction gives an involutory MDS matrix that actually improves the existing lower bound of XOR count, whereas for F28 , it meets the known lower bound.

2009

EPRINT

On the Lower Bounds of the Second Order Nonlinearity of some Boolean Functions
Abstract

The $r$-th order nonlinearity of a Boolean function is an important
cryptographic criterion in analyzing the security of stream as well
as block ciphers. It is also important in coding theory as it is
related to the covering radius of the Reed-Muller code $\mathcal{R}(r, n)$.
In this paper we deduce the lower bounds of the second order nonlinearity
of the two classes of Boolean functions of the form
\begin{enumerate}
\item
$f_{\lambda}(x) = Tr_1^n(\lambda x^{d})$ with $d=2^{2r}+2^{r}+1$
and $\lambda \in \mathbb{F}_{2^{n}}$ where $n = 6r$.
\item
$f(x,y)=Tr_1^t(xy^{2^{i}+1})$
where $x,y \in \mathbb{F}_{2^{t}}, n = 2t, n \ge 6$ and
$i$ is an integer such that $1\le i < t$, $\gcd(2^t-1, 2^i+1) = 1$.
\end{enumerate}
For some $\lambda$, the first class gives bent functions whereas
Boolean functions of the second class are all bent, i.e., they achieve
optimum first order nonlinearity.

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

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

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

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.

#### Coauthors

- Kaushik Chakraborty (1)
- Pascale Charpin (1)
- Deepak Kumar Dalai (1)
- Sugata Gangopadhyay (1)
- Selçuk Kavut (1)
- Subhamoy Maitra (6)
- Bodhisatwa Mazumdar (1)
- Sihem Mesnager (1)
- Debdeep Mukhopadhyay (1)
- Santanu Sarkar (1)
- Habeeb Syed (1)
- Ruchi Telang (1)
- Melek D. Yücel (1)