Discrete logarithms in finite fields are linearly difficult
Michael Nüsken ( Cosec (B-it) )
Thursday 27 April 2006, 15.00 sharp (s.t.), b-it 1.25 (cosec meeting room)
Contents
The talk reports on the paper `Lower bounds on the linear complexity profile for the discrete logarithm in finite fields' by Arne Winterhof (2004):
We consider a sequence $(s_{i}) \in \Z_{d}^{\N}$ of discrete logarithms in a finite field $\F_{q}$ defined as follows: Fix a basis $(\beta_{0},\dots,\beta_{r-1})$ of $\F_{q}$ over its prime field $\F_{p}$, where $q=p^{r}$ and $p$ is prime. To enumerate the field elements write the index $i\in\N$ in its $p$-adic representation $i = i_{0} + i_{1} p + \dots + i_{r-1} p^{r-1} + \dots$ and associate the element $\xi_{i} = i_{0} \beta_{0} + i_{1} \beta_{1} + \dots + i_{r-1} \beta_{r-1}$ to it. Choose any generator $\gamma$ of the multiplicative group $\F_{q}^{\times}$. Further let $d$ be a divisor of the order $q-1$ of $\gamma$. Now, let $$ s_{i} = \dlog_{\gamma}( \xi _{i} ) \mod d \in \Z_{d}. $$ In other words, $\xi_{i} = \gamma^{s_{i}+kd}$ for some $k\in\Z$. If this sequence is cryptologically secure (which we hope) then in particular its linear complexity must be large, ie.\ the linear complexity must not be polynomial in $\log_{2}q = r \log_{2} p$ or $\log_{2} N$! The author proves a lower bound of order $\Omega( N^{1/2} q^{-1/4} p^{-1/2} )$ on the linear complexity of segments of the first $N$ elements of this sequence. The paper improves on the earlier lower bound on the linear complexity of the entire sequence of order $\Omega( r p )$ by \cite{meiwin01} in case $r\geq 5$.