15. ÖMG-Kongress
Jahrestagung der Deutschen Mathematikervereinigung

16. bis 22. September 2001 in Wien

Sektion 3 - Diskrete Mathematik, Algorithmen
Montag, 17. September 2001, 18.00, Hörsaal 23

 

Lineare Komplexität (mit Toleranz $ K$) von Folgen über endlichen Körpern

Wilfried Meidl, Österreichische Akademie der Wissenschaften

 

Die lineare Komplexität $ L(S)$ einer (periodischen) Folge $ S = s_0,s_1,s_2, \ldots$ über einem endlichen Körper $ F_q$ ist definiert durch die kleinste nichtnegative ganze Zahl $ L$ für die es in $ F_q$ Koeffizienten $ d_1,d_2,\ldots d_L$ gibt, sodaß $ S$ die Rekursion

$\displaystyle s_j+d_1s_{j-1}+\ldots+d_cs_{j-L} = 0$   für alle$\displaystyle \;j\ge L $

erfüllt. In der Kryptographie benutzte Folgen müssen eine hohe lineare Komplexität haben. Zusätzlich soll die Änderung einiger weniger Stellen der Folge nicht ein signifikantes Absinken der linearen Komplexität bewirken. Diese Forderung führt zur Definition der linearen Komplexität mit Toleranz $ k$ [1][4], der kleinsten linearen Komplexität, die man durch Änderung von bis zu $ k$ Stellen der Periode einer Folge erhalten kann.
Mit Hilfe einer Verallgemeinerten Diskreten Fourier Transformation [2] wird der Erwartungswert $ E_{N,0}$ der linearen Komplexität einer zufälligen $ N$-periodischen Folge über $ F_q$ mit beliebiger vorgegebener Periodenlänge $ N$ ermittelt. Die Ergebnisse bestätigen eine Vermutung von R. Rueppel in [3]. Weiters wird ein Algorithmus zur Berechnung guter unterer Schranken für den Erwartungswert $ E_{N,k}$ der linearen Komplexität mit Toleranz $ k$ einer zufälligen $ N$-peridischen Folge über $ F_q$ präsentiert, der auf der Kenntnis der Zählfunktion $ \mathcal{N}_{N,0}(L)$, der Anzahl der $ N$-periodischen Folgen mit linearer Komplexität $ L$, basiert.

[1] C. Ding, G. Xiao, W. Shan, ``The Stability Theory of Stream Ciphers,'' Lecture Notes in Computer Science, vol. 561, Springer, Berlin, 1991.
[2] J.L. Massey, S. Serconek, Linear Complexity of Periodic Sequences: A General Theory, Advances in Cryptology-CRYPTO 96, Lecture Notes in Computer Science, vol 1109, Springer, Berlin, 1996, 357-371.
[3] R.A. Rueppel, ``Analysis and Design of Stream Ciphers,'' Springer, Berlin, 1986.
[4] M. Stamp, C.F. Martin, An algorithm for thr $ k$-error linear complexity of binary sequences with period $ 2^n$, IEEE Trans. Inform. Theory 39 (1993), 1398-1401.

E-Mail: wilfried.meidl@oeaw.ac.at
Homepage: www.dismat.oeaw.ac.at

Zeitplan der Sektion   Tagesübersicht   Liste der Vortragenden