Galois Rings and Pseudo-random Sequences
We survey our constructions of pseudo random sequences (binary, \({\mathbb Z}_8\) , \({\mathbb Z}_{2^l},\) ...) from Galois rings. Techniques include a local Weil bound for character sums, and several kinds of Fourier transform. Applications range from cr
- PDF / 521,265 Bytes
- 18 Pages / 430 x 660 pts Page_size
- 44 Downloads / 204 Views
2
CNRS-I3S, Les Algorithmes, Euclide B, 2000, route des Lucioles, 06 903 Sophia Antipolis, France [email protected], [email protected] Institute for Problems of Information Transmission, Russian Academy of Sciences, Bol’shoi Karetnyi, 19, GSP-4, Moscow, 127994, Russia [email protected]
Abstract. We survey our constructions of pseudo random sequences (binary, Z8 , Z2l ,. . . ) from Galois rings. Techniques include a local Weil bound for character sums, and several kinds of Fourier transform. Applications range from cryptography (boolean functions, key generation), to communications (multi-code CDMA), to signal processing (PAPR reduction). Keywords: Correlation, Galois Rings, MSB, CDMA, OFDM, PAPR.
1
Introduction
Since the seminal work of Claude Shannon in the 40’s the algebraic structure of coding alphabets was a finite field. However, there was a push towards finite rings due to modulation requirements, a 4− PSK modulation being more powerful than an antipodal modulation, for instance [1]. This led researchers in the 70’s to consider cyclic codes over Z/M Z, with a special attention for M a power of a prime [2,19]. In the 90’s cyclic codes over rings received a lot of attention due to many pure applications: the solution of the Kerdock Preparata riddle [8], and a new construction of the Leech lattice [3], (both for M = 4), to name but a few. In this golden dawn, new and powerful mathematical techniques arose, the most profound being probably a p−adic analogue of the Weil bound on character sums [10], and families of low correlation sequences (based on weighted degree trace codes) tailored for that bound [20]. In the present decade, new engineering applications emerged that required that machinery, and are significantly different, but not unrelated to the classical use in Spread Spectrum and CDMA systems illustrated in [11,7], or to take a more recent example the 3GPP standard (see www.3gpp.org). In particular an important quantity for the safe processing of electronic equipment is the Peak to Average Power Ratio (PAPR), signals with high dynamic range being potentially harmful to operational amplifiers. Two models of signalling sequences S.D. Galbraith (Eds.): Cryptography and Coding 2007, LNCS 4887, pp. 16–33, 2007. c Springer-Verlag Berlin Heidelberg 2007
Galois Rings and Pseudo-random Sequences
17
both due to Paterson and co-workers lead to somewhat different mathematical formulation. In the first scenario, motivated by OFDM applications, and based on DFT calculation, we are to control some hybrid character sums (i.e. involving not only additive but also multiplicative characters) in relation to many valued sequences [17]. In the second approach, motivated by multi-code CDMA, we are to control the nonlinearity of binary sequences of length a power of 2 [16]. This notion of nonlinearity coincides with the one familiar from boolean functions theory. In both models sequences live in families and are supposed to form a code either spherical in the first case or binary in the second. Both papers [17,16] already use weighted
Data Loading...
