Construction of pseudorandom binary sequences using additive characters over GF(2 k ) II
- PDF / 152,336 Bytes
- 9 Pages / 595 x 842 pts (A4) Page_size
- 0 Downloads / 202 Views
CONSTRUCTION OF PSEUDORANDOM BINARY SEQUENCES USING ADDITIVE CHARACTERS OVER GF(2k ) II ´nos Folla ´th Ja Department of Informatics, University of Debrecen Egyetem t´er 1, H-4032 Debrecen, Hungary E-mail: [email protected] (Received December 10, 2009; Accepted March 14, 2010) [Communicated by Andr´ as S´ ark¨ ozy]
Abstract In a series of papers Mauduit and S´ ark¨ ozy introduced measures of pseudorandomness and they constructed large families of sequences with strong pseudorandom properties. In later papers the structure of families of binary sequences was also studied. In these constructions fields with prime order were used. Throughout this paper the structure of a family of binary sequences based on GF(2k ) will be studied.
1. Introduction Goubin, Mauduit and S´ ark¨ ozy presented a new, large family of pseudorandom binary sequences based on the Legendre symbol [5]. This construction was an extension of the sequence studied in [10]. Although its security cannot be proved by reduction, many mathematical arguments substantiate it: it possesses the strict avalanche property [11], has a high family complexity [1] and a subfamily having small f -correlation was also found [6], the computational complexity of the best known attacks is high and it has an extremly fast implementation [7] and the bound on its correlation measure enables one to estimate its linear complexity profile [3], [2]. Accordingly this generator has mathematically substantiated security and still is faster than most provable secure pseudorandom sequence generators. The above mentioned construction is based on a multiplicative character over prime fields. In [4] a similar construction based on additive characters over fields Mathematics subject classification numbers: 68P25, 11T23. Key words and phrases: binary sequence, character sums, normality measure, pseudorandom. The research was partially supported by the TARIPAR3 project (grant Nr. TECH 08A2/2-2008-0086), the Hungarian-Slovakian project SK-8/2008 and the Hungarian-Croatian project HR-6/2008. 0031-5303/2010/$20.00
c Akad´emiai Kiad´o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
128
´ J. FOLLATH
of characteristic 2 was presented and its pseudorandom measures were studied. Throughout this paper the avalanche property, family complexity and linear complexity of this generator will be studied. Let us define the sequence Eq−1 as follows. Definition 1. Let Fq be a finite field of characteristic 2 and its multiplicative group of prime order. Let χ be a nonprincipal additive character, and α a primitive element of Fq and let f (x) ∈ Fq [x] be of odd degree d ≥ log q and let the coefficients of its terms be zero if and only if the term has an even exponent. Then let (en ) be the trace sequence ([4]) defined as Eq−1 = {χ(f (α1 )), χ(f (α2 )), . . . , χ(f (αq−1 ))} ∈ {−1, +1}q−1 .
(1.1)
In [11] the notion of the avalanche property was adopted for pseudorandom binary sequences. In Section 2 it will be proved that the generator in question posesses the strong avalanche property. In
Data Loading...
