第二类窃密信道中的组合数学方法

当信息在第二类窃密信道中传输时,线性码的广义汉明重量谱完全描述的它在该信道中的密码学特征.计算一个线性码的广义汉明重量谱是一个基本问题,首先提出了线性码的“最简基”的概念.在此基础上给出了一般线性码子码的几种计数公式,并给出了它们之间等价性的证明.     

Weight Hierarchies of Linear Codes Satisfying the Chain Condition

The weight hierarchy of a linear [n,k;q] code C over GF(q) is the sequence (d₁,d₂,...,d_k) where d_r is the smallest support of an r–dimensional subcode of C. By explicit construction, it is shown that if a sequence (a₁,a₂,...,a_k) satisfies certain conditions, then it is the weight hierarchy of a code satisfying the chain condition.     

Binary linear codes from vectorial boolean functions and their weight distribution

Binary linear codes with good parameters have important applications in secret sharing schemes, authentication codes, association schemes, and consumer electronics and communications. In this paper, we construct several classes of binary linear codes from vectorial Boolean functions and determine their parameters, by further studying a generic construction developed by Ding et al. recently. First, by employing perfect nonlinear functions and almost bent functions, we obtain several classes of six-weight linear codes which contain the all-one codeword, and determine their weight distribution. Second, we investigate a subcode of any linear code mentioned above and consider its parameters. When the vectorial Boolean function is a perfect nonlinear function or a Gold function in odd dimension, we can completely determine the weight distribution of this subcode. Besides, our linear codes have larger dimensions than the ones by Ding et al.’s generic construction.     

Antichain Codes

We show that almost all codes satisfy an antichain condition. This states that the minimum length of a two dimensional subcode of a code C increases if the subcode is constrained to contain a minimum weight codeword. In particular, almost no code satisfies the chain condition. In passing, we study the typical behaviour of codes with respect to generalized distances and show that almost all lie on a generalized Varshamov-Gilbert bound.     

On the relative profiles of a linear code and a subcode

Relative dimension/length profile (RDLP), inverse relative dimension/length profile (IRDLP) and relative length/dimension profile (RLDP) are equivalent sequences of a linear code and a subcode. The concepts were applied to protect messages from an adversary in the wiretap channel of type II with illegitimate parties. The equivocation to the adversary is described by IRDLP and upper-bounded by the generalized Singleton bound on IRDLP. Recently, RLDP was also extended in wiretap network II for secrecy control of network coding. In this paper, we introduce new relations and bounds about the sequences. They not only reveal new connections among known results but also find applications in trellis complexities of linear codes. The state complexity profile of a linear code and that of a subcode can be bounded from each other, which is particularly useful when a tradeoff among coding rate, error-correcting capability and decoding complexity is considered. Furthermore, a unified framework is proposed to derive bounds on RDLP and IRDLP from an upper bound on RLDP. We introduce three new upper bounds on RLDP and use some of them to tighten the generalized Singleton bounds by applying the framework. The approach is useful to improve equivocation estimation in the wiretap channel of type II with illegitimate parties.     

一类4维3元线性码的重量谱

GF(q)上[n,k;q]线性码C的重量谱为序列(d1,d2,…dk),其中dr是C的r维子码的最小支持重量.文章利用有限射影几何方法确定了一类4维3元线性码的重量谱,并对其进行了验证.     

GOPPA CODES FROMARTIN-SCHREIER FUNCTION FIELDS

ＧＯＰＰＡＣＯＤＥＳＦＲＯＭＡＲＴＩＮ－ＳＣＨＲＥＩＥＲＦＵＮＣＴＩＯＮＦＩＥＬＤＳ￥ＨＡＮＷＥＮＢＡＯ（ＤｅｐａｔｍｅｌｌｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｉｃｈｕａｎＵｎｉｖｅｒｓｉｔｙｔＣｈｅｎｇｄｕ６１００６４，Ｓｉｃｈｕａｎ，Ｃｈｉｎａ．）Ａ...     

Relative generalized Hamming weights of cyclic codes

Relative generalized Hamming weights (RGHWs) of a linear code with respect to a linear subcode determine the security of the linear ramp secret sharing scheme based on the linear codes. They can be used to express the information leakage of the secret when some keepers of shares are corrupted. Cyclic codes are an interesting type of linear codes and have wide applications in communication and storage systems. In this paper, we investigate the RGHWs of cyclic codes of two nonzeros with respect to its irreducible cyclic subcodes. We give two formulae for RGHWs of the cyclic codes. As applications of the formulae, explicit examples are computed. Moreover, RGHWs of cyclic codes in the examples are very large, comparing with the generalized Plotkin bound of RGHWs. So it guarantees very high security for the secret sharing scheme based on the dual codes.     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

Code constructions and existence bounds for relative generalized Hamming weight

The relative generalized Hamming weight (RGHW) of a linear code C and a subcode C ¹ is an extension of generalized Hamming weight. The concept was firstly used to protect messages from an adversary in the wiretap channel of type II with illegitimate parties. It was also applied to the wiretap network II for secrecy control of network coding and to trellis-based decoding algorithms for complexity estimation. For RGHW, bounds and code constructions are two related issues. Upper bounds on RGHW show the possible optimality for the applications, and code constructions meeting upper bounds are for designing optimal schemes. In this article, we show indirect and direct code constructions for known upper bounds on RGHW. When upper bounds are not tight or constructions are hard to find, we provide two asymptotically equivalent existence bounds about good code pairs for designing suboptimal schemes. Particularly, most code pairs (C, C ¹) are good when the length n of C is sufficiently large, the dimension k of C is proportional to n and other parameters are fixed. Moreover, the first existence bound yields an implicit lower bound on RGHW, and the asymptotic form of this existence bound generalizes the usual asymptotic Gilbert–Varshamov bound.     

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.     

On a code reconstruction by correlation coefficients of its subcodes

A generalization is obtained of the theorem on reconstruction of a binary code from dimensions of its subcodes. The notion is proposed of a correlation coefficient of the family of subcodes which, in the present consideration, is an analog for the dimension of a binary subcode.     

On the second greedy weight for linear codes of dimension 3

The difference g₂−d₂ for a q-ary linear [n,3,d] code C is studied. Here d₂ is the second generalized Hamming weight, that is, the smallest size of the support of a 2-dimensional subcode of C; and g₂ is the second greedy weight, that is, the smallest size of the support of a 2-dimensional subcode of C which contains a codeword of weight d. For codes of dimension 3, it is shown that the problem is essentially equivalent to finding certain weighting of the points in the projective plane, and weighting which give the maximal value of g₂−d₂ are determined in almost all cases. In particular max(g₂−d₂) is determined in all cases for q⩽9.     

Non-free extensions of the simplex codes over a chain ring with four elements

Let R be a chain ring with four elements. In this paper, we present two new constructions of R-linear codes that contain a subcode associated with a simplex code over the ring R. The simplex codes are defined as the codes generated by a matrix having as columns the homogeneous coordinates of all points in some projective Hjelmslev geometry PHG(R ^k ). The first construction generalizes a recent result by Kiermaier and Zwanzger to codes of arbitrary dimension. We provide a geometric interpretation of their construction which is then extended to projective Hjelmslev spaces of arbitrary dimension. The second construction exploits the possibility of adding two non-free rows to the generator matrix of a linear code over R associated with a given point set. Though the construction works over both chain rings with four elements, the better codes are obtained for ${R=\mathbb{Z}_4}$ .     

Testing algebraic geometric codes

Property testing was initially studied from various motivations in 1990’s. A code C  GF (r)n is locally testable if there is a randomized algorithm which can distinguish with high possibility the codewords from a vector essentially far from the code by only accessing a very small (typically constant) number of the vector’s coordinates. The problem of testing codes was firstly studied by Blum, Luby and Rubinfeld and closely related to probabilistically checkable proofs (PCPs). How to characterize locally te...     

A result on the weight distributions of binary quadratic residue codes

Truong et al. [7]proved that the weight distribution of a binary quadratic residue code C with length congruent to −1 modulo 8 can be determined by the weight distribution of a certain subcode of C containing only one-eighth of the codewords of C. In this paper, we prove that the same conclusion holds for any binary quadratic residue codes.     

The non-gap sequence of a subcode of a generalized Reed–Solomon code

This paper addresses the question how often the square code of an arbitrary l-dimensional subcode of the code GRS _k (a, b) is exactly the code GRS_2k-1(a, b * b). To answer this question we first introduce the notion of gaps of a code which allows us to characterize such subcodes easily. This property was first used and stated by Wieschebrink where he applied the Sidelnikov–Shestakov attack to break the Berger–Loidreau cryptosystem.     

Finite Projective Geometries and Classification of the Weight Hierarchies of Codes （Ⅰ）

The weight hierarchy of a binary linear [n,κ] code C is the sequence (d1,d2,...,dκ), where dr is the smallest support of an r-dimensional subcode of C. The codes of dimension 4 are collected in classes and the possible weight hierarchies in each class is determined by finite projective geometries.The possible weight hierarchies in class A, B, C, D are determined in Part (Ⅰ). The possible weight hierarchies in class E, F, G, H, I are determined in Part (Ⅱ).     

Codes of Steiner triple and quadruple systems

The code over a finite fieldF _q of orderq of a design is the subspace spanned by the incidence vectors of the blocks. It is shown here that if the design is a Steiner triple system on points, and if the integerd is such that 2 ^d –1<2 ^d+1–1, then the binary code of the design contains a subcode that can be shortened to the binary Hamming codeH _d of length 2 ^d –1. Similarly the binary code of any Steiner quadruple system on +1 points contains a subcode that can be shortened to the Reed-Muller code (d–2,d) of orderd–2 and length 2 ^d , whered is as above.     

Nonlinear thermoelastic analysis of layered structures

The nonlinear thermoelastic behavior of orthotropic layered slabs and cylinders including radiation boundaries, temperature-dependent material properties, and stress-dependent layer interface conditions is investigated. A one-dimensional finite element formulation employing quadratic layer and linear interface elements is used to perform the analyses. The transient heat conduction portion of the program is temporally discretized via an implicit linear time interpolation algorithm which includes Crank-Nicolson, Galerkin, and Euler backward differencing. The nonlinear heat conduction equations are iteratively evaluated using a modified Newton-Raphson scheme. Direct iteration between heat conduction and stress analysis is employed when stress-dependent interface thermal resistance coefficients are utilized. Verification problems are presented to demonstrate the accuracy of the finite element code.