Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
About Open Problems Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

Open Problems on the Cross-correlation of m-Sequences

verfasst von : Tor Helleseth

Erschienen in: Open Problems in Mathematics and Computational Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Pseudorandom sequences are important for many applications in communication systems, in coding theory, and in the design of stream ciphers. Maximum-length linear sequences (or m-sequences) are popular in sequence designs due to their long period and excellent pseudorandom properties. In code-division multiple-access (CDMA) applications, there is a demand for large families of sequences having good correlation properties. The best families of sequences in these applications frequently use m-sequences in their constructions. Therefore, the problem of determining the correlation properties of m-sequences has received a lot of attention since the 1960s, and many interesting theoretical results of practical interest have been obtained. The cross-correlation of m-sequences is also related to other important problems, such as almost perfect nonlinear functions (APN) and almost bent functions (AB), and to the nonlinearity of S-boxes in many block ciphers including AES. This chapter gives an updated survey of the cross-correlation of m-sequences and describes some of the most important open problems that still remain in this area.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Generating Good Span n Sequences Using Orthogonal Functions in Nonlinear Feedback Shift Registers
Nächstes Kapitel Open Problems on With-Carry Sequence Generators
Literatur
1.
C. Bracken, Designs, Codes, Spin Models and the Walsh Transform, Ph.D. thesis, Department of Mathematics, National University Ireland (NUI), Maynooth, 2004 In this Ph.D. thesis one can find a nice proof of the number of solutions of a linearized polynomial playing an important role in the proof of the 3-valued crosscorrelation with the Kasami–Welch exponent \(d = 2^{2k} - 2^{k} + 1\).
2.
A. Canteaut, P. Charpin, H. Dobbertin, Binary m-sequences with three-valued crosscorrelation: a proof of Welch’s conjecture. IEEE Trans. Inf. Theory 46(1), 4–8 (2000) The more than 30 year old conjecture by Welch on a decimation with 3-valued crosscorrelation between two m-sequences is proved in this paper.
3.
F. Chabaud, S. Vaudenay, Links between differential and linear cryptanalysis, in Advances in Cryptology-EUROCRYPT’94 (Springer, New York, 1995), pp. 356–365 The paper gives important relations between differential and linear analysis and shows in particular that AB functions are APN functions.
4.
T.W. Cusick, H. Dobbertin, Some new three-valued crosscorrelation functions for binary m-sequences. IEEE Trans. Inf. Theory 42(4), 1238–1240 (1996) The authors prove two conjectures due to Niho on two decimation that (for n even) give 3-valued crosscorrelation.
5.
H. Dobbertin, One-to-one highly nonlinear power functions on GF(2 n ). Appl. Algebra Eng. Commun. Comput. 9(2), 139–152 (1998) The author finds a new decimation with 4-valued crosscorrelation, the first new one since Niho’s Ph.D. thesis from 1972.
6.
H. Dobbertin, Almost perfect nonlinear power functions on GF(2 n ): the Niho case. Inf. Comput. 151(1–2), 57–72 (1999) The author shows that two decimations conjectured by Niho to have 3-valued crosscorrelation for odd m give almost perfect nonlinear functions. This was an important step in order to later complete the proof of these conjectures in [16].
7.
H. Dobbertin, P. Felke, T. Helleseth, P. Rosendahl, Niho type cross-correlation functions via Dickson polynomials and Kloosterman sums. IEEE Trans. Inf. Theory 52(2), 613–627 (2006) Dickson polynomials were used for the first time to find the crosscorrelation between m-sequences. The paper also settled the correlation distribution of many new decimations with 4-valued crosscorrelation.
8.
H. Dobbertin, T. Helleseth, P. Vijay Kumar, H. Martinsen, Ternary m-sequences with three-valued crosscorrelation function: two new decimations of Welch and Niho type. IEEE Trans. Inf. Theory 47(4), 1473–1481 (2001) The importance of this paper is that is found the first new nonbinary decimations with three values since the constructions 30 years earlier by Trachtenberg.
9.
R. Gold, Maximal recursive sequences with 3-valued recursive cross-correlation functions. IEEE Trans. Inf. Theory 14(1), 154–156 (1968) This pioneering paper defined the Gold decimation and proved that it had a 3-valued crosscorrelation and determined the complete correlation distribution. This was the basis for the important Gold sequences.
10.
S.W. Golomb, Shift Register Sequences (Holden-Day, San Francisco, 1967) This is a classical book on linear and nonlinear recursions.
11.
S.W. Golomb, Theory of transformation groups of polynomials over GF(2) with applications to linear shift register sequences. Inf. Sci. 1(1), 87–109 (1968) The author states (without proof) that the crosscorrelation between binary m-sequences takes on at least three values. The Welch conjecture that two special decimations have 3-valued crosscorrelation was published here for the first time.
12.
T. Helleseth, Some results about the cross-correlation function between two maximal linear sequences. Discrete Math. 16(3), 209–232 (1976) This paper contains many basic results on the crosscorrelations of m-sequences. The first nonbinary decimation is found giving a four-valued crosscorrelation between two m-sequences. The distributions of several decimations are completely settled. The − 1 conjecture is stated in this paper.
13.
T. Helleseth, Crosscorrelation of m-sequences, exponential sums and Dickson polynomials. IEICE Trans. Fundamentals E93A(11), 2212–2219 (2010) Presents a survey on the crosscorrelation between binary m-sequences having at most 5-valued crosscorrelation with a focus on the many connections between exponential sums and Dickson polynomials.
14.
T. Helleseth, P.V. Kumar, Sequences with low correlation, in Handbook in Coding Theory, eds. by V.S. Pless, W.C. Huffman, ch. 21 (Elsevier Science B.V., Amsterdam, 1998), pp.1765–1853 This is a survey of sequences with low correlation that contains constructions and analysis of many important sequence families and some of their relations to coding theory.
15.
T. Helleseth, P. Rosendahl, New pairs of m-sequences with 4-level cross-correlation. Finite Fields Appl. 11(4), 674–683 (2005) This paper introduced new decimations with 4-valued cross correlation.
16.
H.D.L. Hollmann, Q. Xiang, A proof of the Welch and Niho conjectures on cross-correlations of binary m-sequences. Finite Fields Appl. 7(2), 253–286 (2001) This paper completed the proof of two decimations, for odd m, that were conjectured by Niho to lead to 3-valued crosscorrelation.
17.
A. Johansen, T. Helleseth, A family of m-sequences with five-valued cross correlation. IEEE Trans. Inf. Theory 55(2), 880–887 (2009) The distribution of the crosscorrelation of pairs of m-sequences with decimations giving five-valued crosscorrelation was found using techniques involving Dickson polynomials.
18.
A. Johansen, T. Helleseth, A. Kholosha, Further results on m-sequences with five-valued cross correlation. IEEE Trans. Inf. Theory 55(12), 5792–5802 (2009) This paper extends the results in [17] to other decimations with five-valued crosscorrelation. Some results depend on open conjectures on some exponential sums.
19.
T. Kasami, The weight enumerators for several classes of subcodes of the 2nd order binary Reed–Muller codes. Inf. Control 18(4), 369–394 (1971) The author determined the weight enumerator of some subcodes of the 2nd order Reed–Muller. A consequence of these results is a proof of the Kasami–Welch decimation leading to 3-valued crosscorrelation. This decimation was also proved by Welch (unpublished).
20.
D. Katz, Weil sums of binomials, three-level cross-correlation and a conjecture by Helleseth. J. Combin. Theory A 119(8), 1644–1659 (2012) The paper gives a solution of the conjecture of Helleseth that for n = 2 i and p = 2 the crosscorrelation takes on at least 4 values.
21.
G. Lachaud, J. Wolfmann, The weights of the orthogonals of the extended quadratic binary Goppa codes. IEEE Trans. Inf. Theory 36(3), 686–692 (1990) The paper shows that the Kloosterman sums takes on all possible values \(\equiv -1\pmod 4\) within its bound.
22.
J. Lahtonen, G. McGuire, H.N. Ward, Gold and Kasami–Welch functions, quadratic forms, and bent functions. Adv. Math. Commun. 1(2), 243–250 (2007) Provides a local result on C d (0) for the Kasami–Welch decimation.
23.
Y. Niho, Multi-valued Cross-Correlation Functions Between Two Maximal Linear Recursive Sequences, Ph.D. thesis, University of Southern California, Los Angeles, 1972 This thesis gave the complete crosscorrelation distribution of several decimations with 4-valued cross correlation. Furthermore, many conjectures on the cross correlation distribution of sequences with few values in the crosscorrelation were given. This Ph.D. thesis had a significant influence on later research on the crosscorrelation.
24.
D. Sarwate, M. Pursley, Crosscorrelation properties of pseudorandom and related sequences. Proc. IEEE, 68(5), 593–619 (1980) This is a classical and excellent survey of the crosscorrelation between m-sequences.
25.
H.M. Trachtenberg, On the Cross-Correlation Functions of Maximal Linear Recurring Sequences, Ph.D. thesis, University of Southern California, Los Angeles, 1970 The main result is the two families of decimation giving three-valued crosscorrelation. These are the only decimations that work for all nonbinary m-sequences.
26.
T. Zhang, S. Li, T. Feng, G. Ge, Some new results on the cross correlation of m-sequences. arXiv:1309.7734 [cs.IT] This recent paper gives new ternary decimations with four-valued crosscorrelation.
Metadaten
Titel
Open Problems on the Cross-correlation of m-Sequences
verfasst von
Tor Helleseth
Copyright-Jahr
2014
Buch
Open Problems in Mathematics and Computational Science

Print ISBN: 978-3-319-10682-3

Electronic ISBN: 978-3-319-10683-0

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-319-10683-0_8