Seminar der Algebra-Gruppe
         DMG, TU Wien

Am Freitag, 25.6.2004, hält

         Arne Winterhof 
   (Johann Radon Institute
    for Computational and
    Applied Mathematics, 
    Austrian Academy of Sciences)
    

einen Vortrag über

  Stream Ciphers and Number Theory:
       Sidelnikov Sequences

  

Zeit: 12:15-13:10
Ort: "Kleiner Seminarraum" des
      Instituts für Diskrete Mathematik und Geometrie,
      1040 Wien, Wiedner Hauptstraße 8-10, Turm A, 5.Stock

     
Abstract:

Let m_1,m_2, ... be a binary message represented as a string of bits,
then a cipher consists of two processes: encryption and decryption. In
a stream cipher each bit m_i is enciphered with the element k_i of a
keystream k_1,k_2, ... to c_i equiv m_i+k_i bmod 2 . The ciphertext
c_1,c_2, ... can be converted back by adding the keystream
to the ciphertext (m_i =  c_i + k_i mod 2).

The security of a stream cipher depends on the randomness properties
of the keystream. The cryptographic properties of many classes of keystreams
can be analyzed using number theoretic methods.
     
In this talk we analyze the following keystream introduced by Sidelnikov: 
Let q be an odd prime power, alpha a primitive element of the finite
field F_q, and let eta denote the {quadratic character} of F_q, i.e.,

   eta (alpha^i)=(-1)^i,     i=0,1, ...,q-2, 

and eta (0)=0 .

Then the Sidelnikov sequence is defined 
to be the (q-1)-periodic binary sequence (s_n) with 
  s_n = 1, if  eta (alpha^n+1) =-1, 
  s_n = 0, otherwise. 
for  n=0,1, ... . 

The linear complexity L(a_n) of a binary sequence (a_n) 
is the smallest positive integer L such that there are constants 
 c_1, ...,c_L in {0,1} satisfying

   a_n = c_1a_{n-1}+c_2a_{n-2}+ ... +c_La_{n-L} mod 2 

for all n >= L. 

The Linear complexity provides information on the predictability and
thus unsuitability for cryptography. Hence, a low linear complexity has
turned out to be an undesirable feature of keystreams.

We determine the exact value of the linear complexity of the 
Sidelnikov sequence defined above in many cases.

     
The proofs are based on number theoretic results: bounds on character
sums and formulas for cyclotomic numbers.

Besides linear complexity we also discuss autocorrelation properties
of Sidelnikov sequences.

Back to Algebra Research Group