In this paper, we study algebraic geometry (AG) codes with respect to the Lee metric. We determine a new lower bound on the minimum Lee distance of AG codes. Using the AG codes, we construct non-linear binary codes that can correct deletions and insertions of zero-symbols.

MDS codes with determined Hermitian hull dimensions have attracted significant attention for their application in quantum error correction. From an MDS code over Fq2with fixed Hermitian hull dimension ℓ, whereqis a prime power larger than 2, one can obtain an MDS code with any smaller ℓ′-dimensional Hermitian hull for 0 ≤ ℓ′ ≤ ℓ. Then it is natural to consider the problem of determining the maximum Hermitian hull dimension, denoted byLq(n, k), among all MDS codes with the same lengthnand dimensionkover Fq2. Some constructions of Hermitian self-orthogonal generalized Reed-Solomon (GRS) codes had been proposed, which addressed this problem for certain parameter regimes. However, it is still unknown for many cases, in particular fork≥q+ 1. In this paper, we study the Hermitian hulls of a class of codes which generalizes GRS codes, called twisted generalized Reed-Solomon (TGRS) codes. TGRS codes contain MDS subclasses that are not linearly equivalent to GRS codes (called non-GRS codes). We give a bound on the Hermitian hull dimensions of certain TGRS codes of general twists. In addition, we derive a lower bound onLq(n, k) forn|q2− 1 and 1 ≤k≤n, which generalizes and improves some previous results. For some parameter regimes wheren≥q+ 1 andk≥q+ 1, we prove thatLq(n, k) ≥k/2 and explicitly construct [n, k]q2MDS codes whose Hermitian hulls have dimension at leastk/2. This result solves partially an open problem pointed out in the literature. The constructed MDS codes arise from either GRS or non-GRS TGRS codes. Furthermore, some sufficient conditions for TGRS codes with general twists to be Hermitian self-orthogonal are given, and Hermitian self-orthogonal non-GRS MDS codes are constructed. Based on our constructions, we provide several families of MDS entanglement-assisted quantum error-correcting codes.

Sum-rank codes have wide applications in multishot network coding, distributed storage and the construction of space-time codes. Asymptotically good sequences of linearized algebraic geometry sum-rank codes, exceeding the Gilbert-Varshamov-like bound, were constructed in a recent paper published in IEEE Trans. Inf. Theory by E. Berardini and X. Caruso. We call this bound the Tsfasman-Vlăduţ-Zink-like bound. In this paper, we introduce the concatenation of a sum-rank code and a Hamming metric code. Then many sum-rank codes with good parameters, which are better than sum-rank BCH codes, are constructed simply and explicitly. Moreover, we obtain an asymptotically good sequence of sum-rank codes exceeding the Tsfasman-Vlăduţ-Zink-like bound and the Gilbert-Varshamov-like bound.

In a recent work, quantum locally recoverable codes (qLRCs) have been introduced for their potential application in large-scale quantum data storage and implication for quantum LDPC codes. This work focuses on the bounds and constructions of qLRCs derived from the Hermitian construction, which solves an open problem proposed by Luo $et~al.$ (IEEE Trans. Inf. Theory, 71 (3): 1794-1802, 2025). We present four bounds for qLRCs and give comparisons in terms of their asymptotic formulas. We construct several new infinite families of NMDS codes, with general and flexible dimensions, that support t-designs for $t\in \{2,3\}$, and apply them to obtain Hermitian dual-containing classical LRCs (cLRCs). As a result, we derive three explicit families of optimal qLRCs. Compared to the known qLRCs obtained by the CSS construction, our optimal qLRCs offer new and more flexible parameters. It is also worth noting that the constructed cLRCs themselves are interesting as they are optimal with respect to four distinct bounds for cLRCs.

The existence of optimal binary self-orthogonal codes has been well characterized. In this paper, we develop general methods involving residual codes and the MacWilliams identities to prove the nonexistence of several infinite families of binary self-orthogonal codes, despite the existence of binary linear codes with the same parameters. In particular, we focus on the largest minimum distances of optimal binary self-orthogonal codes with dimension eight.

Motivated by the Hermitian construction of quantum codes using classical linear codes as ingredients, we study the Hermitian hulls of two-point rational algebraic geometry (AG) codes Cℒ(D,G) with G = (k−1)O+rP for some positive integers k and r. We provide a lower bound on their Hermitian hull dimensions. Specifically, we prove that under certain conditions, the Hermitian hull dimensions of such AG codes are lower bounded by k−1−r, giving rise to linear codes of Hermitian hull dimension k−r−1 by some propagation rules. As an application, we derive two families of entanglement-assisted quantum error-correcting codes with new parameters.

Quasi-twisted codes are used here as the classical ingredients in the so-called Construction X for quantum error-control codes. The construction utilizes nearly self-orthogonal codes to design quantum stabilizer codes. We expand the choices of the inner product to also cover the symplectic and trace-symplectic inner products, in addition to the original Hermitian one. A refined lower bound on the minimum distance of the resulting quantum codes is established and illustrated. We report numerous record breaking quantum codes from our randomized search for inclusion in the updated online database.

A code is called a punctured concatenated code if it can be obtained by puncturing a concatenated code at suitable coordinates. Based on this new concept, we construct several classes of optimal or almost optimal linear codes. There are two major contributions in this paper. Let the inner code be an [n,m]qlinear code derived from the defining setD= {d1,d2, . . . ,dn}. On the one hand, by employing a maximum distance separable (MDS) code with dimension 2 over Fqmas the outer code, we propose two classes of linear codes with few weights. The duals of these codes are shown to be dimension-optimal with respect to the sphere-packing bound. On the other hand, letq= 2, by choosing an MDS code with dimension 3 over F2mas the outer code, we construct another class of linear codes. The parameters and weight distributions of these codes are completely determined. Furthermore, their dual codes are almost distance-optimal with respect to the sphere-packing bound.

A binary linear code is calledasymptotic frame error rate (AFER)-optimalif it achieves the maximum possible value of the minimum distance while having the smallest value of the corresponding error coefficient. Over the additive white Gaussian noise channel and under maximum-likelihood decoding, AFER-optimal codes attain the best possible asymptotic frame error rate at high signal-to-noise ratio. In this paper, we present several bounds on the smallest error coefficients of binary linear codes and give several constructions of AFER-optimal binary linear codes. Many examples confirm that our bounds are sharp on numerous occasions. In addition, we give two families of AFER-optimal codes that respectively attain the proposed bounds with equality.

Carlet et al. showed that for$q\gt 2$, there exists a q-ary linear complementary pair (LCP) of codes whose security parameter is as good as the minimum distance of the best linear code with the same length and dimension. In this paper, we study the best security parameters of binary LCPs of codes. As a result, we solve an open problem proposed by Carlet et al. (IEEE Trans. Inf. Theory 65(3): 1694-1704, 2019) and a conjecture proposed by Choi et al. (Cryptogr. Commun. 15(2): 469-486, 2023).

The hull of a linear code over a finite field is the intersection of the code and its dual, which was introduced by Assmus and Key to classify finite projective planes. The main objective of this paper is to obtain a closed mass formula for linear codes with prescribed hull dimension. We simplify the mass formula obtained by Sendrier and provide an alternative proof for the mass formula for self-orthogonal codes obtained by Pless. Finally, we obtain a classification of (optimal) ternary linear codes with small parameters.

Classical locally recoverable codes (LRCs) have become indispensable in distributed storage systems. They provide efficient recovery in terms of localized errors. Quantum LRCs have very recently been introduced for their potential application in quantum data storage. In this paper, we use classical LRCs to investigate quantum LRCs. We prove that the parameters of quantum LRCs are bounded by their classical counterparts. We deduce bounds on the parameters of quantum LRCs from bounds on the parameters of the classical ones. We establish a characterization of optimal pure quantum LRCs based on classical codes with specific properties. Using well-crafted classical LRCs as ingredients in the construction of quantum CSS codes, we offer the first construction of several families of optimal pure quantum LRCs.

Matrix product codes are generalizations of some well-known classes of codes, including generalized Reed-Muller codes and repeated-root constacyclic codes. Recently, a bound for the minimum symbol-pair distance of a matrix product code was given by (Luo et al., 2023), leading to the creation of new families of MDS symbol-pair codes. In this paper, we provide lower and upper bounds for the minimum b-symbol distance of matrix product codes, which naturally extends some of the results by (Luo et al., 2023). Examples meeting the bounds are included to illustrate our results. As an initial application of these new bounds, we establish that constacyclic codes (repeated-root or otherwise) meeting specific criteria can indeed be classified as matrix product codes, and present bounds on the minimum b-symbol distance of such constacyclic codes. Additionally, we determine all the minimum b-symbol distances of Reed-Muller codes as a secondary application of the new bounds.

We craft a special class of unitary matrices over$\mathbb{F}q^{2}$to generate classical linear codes whose Hermitian hulls have dimensions that we can design. We then use the codes as classical ingredients in the construction of good entanglement-assisted quantum codes. Over finite fields of characteristic 2, we propose two explicit constructions. To highlight their efficacy, we list excellent qubit codes whose parameters are either new or strictly better than comparable best-known codes in the literature.

We study the Hermitian hulls of two-point algebraic geometry codes. Under specific conditions on the Weil differential form associated with the Hermitian dual code, we explicitly determine the hull dimension. We construct k-dimensional linear codes, whose Hermitian hulls have dimension$k-2$, from some algebraic plane curves.

We study the Hermitian hulls of matrix product codes and use them to design linear codes with arbitrary hull dimensions. We continue by looking into some propagation rules that preserve the hull dimensions of$\mathbb{F}_{4}$-linear codes. We propose a recursive method to keep the Hermitian hull dimension fixed while increasing the dimensions or the minimum distances of codes built from a given$\mathbb{F}_{4}$-linear code. Using the Hermitian construction route, we derive good entanglement-assisted quantum codes from matrix product codes and recursively iterated codes.

Motivated by applications in distributed storage, distributed computing, and homomorphic secret sharing, we study communication-efficient schemes for computing linear combinations of coded symbols. Specifically, we design low-bandwidth schemes that evaluate the weighted sum of ℓ coded symbols in a codewordc∈ Fn, when we are given access todof the remaining components inc. Formally, suppose that F is a field extension of B of degreet. Letcbe a codeword in a Reed-Solomon code of dimensionkand our task is to compute the weighted sum of ℓ coded symbols. In this paper, for somest, we provide an explicit scheme that performs this task by downloadingd(t-s) sub-symbols in B fromdavailable nodes, wheneverd≥ ℓ|B|s-ℓ +k. In many cases, our scheme outperforms previous schemes in the literature. Furthermore, we provide a characterization of evaluation schemes for general linear codes. Then in the special case of Reed-Solomon codes, we use this characterization to derive a lower bound for the evaluation bandwidth.

The number of nonzero weights of a linear code is essential in coding theory as it unveils salient properties of the code, such as its covering radius. In this paper, we establish two upper bounds on the number of nonzero weights of a linear code with prescribed automorphism. Our bounds are applicable for almost all linear codes and tighter than previously known bounds. Examples confirm that our bounds are sharp on numerous occasions. In addition, we give an infinite family of linear codes that attain our bounds with equality.

The b-symbol metric is a generalization of the Hamming metric. Linear codes in the b-symbol metric have been used in the read channel whose outputs consist of b consecutive symbols. The Griesmer bound outperforms the Singleton bound for${\mathbb {F}}_{q}$-linear codes in the Hamming metric, when q is fixed and the length is large enough. This scenario is also applicable in the b-symbol metric. Shi, Zhu, and Helleseth recently made a conjecture on cyclic codes in the b-symbol metric. In this paper, we present the b-symbol Griesmer bound for linear codes by concatenating linear codes and simplex codes. Based on cyclic codes and extended cyclic codes, we propose two families of distance-optimal linear codes with respect to the b-symbol Griesmer bound.

Spectral bounds form a powerful tool to estimate the minimum distances of quasi-cyclic codes. They generalize the defining set bounds of cyclic codes to those of quasi-cyclic codes. Based on the eigenvalues of quasi-cyclic codes and the corresponding eigenspaces, we provide an improved spectral bound for quasi-cyclic codes. Numerical results verify that the improved bound outperforms the Jensen bound in almost all cases. Based on the improved bound, we propose a general construction of quasi-cyclic codes with excellent designed minimum distances. For the quasi-cyclic codes produced by this general construction, the improved spectral bound is always sharper than the Jensen bound.

Hermitian hulls of linear codes are interesting for theoretical and practical reasons alike. In terms of recent application, linear codes whose hulls meet certain conditions have been utilized as ingredients to construct entanglement-assisted quantum error correcting codes. This family of quantum codes is often seen as a generalization of quantum stabilizer codes. Theoretically, compared with the Euclidean setup, the Hermitian case is much harder to deal with. Hermitian hulls of MDS linear codes with low dimensions have been explored, mostly from generalized Reed-Solomon codes. Characterizing Hermitian hulls which themselves are MDS appears to be more involved and has not been extensively studied. This paper introduces some tools to study linear codes whose Hermitian hulls are MDS. Using the tools, we then propose explicit constructions of such codes. We consider Hermitian hulls of both Reed-Solomon and non Reed-Solomon types of linear MDS codes. We demonstrate that, given the same Hermitian hull dimensions, the codes from our constructions have dimensions which are larger than those in the literature.

Motivated by applications in distributed storage, distributed computing, and homomorphic secret sharing, we study communication-efficient schemes for computing linear combinations of coded symbols. Specifically, we design low-bandwidth schemes that evaluate the weighted sum of ℓ coded symbols in a codeword ${\mathbf{c}} \in {\mathbb{F}^n}$, when we are given access to d of the remaining components in c. Formally, suppose that $\mathbb{F}$ is a field extension of $\mathbb{B}$ of degree t. Let c be a codeword in a Reed-Solomon code of dimension k and our task is to compute the weighted sum of ℓ coded symbols. In this paper, for some s < t, we provide an explicit scheme that performs this task by downloading d(t − s) sub-symbols in $\mathbb{B}$ from d available nodes, whenever $d \geq \ell |\mathbb{B}{|^s} - \ell + k$. In many cases, our scheme outperforms previous schemes in the literature. Furthermore, we provide a characterization of evaluation schemes for general linear codes. Then in the special case of Reed-Solomon codes, we use this characterization to derive a lower bound for the evaluation bandwidth.

We consider the repair scheme of Guruswami-Wootters for the Reed-Solomon code and ask: can we correctly repair a failed node in the presence of erroneous nodes? Equivalently, we consider the collection of downloaded traces as a code and investigate its code-distance properties. We propose three lower bounds on its minimum distance and study methods to efficiently correct errors close to these bounds.

Abstract An accumulator is a function that hashes a set of inputs into a short, constant-size string while preserving the ability to efficiently prove the inclusion of a specific input element in the hashed set. It has proved useful in the design of numerous privacy-enhancing protocols, in order to handle revocation or simply prove set membership. In the lattice setting, currently known instantiations of the primitive are based on Merkle trees, which do not interact well with zero-knowledge proofs. In order to efficiently prove the membership of some element in a zero-knowledge manner, the prover has to demonstrate knowledge of a hash chain without revealing it, which is not known to be efficiently possible under well-studied hardness assumptions. In this paper, we provide an efficient method of proving such statements using involved extensions of Stern’s protocol. Under the Small Integer Solution assumption, we provide zero-knowledge arguments showing possession of a hash chain. As an application, we describe new lattice-based group and ring signatures in the random oracle model. In particular, we obtain: (i) the first lattice-based ring signatures with logarithmic size in the cardinality of the ring and (ii) the first lattice-based group signature that does not require any GPV trapdoor and thus allows for a much more efficient choice of parameters.

Let${\mathrm{ RS}}_{k}(\mathbf {a})$be a$k$-dimensional Reed-Solomon (RS) code over$\mathbb {F}_{q}$associated with$\mathbf {a}=(\alpha _{1},\cdots,\alpha _{n})$and let$h=\prod _{i=1}^{n}(z-\alpha _{i})$be a polynomial in variable$z$. In this paper, by expressing${\mathrm{ RS}}_{k}(\mathbf {a})$as an$\mathcal {L}$-construction algebraic geometry code, we completely determine the dimension of the hull${\mathrm{ RS}}_{k}(\mathbf {a})\bigcap {\mathrm{ RS}}_{k}(\mathbf {a})^{\perp} $in terms of the degree of the derivative of$h$and some relevant polynomials. As applications, we explicitly determine the parameters of MDS entanglement-assisted quantum error-correcting codes constructed from RS codes, and all linear complementary dual (resp. self-dual) RS codes are also fully described.

Convolutional codes are essential in a wide range of practical applications due to their efficient non-algebraic decoding algorithms. In this paper, we first propose a new family of matrices over finite fields by combining Vandermonde and Moore matrices. Using favourable properties of the matrices in this new family enables us to construct a new family of convolutional codes with memory 1 and maximum distance profile. It is notable that the alphabet sizes of this new family of convolutional codes with maximum distance profile can be kept significantly smaller than those in the literature. Keeping the code rate to a constant, the alphabet size is roughly the square root of the previously best-known value.

Locally repairable codes have become a key instrument in large-scale distributed storage systems. This paper focuses on the construction of locally repairable codes with$(r,\delta)$-locality that achieve equality in the Singleton-type bound. We use matrix-product codes to propose two constructions of$q$-ary optimal$(r,\delta)$locally repairable codes of lengths up to$q^{2}+q$. The ingredients in the matrix-product codes are linear maximum distance separable codes. We give another construction of optimal$(r,\delta)$locally repairable codes by using optimal locally repairable codes as ingredients in the matrix-product approach. The codes in this third construction have unbounded lengths not divisible by$(r+\delta -1)$. The three constructions of optimal$(r,\delta)$locally repairable codes constructed here are new. Previously constructed codes in the literature have not covered the same sets of parameters. Our construction proposals are flexible since one can easily vary$r$and$\delta $to come up with particular parameters that can suit numerous scenarios.

In emerging storage technologies, the outputs of the channels consist of overlapping pairs of symbols. The errors are no longer individual symbols. Controlling them calls for a different approach. Symbol-pair codes have been proposed as a solution. The error-correcting capability of such a code depends on its minimum pair distance instead of the usual minimum Hamming distance. Longer codes can be conveniently constructed from known shorter ones by a matrix-product approach. The parameters of a matrix-product code can be determined from the parameters of the ingredient codes. We construct a new family of maximum distance separable (MDS) symbol-pair matrix-product codes. Codes which are permutation equivalent to matrix-product codes may have improved minimum pair distances. We present four new families of MDS symbol-pair codes and a new family of almost MDS symbol-pair codes. The codes in these five new families are permutation equivalent to matrix-product codes. Each of our five constructions identifies permutations that can increase the minimum pair distances. We situate the new families among previously known families of MDS symbol-pair codes to highlight the versatility of our matrix-product construction route.

Holographic representations of data enable distributed storage with progressive refinement when the stored packets of data are made available in any arbitrary order. In this paper, we propose and test patch-based transform coding holographic sensing of image data. Our proposal is optimized for progressive recovery under random order of retrieval of the stored data. The coding of the image patches relies on the design of distributed projections ensuring best image recovery, in terms of the $\ell_2$ norm, at each retrieval stage. The performance depends only on the number of data packets that have been retrieved thus far. Several possible options to enhance the quality of the recovery while changing the size and number of data packets are discussed and tested. This leads us to examine several interesting bit-allocation and rate-distortion trade-offs, highlighted for a set of natural images with ensemble estimated statistical properties.

Spectral bounds on the minimum distance of quasi-twisted codes over finite fields are proposed, based on eigenvalues of polynomial matrices and the corresponding eigenspaces. They generalize the Semenov-Trifonov and Zeh-Ling bounds in a way similar to how the Roos and shift bounds extend the BCH and HT bounds for cyclic codes. The eigencodes of a quasi-twisted code in the spectral theory and the outer codes in its concatenated structure are related. A comparison based on this relation verifies that the Jensen bound always outperforms the spectral bound under special conditions, which yields a similar relation between the Lally and the spectral bounds. The performances of the Lally, Jensen and spectral bounds are presented in comparison with each other.

A robust positioning pattern is a large array that allows a mobile device to locate its position by reading a possibly corrupted small window around it. In this paper, we provide constructions of binary positioning patterns, equipped with efficient locating algorithms, that are robust to a constant number of errors and have redundancy within a constant factor of optimality. Furthermore, we modify our constructions to correct rank errors and obtain binary positioning patterns robust to any errors of rank less than a constant number. Additionally, we construct $q$-ary robust positioning sequences robust to a large number of errors, some of which have length attaining the upper bound. Our construction of binary positioning sequences that are robust to a constant number of errors has the least known redundancy among those explicit constructions with efficient locating algorithms. On the other hand, for binary robust positioning arrays, our construction is the first explicit construction whose redundancy is within a constant factor of optimality. The locating algorithms accompanying both constructions run in time cubic in sequence length or array dimension.

In this paper, we present a lightweight hardware design for a recently proposed quantum-safe key encapsulation mechanism based on QC-LDPC codes called LEDAkem, which has been admitted as a round-2 candidate to the NIST post-quantum standardization project. Existing implementations focus on high speed while few of them take into account area or power efficiency, which are particularly decisive for low-cost or power constrained IoT applications. The solution we propose aims at maximizing the metric of area efficiency by rotating the QC-LDPC code representations amongst the block RAMs in digit level. Moreover, optimized parallelized computing techniques, lazy accumulation and block partition are exploited to improve key decapsulation in terms of area and timing efficiency. We show for instance that our area-optimized implementation for 128-bit security requires 6.82 x 105 cycles and 2.26 x 106 cycles to encapsulate and decapsulate a shared secret, respectively. The area-optimized design uses only 39 slices (3 percent of the available logic) and 809 slices (39 percent of the available logic) for key encapsulation and key decapsulation respectively, on a small-size low-end Xilinx Spartan-6 FPGA.

Permutation codes and multipermutation codes are widely studied due to various applications in information theory. Designing codes correcting deletion errors has been the main subject of works in the literature and to the best of our knowledge, there exist only optimal codes capable of correcting a single deletion in a permutation. In this paper, we construct several classes of permutation and multipermutation codes that are capable of correcting a burst deletion of length s ≥ 2, for both stable and unstable models. Efficient error decoders are provided to show the correctness of our constructions.

We solve an open question in code-based cryptography by introducing two provably secure group signature schemes from code-based assumptions. Our basic scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. The construction produces smaller key and signature sizes than the previous group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed 224, which is roughly comparable to the current population of the Netherlands. We develop the basic scheme further to achieve the strongest anonymity notion, i.e., CCA-anonymity, with a small overhead in terms of efficiency. The feasibility of two proposed schemes is supported by implementation results. Our two schemes are the first in their respective classes of provably secure groups signature schemes. Additionally, the techniques introduced in this work might be of independent interest. These are a new verifiable encryption protocol for the randomized McEliece encryption and a novel approach to design formal security reductions from the Syndrome Decoding problem.

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.

We apply quantum Construction X on quasi-cyclic codes with large Hermitian hulls over F4and F9to derive good qubit and qutrit stabilizer codes, respectively. In several occasions we obtain quantum codes with stricly improved parameters than the current record. In numerous other occasions we obtain quantum codes with best-known performance. For the qutrit ones we supply a systematic construction to fill some gaps in the literature.

New lower bounds on the minimum distance of quasi-twisted codes over finite fields are proposed. They are based on spectral analysis and eigenvalues of polynomial matrices. They generalize the Semenov-Trifonov and Zeh-Ling bounds in a manner similar to how the Roos and shift bounds extend the BCH and HT bounds for cyclic codes.

Non-malleable codes protect against an adversary who can tamper with the coded message by using a tampering function in a specified function family, guaranteeing that the tampering result will only depend on the chosen function and not the coded message. The codes have been motivated for providing protection against tampering with hardware that stores the secret cryptographic keys, and have found significant attention in cryptography. Traditional Shannon model of communication systems assumes the communication channel is perfectly known to the transmitter and the receiver. Arbitrary Varying Channels (AVCs) remove this assumption and have been used to model adversarially controlled channels. Transmission over these channels has been originally studied with the goal of recovering the sent message, and more recently with the goal of detecting tampering with the sent messages. In this paper we introduce non-malleability as the protection goal of message transmission over these channels, and study binary (discrete memoryless) AVCs where possible tampering is modelled by the set of channel states. Our main result is that non-malleability for these channels is achievable at a rate asymptotically approaching 1. We also consider the setting of an AVC with a special state s*, and the additional requirement that the message must be recoverable if s* is applied to all the transmitted bits. We give the outline of a message encoding scheme that in addition to non-malleability, can provide recovery for all s* channel.

A robust positioning pattern is a large array that allows a mobile device to locate its position by reading a possibly corrupted small window around it. This paper provides constructions of binary positioning patterns, equipped with efficient locating algorithms, that are robust to a constant number of errors and have redundancy within a constant factor of optimality. Our construction of binary robust positioning sequences has the least known redundancy amongst those explicit constructions with efficient locating algorithms. On the other hand, for binary robust positioning arrays, our construction is the first explicit construction whose redundancy is within a constant factor of optimality. The locating algorithms accompanying our constructions run in time cubic in sequence length or array dimensions.

Abstract Efficient user revocation is a necessary but challenging problem in many multi-user cryptosystems. Among known approaches, server-aided revocation yields a promising solution, because it allows to outsource the major workloads of system users to a computationally powerful third party, called the server, whose only requirement is to carry out the computations correctly. Such a revocation mechanism was considered in the settings of identity-based encryption and attribute-based encryption by Qin et al. (2015, ESORICS) and Cui et al. (2016, ESORICS ), respectively. In this work, we consider the server-aided revocation mechanism in the more elaborate setting of predicate encryption (PE). The latter, introduced by Katz et al. (2008, EUROCRYPT), provides fine-grained and role-based access to encrypted data and can be viewed as a generalization of identity-based and attribute-based encryption. Our contribution is 2-fold. First, we formalize the model of server-aided revocable PE (SR-PE), with rigorous definitions and security notions. Our model can be seen as a non-trivial adaptation of Cui et al.’s work into the PE context. Second, we put forward a lattice-based instantiation of SR-PE. The scheme employs the PE scheme of Agrawal et al. (2011, ASIACRYPT) and the complete subtree method of Naor et al. (2001, CRYPTO) as the two main ingredients, which work smoothly together thanks to a few additional techniques. Our scheme is proven secure in the standard model (in a selective manner), based on the hardness of the learning with errors problem.

Public key encryption with equality test (PKEET) is a variant of classical public key encryption (PKE) with the special functionality of an equality test, and can be used in many applications such as in keyword search on encrypted data and for efficient management by partitioning encrypted data in the cloud. Since the original proposal of Yang et al. (CT-RSA, 2010), several subsequent proposals to improve the efficiency or functionality of PKEET have been reported. We present a PKEET construction from generic assumptions in the random oracle model . In particular, whereas previous results require number-theoretic assumptions or strictly stronger generic assumptions such as the existence of secure hierarchical identity-based encryption, our proposal requires only the existence of cryptographic hash functions and secure PKE schemes satisfying a special property , called randomness extractability . Informally, randomness extractability means that one can recover the randomness used in a ciphertext when given a secret key corresponding to a public key for the ciphertext . We investigate the fact that PKE schemes satisfying this property can be designed by the Fujisaki-Okamoto (FO) transformation, which is the widely utilized method to obtain secure PKE schemes from basic cryptographic primitives in the random oracle model . As a result, in combination with the FO transformation, we obtain a PKEET construction in the random oracle model if there exist a one-way PKE scheme, a one-time secure symmetric key encryption scheme , collision-resistant and one-way hash functions , and a pseudorandom function. In this sense, we remark that our PKEET construction is derived from fundamental generic assumptions only.

Fully homomorphic encryption (FHE) brings a paradigm shift in cryptographic engineering by enabling us to resolve various unsolved problems. Among them, this work solves the problem to design a private database query (PDQ) protocol that supports compound queries with wildcard conditions on encrypted databases using FHE. More precisely, we consider a setting where clients outsource an encrypted database using FHE to a remote server, and later request results of compound queries including a wildcard search condition-given a set of attribute values {A1; A2; ...; An} and a search pattern W, retrieve a set of all attribute values Ai's in which the pattern W occurs. To this end, we first develop an algorithm for testing whether an encrypted string contains an encrypted pattern without revealing any information of the pattern, taking auxiliary encryptions as additional inputs. Then, using this algorithm, we design PDQ protocols on encrypted databases, which support compound queries using wildcard search conditions. Finally, we demonstrate proof-of-concept implementation results of our protocols by exploiting single-instruction-multiple-data operations and multi-threading techniques.

We investigate constant-composition constrained codes for the mitigation of intercell interference for multilevel cell flash memories with a dynamic threshold scheme. The first explicit formula for the maximum size of a q-ary F-avoiding code with a given composition and certain families of substrings F is presented. In addition, we provide methods to determine the asymptotic rate for F-avoiding codes with any composition ratio and to find the optimal composition ratio that maximizes the asymptotic rate. We also give the first efficient encoder/decoder for these q-ary constant-composition codes achieving the channel capacity, for all q values.

Private query processing is a very attractive problem in the fields of both cryptography and databases. In this work, we restrict our attention to the efficiency aspect of the problem, particularly for basic queries with conditions on various combinations of equality. Without loss of generality, these conditions can be regarded as a Boolean function, and this Boolean function can then be evaluated at ciphertexts produced by a fully homomorphic encryption (FHE) scheme without decryption. From the efficiency perspective, the remaining concern is to efficiently test the equality function without severely downgrading the performance of FHE-based querying solutions. To this end, we first analyze the multiplicative depth required for an equality test algorithm with respect to the plaintext space inhabited by general FHE schemes. The primary reason for this approach is that given an equality test algorithm, its efficiency is measured in terms of the multiplicative depth required to construct its arithmetic circuit expression. Indeed, the implemented equality test algorithm dominates the entire performance of FHE-based query solutions, apart from the performance of the underlying FHE scheme. Then, we measure the multiplicative depth considering an FHE scheme that takes an extension field as its plaintext space and that supports the depth-free evaluation of Frobenius maps. According to our analysis, when the plaintext space of an FHE scheme is a field of characteristic 2, the equality test algorithm for `-bit messages requires the lowest multiplicative depth dlog`e. Furthermore, we design a set of private query protocols for conjunctive, disjunctive, and threshold queries based on the equality test algorithm. Similarly, applying the equality test algorithm over F2ℓ, our querying protocols require the minimum depths. More specifically, a multiplicative depth of [log ℓ] + [log (1 + ρ)] is required for conjunctive and disjunctive queries, and a depth of [log ℓ] + 2[log (1+ρ )] is required for threshold conjunctive queries, when their query conditions have p attributes to be compared. Finally, we provide a communication-efficient version of our solutions, though with additional computational costs, when an upper bound δ (0 ≤ δ ≤ 1) on the selectivity of a database is given. Consequently, we reduce the communication cost from n to approximately [δn] ciphertexts with [log n] additional depth when the database consists of n tuples.

The class of geometric orthogonal codes (GOCs) was introduced by Doty and Winslow (2016) for more robust macrobonding in DNA origami. They observed that GOCs are closely related to optical orthogonal codes (OOCs). It is possible for GOCs to have size greater than OOCs of corresponding parameters due to slightly more relaxed constraints on correlations. However, the existence of GOCs exceeding the size of optimal OOCs of corresponding parameters has never been demonstrated. This paper gives the first infinite family of GOCs of size greater than optimal OOCs.

The class of geometric orthogonal codes (GOCs) were introduced by Doty and Winslow (2016) for more robust macro-bonding in DNA origami. They observed that GOCs are closely related to optical orthogonal codes (OOCs). It is possible for GOCs to have size greater than OOCs of corresponding parameters due to slightly more relaxed constraints on correlations. However, the existence of GOCs exceeding the size of optimal OOCs of corresponding parameters have never been demonstrated. This paper gives the first infinite family of GOCs of size greater than optimal OOCs.

We construct permutation codes capable of correcting bursts of stable deletions. For correcting a single burst of exactly s stable deletions, our code has size sn!/((2s)!n)2, while the upper bound n!/s!(n - s + 1). We also construct permutation codes for the cases of single burst of up to s stable deletions, and up to b bursts of at most s stable deletions each.

For certain families of substrings F, we provide a closed formula for the maximum size of a q-ary F-avoiding code with a given composition. In addition, we provide numerical procedures to determine the asymptotic information rate for F-avoiding codes with certain composition ratios. Using our procedures, we recover known results and compute the information rates for certain classes of F-avoiding constant-composition codes for 2 ≤ q ≤ 8. For these values of q, we find composition ratios such that the rates of F-avoiding codes with constant composition achieve the capacity of the F-avoiding channel.

We give the first known efficient encoder/decoder for q-ary constant-composition ICI-free codes achieving ICI channel capacity, for all q. Previously, the best result known is an efficient encoder/decoder for binary constant-weight ICI-free codes with more than 2% loss over ICI channel capacity.

We construct codes for the Chebyshev permutation channels whose study was initiated by Langberg et al. (2015). We establish several recursive code constructions and present efficient decoding algorithms for our codes. In particular, our constructions yield a family of binary codes of rate 0.643 when r = 1. The upper bound on the rate in this case is 2/3 and the previous highest rate is 0.609.

This paper considers a linear quasi-cyclic product code of two given quasi-cyclic codes of relatively prime lengths over finite fields. We give the spectral analysis of a quasi-cyclic product code in terms of the spectral analysis of the row- and the column-code. Moreover, we provide a new lower bound on the minimum Hamming distance of a given quasi-cyclic code.

In this article, we identify a flaw in Huang et al.'s public key encryption with authorized equality test (The Computer Journal, 2015). More precisely, we point out that the proof of the indistinguishability under adaptive chosen ciphertext attack (IND-CCA2) security for their scheme has a serious flaw. We illustrate this flaw by presenting a polynomial time CCA2 attack on their scheme. We also provide a solution to correct this flaw by modifying their scheme slightly. Our solution is quite efficient because it provides security against CCA2 attack by exploiting only the hash computation of a two times longer input without any increase in the sizes of ciphertexts and warrants.

Public key encryption with equality test (PKEET), which was first introduced by Yang et al. (CT-RSA, 2010), has various applications including facilitating keyword search on encrypted data and partitioning encrypted data on the cloud. It can be also applied to manage personal health records on the internet. For these reasons, there have been improvements on earlier PKEET schemes in terms of performance and functionality. We present a semi-generic method for PKEET constructions, assuming only the existence of IND-CCA2 secure traditional public key encryption (PKE) schemes, the hardness of Computational Diffie-Hellman (CDH) problems, and random oracles. Our approach has several advantages; it enables us to understand requirements for the equality test functionality more clearly. Furthermore, our approach is quite general, in that if we change the underlying PKE scheme with the identity-based encryption (IBE) scheme (and we assume the hardness of Bilinear Diffie-Hellman problems instead of CDH), then we obtain the first IBE scheme with equality test (IBEET) satisfying analogous security arguments to those of PKEET. Although an IBEET construction was recently proposed, but we note that it satisfies only weak security requirements.

This paper considers a linear quasi-cyclic product code of two given quasi-cyclic codes of relatively prime lengths over finite fields. We give the spectral analysis of a quasi-cyclic product code in terms of the spectral analysis of the row and column codes. Moreover, we provide a new lower bound on the minimum Hamming distance of a given quasi-cyclic code and present a new algebraic decoding algorithm. More specifically, we prove an explicit (unreduced) basis of an ℓAℓB-quasi-cyclic product code in terms of the generator matrix in reduced Grobner basis with respect to the position-over-term (RGB/POT) order form of the ℓA-quasi-cyclic row code and the ℓB-quasicyclic column code, respectively. This generalizes the work of Burton and Weldon for the generator polynomial of a cyclic product code (where ℓA= ℓB= 1). Furthermore, we derive the generator matrix in Pre-RGB/POT form of an ℓAℓB-quasi-cyclic product code for two special cases: i) for ℓA= 2 and ℓB= 1 and ii) if the row code is a one-level ℓA-quasi-cyclic code (for arbitrary ℓA) and ℓB= 1. For arbitrary ℓAand ℓB, the PreRGB/POT form of the generator matrix of an ℓAℓB-quasi-cyclic product code is conjectured. The spectral analysis is applied to the generator matrix of the product of an ℓ-quasi-cyclic and a cyclic code, and we propose a new lower bound on the minimum Hamming distance of a given ℓ-quasi-cyclic code. In addition, we develop an efficient syndrome-based decoding algorithm for ℓ-phased burst errors with guaranteed decoding radius.

For any given positive integer m, a necessary and sufficient condition for the existence of Type-I m-adic constacyclic codes is given. Furthermore, for any given integer s, a necessary and sufficient condition for s to be a multiplier of a Type-I polyadic constacyclic code is given. As an application, some optimal codes from Type-I polyadic constacyclic codes, including generalized Reed-Solomon codes and alternant maximum distance separable codes, are constructed.

Quantum maximum-distance-separable (MDS) codes form an important class of quantum codes. To get q-ary quantum MDS codes, one of the effective ways is to find linear MDS codes C over Fq2satisfying C⊥H⊆ C, where C⊥Hdenotes the Hermitian dual code of C. For a linear code C of length n over Fq2, we say that C is a dual-containing code if C⊥H⊆ C and C≠ Fq2n. Several classes of new quantum MDS codes with relatively large minimum distance have been produced through dual-containing constacyclic MDS codes. These works motivate us to make a careful study on the existence conditions for dual-containing constacyclic codes. We obtain necessary and sufficient conditions for the existence of dual-containing constacyclic codes. Four classes of dual-containing constacyclic MDS codes are constructed and their parameters are computed. Consequently, the quantum MDS codes are derived from these parameters. The quantum MDS codes exhibited here have minimum distance bigger than the ones available in the literature.

A new lower bound on the minimum Hamming distance of linear quasi-cyclic codes over finite fields is proposed. It is based on spectral analysis and generalizes the Semenov-Trifonov bound in a similar way as the Hartmann-Tzeng bound extends the BCH approach for cyclic codes. Furthermore, a syndrome-based algebraic decoding algorithm is given.

Hermitian self-dual abelian codes in a group ring Fq2[G], where Fq2is a finite field of order q2and G is a finite abelian group, are studied. Using the well-known discrete Fourier transform decomposition for a semisimple group ring, a characterization of Hermitian self-dual abelian codes in Fq2[G] is given, together with an alternative proof of necessary and sufficient conditions for the existence of such a code in Fq2[G], i.e., there exists a Hermitian self-dual abelian code in Fq2[G] if and only if the order of G is even and q = 2lfor some positive integer l. Later on, the study is further restricted to the case where F22l[G] is a principal ideal group ring, or equivalently, G ≅ A⊕Z2k with 2 ≠ |A|. Based on the characterization obtained, the number of Hermitian self-dual abelian codes in F22l [A⊕Z2k] can be determined easily. When A is cyclic, this result answers an open problem of Jia et al. concerning Hermitian self-dual cyclic codes. In many cases, F22l [A⊕Z2k] contains a unique Hermitian self-dual abelian code. The criteria for such cases are determined in terms of l and the order of A. Finally, the distribution of finite abelian groups A such that a unique Hermitian self-dual abelian code exists in F22l [A ⊕ Z2] is established, together with the distribution of odd integers m such that a unique Hermitian self-dual cyclic code of length 2 m over F22l exists.

Almost perfect nonlinear (APN) functions on ${\mathbb F}_{2^n}$ are functions achieving the lowest possible differential uniformity. All APN functions discovered until now are either power or quadratic ones, except for one sporadic multinomial nonquadratic example on ${\mathbb F}_{2^6}$ due to Edel and Pott. It is well known that certain binary codes with good properties can be obtained from APN functions, and determining their (Hamming) weight distribution is equivalent to determining the Fourier spectra of the corresponding functions. The Fourier spectra of all known infinite families of quadratic APN functions discovered through 2010 have been determined, and it was found that they are the same as the ones of the Gold APN functions, i.e., a $5$-valued set when $n$ is even and a $3$-valued set when $n$ is odd, while a sporadic example on ${\mathbb F}_{2^6}$ found by Dillon has a $7$-valued Fourier spectrum. In 2011, two new generic constructions of APN functions were presented in [Y. Zhou and A. Pott, Adv. Math., 234 (2013), pp. 43--60] and [C. Carlet, Des. Codes Cryptogr., 59 (2011), pp. 89--109]. In this paper, we determine the Fourier spectra of the APN functions obtained from them and show that their Fourier spectra are again the same as those of the Gold APN functions. Moreover, since the APN functions in [C. Bracken, C. H. Tan, and Y. Tan, On a Class of Quadratic Polynomials with No Zeros and Its Applications to APN Functions, preprint, arXiv:1110.3177v1, 2011], which are demonstrated to exist when $n\equiv 0\mod 4$ and $3\nmid n$, are covered by the construction in [C. Carlet, Des. Codes Cryptogr., 59 (2011), pp. 89--109], a positive answer to the conjecture proposed in the former paper on determining their Fourier spectrum is given in this paper.

Asymmetric quantum error-correcting codes (AQCs) may offer some advantage over their symmetric counterparts by providing better error-correction for the more frequent error types. The well-known CSS construction of$q$-ary AQCs is extended by removing the$ \BBF _{q}$-linearity requirement as well as the limitation on the type of inner product used. The proposed constructions are called CSS-like constructions and utilize pairs of nested subfield linear codes under one of the Euclidean, trace Euclidean, Hermitian, and trace Hermitian inner products. After establishing some theoretical foundations, best-performing CSS-like AQCs are constructed. Combining some constructions of nested pairs of classical codes and linear programming, many optimal and good pure$q$-ary CSS-like codes for$q \in \{ 2,3,4,5,7,8,9\}$up to reasonable lengths are found. In many instances, removing the$ \BBF _{q}$-linearity and using alternative inner products give us pure AQCs with improved parameters than relying solely on the standard CSS construction.

We study abelian codes in principal ideal group algebras (PIGAs). We first give an algebraic characterization of abelian codes in any group algebra and provide some general results. For abelian codes in a PIGA, which can be viewed as cyclic codes over a semisimple group algebra, it is shown that every abelian code in a PIGA admits generator and check elements. These are analogous to the generator and parity-check polynomials of cyclic codes. A characterization and an enumeration of Euclidean self-dual and Euclidean self-orthogonal abelian codes in a PIGA are given, which generalize recent analogous results for self-dual cyclic codes. In addition, the structures of reversible and complementary dual abelian codes in a PIGA are established, again extending results on reversible and complementary dual cyclic codes. Finally, asymptotic properties of abelian codes in a PIGA are studied. An upper bound for the minimum distance of abelian codes in a non-semisimple PIGA is given in terms of the minimum distance of abelian codes in semisimple group algebras. Abelian codes in a non-semisimple PIGA are then shown to be asymptotically bad, similar to the case of repeated-root cyclic codes.

Password-authenticated key exchange (PAKE) is where a client and a server, who share a password, authenticate each other and meanwhile establish a cryptographic key by exchange of messages. In this setting, all the passwords necessary to authenticate clients are stored in a single server. If the server is compromised, due to, for example, hacking or even insider attack, passwords stored in the server are all disclosed. In this paper, we consider a scenario where two servers cooperate to authenticate a client and if one server is compromised, the attacker still cannot pretend to be the client with the information from the compromised server. Current solutions for two-server PAKE are either symmetric in the sense that two peer servers equally contribute to the authentication or asymmetric in the sense that one server authenticates the client with the help of another server. This paper presents a symmetric solution for two-server PAKE, where the client can establish different cryptographic keys with the two servers, respectively. Our protocol runs in parallel and is more efficient than existing symmetric two-server PAKE protocol, and even more efficient than existing asymmetric two-server PAKE protocols in terms of parallel computation.

We present a general construction of asymmetric quantum codes based on additive codes under the trace Hermitian inner product. Various families of additive codes over F4are used in the construction of many asymmetric quantum codes over F4.

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.

We study the multicast stream authentication problem when the communication channel is under control of an opponent who can drop, reorder and inject data packets. Recently, many coding theory based protocols have been developed to treat the stream authentication problem over such a channel. In this paper, our goal is to provide a general coding approach for multicast stream authentication. We design an authentication protocol which combines any list recoverable code (provided some conditions on its construction parameters). We demonstrate that the previous schemes can be viewed as instances of our construction when a Reed-Solomon code is used as a list recoverable code. In such settings, we also show that our approach leads to a better upper bound on the number of signature verification queries for each receiver.

An optimal constant-composition or constant-weight code of weight $w$ has linear size if and only if its distance $d$ is at least $2w-1$. When $d\geq 2w$, the determination of the exact size of such a constant-composition or constant-weight code is trivial, but the case of $d=2w-1$ has been solved previously only for binary and ternary constant-composition and constant-weight codes, and for some sporadic instances. This paper provides a construction for quasicyclic optimal constant-composition and constant-weight codes of weight $w$ and distance $2w-1$ based on a new generalization of difference triangle sets. As a result, the sizes of optimal constant-composition codes and optimal constant-weight codes of weight $w$ and distance $2w-1$ are determined for all such codes of sufficiently large lengths. This solves an open problem of Etzion. The sizes of optimal constant-composition codes of weight $w$ and distance $2w-1$ are also determined for all $w\leq 6$, except in two cases.

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.

The preimage distributions of perfect nonlinear functions from an Abelian group of ordernto an Abelian group of order3or4, respectively, are studied. Based on the properties of the preimage distributions of perfect nonlinear functions from an Abelian group of order3rto an Abelian group of order3, the weight distributions of the ternary linear codesCPifrom the perfect nonlinear functionsPi(x) fromF3rto itself are determined. These results suggest that two open problems, proposed by Carlet, Ding, and Yuan in 2005 and 2006, respectively, are answered.

In this paper, the weight distributions of two classes of linear codes based on all known explicit perfect nonlinear functions fromFqmto itself are determined using a unified approach. All the minimal codewords of these codes are characterized according to their weights, which suggests that their covering structures are determined. Finally, all the minimal access sets of the secret sharing schemes based on their dual codes are obtained.

Let $K_{n,n}$ denote the complete bipartite graph with n vertices in each partite set and $K_{n,n}+I$ denote $K_{n,n}$ with a one-factor added. It is proved in this paper that there exists an m-cycle system of $K_{n,n}+I$ if and only if $n \equiv 1 (\rm{mod} 2)$, $m \equiv 0 (\rm{mod} 2)$, $4 \leq m \leq 2n$, and $n(n+1) \equiv$ 0 (mod m).

This correspondence introduces two new constructive techniques to complete the determination of the sizes of optimal$q$-ary codes of constant weight three and distance four.

The design of large libraries of oligonucleotides having constant-content and satisfying Hamming distance constraints between oligonucleotides and their Watson-Crick complements is important in reducing hybridization errors in DNA computing, DNA microarray technologies, and molecular bar coding. Various techniques have been studied for the construction of such oligonucleotide libraries, ranging from algorithmic constructions via stochastic local search to theoretical constructions via coding theory. A new stochastic local search method is introduced, which yields improvements for more than one third of the benchmark lower bounds of Gaborit and King (2005) for n-mer oligonucleotide libraries when n les 14. Several optimal libraries are also found by computing maximum cliques on certain graphs.

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.

This paper introduces a new combinatorial construction for$q$-ary constant-weight codes which yields several families of optimal codes and asymptotically optimal codes. The construction reveals intimate connection between$q$-ary constant-weight codes and sets of pairwise disjoint combinatorial designs of various types.

We show an interesting pairwise balanced design (PBD)-closure result for the set of lengths of constant-composition codes whose distance and size meet certain conditions. A consequence of this PBD-closure result is that the size of optimal constant-composition codes can be determined for infinite families of parameter sets from just a single example of an optimal code. As an application, the sizes of several infinite families of optimal constant-composition codes are derived. In particular, the problem of determining the size of optimal constant-composition codes having distance four and weight three is solved for all lengths sufficiently large. This problem was previously unresolved for odd lengths, except for lengths seven and eleven.

In this paper, we study the probability of undetected error for binary constant weight codes (BCWCs). First, we derive a new lower bound on the probability of undetected error. Next, we show that this bound is tight if and only if the BCWCs are generated from certain t-designs. This means that such BCWCs are uniformly optimal for error detection. Thus, we prove a conjecture of Xia, Fu, Jiang and Ling. Furthermore, we determine the distance distributions of such BCWCs. Finally, we derive some bounds on the exponent of the probability of undetected error for BCWCs. These bounds enable us to extend the region in which the exponent of the probability of undetected error is exactly determined

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

In this correspondence, we consider the decoding of binary block codes over the additive white Gaussian noise (AWGN) channel with binary phase-shift keying (BPSK) signaling. By a reliability-order-based decoding algorithm (ROBDA), we mean a soft-decision decoding algorithm which decodes to the best (most likely) codeword of the form that is the sum of the hard-decision tuple and an error pattern in a set determined only by the order of the reliabilities of the hard decisions. Examples of ROBDAs include many well-known decoding algorithms, such as the generalized-minimum-distance (GMD) decoding algorithm, Chase decoding algorithms, and the reliability-based decoding algorithms proposed by Fossorier and Lin. It is known that the squared error-correction-radii of ROBDAs can be computed from the minimal squared Euclidean distances (MSEDs) between the all-one sequence and the polyhedra corresponding to the error patterns. For the computation of such MSEDs, we give a new method which is more compact than the one proposed by Fossorier and Lin. These results are further used to show that any bounded-distance ROBDA is asymptotically optimal: The ratio between the probability of decoding error of a bounded-distance ROBDA and that of the maximum-likelihood (ML) decoding approaches 1 when the signal-to-noise ratio (SNR) approaches infinity, provided that the minimum Hamming distance of the code is greater than 2.

In this correspondence, we study the probability of undetected error for binary constant weight codes. First, we derive a new lower bound on the probability of undetected error for binary constant weight codes. Next, we show that this bound is tight if and only if the binary constant weight codes are generated from certain t-designs in combinatorial design theory. This means that these binary constant weight codes generated from certain t-designs are uniformly optimal for error detection. Along the way, we determine the distance distributions of such binary constant weight codes. In particular, it is shown that binary constant weight codes generated from Steiner systems are uniformly optimal for error detection. Thus, we prove a conjecture of Xia, Fu, Jiang, and Ling. Furthermore, the distance distribution of a binary constant weight code generated from a Steiner system is determined. Finally, we study the exponent of the probability of undetected error for binary constant weight codes. We derive some bounds on the exponent of the probability of undetected error for binary constant weight codes. These bounds enable us to extend the region in which the exponent of the probability of undetected error is exactly determined

This paper explores the applications of a recent bound on some Weil-type exponential sums over Galois rings in the construction of codes and sequences. A family of codes over $\F_p$, mostly nonlinear, of length $p^{m+1}$ and size $p^2 \cdot p^{m ( D - \lfloor D/p^2 \rfloor )}$, where $1 \le D \le p^{m/2}$, is obtained. The bound on this type of exponential sums provides a lower bound for the minimum distance of these codes. Several families of pairwise cyclically distinct p-ary sequences of period $p(p^m-1)$ of low correlation are also constructed. They compare favorably with certain known p-ary sequences of period $p^m -1$. Even in the case $p=2$, one of these families is slightly larger than the family $Q(D)$ in section 8.8 in [T. Helleseth and P. V. Kumar, Handbook of Coding Theory, Vol. 2, North-Holland, 1998, pp. 1765-1853], while they share the same period and the same bound for the maximum nontrivial correlation.

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.

Following Parts I and II, quasi-cyclic codes of given index are studied as codes over a finite polynomial ring. These latter codes are decomposed by the Chinese Remainder Theorem (CRT), or equivalently the Mattson-Solomon transform, into products of shorter codes over larger alphabets. We characterize and enumerate self-dual one-generator quasi-cyclic codes in that context. We give an algorithm to remove some equivalent codes from that enumeration. A generalization to multigenerator codes is sketched.

In this correspondence, we study the probability of undetected error for binary constant-weight codes. First, we derive a new formula on the probability of undetected error for binary constant-weight codes. Second, using this new formula and linear programming, we give two new lower bounds on the probability of undetected error for binary constant-weight codes. These two new lower bounds improve on previously known lower bounds in certain cases. Furthermore, we show that these two lower bounds are tight if and only if the binary constant-weight codes are generated from certain t-designs in combinatorial design theory. This means that these binary constant-weight codes generated from certain t-designs are uniformly optimal for error detection. Along the way, we determine the distance distributions of such binary constant-weight codes. Finally, several examples are given to illustrate the results obtained in this correspondence.

We present an upper bound for Weil-type exponential sums over Galois rings of characteristic p/sup 2/ which improves on the analog of the Weil-Carlitz-Uchiyama bound for Galois rings obtained by Kumar, Helleseth, and Calderbank (1995). A more refined bound, expressed in terms of genera of function fields, and an analog of McEliece's (1971) theorem on the divisibility of the homogeneous weights of codewords in trace codes over Z/sub p//sup 2/, are also derived. These results lead to an improvement on the estimation of the minimum distance of certain trace codes over Z/sub p//sup 2/ and the bounds on the correlation of certain nonlinear p-ary sequences.

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 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.

We show that there are long binary quasi-cyclic self-dual (either Type I or Type II) codes satisfying the Gilbert-Varshamov bound.

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

We characterize codes over Z/sub p/ which are the Gray images of (1-p/sup k/)-cyclic codes or cyclic codes over Z(p/sup k+l/) (k/spl ges/1). A necessary and sufficient condition for the Gray image of a Z(p/sup 2/)-linear (1-p)-cyclic code to be linear is given. In many cases, this yields an explicit description of the Gray image of a linear (1-p)-cyclic code over Z(p/sup 2/), of length relatively prime to p. Linear cyclic codes over Z(p/sup 2/) whose Gray images are linear cyclic codes over Z/sub p/ have been characterized. Some generalizations of these results to the case of Z(p/sup k+1/), where k/spl ges/2, are also obtained.

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.

Duadic codes constitute a well-known family of binary cyclic codes. They are generalized in this correspondence to the setting of Abelian codes over the ring Z/sub 2k/. Self-duality, isoduality, and Type II properties are studied.

A new algebraic approach to quasi-cyclic codes is introduced. The key idea is to regard a quasi-cyclic code over a field as a linear code over an auxiliary ring. By the use of the Chinese remainder theorem (CRT), or of the discrete Fourier transform (DFT), that ring can be decomposed into a direct product of fields. That ring decomposition in turn yields a code construction from codes of lower lengths which turns out to be in some cases the celebrated squaring and cubing constructions and in other cases the (u+/spl upsi/|u-/spl upsi/) and Vandermonde constructions. All binary extended quadratic residue codes of length a multiple of three are shown to be attainable by the cubing construction. Quinting and septing constructions are introduced. Other results made possible by the ring decomposition are a characterization of self-dual quasi-cyclic codes, and a trace representation that generalizes that of cyclic codes.

We describe a class of codes over GF(q), where q is a power of an odd prime. These codes are analogs of the binary Reed-Muller codes and share several features in common with them. We determine the minimum weight and properties of these codes. For a subclass of codes we find the weight distribution and prove that the minimum nonzero weight codewords give 1-designs.

We construct a class of codes of length n such that the minimum distance d outside of a certain subcode is, up to a constant factor, bounded below by the square root of n, a well-known property of quadratic residue codes. The construction, using the group algebra of an Abelian group and a special partition or splitting of the group, yields quadratic residue codes, duadic codes, and their generalizations as special cases. We show that most of the special properties of these codes have analogues for split group codes, and present examples of new classes of codes obtained by this construction.

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.