## CryptoDB

### Yuriy Tarannikov

#### Affiliation: Moscow State University

#### Publications

**Year**

**Venue**

**Title**

2005

EPRINT

On affine rank of spectrum support for plateaued function
Abstract

The plateaued functions have a big interest for the studying of bent functions and by the reason that many cryptographically important functions are plateaued. In this paper we study the possible values of
the affine rank of spectrum support for plateaued functions. We consider for any positive integer $h$ plateaued functions with a spectrum support of cardinality $4^h$ (the cardinality must have such form), give the bounds on the affine rank for such functions and
construct functions where the affine rank takes all integer values from $2h$ till $2^{h+1}-2$. We solve completely the problem for $h=2$, namely, we prove that the affine rank of any plateaued function with a spectrum support of cardinality $16$ is $4$, $5$ or $6$.

2001

EPRINT

On the Constructing of Highly Nonlinear Resilient Boolean Functions by Means of Special Matrices
Abstract

In this paper we consider matrices of special form introduced in [11]
and used for the constructing of resilient functions with cryptographically
optimal parameters. For such matrices we establish lower bound
${1\over\log_2(\sqrt{5}+1)}=0.5902...$ for the important ratio
${t\over t+k}$ of its parameters and point out that there exists a
sequence of matrices for which the limit of ratio of its parameters
is equal to lower bound. By means of these matrices we construct
$m$-resilient $n$-variable functions with maximum possible nonlinearity
$2^{n-1}-2^{m+1}$ for $m=0.5902...n+O(\log_2 n)$. This result
supersedes the previous record.

2000

EPRINT

On Resilient Boolean Functions with Maximal Possible Nonlinearity
Abstract

It is proved that the maximal possible nonlinearity of $n$-variable
$m$-resilient Boolean function is $2^{n-1}-2^{m+1}$ for
${2n-7\over 3}\le m\le n-2$. This value can be achieved only for
optimized functions (i.~e. functions with an algebraic degree $n-m-1$).
For ${2n-7\over 3}\le m\le n-\log_2{n-2\over 3}-2$ it is suggested a method
to construct an $n$-variable $m$-resilient function with maximal possible
nonlinearity $2^{n-1}-2^{m+1}$ such that each variable presents in ANF of this
function in some term of maximal possible length $n-m-1$.
For $n\equiv 2\pmod 3$, $m={2n-7\over 3}$,
it is given a scheme of hardware implementation for such function that
demands approximately $2n$ gates EXOR and $(2/3)n$ gates AND.

2000

EPRINT

Spectral Analysis of High Order Correlation Immune Functions
Abstract

We use the recent results on the spectral structure of
correlation immune and resilient Boolean functions for the
investigations of high order correlation immune functions.
At first, we give simple proofs of some theorems where only
long proofs were known. Next, we introduce the matrix of
nonzero Walsh coefficients and establish important properties
of this matrix. We use these properties to prove the nonexistence
of some high order correlation immune functions. Finally, we
establish the order of magnitude for the number of (n-4)th
order correlation immune functions of n variables.

2000

EPRINT

New constructions of resilient Boolean functions with maximal nonlinearity
Abstract

In this paper we develop a technique that allows to obtain new effective constructions of highly resilient Boolean functions with high nonlinearity. In particular, we prove that the upper bound
$2^{n-1}-2^{m+1}$ on nonlinearity of m-resilient n-variable Boolean
functions is achieved for $0.6n-1\le m\le n-2$.

#### Coauthors

- Anton Botev (1)
- Maria Fedorova (1)
- Denis Kirienko (1)
- Peter Korolev (1)