## CryptoDB

### An Braeken

#### Publications

**Year**

**Venue**

**Title**

2006

EPRINT

On Zigzag Functions and Related Objects in New Metric
Abstract

In \cite{BCS96}, the concept of zigzag function was introduced in
relation with oblivious transfer \cite{R84}. This subject has
later been studied in \cite{S99,DS01,CFW01}. The definition
of zigzag functions has been generalized to $s$-zigzag functions for
$2\leq s\leq n$. It turns out that zigzag functions are also interesting
combinatorial objects, thanks to their relation with self-intersecting codes and
orthogonal arrays \cite{BCS96,S99}.
The aim of this work is to formulate these objects with respect to a new metric
following the approach proposed in \cite{BNNP} and to investigate the properties
of the generalized zigzag functions and related concepts.

2005

FSE

2005

EPRINT

On the Algebraic Immunity of Symmetric Boolean Functions
Abstract

In this paper, we analyse the algebraic immunity of symmetric Boolean functions. We identify a set of lowest degree annihilators for symmetric functions and propose an efficient algorithm for computing the algebraic immunity of a symmetric function. The existence of several symmetric functions with maximum algebraic immunity is proven. In this way, a new class of function which have good implementation properties and maximum algebraic immunity is found. We also investigate the existence of symmetric functions with high nonlinearity and reasonable order of algebraic immunity. Finally, we give suggestions how to use symmetric functions in a stream cipher.

2005

EPRINT

Classification of Cubic $(n-4)$-resilient Boolean Functions
Abstract

Carlet and Charpin classified in \cite{CC04} the set of cubic $(n-4)$-resilient Boolean functions into four different types with respect to the Walsh spectrum and the dimension of the linear space. Based on the classification of $RM(3,6)/RM(1,6)$, we completed the classification of the cubic $(n-4)$-resilient Boolean function by deriving the corresponding ANF and autocorrelation spectrum for each of the four types. In the same time, we solved an open problem of \cite{CC04} by proving that all plateaued cubic $(n-4)$-resilient Boolean functions have dimension of the linear space equal either to $n-5$ or $n-6$.

2004

EPRINT

On Cheating Immune Secret Sharing
Abstract

This work addresses the problem of cheating prevention in secret sharing. The scheme is said to be $k$-cheating immune if any group of $k$ cheaters has no advantage over honest participants. In this paper we study the constraints of cheating immune secret sharing schemes. We give a necessary and sufficient condition for SSSs to be cheating immune. Then, we improve the upper bound of D'Arco {\textit et.~al} on the number of cheaters tolerated in such scheme. Our proof is much simpler than the proof of D'Arco {\textit et.~al} and relies on certain properties of cryptographic Boolean functions. As a result of independent interest we provide a condition given function to be $t$-resilient and to satisfy the propagation criterion of degree $\ell$ over any finite field.

2004

EPRINT

Covering Radius of the $(n-3)$-rd Order Reed-Muller Code in the Set of Resilient Functions
Abstract

In this paper, we continue the study of the covering
radius in the set of resilient functions, which has been defined by Kurosawa. This new concept is meaningful to cryptography especially in the context of the new class of algebraic attacks on stream ciphers proposed by Courtois and Meier at Eurocrypt 2003 and Courtois at Crypto 2003. In order to resist such attacks the combining Boolean function should be at high distance from lower degree functions.
Using a result from coding theory on the covering radius of
$(n-3)$-rd Reed-Muller codes, we establish exact values of the
the covering radius of $RM(n-3,n)$ in the set of $1$-resilient Boolean
functions of $n$ variables, when $\lfloor n/2 \rfloor = 1 \mod\;2$. We also improve the lower bounds for covering radius of the Reed-Muller
codes $RM(r,n)$ in the set of $t$-resilient functions, where
$\lceil r/2 \rceil = 0 \mod\;2$, $t \leq n-r-2$ and $n\geq r+3$.

2004

EPRINT

Classification of Highly Nonlinear Boolean Power Functions with a Randomised Algorithm for Checking Normality
Abstract

A Boolean function is called normal if it is constant on flats of certain dimensions. This property is relevant for the construction and analysis of cryptosystems. This paper presents an asymmetric Monte Carlo algorithm to determine whether a given Boolean function is normal. Our algorithm is far faster than the best known (deterministic) algorithm of Daum et al. In a first phase, it checks for flats of low dimension whether the given Boolean function is constant on them and combines such flats to flats of higher dimension in a second phase. This way, the algorithm is much faster than exhaustive search. Moreover, the algorithm benefits from randomising the first phase. In addition, by evaluating several flats implicitly in parallel, the time-complexity of the algorithm decreases further. As an application, we determine the level of normality for several, highly nonlinear Boolean power functions.

2004

EPRINT

Classification of Boolean Functions of 6 Variables or Less with Respect to Cryptographic Properties
Abstract

This paper presents an efficient approach for classification of
the affine equivalence classes of cosets of the first order
Reed-Muller code with respect to cryptographic properties such as
correlation-immunity, resiliency and propagation characteristics.
First, we apply the method to completely classify all the $48$
classes into which the general affine group $AGL(2,5)$ partitions
the cosets of $RM(1,5)$. Second, we describe how to find the affine
equivalence classes together with their sizes of Boolean functions in 6 variables.
We perform the same classification for these classes. Moreover, we
also determine the classification of $RM(3,7)/RM(1,7)$.
We also study the algebraic immunity of the corresponding affine equivalence classes.
Moreover, several relations are derived between the algebraic immunity
and other cryptographic properties.
Finally, we introduce two new indicators which can be used to distinguish
affine inequivalent Boolean functions when the known criteria are
not sufficient. From these indicators a method can be derived for
finding the affine relation between two functions (if such
exists). The efficiency of the method depends on the structure of
the Walsh or autocorrelation spectrum.

2004

EPRINT

On Boolean Functions with Generalized Cryptographic Properties
Abstract

By considering a new metric, we generalize cryptographic
properties of Boolean functions such as resiliency and propagation
characteristics. These new definitions result in a better understanding
of the properties of Boolean functions and provide a better insight in
the space defined by this metric. This approach leads to the
construction of ``hand-made'' Boolean functions, i.e., functions for
which the security with respect to some specific monotone sets of inputs
is considered, instead of the security with respect to all possible
monotone sets with the same cardinality, as in the usual definitions.
This approach has the advantage that some trade-offs between important
properties of Boolean functions can be relaxed.

#### Coauthors

- Alex Biryukov (1)
- Yuri Borissov (3)
- Christophe De Cannière (1)
- Ventzislav Nikov (3)
- Svetla Nikova (6)
- Bart Preneel (6)
- Igor Semaev (1)
- Christopher Wolf (1)