Sliding-window dynamic frameproof codes

A sliding-window dynamic frameproof code is a scheme for discouraging the piracy of digital broadcasts through the use of digital fingerprinting. In this paper, we formally define sliding-window dynamic frameproof codes and provide optimal constructions for a certain class of these schemes. We also discuss bounds on the number of users such schemes can support.      

New constructions for perfect hash families and related structures using combinatorial designs and codes

In this paper, we consider explicit constructions of perfect hash families using combinatorial methods. We provide several direct constructions from combinatorial structures related to orthogonal arrays. We also simplify and generalize a recursive construction due to Atici, Magliversas, Stinson and Wei [3]. Using similar methods, we also obtain efficient constructions for separating hash families which result in improved existence results for structures such as separating systems, key distribution patterns, group testing algorithms, cover‐free families and secure frameproof codes. © 2000 John Wiley & Sons, Inc. J Combin Designs 8:189–200, 2000     

A bound on the size of separating hash families

The paper provides an upper bound on the size of a (generalized) separating hash family, a notion introduced by Stinson, Wei and Chen. The upper bound generalizes and unifies several previously known bounds which apply in special cases, namely bounds on perfect hash families, frameproof codes, secure frameproof codes and separating hash families of small type.     

Recursive constructions of secure codes and hash families using difference function families

To protect copyrighted digital data against piracy, codes with different secure properties such as frameproof codes, secure frameproof codes, codes with identifiable parent property (IPP codes), traceability codes (TA codes) are introduced. In this paper, we study these codes together with related combinatorial objects called separating and perfect hash families. We introduce for the first time the notion of difference function families and use these difference function families to give generalized recursive techniques that can be used for any kind of secure codes and hash families. We show that some previous recursive techniques are special cases of these new techniques.     

A tight bound for frameproof codes viewed in terms of separating hash families

Frameproof codes have been introduced for use in digital fingerprinting that prevent a coalition of \(w\) or fewer legitimate users from constructing a fingerprint of another user not in the coalition. It turns out that \(w\) -frameproof codes are equivalent to separating hash families of type \(\{1,w\}\) . In this paper we prove a tight bound for frameproof codes in terms of separating hash families.     

Sequential and dynamic frameproof codes

There are many schemes in the literature for protecting digital data from piracy by the use of digital fingerprinting, such as frameproof codes and traitor-tracing schemes. The concept of traitor-tracing has been applied to a digital broadcast setting in the form of dynamic traitor-tracing schemes and sequential traitor-tracing schemes, which could be used to combat piracy of pay-TV broadcasts, for example. In this paper, we extend the properties of frameproof codes to this dynamic model, defining and constructing both l-sequential c-frameproof codes and l-dynamic c-frameproof codes. We also give bounds on the number of users supported by such schemes.      

AMDS symbol-pair codes from repeated-root cyclic codes

Symbol-pair codes are proposed to guard against pair-errors in symbol-pair read channels. The minimum symbol-pair distance is of significance in determining the error-correcting capability of a symbol-pair code. One of the central themes in symbol-pair coding theory is the constructions of symbol-pair codes with the largest possible minimum symbol-pair distance. Maximum distance separable (MDS) and almost maximum distance separable (AMDS) symbol-pair codes are optimal and sub-optimal regarding the Singleton bound, respectively. In this paper, six new classes of AMDS symbol-pair codes are explicitly constructed through repeated-root cyclic codes. Remarkably, one class of such codes has unbounded lengths and the minimum symbol-pair distance of another class can reach 13.     

Improved bounds for separating hash families

An ${(N;n,m,\{w_1,\ldots, w_t\})}$ -separating hash family is a set ${\mathcal{H}}$ of N functions ${h: \; X \longrightarrow Y}$ with ${|X|=n, |Y|=m, t \geq 2}$ having the following property. For any pairwise disjoint subsets ${C_1, \ldots, C_t \subseteq X}$ with ${|C_i|=w_i, i=1, \ldots, t}$ , there exists at least one function ${h \in \mathcal{H}}$ such that ${h(C_1), h(C_2), \ldots, h(C_t)}$ are pairwise disjoint. Separating hash families generalize many known combinatorial structures such as perfect hash families, frameproof codes, secure frameproof codes, identifiable parent property codes. In this paper we present new upper bounds on n which improve many previously known bounds. Further we include constructions showing that some of these bounds are tight.     

Explicit constructions of separating hash families from algebraic curves over finite fields

Let X be a set of order n and Y be a set of order m. An (n,m,{w ₁, w ₂})-separating hash family is a set of N functions from X to Y such that for any with , |X ₁| = w ₁ and |X ₂| = w ₂, there exists an element such that . In this paper, we provide explicit constructions of separating hash families using algebraic curves over finite fields. In particular, applying the Garcia–Stichtenoth curves, we obtain an infinite class of explicitly constructed (n,m,{w ₁,w ₂})–separating hash families with for fixed m, w ₁, and w ₂. Similar results for strong separating hash families are also obtained. As consequences of our main results, we present explicit constructions of infinite classes of frameproof codes, secure frameproof codes and identifiable parent property codes with length where n is the size of the codes. In fact, all the above explicit constructions of hash families and codes provide the best asymptotic behavior achieving the bound , which substantially improve the results in [ 8, 15, 17] give an answer to the fifth open problem presented in [11].     

Constant Weight Codes and Group Divisible Designs

The study of a class of optimal constant weight codes over arbitrary alphabets was initiated by Etzion, who showed that such codes are equivalent to special GDDs known as generalized Steiner systems GS(t,k,n,g) Etzion. This paper presents new constructions for these systems in the case t=2, k=3. In particular, these constructions imply that the obvious necessary conditions on the length n of the code for the existence of an optimal weight 3, distance 3 code over an alphabet of arbitrary size are asymptotically sufficient.     

Universal hashing and authentication codes

In this paper, we study the application of universal hashing to the construction of unconditionally secure authentication codes without secrecy. This idea is most useful when the number of authenticators is exponentially small compared to the number of possible source states (plaintext messages). We formally define some new classes of hash functions and then prove some new bounds and give some general constructions for these classes of hash functions. Then we discuss the implications to authentication codes.A preliminary version of this paper was presented at CRYPTO '91 and appeared in Lecture Notes in Computer Science, vol. 576, pp. 74–85, Springer-Verlag, 1992.     

Connections between Construction D and related constructions of lattices

Most practical constructions of lattice codes with high coding gains are multilevel constructions where each level corresponds to an underlying code component. Construction D, Construction \(\hbox {D}'\) , and Forney’s code formula are classical constructions that produce such lattices explicitly from a family of nested binary linear codes. In this paper, we investigate these three closely related constructions along with the recently developed Construction \(\hbox {A}'\) of lattices from codes over the polynomial ring \(\mathbb {F}_2[u]/u^a\) . We show that Construction by Code Formula produces a lattice packing if and only if the nested codes being used are closed under Schur product, thus proving the similarity of Construction D and Construction by Code Formula when applied to Reed–Muller codes. In addition, we relate Construction by Code Formula to Construction \(\hbox {A}'\) by finding a correspondence between nested binary codes and codes over \(\mathbb {F}_2[u]/u^a\) . This proves that any lattice constructible using Construction by Code Formula is also constructible using Construction \(\hbox {A}'\) . Finally, we show that Construction \(\hbox {A}'\) produces a lattice if and only if the corresponding code over \(\mathbb {F}_2[u]/u^a\) is closed under shifted Schur product.     

Symmetric LDPC codes and local testing

Coding theoretic and complexity theoretic considerations naturally lead to the question of generating symmetric, sparse, redundant linear systems. This paper provides a new way of construction with better parameters and new lower bounds.Low Density Parity Check (LDPC) codes are linear codes defined by short constraints (a property essential for local testing of a code). Some of the best (theoretically and practically) used codes are LDPC. Symmetric codes are those in which all coordinates “look the same,” namely there is some transitive group acting on the coordinates which preserves the code. Some of the most commonly used locally testable codes (especially in PCPs and other proof systems), including all “low-degree” codes, are symmetric. Requiring that a symmetric binary code of length n has large (linear or near-linear) distance seems to suggest a “con ict” between 1/rate and density (constraint length). In known constructions, if one is constant, then the other is almost the worst possible - n/poly(logn).Our main positive result simultaneously achieves symmetric low density, constant rate codes generated by a single constraint. We present an explicit construction of a symmetric and transitive binary code of length n, near-linear distance n/(log logn)², of constant rate and with constraints of length (logn)⁴. The construction is in the spirit of Tanner codes, namely the codewords are indexed by the edges of a sparse regular expander graph. The main novelty is in our construction of a transitive (non Abelian!) group acting on these edges which preserves the code. Our construction is one instantiation of a framework we call Cayley Codes developed here, that may be viewed as extending zig-zag product to symmetric codes.Our main negative result is that the parameters obtained above cannot be significantly improved, as long as the acting group is solvable (like the one we use). More specifically, we show that in constant rate and linear distance codes (aka “good” codes) invariant under solvable groups, the density (length of generating constraints) cannot go down to a constant, and is bounded below by (log^(Ω(?)) n)(an Ω(?) iterated logarithm) if the group has a derived series of length ?. This negative result precludes natural local tests with constantly many queries for such solvable “good” codes.     

\mathbb{Z }_2\mathbb{Z }_4-Additive formally self-dual codes

We study odd and even \(\mathbb{Z }_2\mathbb{Z }_4\) formally self-dual codes. The images of these codes are binary codes whose weight enumerators are that of a formally self-dual code but may not be linear. Three constructions are given for formally self-dual codes and existence theorems are given for codes of each type defined in the paper.     

Almost Factorizable Weakly Ample Semigroups

An appropriate generalization of the notion of permissible sets of inverse semigroups is found within the class of weakly ample semigroups that allows us to introduce the notion of an almost left factorizable weakly ample semigroup in a way analogous to the inverse case. The class of almost left factorizable weakly ample semigroups is proved to coincide with the class of all (idempotent separating) (2, 1, 1)-homomorphic images of semigroups W(T, Y) where Y is a semilattice, T is a unipotent monoid acting on Y, and W(T, Y) is a well-defined subsemigroup in the respective semidirect product that appeared in the structure theory of left ample monoids more than ten years ago. Moreover, the semigroups W(T, Y) are characterized to be, up to isomorphism, just the proper and almost left factorizable weakly ample semigroups.     

A generalization of combinatorial designs and related codes

In this paper we study a certain generalization of combinatorial designs related to almost difference sets, namely the t-adesign, which was coined by Ding (Codes from difference sets, 2015). It is clear that 2-adesigns are partially balanced incomplete block designs which naturally arise in many combinatorial and statistical problems. We discuss some of their basic properties and give several constructions of 2-adesigns (some of which correspond to new almost difference sets and some to new almost difference families), as well as two constructions of 3-adesigns. We discuss basic properties of the incidence matrices and make an initial investigation into the codes which they generate. We find that many of the codes have good parameters in the sense they are optimal or have relatively high minimum distance.     

Projective Plane and Planar Quantum Codes

Cellulations of the projective plane RP ^2 define single qubit topological quantum error correcting codes since there is a unique essential cycle in H ₁ (RP ² ;Z ₂ ) . We construct three of the smallest such codes, show they are inequivalent, and identify one of them as Shor's original 9 qubit repetition code. We observe that Shor's code can be constructed in a planar domain and generalize to planar constructions of higher-genus codes for multiple qubits. June 21, 2000. Final version recieved: April 27, 2001.     

Codes of Small Defect

The parameters of a linear code C over GF(q) are given by [n,k,d], where n denotes the length, k the dimension and d the minimum distance of C. The code C is called MDS, or maximum distance separable, if the minimum distance d meets the Singleton bound, i.e. d = n-k+1 Unfortunately, the parameters of an MDS code are severely limited by the size of the field. Thus we look for codes which have minimum distance close to the Singleton bound. Of particular interest is the class of almost MDS codes, i.e. codes for which d=n-k. We will present a condition on the minimum distance of a code to guarantee that the orthogonal code is an almost MDS code. This extends a result of Dodunekov and Landgev Dodunekov. Evaluation of the MacWilliams identities leads to a closed formula for the weight distribution which turns out to be completely determined for almost MDS codes up to one parameter. As a consequence we obtain surprising combinatorial relations in such codes. This leads, among other things, to an answer to a question of Assmus and Mattson 5 on the existence of self-dual [2d,d,d]-codes which have no code words of weight d+1. Actually there are more codes than Assmus and Mattson expected, but the examples which we know are related to the expected ones.     

Bounds for the Multicovering Radii of Reed-Muller Codes with Applications to Stream Ciphers

The multicovering radii of a code are recentgeneralizations of the covering radius of a code. For positivem, the m-covering radius of C is the leastradius t such that everym-tuple of vectors is contained in at least one ball of radiust centered at some codeword. In this paper upper bounds arefound for the multicovering radii of first order Reed-Muller codes. These bounds generalize the well-known Norse bounds for the classicalcovering radii of first order Reed-Muller codes. They are exactin some cases. These bounds are then used to prove the existence of secure families of keystreams against a general class of cryptanalytic attacks. This solves the open question that gave rise to the study ofmulticovering radii of codes.     

Cryptanalysis of Two McEliece Cryptosystems Based on Quasi-Cyclic Codes

We cryptanalyse here two variants of the McEliece cryptosystem based on quasi-cyclic codes. Both aim at reducing the key size by restricting the public and secret generator matrices to be in quasi-cyclic form. The first variant considers subcodes of a primitive BCH code. The aforementioned constraint on the public and secret keys implies to choose very structured permutations. We prove that this variant is not secure by producing many linear equations that the entries of the secret permutation matrix have to satisfy by using the fact that the secret code is a subcode of a known BCH code. This attack has been implemented and in all experiments we have performed the solution space of the linear system was of dimension one and revealed the permutation matrix. The other variant uses quasi-cyclic low density parity-check (LDPC) codes. This scheme was devised to be immune against general attacks working for McEliece type cryptosystems based on LDPC codes by choosing in the McEliece scheme more general one-to-one mappings than permutation matrices. We suggest here a structural attack exploiting the quasi-cyclic structure of the code and a certain weakness in the choice of the linear transformations that hide the generator matrix of the code. This cryptanalysis adopts a polynomial-oriented approach and basically consists in searching for two polynomials of low weight such that their product is a public polynomial. Our analysis shows that with high probability a parity-check matrix of a punctured version of the secret code can be recovered with time complexity O(n ³) where n is the length of the considered code. The complete reconstruction of the secret parity-check matrix of the quasi-cyclic LDPC codes requires the search of codewords of low weight which can be done with about 2³⁷ operations for the specific parameters proposed.