Some Constructions For (m,t)-Splitting Systems

An (m, t)-splitting system is a pair (X, B) called set system, where|X|=m, in which exists a block B∈B such that|B(?)Y|=「t/2」for every Y C X and|Y|=t. In the paper, we use the notation (N; m, t) to denote an (m,t)-splitting system having N blocks. Given the parameter m, t, N(m, t) denote the minimum value of N in all (N; m,t)-splitting systems. In splitting systems,(N(m, t);m,t)-splitting systems are called optimal.Splitting systems were used by Stinson and Coppersmith in baby-step giant-step al-gorithms for the low hamming weight discrete logarithm problem. In baby-step giant-step algorithms, N is required to be as small as possible. There exists a ((「t/2」m);m,t)-splitting system for all integers m and t≥2, therefore main work for researching splitting systems is to study their properties and constructions and to look for optimal splitting system with them. In2007, Deng, Stinson studied some properties of splitting systems, presented some constructions for (m,3)-splitting systems and proved N(m, t)≥「log2(m-t+1)」+1for all integers m≥t+1.In this paper, by applying the incidence matrix of splitting system and other related combinatorial structures, we research constructions of (m,t)-splitting systems and deter-mine the bound of N(m,t), furthermore, find out some optimal splitting systems. Main content of this paper is divided into two parts as follows:In the first part, firstly, we determine N(t+2,t)=3and N(m,2)=[log2m] by directly constructing (m, t)-splitting system and the lower bound of N(m,t). Secondly, We get 「log2(m-3)」≤N(m,4)≤「m/2」 by constructing an (「m/2」;m,4)-SS, and obtain an (N-1/2(t2t)+1; m,2t)-SS from an (N; m, t,t)-separating system. Lastly, we present a construction method of (m,t)-splitting systems with perfect hash families, and use it to construct (3×4j;52j,3)-SS (positive integer j),(7「m/2」; m2,4)-SS,(6「m/2」; m2,4)-SS, where m is power of a prime, and so on.In the second part, for t=4, by researching construction of the incidence matrix of splitting system, we present some recursive constructions for (m,4)-splitting systems, including indirect construction and product construction. First of all, by applying matrix cross product, we obtain a disjuct (N1+N2+m1+m2; m2m1,4)-SS from known (N1; m1,4)-SS and (N2;m2,4)-SS, and get a disjunct (2(N1+n);m2,4)-SS from an (N1;m,4)-SS combined with properties of cover-free families,where n≥7,n≡1,3(mod6)and m=(n((n-1)))/6.Finally,we obtain a(km1,4)-SS(k=3,4)from existing(m1,4)-SS with matrix block and residue class idea,and use balanced incomplete block design to construct a regular(((m2-m))/6;(m-1)/2,m,4)-SS,where m≡1,3(mod6).