MDS codes have garnered significant attention due to their wide applications in practice. To date, most known MDS codes are equivalent to Reed-Solomon codes. The construction of non-Reed-Solomon (non-RS) type MDS codes has emerged as an intriguing and important problem in both coding theory and finite geometry. Although some constructions of non-RS type MDS codes have been presented in the literature, the parameters of these MDS codes remain subject to strict constraints. In this paper, we introduce a general framework of constructing [n,k] MDS codes using the idea of selecting a suitable set of evaluation polynomials and a set of evaluation points such that all nonzero polynomials have at mostk–1 zeros in the evaluation set. Moreover, these MDS codes can be proved to be non-Reed-Solomon by computing their Schur squares. Furthermore, several explicit constructions of non-RS MDS codes are given by converting to combinatorial problems. As a result, new families of non-RS MDS codes with much more flexible lengths can be obtained and most of them are not covered by the known results.

Code-based Distributed Matrix Multiplication (DMM) has been widely studied as an effective method for large-scale matrix computations in distributed systems. Two central challenges in code-based DMM are minimizing the communication cost and reducing the recovery threshold—the minimum number of worker nodes required to successfully recover the matrix multiplication. Several Reed-Solomon (RS)-based schemes, including Polynomial, MatDot, and PolyDot codes, have been proposed; however, their applicability is constrained by the size of the underlying finite field, limiting the number of usable worker nodes. Algebraic geometry (AG) codes, as a generalization of RS codes, overcome this limitation by enabling longer code lengths over small fields. Prior work has generalized Polynomial and MatDot codes to AG codes, achieving recovery thresholds that increase additively with the genus of the underlying algebraic function field. However, extending PolyDot codes to AG settings with a similar additive increase has remained an open challenge, due to the more complex structure of functions on algebraic curves compared to univariate polynomials. In this work, we generalize RS-based Polynomial, MatDot, and PolyDot codes under a unified AG framework based on local expansions of functions. Our main contribution is the first construction of AG-based PolyDot codes with recovery thresholds that scale additively with the genus. Moreover, our AG-based Polynomial and MatDot codes achieve better recovery thresholds than existing AG-based DMM schemes, while maintaining comparable communication costs. A key innovation of our construction is a novel basis for the Riemann–Roch space, derived from local expansions, which avoids the cancellation issues caused by using non-gap numbers in prior constructions.

Reverse multiplication-friendly embeddings have played a crucial role in secure multiparty computation and zero-knowledge proofs. In this work, we generalize the notion of RMFEs todegree-DRMFEs. We present a general construction of degree-DRMFEs by generalizing the ideas on algebraic geometry used to construct traditional degree-2 RMFEs. Furthermore, our theory is given in a unified manner for general Galois rings, which include both rings of the form Zpkand fields like Fpk, which have been treated separately in prior works. We present multiple concrete sets of parameters for degree-DRMFEs (includingD= 2), which can be useful for future works. In the recent work of (Cheon & Lee, Eurocrypt’22), the concept of adegree-D packing methodwas formally introduced, which captures the idea of embedding multiple elements of a smaller ring into a larger ring. We show that the generalized notion of RMFEs todegree-D RMFEswhich, in spite of being “more algebraic” than packing methods, turn out to be essentially equivalent. Thus, our constructions of degree-DRMFEs are also degree-Dpacking methods.

In the realm of modern digital communication, cryptography, and signal processing, binary sequences with good correlation properties play a pivotal role. In the literature, considerable efforts have been dedicated to constructing good binary sequences of various lengths. As a consequence, numerous constructions of good binary sequences have been put forward. However, the majority of known constructions leverage the multiplicative cyclic group structure of finite fields Fpn, wherepis a prime andnis a positive integer. Recently, the authors made use of the cyclic group structure of all rational places of the rational function field over the finite field Fpn, and firstly constructed good binary sequences of lengthpn+ 1 via cyclotomic function fields over Fpnfor any primep[8], [10]. This approach has paved a new way for constructing good binary sequences. Motivated by the above constructions, we exploit the cyclic group structure of rational points of elliptic curves to design a family of binary sequences of length 2n+1+twith low correlation for many given integers |t| ⩽ 2(n+2)/2. Specifically, for any positive integerdwith gcd(d; 2n+1+t) = 1, we introduce a novel family of binary sequences of length 2n+1+t, sizeqd−1− 1, correlation bounded by (2d+ 1) · 2(n+2)/2+ |t|, and large linear complexity via elliptic curves.

Encoding and decoding of Reed-Muller codes have been a major research topic in coding and theoretical computer science communities. Despite of the fact that there have been numerous encoding and decoding algorithms in the literature, most of them are not quasi-linear time algorithms for arbitrary order Reed-Muller codes. Under the decoding framework proposed by Pellikaan and Wu (IEEE TIT, 2004) which regards Reed-Muller codes as subfield subcodes of Reed-Solomon codes, we propose a new decoding algorithm for Reed-Muller codes that improves previous polynomial decoding complexity to quasilinear complexity. Our new decoding algorithm includes multivariate multipoint evaluation (MPE) and interpolation under a new basis of the multivariate polynomial space as two main steps. We show that the MPE and interpolation at certain multipoint sets can be performed in quasi-linear time as well. Our approach is based on a well-known transform between univariate polynomials and multivariate polynomials. We make use of the key fact that the transformation matrix between univariate polynomials and multivariate polynomials is sparse. Due to sparsity, MPE and interpolation of multivariate polynomials and decoding of Reed-Muller codes can be reduced to MPE and interpolation of univariate polynomials and decoding of Reed-Solomon codes without extra cost respectively, i.e, the complexity of MPE and interpolation of multivariate polynomials (and, respectively, decoding of Reed-Muller codes) is dominated by that of MPE and interpolation of univariate polynomials (and, respectively, decoding of Reed-Solomon codes). As a result of this reduction, we obtain our quasi-linear time algorithms.

Coded Distributed Matrix Multiplication (CDMM) is a distributed matrix multiplication (DMM) for large-scale matrices through a coding scheme such that anyRworker nodes among allNworker nodes can recover the final product, whereNcorresponds to the length of the code andR≤Nis called the recovery threshold. The state-of-art CDMM schemes, such as EP codes for Single DMM and GCSA codes for batch DMM, are defined over a Galois field GF(q) of sizeq≥N. These are inefficient for small Galois fields such as GF(2) and the integer residue ring Zpℓdue to the lack of invertible elements for interpolation. DMM over Zpℓ(such as Z264) is well-motivated in practice due to their direct compatibility with hardware. In this work, we construct efficient CDMM over the Galois ring GR(pℓ,d) which is an extension ring over Zpℓof degreed, particularly, GR(p, d) = GF(pd) is the Galois field and GR(pℓ, 1) = Zpℓ. We first give a general CDMM framework for the batch ofnmatrix multiplications via the famous RMFE (Cascudo et al. Crypto’18). Compared with GCSA, our construction has a smaller recovery threshold by a factor of 1/n. Next, we optimize EP codes via batch preprocessing of the input matrices. We give two types of Single CDMM, which can achieve almost the same performance as EP codes over a Galois field with sizeq≥N. Finally, we present the experimental analysis of our CDMM on Galois rings.

Fast encoding and decoding of codes have always been an important topic in coding theory as well as complexity theory. Although encoding is easier than decoding in general, designing an encoding algorithm of codes of lengthNwith quasi-linear complexityO(NlogN) is not an easy task. Despite of the fact that algebraic geometry codes (AG codes) were discovered in the early 1980s, encoding algorithms of algebraic geometry codes with quasi-linear complexityO(NlogN) have not been found except for the simplest algebraic geometry codes–Reed-Solomon codes. The best-known encoding algorithm of algebraic geometry codes based on a class of plane curves has quasi-linear complexity at leastO(Nlog2N) (Beelen et al. IEEE Trans. Inf. Theory 2021). In this paper, we design an encoding algorithm for algebraic geometry codes with quasi-linear complexityO(NlogN). Moreover, for these fast encodable AG codes, the inverse of encoding, that is, interpolating the message function from the corresponding codeword, can be computed with the same complexityO(NlogN). Our algorithms are applicable to a large class of algebraic geometry codes based on both plane and non-plane curves, including Kummer extensions, Artin-Schreier extensions, and Hermitian field towers.

Gabidulin codes, serving as the rank-metric counterpart of Reed-Solomon codes, constitute an important class of maximum rank distance (MRD) codes. However, unlike the fruitful positive results about the list decoding of Reed-Solomon codes, results concerning the list decodability of Gabidulin codes in the rank metric are all negative so far. For example, in contrast to Reed-Solomon codes, which are always list decodable up to the Johnson bound in the Hamming metric, Raviv and Wachter-Zeh (IEEE TIT, 2016 and 2017) constructed a class of Gabidulin codes that are not even combinatorially list decodable beyond the unique decoding radius in the rank metric. Proving the existence of Gabidulin codes with good combinatorial list decodability in the rank metric has remained a long-standing open problem. In this paper, we resolve the aforementioned open problem by showing that, with high probability, random Gabidulin codes over sufficiently large alphabets attain the optimal generalized Singleton bound for list decoding in the rank metric. In particular, they achieve list decoding capacity in the rank metric. Our work is significantly influenced by the recent break-throughs in the combinatorial list decodability of Reed-Solomon codes, especially the work by Brakensiek, Gopi, and Makam (STOC 2023). Our major conceptual and technical contributions, which may hold independent interest, consist of the following: (1) We initiate the study of “higher order MRD codes” and provide a novel unified theory, which runs parallel to the theory of “higher order MDS codes” developed by Brakensiek, Gopi, and Makam. (2) We prove a natural analog of the GM-MDS theorem, proven by Lovett (FOCS 2018) and Yildiz and Hassibi (IEEE TIT, 2019), which we call the GM-MRD theorem. In particular, our GMMRD theorem for Gabidulin codes is strictly stronger than the GM-MDS theorem for Gabidulin codes proven by Yildiz and Hassibi.

Guruswami and Wootters first provided a decoding framework for repairing Reed-Solomon codes. There is a series of work after Guruswami-Wootters' repairing scheme. In particular, based on this framework a repairing scheme achieving the cut-set bound was presented by Tamo, Ye and Barg. Guruswami-Wootters' repairing scheme can be modified so that we require downloading less data, i.e., less communication bandwidth. We illustrate our improvement by two examples given in the pioneer paper by Guruswami and Wootters. These examples show that our repairing scheme can save bandwidth$(1-R)^{2}n$and$(1-2R)n$over the base field, respectively, where$R$is the code rate and$n$is the code length.

Determining the largest size, or equivalently finding the lowest redundancy, of q-ary codes for given length and minimum distance is one of the central and fundamental problems in coding theory. Inspired by the construction of Varshamov-Tenengolts (VT for short) codes via check-sums, we provide an explicit construction of nonlinear codes with lower redundancy than linear codes under the same length and minimum distance. Similar to the VT codes, our construction works well for small distance (or even constant distance). Furthermore, we design$O(n\log^{4}n)$bit operations decoding algorithms for both erasures and adversarial errors, where$n$is the code length.

Locally repairable codes have been extensively investigated due to practical applications in distributed and cloud storage systems in recent years. However, not much work on asymptotic behavior of locally repairable codes has been done. In particular, there is few result on constructive lower bound of asymptotic behavior of locally repairable codes with multiple recovering sets. In this paper, we construct some families of asymptotically good locally repairable codes with multiple recovering sets via automorphism groups of function fields of the Garcia-Stichtenoth towers. The main advantage of our construction is to allow more flexibility of localities.

The Fast Fourier Transform (FFT) over a finite field 𝔽q computes evaluations of a given polynomial of degree less than n at a specifically chosen set of n distinct evaluation points in 𝔽q. If q or q — 1 is a smooth number, then the divide-and-conquer approach leads to the fastest known FFT algorithms. Depending on the type of group that the set of evaluation points forms, these algorithms are classified as multiplicative (Math of Comp. 1965) and additive (FOCS 2014) FFT algorithms. In this work, we provide a unified framework for FFT algorithms that include both multiplicative and additive FFT algorithms as special cases, and beyond: our framework also works when q + 1 is smooth, while all known results require q or q — 1 to be smooth. For the new case where q + 1 is smooth (this new case was not considered before in literature as far as we know), we show that if n is a divisor of q + 1 that is B-smooth for a real B > 0, then our FFT needs O(Bn log n) arithmetic operations in 𝔽q. Our unified framework is a natural consequence of introducing the algebraic function fields into the study of FFT.

A locally repairable code is called Singleton-optimal if it achieves the Singleton-type bound. Such codes are of great theoretic interest in the study of locally repairable codes. One of the major problems in this topic is to determine the maximum length of aq-ary Singleton-optimal locally repairable code with fixed locality and minimum distance. Unlike classical MDS codes, the maximum length of Singleton-optimal locally repairable codes is very sensitive to the minimum distance and locality. Thus, determining the maximum length of the Singleton-optimal locally repairable codes is more challenging and complicated. In literature, many efforts are paid to solve this problem especially for small distance and locality regime. Moreover, most of works also requires that (r+ 1)|nand the recovery sets are disjoint so as to simplify the argument,whereris locality andnis the code length. In this paper, we derive some upper bounds on the maximum length of Singleton-optimal locally repairable codes with minimum distance 5, 6 and 7 without the constraint that (r+ 1)|nand the recovery sets are disjoint.It turns out that even without this constraint we still obtain better upper bounds for codes with small locality and distance compared to known results. Furthermore, based on our upper bounds for codes with small distance and locality, we propose the propagation rule to derive some upper bounds for codes with relatively large distance and locality assuming that (r+1)|nand recovery sets are disjoint.

Sequences with a low correlation have very important applications in communications, cryptography, and compressed sensing. In the literature, many efforts have been made to construct good sequences with various lengths, where binary sequences attract great attention. As a result, various constructions of good binary sequences have been proposed. However, most of the known constructions made use of the multiplicative cyclic group structure of finite field$\mathbb {F}_{p^{n}}$for a prime$p$and a positive integer$n$. In fact, all$p^{n}+1$rational places including the place at infinity of the rational function field over$\mathbb {F}_{p^{n}}$can form a cyclic structure under an automorphism of order$p^{n}+1$. In this paper, we make use of this cyclic structure to provide an explicit construction of binary sequences with a low correlation of length$p^{n}+1$via cyclotomic function fields over$\mathbb {F}_{p^{n}}$for any odd prime$p$. Each family of binary sequences has size$p^{n}-2$and its correlation is upper bounded by$4+\lfloor 2\cdot p^{n/2}\rfloor $. To the best of our knowledge, this is the first construction of binary sequences with a low correlation of length$p^{n}+1$for odd prime$p$. Moreover, our sequences can be constructed explicitly and have competitive parameters.

We consider the problem of efficient construction ofq-ary 2-deletion correcting codes with low redundancy. We show that our construction requires less redundancy than any existing efficiently encodableq-ary 2-deletion correcting codes. Precisely speaking, we present an explicit construction of aq-ary 2-deletion correcting code with redundancy 5 logn+10 log logn+ 3 logq+O(1) whereqis assumed to be a constant with respect ton. Using a minor modification to the original construction, we obtain an efficiently encodableq-ary 2-deletion code that is efficiently list-decodable. Similarly, we show that our construction of list-decodable code requires a smaller redundancy compared to any existing list-decodable codes. To obtain our sketches, we transform aq-ary code-word to a binary string which can then be used as an input to the underlying base binary sketch. This is then complemented with additionalq-ary sketches that the originalq-ary codeword is required to satisfy. In other words, we build our codes via a binary 2-deletion code as a black-box. Finally we utilize the binary 2-deletion code proposed by Guruswami and Håstad to our construction to obtain the main result of this paper.

A secret sharing scheme enables the dealer to share a secret amongnparties. A classic secret sharing scheme takes the numbernof parties and the secret as the input. Ifnis not known in advance, the classic secret sharing scheme may fail. Komargodski, Naor, and Yogev [8] first proposed the evolving secret sharing scheme that only takes the secret as the input. In the work [8], [9], and [2], evolving threshold and ramp secret sharing schemes were extensively investigated. However, all of their constructions except for the first construction in [2] are inspired by the scheme given in [8], namely, these schemes rely on the scheme for st-connectivity which allows to generate infinite number of shares. In this work, we revisit evolving secret sharing schemes and present three constructions that take completely different approach. Our first scheme is an evolvingk-threshold secret sharing scheme with share sizek1+ϵlogtfor any constant ϵ > 0. Thus, our scheme achieves almost the same share size as in [8]. Moreover, our scheme is obtained by a direct construction while the scheme in [8] that achieves the (k- 1) logtshare size is obtained by a recursive construction, which makes their structure complicated. Our second scheme is an evolvingkt-threshold secret sharing scheme with any sequence {kt}∞t=1of threshold values that has share sizet4. This scheme improves the share size by logtgiven in [9], where a dynamic evolvingkt-threshold secret sharing scheme with the share sizeO(t4logt) was proposed. In addition, we also show that if the threshold valuesktgrow in rate ⌊tβ⌋ for a real β ∈ (0, 1), then we have a dynamic evolving threshold secret sharing scheme with the share sizeO(t4β). Our last scheme is an evolving (αt, βt)-ramp secret sharing scheme with constant share size for some α, β. One major feature of this ramp scheme is that it is multiplicative as the scheme is also an arithmetic secret sharing scheme. We note that the same technique in [9] can also transform all of our schemes to a robust scheme as our scheme is linear.

The Gilbert-Varshamov (GV for short) bound has been a benchmark for good Hamming-metric codes. It was even conjectured by some coding theorists that the asymptotic Gilbert-Varshamov bound is tight. The GV bound had remained to be the best asymptotic lower bound for thirty years before it was broken by the Tsfasman-Vlăduţ-Zink bound via algebraic geometry codes. The discovery of algebraic geometry codes by Goppa was a breakthrough in coding theory. After another twenty years, no any improvements on the Tsfasman-Vlăduţ-Zink bound took place before the work by Xing-Elkies [14, 15, 1, 2] in the early of 2000 via tools from algebraic geometry. By using the similar ideas as in [14, 15, 9], some further improvements were given in [7, 17]. Since then, no further progress on asymptotic lower bounds has been made. The main result of this paper is to show that all previous asymptotic lower bounds can be improved in an interval. We present two types of constructions of Hamming-metric codes. Both constructions involve algebraic geometry and need insights on applications of algebraic geometry to coding theory. In order to obtain good codes, one construction requires a larger number of positive divisors of fixed degree, while other construction requires a smaller number of positive divisors of fixed degree. As a result, no matter how large the number of positive divisors of fixed degree is, we can always obtain codes with good parameters. It turns out that all previous asymptotic lower bounds are improved.

In classical coding theory, it is common to construct new codes via propagation rules. There are various propagation rules to construct classical block codes. However, propagation rules have not been extensively explored for locally repairable codes. In this paper, we systematically study some of propagation rules to construct optimal and asymptotically good locally repairable codes. To our surprise, these simple propagation rules produce interesting results. Firstly, by a lengthening propagation rule that adds some rows and columns to a parity-check matrix of a given linear code, we are able to convert a classical maximum distance separable (MDS) code into a Singleton-optimal locally repairable code and provide a simplified proof of the asymptotic Tafasman-Vlăduţ-Zink bound which exceeds the asymptotic Gilbert-Varshamov bound of locally repairable codes. Secondly, by concatenating a locally repairable code as an inner code with a classical block code as an outer code, we obtain a family of dimension-optimal locally repairable codes. Thirdly, we can make use of the shortening technique to produce more dimension-optimal locally repairable codes. Finally, one of phenomena that we observe in this paper is that some trivial propagation rules in classical block codes do not hold anymore for locally repairable codes.

A pure quantum state of$n$parties associated with the Hilbert space$\mathbb {C}^{d_{1}}\otimes \mathbb {C} ^{d_{2}}\otimes \cdots \otimes \mathbb {C} ^{d_{n}}$is called$k$-uniform if all the reductions to$k$-parties are maximally mixed. The$n$partite system is called homogenous if the local dimensions$d_{1}=d_{2}=\cdots =d_{n}$, while it is called heterogeneous if the local dimensions are not all equal.$k$-uniform sates play an important role in quantum information theory. There are much progress in characterizing and constructing$k$-uniform states in homogeneous systems. However, the study of entanglement for heterogeneous systems is much more challenging than that for the homogeneous case. There are very few results known for the$k$-uniform states in heterogeneous systems for$k>3$. We present two general methods to construct$k$-uniform states in the heterogeneous systems for general$k$. The first construction is derived from the error correcting codes by establishing a connection between irredundant mixed orthogonal arrays and error correcting codes. We can produce many new$k$-uniform states such that the local dimension of each subsystem can be a prime power. The second construction is derived from a matrix$H$meeting the condition that$H_{A\times \bar {A}}+H^{T}_{\bar {A}\times A}$has full rank for any row index set$A$of size$k$. These matrix construction can provide more flexible choices for the local dimensions, i.e., the local dimensions can be any integer (not necessarily prime power) subject to some constraints. Our constructions imply that for any positive integer$k$, one can construct$k$-uniform states of a heterogeneous system in many different Hilbert spaces.

In coding theory, constructing codes with good parameters is one of the most important and fundamental problems. A great many good codes have been constructed over alphabets of sizes equal to prime powers, however, good block codes over other alphabet sizes are rare. In this paper, we provide a new explicit construction of$(q+1)$-ary nonlinear codes via algebraic function fields, where$q$is a prime power. Our codes are constructed by evaluating rational functions at all rational places of an algebraic function field. Compared with algebraic geometry codes, the main difference is that we allow rational functions to be evaluated at pole places. After evaluating rational functions from a union of Riemann-Roch spaces, we obtain a family of nonlinear codes over the alphabet$\mathbb {F}_{q}\cup \{\infty \}$. It turns out that our codes have better parameters than those obtained from MDS codes or good algebraic geometry codes via code alphabet extension and restriction.

For codes equipped with metrics such as Hamming metric, symbol pair metric or cover metric, the Johnson bound guarantees list-decodability of such codes. That is, the Johnson bound provides a lower bound on the list-decoding radius of a code in terms of its relative minimum distance$\delta $, list size$L$and the alphabet size$q$. For study of list-decodability of codes with insertion and deletion errors (we call such codes insdel codes), it is natural to ask the open problem whether there is also a Johnson-type bound. The problem was first investigated by Wachter-Zeh and the result was amended by Hayashi and Yasunaga where a lower bound on the list-decodability for insdel codes was derived. The main purpose of this paper is to move a step further towards solving the above open problem. In this work, we provide a new lower bound for the list-decodability of an insdel code. As a consequence, we show that unlike the Johnson bound for codes under other metrics that is tight, the bound on list-decodability of insdel codes given by Hayashi and Yasunaga is not tight. Our main idea is to show that if an insdel code with a given Levenshtein distance$d$is not list-decodable with list size$L$, then the list decoding radius is lower bounded by a bound involving$L$and$d$. In other words, if the list decoding radius is less than this lower bound, the code must be list-decodable with list size$L$. At the end of the paper we use such bound to provide an insdel-list-decodability bound for various well-known codes, which has not been extensively studied before.

Insertion and deletion (insdel for short) codes have recently attracted a lot of attention due to their applications in many interesting fields such as DNA storage, DNA analysis, race-track memory error correction and language processing. The present paper mainly studies limits and constructions of insdel codes. The paper can be divided into two parts. The first part focuses on various bounds, while the second part concentrates on constructions of insdel codes. Although the insdel-metric Singleton bound has been derived before, it is still unknown if there are any nontrivial codes achieving this bound. Our first result shows that any nontrivial insdel codes do not achieve the insdel-metric Singleton bound. The second bound shows that every$[n,k]$Reed-Solomon code has insdel distance upper bounded by$2n-4k+4$and it is known in literature that an$[n,k]$Reed-Solomon code can have insdel distance$2n-4k+4$as long as the field size is sufficiently large. The third bound shows a trade-off between insdel distance and code alphabet size for codes achieving the Hamming-metric Singleton bound. In the second part of the paper, we first provide a non-explicit construction of nonlinear codes that can approach the insdel-metric Singleton bound arbitrarily when the code alphabet size is sufficiently large. The second construction gives two-dimensional Reed-Solomon codes of length$n$and insdel distance$2n-4$with field size$q=O(n^{5})$. The non-explicit construction of insdel codes is based on constant-weight$L^{1}$-codes that are introduced in this paper. We first establish a relation between constant-weight$L^{1}$-codes and insdel codes. Based on this relation, we construct constant-weight$L^{1}$-codes with reasonable parameters and subsequently give insdel codes approaching the insdel-metric Singleton bound. Via automorphism group of rational function field, we provide a necessary and sufficient condition under which a two-dimensional Reed-Solomon code of length$n$has insdel distance$2n-4$. Based on this criterion, we present a construction of$q$-ary two-dimensional Reed-Solomon codes of length$n$and insdel distance$2n-4$with$q=O(n^{5})$. Though this is worse than the current best field size, we provide a new angle to look into the problem.

Maximally recoverable local repairable codes (MR LRCs for short) have received great attention in the last few years. Various constructions have been proposed in literature. The main focus of this topic is to construct MR LRCs over small fields. An interesting parameter regime for an$(N=nr,r,h, \delta)$-MR LRC is the constant global parities$h=O(1)$. In this parameter setting, all previous constructions require the field size$\ell =\Omega _{h} (N^{h-1-o(1)})$. It remains challenging to improve this bound. In this paper, via subspace direct sum systems, we present a construction of MR LRC with the field size$\ell = O\left({N^{h-2+\frac {1}{h-1}-o(1)}}\right)$. In particular, for the interesting cases where$h=2,3$, we improve previous constructions by either reducing field size or removing constraints. In addition, we also offer some constructions of MR LRCs for larger global parity$h$. The main techniques used in this paper is through subspace direct sum systems that we introduce.

We give new constructions of two classes of algebraic code families that are efficiently list decodable with small output list size from a fraction 1-R-ε of adversarial errors, where R is the rate of the code, for any desired positive constant ε. The alphabet size depends only ε and is nearly optimal. The first class of codes are obtained by folding algebraic-geometric codes using automorphisms of the underlying function field. The second class of codes are obtained by restricting evaluation points of an algebraic-geometric code to rational points from a subfield . In both cases, we develop a linear-algebraic approach to perform list decoding, which pins down the candidate messages to a subspace with a nice “periodic” structure. To prune this subspace and obtain a good bound on the list size, we pick subcodes of these codes by pre-coding into certain subspace-evasive sets that are guaranteed to have small intersection with the sort of periodic subspaces that arise in our list decoding. We develop two approaches for constructing such subspace-evasive sets. The first is a Monte Carlo construction of hierearchical subspace-evasive (h.s.e.) sets that leads to excellent list size but is not explicit. The second approach exploits a further ultra-periodicity of our subspaces and uses a novel construct called subspace designs , which were subsequently constructed explicitly and also found further applications in pseudorandomness. To get a family of codes over a fixed alphabet size, we instantiate our approach with algebraic-geometric codes based on the Garcia–Stichtenoth tower of function fields. Combining this with pruning via h.s.e. sets yields codes list-decodable up to a 1-R-ε error fraction with list size bounded by O (1/ε), matching the existential bound for random codes up to constant factors. Further, the alphabet size can be made exp ( Õ (1/ε 2 )), which is not much worse than the lower bound of exp (Ω (1/ε)). The parameters we achieve are thus quite close to the existential bounds in all three aspects (error-correction radius, alphabet size, and list size) simultaneously. This construction is, however, Monte Carlo and the claimed list-decoding property only holds with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time O _ε ( N c ) for an absolute constant c , where N is the code’s block length. Using subspace designs instead for the pruning, our approach yields the first deterministic construction of an algebraic code family of rate R with efficient list decoding from 1-R-ε fraction of errors over an alphabet of constant size exp (Õ(1/ε 2 )). The list-size bound is upper bounded by a very slowly growing function of the block length N ; in particular, it is at most O(log ( r ) N ) (the r th iterated logarithm) for any fixed integer r . The explicit construction avoids the shortcoming of the Monte Carlo sampling at the expense of a slightly worse list size.

Communication efficient secret sharing (CESS) schemes are a class of threshold schemes that aim to minimize the so-called decoding bandwidth, namely the necessary amount of communication between a combiner who wants to reconstruct the secret and the available participants storing shares of the secret. Previous works proved that the decoding bandwidth had a tight lower bound related to the number of available participants. Some threshold schemes that achieved the lower bound (optimal decoding bandwidth) and optimal information rate were constructed for a given number (non-universal case) or multiple distinct number ($\triangle $-universal case) of available participants. However, all those CESS schemes have large share sizes. Moreover, they have a common feature that each secret and share are a vector with multiple coordinates, which results in thedecoding delaysince the combiner must reconstruct a part of coordinates of the secret at first, and these recovered coordinates will be used to reconstruct another part of coordinates of the secret. In this work, we describe a new construction for CESS schemes of non-universal and$\triangle $-universal cases, whereas each secret and share of our schemes are asingleelement of a finite field$\mathbb {F}_{q^{e}}$, and each participant of an authorized subset provides asingleelement of a same subfield of$\mathbb {F}_{q^{e}}$to the combiner to reconstruct the secret. We find that the CESS schemes of this type, termed balanced CESS schemes, have an inevitable restriction on the number of available participants, but our schemes has no decoding delay. Furthermore, our schemes havesmallershare sizes than other existing works, which are realized by using a smaller sub-packetization$e$and a smaller base field$\mathbb {F}_{q}$. Indeed, the sub-packetizations of our schemes areminimumfor given$\mathbb {F}_{q}$among balanced CESS schemes. In addition, when our constructions are used to generate communication efficient$(n,r)$threshold schemes, we derive a generalized Shamir’s scheme that universally achieves optimal decoding bandwidth and optimal information rate forthe first time, where the restriction on the number of available participants is removed.

Due to wide applications of binary sequences with a low correlation to communications, various constructions of such sequences have been proposed in the literature. Many efforts have been made to construct good binary sequences with various lengths. However, most of the known constructions make use of the multiplicative cyclic group structure of finite field$\mathbb {F}_{2^{n}}$for a positive integer$n$. It is often overlooked in this community that all$2^{n}+1$rational places (including “the place at infinity”) of the rational function field over$\mathbb {F}_{2^{n}}$form a cyclic structure under an automorphism of order$2^{n}+1$. In this paper, we make use of this cyclic structure to provide an explicit construction of binary sequences with a low correlation of length$2^{n}+1$via cyclotomic function fields over$\mathbb {F}_{2^{n}}$. Each family of our sequences has size$2^{n}-1$and its correlation is upper bounded by$\lfloor 2^{(n+2)/2}\rfloor $. To the best of our knowledge, this is the first construction of binary sequences with a low correlation of length$2^{n}+1$. Moreover, our sequences can be constructed explicitly and have competitive parameters. In particular, compared with the Gold sequences of length$2^{n}-1$for even$n$, our sequences have a smaller correlation and a larger length although the family size of our sequences is slightly smaller.

In this work, we consider the leakage-resilience of algebraic-geometric (AG for short) codes based ramp secret sharing schemes extending the analysis on the leakage-resilience of linear threshold secret sharing schemes over prime fields that is done by Benhamouda et al. in the effort to construct linear leakage-resilient secret sharing schemes with constant share size. Since there does not exist any explicit efficient construction of AG codes over prime fields with constant field size, we consider constructions over prime fields with the help of concatenation method and constructions of codes over field extensions. Extending the Fourier analysis done by Benhamouda et al., one can show that concatenated algebraic geometric codes over prime fields do produce some nice leakage-resilient secret sharing schemes. One natural and curious question is whether AG codes over extension fields produce better leakage-resilient secret sharing schemes than the construction based on concatenated AG codes. Such construction provides several advantage compared to the construction over prime fields using concatenation method. It is clear that AG codes over extension fields give secret sharing schemes with a smaller reconstruction threshold for a fixed privacy parameter$t$. In this work, it is also confirmed that indeed AG codes over extension fields have stronger leakage-resilience under some reasonable assumptions. Furthermore, we also show that AG codes over extension fields may provide strong multiplicative property which may be used in its application to the study of multiparty computation. In contrast, the same cannot be said for constructions based on concatenated AG codes, even when we are considering multiplication friendly embeddings. These advantages strongly motivate the study of secret sharing schemes from AG codes over extension fields. The current paper has two main contributions: (i) we obtain leakage-resilient secret sharing schemes with constant share sizes and unbounded numbers of players. Some of the schemes constructed without the use of concatenation also possesses strong multiplicative property (ii) via Fourier Analysis, we analyze the leakage-resilience of secret sharing schemes from codes over extension fields. This is of its own theoretical interest independent of its application to secret sharing schemes from algebraic geometric codes over extension fields.

A block code is called a locally recoverable code (LRC for short) with$(r,\delta)$-locality, if subject to any$\delta -1$erasure failures, every symbol in the encoding can still be recovered by accessing at most$r$other symbols. Recently, it was discovered by several authors that a$q$-ary optimal$(r,\delta)$-LRC, i.e., an LRC achieving the generalized Singleton-type bound, can have length much bigger than$q+1$. This is quite different from the classical$q$-ary MDS codes where it is conjectured that the code length is upper bounded by$q+1$(or$q+2$for some special cases). In this paper, we further investigate constructions of optimal$(r,\delta)$-LRCs along the line of using parity-check matrices. Inspired by classical Reed-Solomon codes and the work in Jin (2019), we equip parity-check matrices with the Vandermonde structure. It turns out that a parity-check matrix with the Vandermonde structure that produces an optimal LRC must obey certain disjoint property for subsets of$\mathbb {F}_{q}$. We manage to show the existence of these disjoint subsets. Thus, this yields an optimal$(r,\delta)$-LRC with code length$\Omega \left({q^{\frac {\delta }{2}\left({1+\frac {1}{\lfloor \frac {d-1}{\delta }\rfloor -1}}\right)}}\right)\vphantom {\bigg)_{j}}$, where$d$is the minimum distance. In particular, to our surprise, for$\delta =2$this disjoint condition is equivalent to a well-studied problem in extremal graph theory. With the help of extremal graph theory, we succeed to improve all of the best known results in Guruswamiet al.(2018) for$d\geq 7$. In addition, for$d=6$, we are able to remove the constraint required in Jin (2019) that$q$is even.

For an integer q ≥ 2, a perfect q-hash code C is a block code over [q] ≔ {1, …, q} of length n in which every subset {c1, c2, …, cq} of q elements is separated, i.e., there exists i ∊ [n] such that {proji(c1), …, proji(cq)} = [q], where proji(cj) denotes the ith position of cj. Finding the maximum size M(n, q) of perfect q-hash codes of length n, for given q and n, is a fundamental problem in combinatorics, information theory, and computer science. In this paper, we are interested in asymptotical behavior of this problem. More precisely speaking, we will focus on the quantity . A well-known probabilistic argument indicates [10, 12]. This is still the best-known lower bound so far except for the case q = 3 for which Körner and Matron [13] found that the concatenation technique could lead to perfect 3-hash codes that could beat this probabilistic lower bound. This improved lower bound on R3 was discovered in 1988 and there has been no progress of this lower bound on Rq for more than 30 years despite of some work on upper bounds on Rq. In this paper we show that this probabilistic lower bound can be improved for q = 4, 8 and all odd integers between 5 and 25,1 and all sufficiently large q with q (mod 4) ≠ 2. Although we are not able to prove that our construction can beat the probabilistic method for all q with q (mod 4) ≠ 2, the fact that our construction beat the probabilistic method for both small and large q sheds light on that our new construction might beat the previous lower bound for all q with q (mod 4) ≠ 2. Our idea is based on a modified concatenation differing from the concatenation [10] where both the inner and outer codes are separated. In our concatenation, the inner code is not necessarily a perfect q-hash code. This gives a more flexible choice of inner codes and hence we are able to improve the lower bound on Rq.

Insertion and deletion (insdel for short) errors are synchronization errors in communication systems caused by the loss of positional information in the message. Reed-Solomon codes have gained a lot of interest due to its encoding simplicity, well structuredness and list-decoding capability in the classical setting. This interest also translates to the insdel metric setting, as the Guruswami-Sudan decoding algorithm can be utilized to provide a deletion correcting algorithm in the insdel metric. Nevertheless, there have been few studies on the insdel error-correcting capability of Reed-Solomon codes. Our main contributions in this article are explicit constructions of two families of 2-dimensional Reed-Solomon codes with insdel error-correcting capabilities asymptotically reaching those provided by the Singleton bound. The first construction gives a family of Reed-Solomon codes with insdel error-correcting capability asymptotic to its length. The second construction provides a family of Reed-Solomon codes with an exact insdel error-correcting capability up to its length. Both our constructions improve the previously known construction of 2-dimensional Reed-Solomon codes whose insdel error-correcting capability is only logarithmic on the code length.

It is well known that constructing codes with good parameters is one of the most important and fundamental problems in coding theory. Though a great many of good codes have been produced, most of them are defined over alphabets of sizes equal to prime powers. In this article, we provide a new explicit construction of$(q+1)$-ary nonlinear codes via rational function fields, where$q$is a prime power. Our codes are constructed by evaluations of rational functions at all rational places (including the place of “infinity”) of the rational function field. Compared to the rational algebraic geometry codes, the main difference is that we allow rational functions to be evaluated at pole places. After evaluating rational functions from a union of Riemann-Roch spaces, we obtain a family of nonlinear codes with length$q+1$over the alphabet$\mathbb {F}_{q}\cup \{\infty \}$. As a result, our codes have reasonable parameters as they are rather close to the Singleton bound. Furthermore, our codes have better parameters than those obtained from MDS codes via code alphabet restriction or extension. Amazingly, an efficient decoding algorithm can be provided for our codes.

In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of insdel codes along with their efficient encoding and decoding algorithms through concatenation method which provides a Zyablov-type bound for insdel metric codes.

Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a single coordinate. This decoding algorithm might be more expensive, i.e., require higher query complexity. In this paper, we focus on Reed-Muller codes with usual parameter regime, namely, the total degree of evaluation polynomials is d = Θ(q), where q is the code alphabet size (in fact, d can be as big as q/4 in our setting). By introducing a novel variation of codex, i.e., interleaved codex (the concept of codex has been used for arithmetic secret sharing), we are able to locally recover arbitrarily large number k of coordinates of a Reed-Muller code simultaneously with error probability exp(-Ω(k)) at the cost of querying merely O(q2k) coordinates. It turns out that our local decoding of Reed-Muller codes shows (perhaps surprisingly) that accessing k locations is in fact cheaper than repeating the procedure for accessing a single location for k times. Precisely speaking, to get the same success probability by repeating the local decoding algorithm of a single coordinate, one has to query Ω(qk2) coordinates. Thus, the query complexity of our local decoding is smaller for k = Ω(q). If we impose the same query complexity constraint on both algorithm, our local decoding algorithm yields smaller error probability when k = Ω(qq). In addition, our local decoding is efficient, i.e., the decoding complexity is Poly(k, q). Construction of an interleaved codex is based on concatenation of a codex with a multiplication friendly pair, while the main tool to realize codex is based on algebraic function fields (or more precisely, algebraic geometry codes).

Local Reconstruction Codes (LRCs) allow for recovery from a small number of erasures in a local manner based on just a few other codeword symbols. They have emerged as the codes of choice for large scale distributed storage systems due to the very efficient repair of failed storage nodes in the typical scenario of a single or few nodes failing, while also offering fault tolerance against worst-case scenarios with more erasures. A maximally recoverable (MR) LRC offers the best possible blend of such local and global fault tolerance, guaranteeing recovery from all erasure patterns which are information-theoretically correctable given the presence of local recovery groups. MR LRCs have received much attention recently, with many explicit constructions covering different regimes of parameters. Unfortunately, all known constructions require a large field size. In this work, we develop an approach based on function fields to construct MR LRCs. Our method recovers, and in most parameter regimes improves, the field size of previous approaches. The improvements are modest, but more importantly are obtained in a unified manner via a promising new idea.

Locally repairable codes, or locally recoverable codes (LRC for short), are designed for applications in distributed and cloud storage systems. Similar to classical block codes, there is an important bound called the Singleton-type bound for locally repairable codes. In this paper, an optimal locally repairable code refers to a block code achieving this Singleton-type bound. Like classical MDS codes, optimal locally repairable codes carry some very nice combinatorial structures. Since the introduction of the Singleton-type bound for locally repairable codes, people have put tremendous effort into construction of optimal locally repairable codes. There are a few constructions of optimal locally repairable codes in the literature. Most of these constructions are realized via either combinatorial or algebraic structures. In this paper, we apply automorphism group of the rational function field to construct optimal locally repairable codes by considering the group action on projective lines over finite fields. Due to various subgroups of the projective general linear group, we are able to construct optimal locally repairable codes with flexible locality as well as smaller alphabet size comparable to the code length. In particular, we produce new families of q-ary locally repairable codes, including codes of length q+1 via cyclic groups.

In this paper, we propose new classes of trapdoor functions to solve the bounded distance decoding problem in lattices. Specifically, we construct lattices based on properties of polynomials for which the bounded distance decoding problem is hard to solve unless some trapdoor information is revealed. We thoroughly analyze the security of our proposed functions using state-of-the-art attacks and results on lattice reductions. Finally, we describe how our functions can be used to design quantum-safe encryption schemes with reasonable public key sizes. Our encryption schemes are efficient with respect to key generation, encryption and decryption.

Locally repairable codes have been investigated extensively in recent years due to practical applications in distributed and cloud storage systems. However, there are few asymptotic constructions of locally repairable codes in the literature. In this paper, we provide a new explicit asymptotic construction of locally repairable codes over arbitrary finite fields from local expansions of functions at a rational place. This construction gives a Tsfasman-Vladut-Zink type bound for locally repairable codes. Its main advantage is that there are no constraints on both locality and alphabet size. Furthermore, we show that the Gilbert-Varshamov type bound of locally repairable codes over non-prime finite fields can be improved for sufficiently large alphabet sizes.

In literatures, there are various constructions of frequency hopping sequence (FHS for short) sets with good Hamming correlations. Some papers employed only multiplicative groups of finite fields to construct FHS sets, while other papers implicitly used only additive groups of finite fields for construction of FHS sets. In this paper, we make use of both multiplicative and additive groups of finite fields simultaneously to present a construction of optimal FHS sets. The construction provides a new family of optimal (qm- 1, qm-t-1/r , rqt; qm-t-1/r + 1) frequency hopping sequence sets archiving the Peng-Fan bound. Thus, some FHS sets constructed in literatures using either multiplicative groups or additive groups of finite fields are included in our family. In addition, some other FHS sets can be obtained via the well-known recursive construction through one-coincidence sequence set.

Given a q-ary frequency hopping sequence set of length n and size M with Hamming correlation H, one can obtain a q-ary (nonlinear) cyclic code of length n and size nM with Hamming distance n-H. Thus, every upper bound on the size of a code from coding theory gives an upper bound on the size of a frequency hopping sequence set. Indeed, all upper bounds from coding theory have been converted to upper bounds on frequency hopping sequence sets [1]. On the other hand, a lower bound from coding theory does not automatically produce a lower bound for frequency hopping sequence sets. In particular, the most important lower bound, the Gilbert-Varshamov bound in coding theory, has not been transformed to a valid lower bound on frequency hopping sequence sets. The purpose of this paper is to transform the Gilbert-Varshamov bound from coding theory to frequency hopping sequence sets by establishing a connection between a special family of cyclic codes (which are called hopping cyclic codes in this paper) and frequency hopping sequence sets. We provide two proofs of the Gilbert-Varshamov bound. One is based on a probabilistic method that requires advanced tool- martingale. This proof covers the whole rate region. Another proof is purely elementary but only covers part of the rate region.

Machine Learning models require a vast amount of data for accurate training. In reality, most data is scattered across different organizations and cannot be easily integrated under many legal and practical constraints. Federated Transfer Learning (FTL) was introduced in [1] to improve statistical models under a data federation that allow knowledge to be shared without compromising user privacy, and enable complementary knowledge to be transferred in the network. As a result, a target-domain party can build more flexible and powerful models by leveraging rich labels from a source-domain party. However, the excessive computational overhead of the security protocol involved in this model rendered it impractical. In this work, we aim towards enhancing the efficiency and security of existing models for practical collaborative training under a data federation by incorporating Secret Sharing (SS). In literature, only the semi-honest model for Federated Transfer Learning has been considered. In this paper, we improve upon the previous solution, and also allow malicious players who can arbitrarily deviate from the protocol in our FTL model. This is much stronger than the semi-honest model where we assume that parties follow the protocol precisely. We do so using the one of the practical MPC protocol called SPDZ, thus our model can be efficiently extended to any number of parties even in the case of a dishonest majority. In addition, the models evaluated in our setting significantly outperform the previous work, in terms of both runtime and communication cost. A single iteration in our model executes in 0.8 seconds for the semi-honest case and 1.4 seconds for the malicious case for 500 samples, as compared to 35 seconds taken by the previous implementation.

Local Reconstruction Codes (LRCs) allow for recovery from a small number of erasures in a local manner based on just a few other codeword symbols. A maximally recoverable (MR) LRC offers the best possible blend of such local and global fault tolerance, guaranteeing recovery from all erasure patterns which are information-theoretically correctable given the presence of local recovery groups. In an $(n,r,h,a)$-LRC, the $n$ codeword symbols are partitioned into $r$ disjoint groups each of which include $a$ local parity checks capable of locally correcting $a$ erasures. MR LRCs have received much attention recently, with many explicit constructions covering different regimes of parameters. Unfortunately, all known constructions require a large field size that exponential in $h$ or $a$, and it is of interest to obtain MR LRCs of minimal possible field size. In this work, we develop an approach based on function fields to construct MR LRCs. Our method recovers, and in most parameter regimes improves, the field size of previous approaches. For instance, for the case of small $r \ll ε\log n$ and large $h \ge Ω(n^{1-ε})$, we improve the field size from roughly $n^h$ to $n^{εh}$. For the case of $a=1$ (one local parity check), we improve the field size quadratically from $r^{h(h+1)}$ to $r^{h \lfloor (h+1)/2 \rfloor}$ for some range of $r$. The improvements are modest, but more importantly are obtained in a unified manner via a promising new idea.

Locally recoverable codes are a class of block codes with an additional property called locality. A locally recoverable code with locality r can recover a symbol by reading at most r other symbols. Recently, it was discovered by several authors that a q-ary optimal locally recoverable code, i.e., a locally recoverable code achieving the Singleton-type bound, can have length much bigger than q+1. In this paper, we present both the upper bound and the lower bound on the length of optimal locally recoverable codes. Our lower bound improves the best known result in [Yuan Luo et al., 2018] for all distance d >= 7. This result is built on the observation of the parity-check matrix equipped with the Vandermonde structure. It turns out that a parity-check matrix with the Vandermonde structure produces an optimal locally recoverable code if it satisfies a certain expansion property for subsets of F_q. To our surprise, this expansion property is then shown to be equivalent to a well-studied problem in extremal graph theory. Our upper bound is derived by an refined analysis of the arguments of Theorem 3.3 in [Venkatesan Guruswami et al., 2018].

A locally repairable code (LRC) with locality r allows for the recovery of any erased codeword symbol using only r other codeword symbols. A Singleton-type bound dictates the best possible tradeoff between the dimension and distance of LRCs-an LRC attaining this tradeoff is deemed optimal. Such optimal LRCs have been constructed over alphabets growing linearly in the block length. Unlike the classical Singleton bound, however, it was not known if such a linear growth in the alphabet size is necessary or, for that matter, even if the alphabet needs to grow at all with the block length. Indeed, for small code distances 3 and 4, arbitrarily long optimal LRCs were known over fixed alphabets. Here, we prove that for distances d ≥ 5, the code length n of an optimal LRC over an alphabet of size q must be at most roughly O(dq3). For the case d = 5, our upper bound is O(q2). We complement these bounds by showing the existence of optimal LRCs of length Ωd,r(q1+1/〈(d-3)/2〉) when d r + 2. These bounds match when d = 5, thus pinning down n = Θ(q2) as the asymptotically largest length of an optimal LRC for this case.

Constructing locally repairable codes achieving Singleton-type bound (we call them optimal codes in this paper) is a challenging task and has attracted great attention in the last few years. Tamo and Barg first gave a breakthrough result in this topic by cleverly considering subcodes of Reed-Solomon codes. Thus, q-ary optimal locally repairable codes from subcodes of Reed-Solomon codes given by Tamo and Barg have length upper bounded by q. Recently, it was shown through extension of construction by Tamo and Barg that length of q-ary optimal locally repairable codes can be q+1 by Jin et al.. Surprisingly it was shown by Barg et al. that, unlike classical MDS codes, q-ary optimal locally repairable codes could have length bigger than q+1. Thus, it becomes an interesting and challenging problem to construct q-ary optimal locally repairable codes of length bigger than q+1. In this paper, we make use of rich algebraic structures of elliptic curves to construct a family of q-ary optimal locally repairable codes of length up to q+2√(q). It turns out that locality of our codes can be as big as 23 and distance can be linear in length.

Locally repairable codes have been investigated extensively in recent years due to practical applications in distributed storage as well as theoretical interest. However, not much work on asymptotical behavior of locally repairable codes has been done until now. In particular, there is little result on constructive lower bound of asymptotical behavior of locally repairable codes. In this paper, we extend the construction given by Barg et al. via automorphism groups of function field towers. The main advantage of our construction is to allow more flexibility of locality. Furthermore, we show that the Gilbert-Varshamov type bound on locally repairable codes can be improved for all sufficiently large alphabet size q.

We investigate the list decodability of symbol-pair codes1in this paper. First, we show that the list decodability of every symbol-pair code does not exceed the Gilbert-Varshamov bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert-Varshamov bound. Our second result of this paper is to derive the Johnson-type bound, i.e., a lower bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed-Solomon codes beyond the Johnson-type bound in the pair metric.1A symbol-pair code is referred to a code in the pair metric.

Like classical block codes, a locally repairable code also obeys the Singleton-type bound (we call a locally repairable code optimal if it achieves the Singleton-type bound). In the breakthrough work of Tamo and Barg, several classes of optimal locally repairable codes were constructed via subcodes of Reed-Solomon codes. Thus, the lengths of the codes given by Tamo and Barg are upper bounded by the code alphabet size q. Recently, it was proved through the extension of construction by Tamo and Barg that the length of q-ary optimal locally repairable codes can be q +1 by Jin et al. Surprisingly, Barg et al. presented a few examples of q-ary optimal locally repairable codes of small distance and locality with code length achieving roughly q2. Very recently, it was further shown in the work of Li et al. that there exist q-ary optimal locally repairable codes with the length bigger than q+1 and the distance proportional to n. Thus, it becomes an interesting and challenging problem to construct new families of q-ary optimal locally repairable codes of length bigger than q+1. In this paper, we construct a class of optimal locally repairable codes of distances 3 and 4 with unbounded length (i.e., length of the codes is independent of the code alphabet size). Our technique is through cyclic codes with particular generator and parity-check polynomials that are carefully chosen.

In this paper, a general framework of constructing the optimal frequency-hopping sequence (FHS) sets is presented based on the designated direct product. Under this framework, we obtain infinitely many new optimal FHS sets by combining some one-coincide (OC) sequence sets that are newly constructed in this paper with some known optimal FHS sets. Our constructions are also based on extension method. However, our constructions give new and flexible parameters due to the free choice of OC sequence set. As a result, our constructions allow a great flexibility of choosing parameters of FHS sets for a given frequency-hopping spread spectrum system.

A locally repairable code (LRC) with locality $r$ allows for the recovery of any erased codeword symbol using only $r$ other codeword symbols. A Singleton-type bound dictates the best possible trade-off between the dimension and distance of LRCs --- an LRC attaining this trade-off is deemed \emph{optimal}. Such optimal LRCs have been constructed over alphabets growing linearly in the block length. Unlike the classical Singleton bound, however, it was not known if such a linear growth in the alphabet size is necessary, or for that matter even if the alphabet needs to grow at all with the block length. Indeed, for small code distances $3,4$, arbitrarily long optimal LRCs were known over fixed alphabets. Here, we prove that for distances $d \ge 5$, the code length $n$ of an optimal LRC over an alphabet of size $q$ must be at most roughly $O(d q^3)$. For the case $d=5$, our upper bound is $O(q^2)$. We complement these bounds by showing the existence of optimal LRCs of length $Ω_{d,r}(q^{1+1/\lfloor(d-3)/2\rfloor})$ when $d \le r+2$. These bounds match when $d=5$, thus pinning down $n=Θ(q^2)$ as the asymptotically largest length of an optimal LRC for this case.

For a vector space F^n over a field F, an (eta,beta)-dimension expander of degree d is a collection of d linear maps Gamma_j : F^n -> F^n such that for every subspace U of F^n of dimension at most eta n, the image of U under all the maps, sum_{j=1}^d Gamma_j(U), has dimension at least beta dim(U). Over a finite field, a random collection of d = O(1) maps Gamma_j offers excellent "lossless" expansion whp: beta ~~ d for eta >= Omega(1/d). When it comes to a family of explicit constructions (for growing n), however, achieving even modest expansion factor beta = 1+epsilon with constant degree is a non-trivial goal. We present an explicit construction of dimension expanders over finite fields based on linearized polynomials and subspace designs, drawing inspiration from recent progress on list-decoding in the rank-metric. Our approach yields the following: - Lossless expansion over large fields; more precisely beta >= (1-epsilon)d and eta >= (1-epsilon)/d with d = O_epsilon(1), when |F| >= Omega(n). - Optimal up to constant factors expansion over fields of arbitrarily small polynomial size; more precisely beta >= Omega(delta d) and eta >= Omega(1/(delta d)) with d=O_delta(1), when |F| >= n^{delta}. Previously, an approach reducing to monotone expanders (a form of vertex expansion that is highly non-trivial to establish) gave (Omega(1),1+Omega(1))-dimension expanders of constant degree over all fields. An approach based on "rank condensing via subspace designs" led to dimension expanders with beta >rsim sqrt{d} over large fields. Ours is the first construction to achieve lossless dimension expansion, or even expansion proportional to the degree.

Minimum storage regenerating codes have minimum storage of data in each node and therefore are maximal distance separable (for short) codes. Thus, the number of nodes is upper-bounded by 2b, where ú is the bits of data stored in each node. From both theoretical and practical points of view (see the details in Section 1), it is natural to consider regenerating codes that nearly have minimum storage of data, and meanwhile, the number of nodes is unbounded. One of the candidates for such regenerating codes is an algebraic geometry code. In this paper, we generalize the repairing algorithm of Reed-Solomon codes given by Guruswami and Wotters to algebraic geometry codes and present a repairing algorithm for arbitrary one-point algebraic geometry codes. By applying our repairing algorithm to the one-point algebraic geometry codes based on the Garcia- Stichtenoth tower, one can repair a code of rate 1 - e and length n over Fqwith bandwidth (n - 1)(1 - τ) log q for any e = 2(τ-1/2)logq with a real τ ∈ (0, 1/2). In addition, storage in each node for an algebraic geometry code is close to the minimum storage. Due to nice structures of Hermitian curves, repairing of Hermitian codes is also investigated. As a result, we are able to show that algebraic geometry codes are regenerating codes with good parameters.

It was shown by Massey that linear complementary dual (LCD) codes are asymptotically good. In 2004, Sendrier proved that LCD codes meet the asymptotic Gilbert-Varshamov (GV) bound. Until now, the GV bound still remains to be the best asymptotical lower bound for LCD codes. In this paper, we show that an algebraic geometry code over a finite field of even characteristic is equivalent to an LCD code and consequently there exists a family of LCD codes that are equivalent to algebraic geometry codes and exceed the asymptotical GV bound.

Wachter-Zeh showed that every cover metric code can be list decoded up to the Johnson-like bound. Furthermore, it was shown that the efficient list decoding of cover metric codes up to the Johnson-like bound can be performed. From the work of Wachter-Zeh, one natural question is whether the Johnson-like bound can be improved. In this paper, we give a confirmative answer to this question by showing that the cover metric codes can be list decoded up to the Singleton bound. Our contributions consist of three parts. First, we prove that the list decodability of cover metric codes does not exceed the Singleton bound. Second, we show that, with high probability, a random cover metric code can be list decoded up to the Singleton bound, which is better than the Johnson-like bound. Third, by applying the existing decoding algorithms for Hamming metric and rank metric codes, we present explicit constructions of cover metric codes that can be efficiently list decoded up to the Singleton bound.

Compared with classical block codes, list decoding rank-metric codes efficiently seems more difficult. The evidences to support this view include: 1) so far the only known efficient list decoding of rank-metric codes C gives decoding radius beyond (1 - R)/2 with positive rate R when the ratio of the number of rows over the number of columns is extremely small, 2) the Johnson bound for rank-metric codes does not exist as opposed to classical codes, and 3) the Gabidulin codes of square matrices cannot be list decoded beyond half of the minimum distance. Although the list decodability of random rank-metric codes and the limits to the list decodability have been determined completely, little work on efficient list decoding of rank-metric codes has been done. The only known efficient list decoding of rank-metric codes C gives decoding radius up to the singleton bound 1-R-e with positive rate R when ρ(C) is extremely small, i.e., O(ε2), where ρ(C) denotes the ratio of the number of rows over the number of columns of C. It is commonly believed that it is difficult to list decode rank-metric codes C with the ratio ρ(C) close to 1. The main purpose of this paper is to explicitly construct a class of rank-metric codes C with the ratio ρ(C) up to 1/2 and efficiently list decode these codes beyond unique decoding radius (1 - R)/2. Furthermore, encoding and list decoding algorithms run in polynomial time poly(n, exp(1/e)). The list size can be reduced to O(1/e) by randomizing the algorithm. Our key idea is to employ bivariate polynomials f (x, y), where f is linearized in variable y and the variable x is used to “fold” the code. In other words, the rows are used to correct rank errors and the columns are used to “fold” the code to enlarge the decoding radius. Apart from the above algebraic technique, we have to prune down the list. The algebraic idea enables us to pin down the messages into a structured subspace whose dimension is linear in the number n of columns. This “periodic” structure allows us to pre-encode the messages to prune down the list. More precisely, we use subspace design introduced by Guruswami and Xing to obtain a deterministic algorithm with a larger constant list size and employ hierarchical subspace-evasive sets introduced by Guruswami et al. to obtain a randomized algorithm with a smaller constant list size.

Subspace designs are a (large) collection of high-dimensional subspaces {H_i} of F_q^m such that for any low-dimensional subspace W, only a small number of subspaces from the collection have non-trivial intersection with W; more precisely, the sum of dimensions of W cap H_i is at most some parameter L. The notion was put forth by Guruswami and Xing (STOC'13) with applications to list decoding variants of Reed-Solomon and algebraic-geometric codes, and later also used for explicit rank-metric codes with optimal list decoding radius. Guruswami and Kopparty (FOCS'13, Combinatorica'16) gave an explicit construction of subspace designs with near-optimal parameters. This construction was based on polynomials and has close connections to folded Reed-Solomon codes, and required large field size (specifically q >= m). Forbes and Guruswami (RANDOM'15) used this construction to give explicit constant degree "dimension expanders" over large fields, and noted that subspace designs are a powerful tool in linear-algebraic pseudorandomness. Here, we construct subspace designs over any field, at the expense of a modest worsening of the bound $L$ on total intersection dimension. Our approach is based on a (non-trivial) extension of the polynomial-based construction to algebraic function fields, and instantiating the approach with cyclotomic function fields. Plugging in our new subspace designs in the construction of Forbes and Guruswami yields dimension expanders over F^n for any field F, with logarithmic degree and expansion guarantee for subspaces of dimension Omega(n/(log(log(n)))).

A pure quantum state is called k-uniform if all its reductions to k-qudit are maximally mixed. We investigate the general constructions of k-uniform pure quantum states of n subsystems with d levels. We provide one construction via symmetric matrices and the second one through the classical error-correcting codes. There are three main results arising from our constructions. First, we show that for any given even n ≥ 2, there always exists an n/2-uniform n-qudit quantum state of level p for sufficiently large prime p. Second, both constructions show that there exist k-uniform n-qudit pure quantum states such that k is proportional to n, i.e., k = Ω(n) although the construction from symmetric matrices in general outperforms the one by error-correcting codes. Third, our symmetric matrix construction provides a positive answer to the open question on whether there exists a 3-uniform n-qudit pure quantum state for all n ≥ 8. In fact, we can further prove that, for every k, there exists a constant Mksuch that there exists a k-uniform n-qudit quantum state for all n ≥ Mk. In addition, by using the concatenation of algebraic geometry codes, we give an explicit construction of k-uniform quantum state when k tends to infinity.

The Reed-Muller (RM) code, encoding n-variate degree-d polynomials over Fqfor dqn, has a relative distance 1 - d/q and can be list decoded from a 1- O(√d/q) fraction of errors. In this paper, for d ≪ q, we give a length-efficient puncturing of such codes, which (almost) retains the distance and list decodability properties of the RM code, but has a much better rate. Specifically, when q = Ω(d2/ε2), we give an explicit rate Ω (ε/d!) puncturing of RM codes, which have a relative distance at least (1 - √ε) and efficient list decoding up to (1 - √ε) error fraction. This almost matches the performance of random puncturings, which work with the weaker field size requirement q = Ω(d/ε2). We can also improve the field size requirement to the optimal (up to constant factors) q = Ω(d/ε), at the expense of a worse list decoding radius of 1-ε1/3and rate Ω (ε/d!). The first of the above tradeoffs is obtained by substituting for the variables functions with carefully chosen pole orders from an algebraic function field; this leads to a puncturing for which the RM code is a subcode of a certain algebraic-geometric code (which is known to be efficiently list decodable). The second tradeoff is obtained by concatenating this construction with a Reed-Solomon-based multiplication friendly pair, and using the list recovery property of algebraic-geometric codes.

Both Maximum Distance Separable and Euclidean self-dual codes have theoretical and practical importance and the study of MDS self-dual codes has attracted lots of attention in recent years. In particular, determining the existence of q-ary MDS self-dual codes for various lengths has been investigated extensively. The problem is completely solved for the case where q is even. This paper focuses on the case where q is odd. We construct a few classes of new MDS self-dual codes through generalized Reed-Solomon codes. More precisely, we show that for any given even length n, we have a q-ary MDS code as long as q ≡ 1 mod 4 and q is sufficiently large (say q ≥ 4n× n2). Furthermore, we prove that there exists a q-ary MDS self-dual code of length n if q = r2and n satisfies one of the three conditions: 1) n ≤ r and n is even; 2) q is odd and n - 1 is an odd divisor of q - 1; and 3) r ≡ 3 mod 4 and n=2tr for any t ≤ (r - 1)/2.

Efficient list decoding of rank-metric codes seems more difficult compared with classical block codes although list decodability of random rank-metric codes is completely determined by Ding. For example, it was shown by Raviv and Wachter-Zeh that the list decoding radius of Gabidulin codes is the same as the unique decoding radius, i.e., half the minimum distance for some instances of parameters. On the other hand, Guruswami and Xing give an explicit construction of subcodes of Gabidulin codes, which can be list decoded up to the Singleton bound. This implies that subcodes of Gabidulin codes are good candidates for list decoding. In this paper, we confirm that, with overwhelming probability, a random subcode of a Gabidulin code can be list decoded with decoding radius far beyond half of the minimum distance.

Complexity of sequences plays an important role in pseudorandom sequences and cryptography. In this paper, we present a construction of sequences with high nonlinear complexity from function fields. The main idea is to make use of function fields with many rational places as well as an automorphism of large order. We illustrate our construction through rational function fields and cyclotomic function fields in which there exist some automorphisms of large order. It turns out that we are able to: 1) slightly increase the length of the inversive sequence without losing nonlinear complexity and 2) obtain sequences with much larger nonlinear complexity than random sequences.

We construct an explicit family of Fh-linear rankmetric codes over any field Fh that enables efficient list-decoding up to a fraction p of errors in the rank metric with a rate of 1 - ρ - e, for any desired ρ ∈ (0, 1) and e > 0. This is the first explicit construction of positive rate rank-metric codes for efficient list-decoding beyond the unique decoding radius. Our codes are explicit subcodes of the well-known Gabidulin codes, which encode linearized polynomials of low degree via their values at a collection of linearly independent points. The subcode is picked by restricting the message polynomials to an Fh-subspace that evades the structured subspaces over an extension field Fht that arise in our linear-algebraic list decoder for Gabidulin codes. This subspace is obtained by combining subspace designs constructed by Guruswami and Kopparty (FOCS'13) with subspace-evasive varieties due to Dvir and Lovett (STOC'12). We establish a similar result for subspace codes, which have received much attention recently in the context of network coding. We also give explicit subcodes of folded Reed-Solomon (RS) codes with small folding order, which are list-decodable (in the Hamming metric) with optimal redundancy, motivated by the fact that listdecoding RS codes reduces to list-decoding such folded RS codes. However, as we only list-decode a subcode of these codes, the Johnson radius continues to be the best known error fraction for list-decoding RS codes.

Multiplicative linear secret sharing is a fundamental notion in the area of secure multiparty computation and, since recently, in the area of two-party cryptography as well. In a nutshell, this notion guarantees that the product of two secrets is obtained as a linear function of the vector consisting of the coordinatewise product of two respective share-vectors. This paper focuses on the following foundational question, which is novel to the best of our knowledge. Suppose we abandon the latter linearity condition and instead require that this product is obtained by some, not-necessarily-linear “product reconstruction function.” Is the resulting notion equivalent to multiplicative linear secret sharing? We show the (perhaps somewhat counterintuitive) result that this relaxed notion is strictly more general. Concretely, fix a finite field ${\mathbb F}_q$ as the base field over which linear secret sharing is considered. Then we show there exists an (exotic) linear secret sharing scheme with an unbounded number of players $n$ such that it has $t$-privacy with $t = \Omega(n)$ and such that it does admit a product reconstruction function, yet this function is necessarily nonlinear. In addition, we determine the minimum number of players for which those exotic schemes exist. Our proof is based on combinatorial arguments involving quadratic forms. It extends to similar separation results for important variations, such as strongly multiplicative secret sharing.

In this paper, we present an algebraic construction of binary codes through rational function fields. We make use of certain multiplicative group of rational functions for our construction. In particular, the point at infinity can be employed in our construction to get codes of length up to q+1, where q is the ground field size. As a result, several new binary constant-weight codes are found and many new binary nonlinear codes are presented.

Guruswami et al. showed that the list-decodability of random linear codes is as good as that of general random codes. In this paper, we further strengthen the result by showing that the list-decodability of random Euclidean self-orthogonal codes is as good as that of general random codes as well, i.e., achieves the classical Gilbert-Varshamov bound. In particular, we show that, for any fixed finite field Fq, error fraction δ ∈ (0,1 - 1/q) satisfying 1 - Hq(δ) ≤ 1/2, and small ε > 0, with high probability a random Euclidean self-orthogonal code over Fqof rate 1 - Hq(δ) - ε is (δ, O(1/ε))-list-decodable. This generalizes the result of linear codes to Euclidean self-orthogonal codes. In addition, we extend the result to list decoding symplectic dual-containing codes by showing that the list-decodability of random symplectic dual-containing codes achieves the quantum Gilbert-Varshamov bound as well. This implies that list-decodability of quantum stabilizer codes can achieve the quantum Gilbert-Varshamov bound. The counting argument on self-orthogonal codes is an important ingredient to prove our result.

We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding n-variate degree-d polynomials over Fqwith q ≳ d/δ, we present an explicit (multi)-set S ⊆ Fqnof size N=poly(nd/δ) such that every nonzero polynomial vanishes on at most delta N points in S. Equivalently, we give an explicit hitting set generator (HSG) for degree-d polynomials of seed length log N = O(d log n + log (1/δ)) with "density" 1-δ (meaning every nonzero polynomial is nonzero with probability at least 1-δ on the output of the HSG). The seed length is optimal up to constant factors, as is the required field size Omega(d/delta). Plugging our HSG into a construction of Bogdanov (STOC'05) gives explicit pseudorandom generators for n-variate degree-d polynomials with error eps and seed length O(d4log n + log (1/ε)) whenever the field size satisfies q gtrsim d6/ε2. Our approach involves concatenating previously known HSGs over large fields with multiplication friendly codes based on algebraic curves. This allows us to bring down the field size to the optimal bounds. Such multiplication friendly codes, which were first introduced to study the bilinear complexity of multiplication in extension fields, have since found other applications, and in this work we give a further use of this notion in algebraic pseudorandomness.

Locally correctable codes have found numerous applications in complexity theory, cryptography and the theory of fault tolerant computation. Recently, Guo et al. [1], discovered a family of high rate locally correctable codes by considering lifting of multivariate polynomials. In this paper, we extend their method by lifting multivariate polynomials on curves, and generalize the “decoding on curve” algorithm from Reed-Muller codes to these lifted codes to provide correcting algorithms with success probability arbitrarily approaching 1. This gives a family of high rate locally correctable codes that is highly sound.

We construct a new list-decodable family of asymptotically good algebraic-geometric (AG) codes over fixed alphabets. The function fields underlying these codes are constructed using class field theory, specifically Drinfeld modules of rank 1, and designed to have an automorphism of large order that is used to “fold” the AG code. This generalizes earlier work by the first author on folded AG codes based on cyclotomic function fields. The recent linear-algebraic approach to list decoding can be applied to our new codes, and crucially, we use the Chebotarev density theorem to establish a polynomial upper bound on the list-size for list decoding up to an error fraction approaching 1 – R where R is the rate. The list decoding can be performed in polynomial time given polynomial amount of pre-processed information about the function field. Our construction yields algebraic codes over constant-sized alphabets that can be list decoded up to the Singleton bound — specifically, for any desired rate R ∊ (0, 1) and constant ∊ > 0, we get codes over an alphabet size that can be list decoded up to error fraction 1 – R – ∊ confining close-by messages to a subspace with elements. Previous results for list decoding up to error-fraction 1 – R – ∊ over constant-sized alphabets were either based on concatenation or involved taking a carefully chosen subcode of algebraic-geometric codes. In contrast, our result shows that these folded algebraic-geometric codes themselves have the claimed list decoding property. Further, our methods to get function fields with the properties needed for constructing and decoding the code might be of independent algebraic interest.

Private searching on streaming data is a process to dispatch to a public server a program, which searches streaming sources of data without revealing searching criteria and then sends back a buffer containing the findings. From an Abelian group homomorphic encryption, the searching criteria can be constructed by only simple combinations of keywords, for example, disjunction of keywords. The recent breakthrough in fully homomorphic encryption has allowed us to construct arbitrary searching criteria theoretically. In this paper, we consider a new private query, which searches for documents from streaming data on the basis of keyword frequency, such that the frequency of a keyword is required to be higher or lower than a given threshold. This form of query can help us in finding more relevant documents. Based on the state of the art fully homomorphic encryption techniques, we give disjunctive, conjunctive, and complement constructions for private threshold queries based on keyword frequency. Combining the basic constructions, we further present a generic construction for arbitrary private threshold queries based on keyword frequency. Our protocols are semantically secure as long as the underlying fully homomorphic encryption scheme is semantically secure.

The Ihara limit (or constant) A(q) has been a central problem of study in the asymptotic theory of global function fields (or equivalently, algebraic curves over finite fields). It addresses global function fields with many rational points and, so far, most applications of this theory do not require additional properties. Motivated by recent applications, we require global function fields with the additional property that their zero class divisor groups contain at most a small number of d -torsion points. We capture this with the notion of torsion limit, a new asymptotic quantity for global function fields. It seems that it is even harder to determine values of this new quantity than the Ihara constant. Nevertheless, some nontrivial upper bounds are derived. Apart from this new asymptotic quantity and bounds on it, we also introduce Riemann-Roch systems of equations. It turns out that this type of equation system plays an important role in the study of several other problems in each of these areas: arithmetic secret sharing, symmetric bilinear complexity of multiplication in finite fields, frameproof codes, and the theory of error correcting codes. Finally, we show how our new asymptotic quantity, our bounds on it and Riemann-Roch systems can be used to improve results in these areas.

Erasure list decoding was introduced to correct a larger number of erasures by outputting a list of possible candidates. In this paper, we consider both random linear codes and algebraic geometry codes for list decoding from erasures. The contributions of this paper are twofold. First, for arbitrary 00 (R and ϵ are independent), we show that with high probability a q-ary random linear code of rate R is an erasure list-decodable code with constant list size qO(1/ϵ)that can correct a fraction 1 - R - ϵ of erasures, i.e., a random linear code achieves the information-theoretic optimal tradeoff between information rate and fraction of erasures. Second, we show that algebraic geometry codes are good erasure list-decodable codes. Precisely speaking, a q-ary algebraic geometry code of rate R from the Garcia-Stichtenoth tower can correct 1 - R - (1/√q - 1) + (1/q) - ϵ fraction of erasures with list size O(1/ϵ). This improves the Johnson bound for erasures applied to algebraic geometry codes. Furthermore, list decoding of these algebraic geometry codes can be implemented in polynomial time. Note that the code alphabet size q in this paper is constant and independent of ϵ.

We present new families of access structures that, similarly to the multilevel and compartmented access structures introduced in previous works, are natural generalizations of threshold secret sharing. Namely, they admit ideal linear secret sharing schemes over every large enough finite field, they can be described by a small number of parameters, and they have useful properties for the applications of secret sharing. The use of integer polymatroids makes it possible to find many new such families and it simplifies in great measure the proofs for the existence of ideal secret sharing schemes for them.

It has been a great challenge to construct new quantum maximum-distance-separable (MDS) codes. In particular, it is very hard to construct the quantum MDS codes with relatively large minimum distance. So far, except for some sparse lengths, all known q-ary quantum MDS codes have minimum distance ≤q/2 + 1. In this paper, we provide a construction of the quantum MDS codes with minimum distance >q/2 + 1. In particular, we show the existence of the q-ary quantum MDS codes with length n = q2+ 1 and minimum distance d for any d q + 1 (this result extends those given in the works of Guardia (2011), Jin et al. (2010), and Kai an Zhu (2012)); and with length (q2+ 2)/3 and minimum distance d for any d (2q+2)/3 if 3|(q + 1). Our method is through Hermitian selforthogonal codes. The main idea of constructing the Hermitian self-orthogonal codes is based on the solvability in Fqof a system of homogenous equations over Fq2.

We improve lower bounds on the k th-order nonlinear complexity of pseudorandom sequences over finite fields, including explicit inversive sequences and sequences obtained from Hermitian function fields, and we establish a probabilistic result on the behavior of the k th-order nonlinear complexity of random sequences over finite fields.

We consider Reed-Solomon (RS) codes whose evaluation points belong to a subfield, and give a linear-algebraic list decoding algorithm that can correct a fraction of errors approaching the code distance, while pinning down the candidate messages to a well-structured affine space of dimension a constant factor smaller than the code dimension. By pre-coding the message polynomials into a subspace-evasive set, we get a Monte Carlo construction of a subcode of Reed-Solomon codes that can be list decoded from a fraction (1-R-ε) of errors in polynomial time (for any fixed ε > 0) with a list size of O(1/ε). Our methods extend to algebraic-geometric (AG) codes, leading to a similar claim over constant-sized alphabets. This matches parameters of recent results based on folded variants of RS and AG codes. but our construction here gives subcodes of Reed-Solomon and AG codes themselves (albeit with restrictions on the evaluation points).

Every biuniform matroid is representable over all sufficiently large fields. But it is not known exactly over which finite fields they are representable, and the existence of efficient methods to find a representation for every given biuniform matroid has not been proved. The interest of these problems is due to their implications to secret sharing. The existence of efficient methods to find representations for all biuniform matroids is proved here for the first time. The previously known efficient constructions apply only to a particular class of biuniform matroids, while the known general constructions were not proved to be efficient. In addition, our constructions provide in many cases representations over smaller finite fields.

Let μq2(n,k) denote the minimum number of multiplications required to compute the coefficients of the product of two degree n k - 1 polynomials modulo the kth power of an irreducible polynomial of degree n over the q2element field \BBF q2. It is shown that for all odd q and all n = 1,2,..., liminfk → ∞[( μq2(n,k))/ k n] ≤ 2 (1 + [ 1/( q - 2)] ). For the proof of this upper bound, we show that for an odd prime power q, all algebraic function fields in the Garcia-Stichtenoth tower over \BBF q2have places of all degrees and apply a Chudnovsky like algorithm for multiplication of polynomials modulo a power of an irreducible polynomial.

We consider the class of secret sharing schemes where there is no a priori bound on the number of players n but where each of the n share-spaces has fixed cardinality q. We show two fundamental lower bounds on the threshold gap of such schemes. The threshold gap g is defined as r-t, where r is minimal and t is maximal such that the following holds: for a secret with arbitrary a priori distribution, each r-subset of players can reconstruct this secret from their joint shares without error ( r-reconstruction) and the information gain about the secret is nil for each t-subset of players jointly ( t-privacy). Our first bound, which is completely general, implies that if , then g ≥ [( n-t+1)/q] independently of the cardinality of the secret-space. Our second bound pertains to \BBF q-linear schemes with secret-space \BBF qk( k ≥ 2). It improves the first bound when k is large enough. Concretely, it implies that g ≥ [( n-t+1)/ q]+f(q,k,t,n), for some function f that is strictly positive when k is large enough. Moreover, also in the \BBF q-linear case, bounds on the threshold gap independent of t or r are obtained by additionally employing a dualization argument. As an application of our results, we answer an open question about the asymptotics of arithmetic secret sharing schemes and prove that the asymptotic optimal corruption tolerance rate is strictly smaller than 1.

There have been various constructions of classical codes from polynomial valuations in literature [2], [7], [8], [10], [11]. In this paper, we present a construction of classical codes based on polynomial construction again. One of the features of this construction is that not only the classical codes arisen from the construction have good parameters, but also quantum codes with reasonably good parameters can be produced from these classical codes. In particular, some new quantum codes are constructed (see Examples V.5 and V.6).

In this invited talk,1we introduce the notion of arithmetic codex, or codex for short. It encompasses several well-established notions from cryptography (arithmetic secret sharing schemes, which enjoy additive as well as multiplicative properties) and algebraic complexity theory (bilinear complexity of multiplication) in a natural mathematical framework. Arithmetic secret sharing schemes have important applications to secure multi-party computation and even to two-party cryptography. Interestingly, several recent applications to two-party cryptography rely crucially on the existing results on “asymptotically good families” of suitable such schemes. Moreover, the construction of these schemes requires asymptotically good towers of function fields over finite fields: no elementary (probabilistic) constructions are known in these cases. Besides introducing the notion, we discuss some of the constructions, as well as some limitations.

We give a new construction of algebraic codes which are efficiently list decodable from a fraction 1-R-ε of adversarial errors where R is the rate of the code, for any desired positive constant ε. The worst-case list size output by the algorithm is O(1/ε), matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on ε --- it can be made exp(~O(1/ε2)) which is not much worse than the non-constructive exp(1/ε) bound of random codes. The code construction is Monte Carlo and has the claimed list decoding property with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time Oε(Nc) for an absolute constant $c$, where N is the code's block length. Our construction is based on a careful combination of a linear-algebraic approach to list decoding folded codes from towers of function fields, with a special form of subspace-evasive sets. Instantiating this with the explicit "asymptotically good" Garcia-Stichtenoth (GS for short) tower of function fields yields the above parameters. To illustrate the method in a simpler setting, we also present a construction based on Hermitian function fields, which offers similar guarantees with a list-size and alphabet size polylogarithmic in the block length N.

In the present paper, we generalize the ideas of code constructions from our previous papers . It turns out that the codes in the previous papers can be viewed as special cases of those in this paper. Moreover, our constructions produce some good codes in terms of their parameters. In particular, some best-known codes can be obtained through our methods. Furthermore, our constructions are explicit and the codes can be easily implemented as shown in the tables of Appendix. Besides, one new code, i.e., a 4-ary [64,15,31]-linear code, is found through our constructions.

In the present paper, we show that if the dimension of an arbitrary algebraic geometry code over a finite field of even characteristic is slightly less than n/2-g with n being the length of the code and g being the genus of the base curve, then it is equivalent to an Euclidean self-orthogonal code. Previously, such results required a strong condition on the existence of a certain differential. We also show a similar result on Hermitian self-orthogonal algebraic geometry codes. As a consequence, we can apply our result to quantum codes and obtain some good quantum codes. In particular, we obtain a q-ary quantum [[q+1,1]]-MDS code for an even power q which is essential for quantum secret sharing.

In 1986, D. V. Chudnovsky and G. V. Chudnovsky first employed algebraic curves over finite fields to construct bilinear multiplication algorithms implicitly through supercodes introduced by Shparlinski-Tsfasman-Vladuţ, or equivalently, multiplication-friendly codes that we will introduce in this paper. This idea was further developed by Shparlinski-Tsfasman-Vladuţ in order to study the asymptotic behavior of multiplication complexity in extension fields. Later on, Ballet et al. further investigated the method and obtained some improvements. Recently, Ballet and Pieltant made use of curves over an extension field of to obtain an improvement on the complexity of multiplications in extensions of the binary field. In this paper, we develop the multiplication-friendly splitting technique and then apply this technique to study asymptotic behavior of multiplications in extension fields. By combining this with the idea of using algebraic function fields, we are able to improve further the asymptotic results of multiplication complexity. In particular, the improvement for small fields such as the binary and ternary fields is substantial.

It is well known that quantum codes can be constructed through classical symplectic self-orthogonal codes. In this paper, we give a kind of Gilbert-Varshamov bound for symplectic self-orthogonal codes first and then obtain the Gilbert-Varshamov bound for quantum codes. The idea of obtaining the Gilbert-Varshamov bound for symplectic self-orthogonal codes follows from counting arguments.

In coding theory, self-dual codes and cyclic codes are important classes of codes which have been extensively studied. The main objects of study in this paper are self-dual cyclic codes over finite fields, i.e., the intersection of these two classes. We show that self-dual cyclic codes of lengthnover \BBFqexist if and only ifnis even andq= 2mwithma positive integer. The enumeration of such codes is also investigated. Whennandqare even, there is always a trivial self-dual cyclic code with generator polynomialxn/2+1. We, therefore, classify the existence of self-dual cyclic codes, for givennandq, into two cases: when only the trivial one exists and when two or more such codes exist. Givennandm, an easy criterion to determine which of these two cases occurs is given in terms of the prime factors ofn, for mostn. We also show that, over a fixed field, the latter case occurs more frequently as the length grows.

By employing algebraic curves, we give some new asymptotic bounds for (q-1)-ary and (q+1)-ary codes, whereq>; 2 is a prime power. In particular, our asymptotic bound for (q-1)-ary codes improves on the bound obtained directly from alphabet restriction given by Tafasman and Vlăduţ , [Th. 1.3.19], while our asymptotic bound for (q+1) -ary codes includes Elkies' result for the squareqcase (STOC 01) (however, the idea in this paper is different from Elkies' one). Our constructions of asymptotically good nonlinear codes are NOT the same as Goppa's construction of algebraic geometry codes in the sense that we consider evaluation of functions at some pole points as well.

This paper proposes some simple propagation rules which give rise to new binary constant-weight codes.

In this paper, we first construct several classes of classical Hermitian self-orthogonal maximum distance separable (MDS) codes. Through these classical codes, we are able to obtain various quantum MDS codes. It turns out that many of our quantum codes are new in the sense that the parameters of our quantum codes cannot be obtained from all previous constructions.

We generalize Steane’s enlargement construction of binary quantum codes to q-ary quantum codes. We then apply this result to BCH codes and the study of asymptotic bounds, and obtain improvements to the quantum BCH codes constructed by Aly and Klappenecker and the quantum asymptotic bounds from algebraic geometry codes obtained by Feng, Ling and Xing.

The stabilizer method for constructing a class of asymmetric quantum codes (AQC), called additive AQC, has been established by Aly et.al. In this paper, we present a new characterization of AQC, which generalizes a result of the symmetric case known previously. As an application of the characterization, we establish a relationship of AQC with classical error-correcting codes and show a few examples of good AQC with specific parameters. By using this relationship, we obtain an asymptotic bound on AQCs from algebraic geometry codes.

In the present paper, by making use of some special properties of the Hermitian function fields, we construct multisequences with both large linear complexity and k-error linear complexity. Moreover, these sequences can be explicitly constructed.

It is a central problem in secret sharing to understand the access structures of secret sharing schemes. In Chen and Kramer, secret sharing schemes from algebraic-geometric codes and their applications in secure multiparty computation were proposed and studied. For any given finite field , these secret sharing schemes are ideal ramp secret sharing schemes and allow arbitrarily many players. In this correspondence, we give the access structures explicitly for the elliptic secret sharing schemes from algebraic-geometric (AG) codes associated with elliptic curves. Based on higher degree rational points on elliptic curves, we also construct some nonideal secret sharing schemes with weighted threshold structures.

In this paper, we reformulate some constructions of real and complex diagonal lattice space-time codes from number fields which have been given explicitly or implicitly by other researchers. These constructions establish a connection between good diagonal lattice space-time codes and number fields with small absolute values of discriminants. We present two tables for diversity products of some lattice space-time codes from these constructions. The maximal rank of diagonal lattice space-time codes with positive diversity product is determined. We also discuss the asymptotic problem of lattice space-time codes. By using an infinite tower of Hilbert class field and a tamely ramified class field tower, we obtain asymptotically good sequences of lattice space-time codes. Some asymptotic upper bounds are given in the paper as well.

In this correspondence, we present 129 new linear codes over F8and F9based on the construction by Xing and Niederreiter using algebraic function fields and places of small degrees. In addition, we construct some global function fields in which the number of rational places improves the lower bounds given by van der Geer and van der Vlugt.

We generalize a characterization of p-ary (p is a prime) quantum codes given by Feng and Xing to q-ary (q is a prime power) quantum codes. This characterization makes it possible to convert an asymptotic bound of Stichtenoth and Xing for nonlinear algebraic geometry codes to a quantum asymptotic bound. Besides, we also investigate the asymptotic behavior of quantum codes

We apply Steane's enlargement of the Calderbank-Shor-Steane (CSS) codes and additive codes over F/sub 4/ to concatenated algebraic-geometric codes to construct many good quantum codes with fewer restrictions on the parameters compared to some known quantum codes. Some of the quantum codes we have constructed are either optimal or have parameters as good as the best known codes, while some have parameters better than those obtained from other known constructions.

The Gilbert-Varshamov (GV) bound for asymptotic families of codes over F/sub q/ has been improved by Tsfasman, Vla/spl breve/dut$80, and Zink (TVZ) in 1982, and only recently further improvements have been obtained by Xing, Elkies, and Niederreiter-O/spl uml/zbudak, by considering also nonlinear codes. These improvements involve higher derivations in function fields and are very computational. We give in this correspondence a much simpler proof for those improvements. Our construction of asymptotically good nonlinear codes is very similar to Goppa's construction of algebraic-geometry codes.

Based on s-zeta-functions of curves over finite fields, we show that Goppa geometry codes achieve the q-ary Gilbert-Varshamov bound for all prime powers q (including q=2).

By employing the narrow ray class groups of algebraic curves, we give a construction of constant weight codes. This construction is a generalization of the one proposed by Xing. It turns out that this generalization gives an improvement on the lower bound of binary constant codes in the earlier work of Xing, while the latter one improves an earlier result of Graham and Sloane.

Optical orthogonal codes (OOCs) have applications in optical code-division multiple-access communications systems and other wideband code-division multiple environments. They can also be used to construct protocol sequences for multiuser collision channel without feedback, and constant-weight codes for error detection and correction. We have given a cyclotomic construction of several classes of (2/sup m/-1,w,2) OOCs recently. The purpose of this paper is to present five classes of (q-1,w,2) OOCs, and thus five classes of binary constant-weight cyclic codes, where q is a power of an odd prime.

We generalize the notions of duadic codes, triadic codes, polyadic codes, and split group codes to include noncyclic Abelian codes. Necessary and sufficient conditions for the existence of such codes, and properties such as a duality property and a lower bound on the minimum weight of the subcode of "odd-like" codewords, are studied. This construction and its modification lead to many good codes, eight of which have minimum distance better than the lower bound given in Brouwer's table.

In this correspondence, we study disjoint linear codes and give constructions of families of disjoint linear codes based on algebraic function fields. It turns out that, for some parameters, our constructions improve on a result of Johansson and Pasalic.

By employing the narrow ray class groups of algebraic curves and the Hurwitz genus formula, we construct a class of linear codes over prime fields with reasonable parameters. In particular, we obtain some new codes compared with Brouwer's table.

We present a construction of linear codes from polynomials. It turns out that some new codes are obtained from our construction and improve parameters of Brouwer's table.

In this correspondence, we study binary asymmetric error-correcting codes. A general construction for binary asymmetric error-correcting codes is presented. We show that some previously known lower bounds for binary asymmetric error-correcting codes can be obtained from this general construction. Furthermore, some new lower bounds for binary asymmetric error-correcting codes are obtained from this general construction. These new lower bounds improve the existing ones.

In this paper, we consider a new class of unconditionally secure authentication codes, called linear authentication codes (or linear A-codes). We show that a linear A-code can be characterized by a family of subspaces of a vector space over a finite field. We then derive an upper bound on the size of the source space when other parameters of the system, that is, the sizes of the key space and the authenticator space, and the deception probability, are fixed. We give constructions that are asymptotically close to the bound and show applications of these codes in constructing distributed authentication systems.

In the present paper, we construct a class of nonlinear codes by making use of higher order derivatives of certain functions of algebraic curves. It turns out that the asymptotic bound derived from the Goppa geometry codes can be improved for the entire interval (0,1). In particular, the Tsfasman-Vladut-Zink (TVZ) bound is ameliorated for the entire interval (0,1).

A general method of generating families of binary sequences with low correlation as well as large linear span is presented. The lower bound on the linear span is on the order of the square root of the period of each sequence within the family. The design makes use of the theory of function fields. Two example applications of this method are presented in which the underlying function fields are the rational and elliptic function fields respectively.

Irreducible cyclic codes have been an interesting subject of study for many years. The weight distribution of some of them have been determined. We determine the minimum distance and certain weights of the duals of binary irreducible cyclic codes. We show that the weight distribution of these codes is determined by the cyclotomic numbers of certain order. As a byproduct, we describe a class of double-error correcting codes.

Many new binary linear codes (compared with Brouwer's (2000) table) are found from a construction based on algebraic curves over finite fields.

We study the asymptotic behavior of frameproof codes. Some lower bounds are derived from the theory of error-correcting codes. In particular, the lower bound obtained directly by applying algebraic-geometry codes is improved by employing the Jacobian group structure of algebraic curves.

We present one construction for nonlinear codes and one construction for binary constant-weight codes based on residue rings of polynomials. It turns out that the first construction yields nonlinear codes with reasonable parameters, and a bound of Graham and Sloane (1980) is improved by the second construction.

By choosing specific divisors, we show that some algebraic-geometry (AG) codes from the Hermitian curves have better parameters than one-point Hermitian codes. The general lower bound is discussed.

It is known that quantum error correction can be achieved using classical binary codes or additive codes over F/sub 4/. Asymptotically good quantum codes have been constructed from algebraic-geometry codes and a bound on (/spl delta/, R) was computed from the Tsfasman-Vladut-Zink bound of the theory of classical algebraic-geometry codes. In this correspondence, by the use of a concatenation technique we construct a family of asymptotically good quantum codes exceeding the bound in a small interval.

In this correspondence, we show that both the Gilbert-Varshamov and the Tsfasman-Vladut-Zink bounds can be improved by Goppa geometric codes around two points where these two bounds intersect.

Based on a construction of Xing, Niederreiter, and Lam (see ibid., vol.45, p.2498-2501, 1999), some new linear codes are found from suitable algebraic curves over finite fields. These codes have better parameters compared with Brouwer's table.

A class of linear codes with good parameters is constructed in this correspondence. It turns out that linear codes of this class are subcodes of the subfield subcodes of Goppa's geometry codes. In particular, we find 61 improvements on Brouwer's table based on our codes.

A construction of linear codes with good parameters is given. Based on Brouwer's table, more than 100 new codes are obtained from our construction.

We present a new application of algebraic curves over finite fields to the constructions of universal hash families and unconditionally secure codes. We show that the constructions derived from the Garcia-Stichtenoth curves yield new classes of authentication codes and universal hash families which are substantially better than those previously known.

In this paper we present a binary-tree approach to the construction of all binary duadic codes of length n = pm . We also calculate the number of binary duadic codes of length n = pm , where p ≡ +1 (mod 8) is a prime.

For stream ciphers, we need to generate pseudorandom sequences which are of properties of unpredictability and randomness. A important measure of unpredictability and randomness is the linear complexity profile (l.c.p.) l/sub a/(n) of a sequence a. A sequence a is called almost perfect if the l.c.p. is l/sub a/(n)=n/2+O(1). Based on curves over finite fields, we present a method to construct almost perfect sequences. We also illustrate our construction by explicit examples from the projective line and elliptic curves over the binary field.

Based on curves over finite fields with many rational points, we present two constructions of linear codes from local expansions of functions at a fixed rational point. It turns out that codes from our constructions have the same bound on their parameters as Goppa's (1981) geometry codes. Furthermore, we prove that our second construction is equivalent to Goppa's construction. Finally, an additional construction of linear codes from maximal curves shows that these codes have better parameters than Goppa's geometry codes from maximal curves for a certain interval of parameters.

A generalization of algebraic-geometry codes based on function fields over finite fields with many places of small degree is presented. It turns out that many good linear codes can be obtained from these generalized algebraic-geometry codes. In particular, we calculate some examples of q-ary linear codes for q=2,3, 5. These examples show that many best possible linear codes can be found from our construction.

We determine the exact automorphism groups of the Goppa geometric codes from the Hermitian curves over GF(q/sup 2/).

Sufficient and necessary conditions are obtained for which the geometric Goppa codes C(D,G) and C(D,H) are equal for two divisors G and H. In particular, it is proven that if G and H are two effective divisors of the same degree smaller than n-1, then C(D,G) and C(D,H) are equal, if and only if G=H.>