Several Properties Of Monotone Span Program

The study of secure multiparty computation is important in the field of cryptog-raphy. Linear secret sharing scheme is one of the main tools to construct the securemultiparty computation protocol, and there are two important tools to realize linearsecret sharing scheme, which are linear code and monotone span program. There isan1-1correspondence between the linear code and monotone span program, hencemonotone span program becomes a key to construct secure multiparty computation.On the one hand, the row size and column size of a monotone span program arecorresponding to the efficiency of a linear secret sharing scheme and computationalcomplexity for reconstructing key respectively, so it is a significative topic to find theinfima of row size and column size of monotone span program; On the other hand,when using linear secret sharing scheme to realize secure multiparty computation, weneed to use monotone span program with multiplication, so it is a core of secure mul-tiparty computation to construct a monotone span program with multiplication. In thispaper, we get the following results for these two issues:1. For any given access structure Γ, there is an1-1correspondence betweenthe linear code C and monotone span program (Fq, M, φ, ε) to realize it;2. infRsize(M)=minG,H{number(Gc)1|GH=0}, where Rsize(M)is the row size of matrix M, infRsize(M) is the infima of Rsize(M), andnumber(Gc) denotes the column number of G;3. infCsize(M)=minG,H{Rrank(G)|GH=0}≤|R(G)|, where Csize (M) is the column size of matrix M, infCsize(M) is the infima of Csize(M),|R(G)|denotes the number of elements in maximal adversary structure, and Rrank(G)is the rows rank of G.4. Give algorithms to generate monotone span programs with infima of rowsize and column size.5. Give a new algorithm to construct monotone span program with multipli-cation, which has the following advantage compare to Cramer’s： Without changing the column size, we may get a monotone span programwith multiplication, which has the row size less than double of the original one.6. We obtain a theory that, if the adversary structure does’t meet the Q2condition, there must be two columns in the monotone span program received bythe above algorithms, such that the result of the two columns’ operation”” is zerovector.7. Finally, we point out that the optimal monotone span program with multi-plication can be found in theory, and then it can be used to construct secure multipartycomputation protocol.