Institute for Mathematics and Its Applications

Talk abstract:

On the crosscorrelation of m-sequences and related topics

Tor Helleseth,

The crosscorrelation function between two m-sequences of period pm - 1, that differ by a decimation d is defined as

$C_d(\tau)=\sum_{t=0}^{p^m-2}\omega^{s(t+\tau)-s(dt)}$
where $\omega$ is a primitive pth root of unity. We give a survey of known results on the crosscorrelation function of m-sequences.
Let$f(x)$ be a mapping $f : GF(p^m) \rightarrow GF(p^m)$. Let $N(a,b)$ denote the number of solutions $x \in GF(p^m)$ of $f(x+a)-f(x)=b$ where $a, b \in GF(p^m)$ and let\[\Delta_f = \max\{ N(a,b) \; | \; a, b \in GF(p^m), \; a \neq 0 \}. \]

The mapping f is said to be differentially k-uniform if $\Delta$f = k. This concept is of interest in cryptography since differential and linear cryptanalysis exploit weaknesses of the uniformity of the functions which are used in DES and in several other block ciphers.

We show how to consruct sequences with optimal correlation properties from 1-differential power mappings. We also survey results on known results on 2-uniform mappings (called almost perfect nonlinear (APN)).

Back to Workshop Schedule