Generalised Cumulative Arrays in Secret Sharing

Cumulative arrays have played an important role in the early development of the secret sharing theory. They have not been subject to extensive study so far, as the secret sharing schemes built on them generally result in much larger sizes of shares, when compared with other conventional approaches. Recent works in threshold cryptography show that cumulative arrays may be the appropriate building blocks in non-homomorphic threshold cryptosystems where the conventional secret sharing methods are generally of no use. In this paper we study several extensions of cumulative arrays and show that some of these extensions significantly improve the performance of conventional cumulative arrays. In particular, we derive bounds on generalised cumulative arrays and show that the constructions based on perfect hash families are asymptotically optimal. We also introduce the concept of ramp perfect hash families as a generalisation of perfect hash families for the study of ramp secret sharing schemes and ramp cumulative arrays.     

强度m的对称正交表的递归构造

本文证明了Q~n空间的正交分划的存在性,对2水平正交表的递归构造方法进行了改进,通过对正交分划的构造提出了任意强度的高水平对称正交表的递归构造方法.     

强度1二元正交阵列计数

利用Pólya计数理论给出强度1二元正交阵列计数公式.     

Parameter Inequalities for Orthogonal Arrays with Mixed Levels

An important question in the construction of orthogonal arrays is what the minimal size of an array is when all other parameters are fixed. In this paper, we will provide a generalization of an inequality developed by Bierbrauer for symmetric orthogonal arrays. We will utilize his algebraic approach to provide an analogous inequality for orthogonal arrays having mixed levels and show that the bound obtained in this fashion is often sharper than Raos bounds. We will also provide a new proof of Raos inequalities for arbitrary orthogonal arrays with mixed levels based on the same method.     

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     

Construction of Asymmetric Orthogonal Arrays of Strength Three via a Replacement Method

A replacement procedure to construct orthogonal arrays of strength three was proposed by Suen et al. [7]. This method was later extended by Suen and Dey [8]. In this paper, we further explore the replacement procedure to obtain some new families of orthogonal arrays of strength three.     

Linear hash families and forbidden configurations

The classical orthogonal arrays over the finite field underlie a powerful construction of perfect hash families. By forbidding certain sets of configurations from arising in these orthogonal arrays, this construction yields previously unknown perfect, separating, and distributing hash families. When the strength s of the orthogonal array, the strength t of the hash family, and the number of its rows are all specified, the forbidden sets of configurations can be determined explicitly. Each forbidden set leads to a set of equations that must simultaneously hold. Hence computational techniques can be used to determine sufficient conditions for a perfect, separating, and distributing hash family to exist. In this paper the forbidden configurations, resulting equations, and existence results are determined when (s, t) ∈ {(2, 5), (2, 6), (3, 4), (4, 3)}. Applications to the existence of covering arrays of strength at most six are presented.      

Packing Arrays and Packing Designs

A packing array is a b × k array, A with entriesa _i,j from a g-ary alphabet such that given any two columns,i and j, and for all ordered pairs of elements from a g-ary alphabet,(g ₁, g ₂), there is at most one row, r, such thata _r,i = g ₁ anda _r,j = g ₂. Further, there is a set of at leastn rows that pairwise differ in each column: they are disjoint. A central question is to determine, forgiven g, k and n, the maximum possible b. We examine the implications whenn is close to g. We give a brief analysis of the case n = g and showthat 2g rows is always achievable whenever more than g exist. We give an upper bound derivedfrom design packing numbers when n = g – 1. When g + 1 k then this bound is always at least as good as the modified Plotkin bound of [12]. When theassociated packing has as many points as blocks and has reasonably uniform replication numbers, we show thatthis bound is tight. In particular, finite geometries imply the existence of a family of optimal or near optimalpacking arrays. When no projective plane exists we present similarly strong results. This article completelydetermines the packing numbers, D(v, k, 1), when .     

Constructing Covering Codes with Given Automorphisms

Let K(n,r) denote the minimum cardinality of a binary covering code of length n and covering radius r. Constructions of covering codes give upper bounds on K(n,r). It is here shown how computer searches for covering codes can be sped up by requiring that the code has a given (not necessarily full) automorphism group. Tabu search is used to find orbits of words that lead to a covering. In particular, a code D found which proves K(13,1) 704, a new record. A direct construction of D given, and its full automorphism group is shown to be the general linear group GL(3,3). It is proved that D is a perfect dominating set (each word not in D is covered by exactly one word in D) and is a counterexample to the recent Uniformity Conjecture of Weichsel.     

混合水平正交设计的最优选择

利用矩阵象方法,首先将强度2下混合水平正交设计的混杂度量,推广到强度t下混合水平正交设计的混杂度量,然后通过这些混杂度量指标,给出了强度t下混合水平正交设计的四个分辨度指标,其具有水平置换不变性,并能同时用于等水平情形和混合水平情形。最后对混合水平正交表OA(18,6~13~6,2)进行了实例计算,并讨论四个分辨度的差异性。     

New Constructions of Covering Codes

Coveringcode constructions obtaining new codes from starting ones weredeveloped during last years. In this work we propose new constructionsof such kind. New linear and nonlinear covering codes and aninfinite families of those are obtained with the help of constructionsproposed. A table of new upper bounds on the length functionis given.     

由正交表变换得到的2阶平衡的相关免疫函数

本本文给出了一种运用正交表变换来得到2阶相关免疫函数的特征矩阵的新方法,构造出10个不同的(8,4,2,2)特征矩阵,得到了几个相关结论。