PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-sequences with large linear and error linear complexity from function fields

Xubin Hu, Shu Liu, Liming Ma, Chaoping Xing

arXiv:2609.17381v1cs.ITmath.IT

TL;DR

Stream-cipher security motivates multi-sequences with high linear and error linear complexity, but existing constructions offer limited parameter flexibility. The paper develops a function-field framework and applies it to construct new multi-sequences and quasi-cyclic algebraic geometric codes.

  • Problem

    Stream-cipher applications use linear and ε-error linear complexity to assess multi-sequence unpredictability and stability, while existing constructions offer limited flexibility in parameters such as period and dimension.

    Source: §I · pp. 1–2

  • Method

    The paper constructs periodic multi-sequences by evaluating functions at rational places arranged in automorphism orbits, with functions chosen from Riemann–Roch spaces.

    Source: A. Main Results and Techniques · pp. 2–3

  • Results

    The framework yields multi-sequences with large linear and ε-error linear complexity and is applied to maximal function fields to produce new sequences with varied parameters.

    Source: A. Main Results and Techniques · p. 2, §III · pp. 7–8, A. Cyclotomic function fields · pp. 11–12

  • Takeaways & Limitations

    The function-field construction also extends to quasi-cyclic algebraic geometric codes by using Riemann–Roch spaces for their evaluation functions.

    Source: A. Main Results and Techniques · p. 3

Abstract

from arXiv · show

The linear complexity and the error linear complexity of multi-sequences are measures for security in stream ciphers. In this manuscript, we present a general framework for constructing periodic multi-sequences via function fields. We prove that the constructed multi-sequences possess both large linear complexity and large error linear complexity. We apply this framework of constructing multi-sequences to various maximal function fields and we obtain many new multi-sequences with various lengths and dimensions. As a byproduct, we adopt this idea and produce many new quasi-cyclic algebraic geometric codes as well.

I. INTRODUCTION

The introduction motivates flexible constructions of multi-sequences with high linear and error linear complexity, then outlines a function-field framework and its applications to sequences and quasi-cyclic codes. It also previews the paper’s background and section organization.

I. INTRODUCTION

  • Stream-cipher security motivates measuring sequence unpredictability and stability, while prior constructions leave limited flexibility in period, dimension, and complexity parameters.The introduction identifies linear complexity and ε-error linear complexity as relevant measures and calls for broader parameter choices.Source: §I · pp. 1–2

A. Main Results and Techniques

  • The proposed function-field framework constructs periodic multi-sequences with high linear and ε-error linear complexity, using automorphism-related evaluation places and functions from Riemann–Roch spaces.The evaluation places are arranged in long automorphism orbits, and the divisor is fixed by the automorphism and avoids those places.Source: A. Main Results and Techniques · pp. 2–3
  • The framework is also applied to maximal function fields to obtain new multi-sequences, and its Riemann–Roch-space idea is adapted to quasi-cyclic algebraic geometric codes.For the codes, L(G) supplies the functions evaluated at the selected places.Source: A. Main Results and Techniques · pp. 2–3

B. Organization of this paper

  • The paper proceeds from function-field and multi-sequence preliminaries to the general construction, then treats four function-field families and quasi-cyclic codes.The named families are cyclotomic, second-largest-genus maximal, Suzuki, and Giulietti–Korchmáros function fields.Source: B. Organization of this paper · p. 3

II. PRELIMINARIES

  • The preliminaries collect function-field extension theory and the definitions of multi-sequences, linear complexity, and ε-error linear complexity.They direct readers to references for fuller background on these topics.Source: §II · p. 4

A. Algebraic function fields

  • An algebraic function field over Fq is presented as a finite algebraic extension of the rational function field, with Fq algebraically closed in the extension.The passage also introduces places and valuation rings.Source: A. Algebraic function fields · p. 4

B. Extension theory of function fields

This section reviews extension-theory tools for function fields, including the Hurwitz genus formula and a criterion for complete splitting in an intermediate field.

B. Extension theory of function fields

  • The Hurwitz genus formula relates the genera of a finite Galois extension and its base field through the degree and different divisor.The passage introduces the different divisor using different exponents at places above places of the base field.Source: B. Extension theory of function fields · p. 5
  • For an unramified place in an abelian extension, the decomposition-group map to the residue-field Galois group is an isomorphism, defining the Frobenius symbol.In an abelian extension, the symbol is independent of the choice of place above the base place and is called its Artin symbol.Source: B. Extension theory of function fields · p. 5
  • An unramified place splits completely in an intermediate field exactly when its Artin symbol satisfies the stated splitting criterion.The lemma is presented as a tool for determining complete splitting.Source: B. Extension theory of function fields · p. 5

C. Multi-sequences and their linear complexity

The section defines periodic multi-sequences over finite fields and gives their linear and error linear complexity measures.

C. Multi-sequences and their linear complexity

  • A periodic sequence over Fq repeats with a fixed period, and a finite set of such sequences forms a multi-sequence whose dimension is the set’s size.The sequence is represented by one period of finite length.Source: C. Multi-sequences and their linear… · p. 5
  • Linear complexity is the least recurrence order that simultaneously generates every sequence in the multi-sequence.The associated polynomial is called its generating polynomial.Source: C. Multi-sequences and their linear… · p. 6
  • ε-error linear complexity is the minimum linear complexity after changing at most ε terms, and it cannot increase as ε grows.The definition considers changes to the multi-sequence’s array of terms.Source: C. Multi-sequences and their linear… · p. 6

III. A GENERAL FRAMEWORK OF MULTI-SEQUENCES VIA FUNCTION FIELDS

The section constructs periodic multi-sequences by evaluating functions along automorphism orbits of rational places, then proves conditions for large linear complexity and ε-error linear complexity.

III. A GENERAL FRAMEWORK OF MULTI-SEQUENCES VIA FUNCTION FIELDS

  • The construction requires a σ-invariant divisor G disjoint from the selected orbit places, with deg(G) ≥ 2g−1.The places are arranged in σ-orbits above rational places that split completely in the extension over the fixed subfield.Source: §III · p. 6
  • A function f ∈ L(G + R) \ L(G) supplies the orbit evaluations that form the periodic multi-sequence.The section establishes such a nonzero function using the Riemann–Roch theorem and specifies its pole divisor as R + G′.Source: §III · pp. 6–7
  • Under the stated genus and divisor bounds, the constructed periodic multi-sequence has linear complexity m.The construction uses an automorphism of order m and ℓ+1 completely split rational places of the fixed subfield; the sequence has dimension ℓ and period m.Source: §III · pp. 6–7
  • Any δ sequences in S form a multi-sequence of linear complexity m when δ ≥ 1 + (deg(G) + 1)/m.Source: §III · p. 7
  • For ε ≤ ℓ−δ0, the ε-error linear complexity is m; for ε ≤ ℓ−δ0 + 1, it is at least −1 + (ℓm−deg(G))/(ℓ−δ0 + 2).These bounds apply when 2g−1 ≤ deg(G) ≤ (ℓ−2)m−ℓ+δ0−3, with δ0 = 1+⌈(deg(G)+1)/m⌉.Source: §III · p. 8

IV. MULTI-SEQUENCES FROM VARIOUS FUNCTION FIELDS

The section applies the framework to several function-field families to construct multi-sequences with large linear and error linear complexity.

IV. MULTI-SEQUENCES FROM VARIOUS FUNCTION FIELDS

  • The constructions use subfields of cyclotomic function fields, the maximal function field with second largest genus, Suzuki function fields, and the Giulietti–Korchmáros function field.Source: §IV · p. 10

A. Cyclotomic function fields

The cyclotomic-function-field construction yields multi-sequences with dimension, period, and linear complexity specified in Proposition IV.4. Under two divisibility cases, the paper gives bounds on their ε-error linear complexity.

A. Cyclotomic function fields

  • The fixed subfield M has at least q + 1 rational places of K that split completely in M/K.Its extension degree is (q^d + 1)/(q + 1), and the place P is the unique ramified place, totally and tamely ramified.Source: A. Cyclotomic function fields · p. 11
  • Proposition IV.4 constructs a multi-sequence over Fq2 with dimension q, period ψ(d), and linear complexity ψ(d), where ψ(d) = (q^d + 1)/(q + 1).The proposition assumes q ≥ 5 is a prime power and odd 3 ≤ d ≤ q.Source: A. Cyclotomic function fields · p. 11
  • When d divides (d − 2)ψ(d), the ε-error linear complexity equals ψ(d) for ε ≤ q − d and has the stated lower bounds for ε ≤ q − d + 1 and q − d + 2.The latter bounds are ψ(d) − 1 and ψ(d) − 1 − ψ(d)/(q − d + 3), respectively.Source: A. Cyclotomic function fields · p. 12
  • When d does not divide (d − 2)ψ(d), the ε-error linear complexity equals ψ(d) for ε ≤ q − d + 1, with lower bounds at the next two thresholds.Those bounds are ψ(d) − 1 − (ψ(d) + 1)/(q − d + 3) for ε ≤ q − d + 2 and ψ(d) − 1 − (2ψ(d) − 1)/(q − d + 4) for ε ≤ q − d + 3.Source: A. Cyclotomic function fields · p. 12
  • For d = 3, M is isomorphic to the Hermitian function field, and the Proposition IV.6 bounds are slightly better than those in [34, Theorem 3.7].The paper describes this construction as a generalization of the Hermitian-function-field construction [34, Section III.C].Source: A. Cyclotomic function fields · p. 13

B. Maximal function fields with the second largest genus

The section introduces constructions using maximal function fields over Fq2 with the second largest genus. It organizes the discussion by characteristic.

B. Maximal function fields with the second largest genus

  • The construction of multi-sequences is presented separately according to the characteristic of the maximal function fields.The fields considered are over Fq2 and have the second largest genus.Source: B. Maximal function fields with the… · p. 13
  • The section’s stated scope is explicit construction of multi-sequences via these maximal function fields over Fq2.The later discussion is divided into even- and odd-characteristic cases.Source: B. Maximal function fields with the… · p. 13
  • For q = 2^s ≥ 4, the section turns to a maximal function field with the second largest genus.The passage introduces the field by a displayed expression but does not state its form in the supplied text.Source: 1) The even characteristic case · p. 13

1) The even characteristic case:

In even characteristic, the paper constructs a multi-sequence from a maximal function field with the second largest genus and derives ε-error linear-complexity bounds. The construction applies for q ≥ 16 a power of 2.

1) The even characteristic case:

  • The underlying maximal function field has genus g(Y2) = q(q − 2)/4 = ⌊(q − 1)^2/4⌋.The section also states that a set of rational places splits into (q^2 − q)/4 pairwise disjoint orbits.Source: 1) The even characteristic case · pp. 13–14
  • For q ≥ 16 a power of 2, a multi-sequence over Fq2 has dimension (q^2 − q − 4)/4, period 2(q + 1), and linear complexity 2(q + 1).This is Theorem IV.8’s construction.Source: 1) The even characteristic case · p. 14
  • For q ≥ 16 a power of 2, its ε-error linear complexity is 2(q + 1) when ε ≤ (q^2 − 2q − 8)/4, and is at least 2q + 1 when ε ≤ (q^2 − 2q)/4.The bounds are stated for the multi-sequence defined in Theorem IV.8’s proof.Source: 1) The even characteristic case · p. 14

2) The odd characteristic case:

In odd characteristic, the paper constructs a periodic multi-sequence from a maximal function field with the second largest genus. It gives its dimension, period, linear complexity, and ε-error bounds.

2) The odd characteristic case:

  • The construction uses a function field X2 over Fq2 with genus (q − 1)^2/4 and 1 + q(q^2 + 1)/2 rational places.The cited passage identifies X2 as the unique maximal function field over Fq2 with the second largest genus.Source: 2) The odd characteristic case · p. 14
  • For q ≥ p^2 a power of an odd prime p, a periodic multi-sequence over Fq2 has dimension q(q − 1)/p − 1, period p(q + 1)/2, and linear complexity p(q + 1)/2.This is Theorem IV.10’s construction.Source: 2) The odd characteristic case · p. 15
  • For S, the ε-error linear complexity is p(q + 1)/2 when ε ⩽ q(q − 2)/p − 2, and at least p(q + 1)/2 − 1 when ε ⩽ q(q − 2)/p.Source: 2) The odd characteristic case · p. 15

C. The Suzuki function field

The Suzuki function field yields periodic multi-sequences with dimension and linear complexity q−1 and period q−1. Their ε-error linear complexity remains high across the stated ranges of ε.

C. The Suzuki function field

  • The Suzuki field has genus q0(q−1) and q²+1 rational places, including the common pole P∞ and q² common zeros Pμ,ν.Its automorphism group over F_q is Sz(q).Source: C. The Suzuki function field · p. 16
  • For q0 ≥ 8 a power of 2 and q = 2q_0^2, the construction gives a multi-sequence over F_q with dimension, period, and linear complexity all q−1.The construction uses G = (2g(F)−1)P∞ and orbits of length q−1 under an automorphism.Source: C. The Suzuki function field · p. 16
  • The construction uses an automorphism of order q−1 that fixes P∞ and P0,0; the remaining rational places split into q+1 orbits of length q−1.The divisor G is chosen as (2g(F)−1)P∞.Source: C. The Suzuki function field · p. 16
  • The ε-error linear complexity is q−1 if ε ≤ q−2q0−1, at least q−3 if ε ≤ q−2q0, and at least q−4 if ε ≤ q−2q0+1.The bounds are stated for the multi-sequence constructed in this subsection.Source: C. The Suzuki function field · p. 17

D. The Giulietti–Korchm´aros function field

The Giulietti–Korchmáros function field produces a multi-sequence with period and linear complexity q²−q+1. The paper also establishes ε-error linear-complexity bounds for this construction.

D. The Giulietti–Korchmáros function field

  • The field is maximal over F_{q^6}, has genus (q^5−2q^3+q²)/2, and has q^8−q^6+q^5+1 rational places.Its automorphism group contains a cyclic normal subgroup of order q²−q+1.Source: D. The Giulietti–Korchm´aros function… · p. 17
  • The sets F_c partition the rational places other than P∞, and each contains exactly q³ rational places when c ∈ Γ ∪ {0}.The number of distinct sets F_c is q^5−q^3+q².Source: D. The Giulietti–Korchm´aros function… · p. 18
  • For q ≥ 3 a prime power, the construction gives a multi-sequence over F_{q^6} with dimension q^3(q+1)^2(q−1)−1, period q²−q+1, and linear complexity q²−q+1.The proof uses a cyclic automorphism group of order q²−q+1 and a divisor invariant under its generator.Source: D. The Giulietti–Korchm´aros function… · p. 18
  • The ε-error linear complexity is q²−q+1 if ε ≤ q^6+q^5−q^4−2q^3−q²+2q−1, and at least q²−q if ε ≤ q^6+q^5−q^4−2q^3−q²+2q+1.These bounds apply to the multi-sequence constructed in the proof of Theorem IV.15.Source: D. The Giulietti–Korchm´aros function… · p. 18

V. EXPLICIT CONSTRUCTION OF QUASI-CYCLIC CODES VIA FUNCTION FIELDS

The section constructs quasi-cyclic algebraic-geometric codes using automorphisms of function fields. It gives a general parameter theorem and explicit code families from cyclotomic, maximal, Suzuki, and Giulietti–Korchmáros function fields.

V. EXPLICIT CONSTRUCTION OF QUASI-CYCLIC CODES VIA FUNCTION FIELDS

  • An automorphism-invariant divisor and distinct rational-place orbits yield a q-ary quasi-cyclic code of length ℓm and index ℓ, with dimension deg(G)−g+1 and minimum distance at least ℓm−deg(G).The theorem assumes 2g−1 ≤ deg(G) < ℓm and that the evaluation places lie outside Supp(G).Source: §V · p. 19
  • For q ≥ 4 and odd 3 ≤ d ≤ q−2, a q²-ary quasi-cyclic code of index q+1 has parameters [qd+1, td+1−(d−2)(ψ(d)−1)/2, ≥qd+1−td].Here ψ(d)=(qd+1)/(q+1), with (d−2)(ψ(d)−1) ≤ td ≤ qd.Source: §V · p. 19
  • For q a prime power with q ≥ p² and m dividing p(q+1)/2, the construction gives a q²-ary quasi-cyclic code of index (q²−q)/(2m) and length q(q²−1)/2.Its dimension is k−⌊(q−1)²/4⌋+1 and minimum distance is at least q(q²−1)/2−k, for (q−1)²/2 ≤ k < q(q²−1)/2.Source: §V · p. 20
  • The Suzuki function field gives a q-ary quasi-cyclic code of index q+1 and length q²−1, with dimension k−q0(q−1)+1 and minimum distance at least (q²−1)−k.The stated range is 2q0−2q0−1 ≤ k ≤ q²−2.Source: §V · p. 20
  • The Giulietti–Korchmáros function field gives a q^6-ary quasi-cyclic code of index q³(q+1)²(q−1) and length q³(q³+1)(q²−1).Its dimension is k+1−(q^5−2q³+q²)/2 and minimum distance is at least q³(q³+1)(q²−1)−k.Source: §V · p. 20
Loading 2609.17381v1…