CS Paper Radar

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

Xubin Hu, Shu Liu, Liming Ma, Chaoping Xing

cs.IT ·submitted 2026-09-15 16:23 UTC · v1
theory

Abstract

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.

Comment
21 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Construction of Multi-sequences With High Nonlinear Complexity via Narrow Ray Class Fields

cs.IT ·2026-09-09 ·Xiaofeng Liu, Jun Zhang, Fang-Wei Fu
similarity 0.72
Abstract

Nonlinear complexity is a fundamental criterion in the evaluation of pseudorandom sequences. The construction of multi-sequences with high nonlinear complexity is both theoretically and practically important in cryptography. Motivated by prior constructions of multi-sequences with high nonlinear complexity in [IEEE Trans. Inf. Theory, 60(10), 2014] and [IEEE Trans. Inf. Theory, 63(12), 2017], we provide a unified framework via narrow ray class fields and the cyclic descent introduced by Guruswami and Xing in [J. Combin. Theory Ser. A 129 (2015) ]. Then we can generate new multi-sequences with high nonlinear complexity over function fields with arbitrary genera.

0.22

The Walsh spectrum of the Dobbertin APN function

cs.IT math.CO ·2026-11-13 ·Lukas Kölsch
similarity 0.61
Abstract · 27 pages

APN functions yield the best resistance to differential attacks when used as a building block of a block cipher. APN functions induced by monomials over finite fields have received particular interest both for their simplicity and their unique properties. A key property of APN functions is their linearity, which has been determined for all known APN monomials outside of the Dobbertin APN monomials. In this paper, we close this gap and determine the complete Walsh spectrum and in particular the linearity of the Dobbertin APN monomial, answering a problem that has been open for more than 20 years. Using known connections, our result also yields the asymptotically largest Sidon sets in elementary abelian $2$-groups constructed so far as well as binary linear codes of minimum distance $5$ that are almost optimal.

0.25

Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size

cs.IT cs.DSmath.CO ·2026-09-04 ·Neehar Verma, Camilla Hollanti, Razane Tajeddine
theory similarity 0.59
Abstract

We study linear codes for insertion and deletion (insdel) errors through the lens of evaluation codes. We develop a general framework for analyzing random puncturings of evaluation codes, where the edit distance is controlled by only the size of the evaluation domain and the maximum number of zeros of a nonzero function in the underlying function space. Our proof generalizes the results of Con, Guo, Li, and Zhang (ICALP 2025), and simultaneously simplifies their arguments by avoiding an in-depth analysis of longest common subsequences. We demonstrate the applicability of our core theorem by instantiating it with random puncturings of Reed--Muller codes. We then recover the result that random Reed--Solomon codes approach the half-Singleton bound over linear-sized fields while also improving the dependence on the additive gap $\varepsilon$ from $2^{O(1/\varepsilon^2)}$ to $2^{O(1/\varepsilon)}$. Finally, by applying the framework to algebraic geometry codes arising from asymptotically good towers of function fields, we show that there exist randomized families of structured linear codes over constant-sized fields that approach the half-Singleton bound.

0.34

Good rational functions up to degree six

cs.IT math.NT ·2026-11-02 ·Anuvrat Jaindungarwal, Divyesh Vaghasiya
similarity 0.59
Abstract · 14 pages, 1 table

Locally recoverable codes (LRCs) are fundamental to the architecture of modern distributed storage systems. The Tamo-Barg construction of optimal LRCs was revolutionized by the introduction of good polynomials, which group evaluation points into local recovery sets. However, polynomial constructions are constrained by their inherently large Galois groups, which limit the number of totally split rational places. Recent advances have generalized this paradigm to good rational functions, which leverage the geometry of the projective line to achieve minimal Galois groups and subsequently codes with greater length. In this paper, we complete the classification of good rational functions of degree up to $6$ in characteristic $2$. By embedding the problem into algebraic function field theory, we explicitly determine the minimal arithmetic and geometric Galois groups for these low degrees. Furthermore, we move beyond asymptotic Hasse-Weil estimates by proving that the exact number of totally split places over extension fields obeys a linear recurring sequence (LRS). This gives an efficient method for computing the exact lengths and dimensions of the corresponding optimal LRCs and, in many cases, yields parameters beyond those obtainable from good polynomials.

0.24

Construction of Ternary Minimal Linear Codes with Dimension $n+r$ Via Index Codes and The Access Structures of Their Dual Codes

cs.IT ·2026-11-18 ·Haibo Liu, Qunying Liao
similarity 0.58
Abstract

Recently, minimal linear codes have been extensively studied due to their applications in secret sharing schemes, secure two-party computations, and so on. Constructing minimal linear codes violating the Ashikhmin-Barg condition and then determining their weight distributions have been interesting in coding theory and cryptography. In this paper, we present a general construction of ternary linear codes of dimension $n+r$, where $n$ and $r$ are positive integers, and derive a necessary and sufficient condition for the resulting codes to be minimal. We first specialize the construction using index codes arising from spreads, with three classes of index codes satisfying the minimality condition, we obtain the parameters and weight enumerators of the corresponding minimal codes, and determine the access structures type of the secret-sharing schemes based on their dual codes. By the index codes from Krawtchouk polynomials, we then give a second specialization of the construction, with a class of index codes satisfying the minimality condition, we obtain the parameters of the resulting minimal codes, and determine the access-structure type of the secret-sharing scheme based on each dual code. Several constructed families of minimal codes violate the Ashikhmin-Barg condition.

0.19

New linear codes over GF(7), GF(8) and GF(9) from quasi-cyclic codes and Construction X

cs.IT ·2026-11-10 ·Sebastian Cochinescu
theory similarity 0.58
Abstract · 12 pages, 1 table. Ancillary files: verification program and generator matrices. v2: three more codes and two more derived codes added. Code…

We present linear codes with parameters [88,8,64]_7, [90,8,65]_7, [98,7,75]_8, [97,8,72]_8, [44,7,31]_9, [97,8,71]_7, [85,6,67]_8 and [78,8,56]_7. Each has a minimum distance one larger than the lower bound listed in Grassl's tables of best known linear codes; codes with parameters [89,8,64]_7, [96,8,71]_8, [95,8,70]_8, [94,8,69]_8, [77,8,55]_7 and [86,6,68]_8 follow. Seven of the eight codes are obtained from a quasi-cyclic code and a vector that is constant on each block, by Construction X with a repetition code. The remaining one, the [90,8,65]_7 code, is obtained from the first by appending two coordinates. The parameters and all weight counts were obtained by exhaustive enumeration, and a short program that repeats these computations is included.

0.12

Euclidean Hulls of Double Cyclic Codes of Arbitrary Block Lengths

cs.IT ·2026-11-10 ·Awadhesh Kumar Shukla, Om Prakash Pandey, Sachin Pathak, Ashish Upadhyay
similarity 0.58
Abstract

Gao et al. \cite{GWF23} recently explored the Euclidean hulls of double cyclic codes over $\mathbb{Z}_2$. While they found answers for non-separable codes with coprime lengths ($\gcd(r, s) = 1$), the non-coprime case ($\gcd(r, s) > 1$) remained an open question. This paper completely solves that problem for all possible block lengths. We calculate the exact generator polynomials for the hull and show the precise conditions needed for a non-separable code to turn into a separable one. Using this, we show how to construct non-separable LCD codes. We also include several numerical examples to confirm our findings.

0.11

On cryptographically non-linear all-or-nothing transforms

cs.CR ·2026-11-12 ·Anantajeet Devaraj, Navid Nasr Esfahani
unusual similarity 0.58
Abstract

An unconditionally secure $(t, s, v)$-all-or-nothing transform (AONT) is a bijection from $s$ input elements to $s$ output elements over an alphabet of size $v$, such that given any $s - t$ output elements, no information can be obtained about any $t$ input elements. While linear AONTs have been extensively studied, comparatively little is known about the existence of non-linear AONTs. In this paper, we investigate unconditionally secure cryptographically non-linear $(t, s, v)$-AONTs, distinguishing between non-additivity, non-affinity, and cryptographic non-linearity. To achieve this, we first present a computational method for enumerating general AONTs focusing on the case $(t, 3, 3)$-AONTs for $t = 1 and 2$, establishing the existence of non-additive AONTs. We then introduce a general construction of non-additive AONTs from linear ones using coordinate-wise symbol permutations. We measure the non-linearity of the AONT instances generated from this construction, using differential $Δ_F$-uniformity and Walsh magnitude. Finally, we establish theoretical conditions under which $Δ_F$-uniformity is reduced and present statistical results examining the non-linearity of AONTs obtained through our construction.

0.37