Open AccessMonotone Span Program vs. Linear Code
Author(s) -
Tang Chunming,
Chen Yuenai,
Gao Xuhong
Publication year - 2016
Publication title -
chinese journal of electronics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.267
H-Index - 25
eISSN - 2075-5597
pISSN - 1022-4653
DOI - 10.1049/cje.2016.10.025
Subject(s) - monotone polygon , span (engineering) , code (set theory) , mathematics , computer science , programming language , structural engineering , geometry , engineering , set (abstract data type)
Monotone span program(MSP) and Linear code(LC) are efficient tools to construct Linear secret sharing scheme (LSSS) for a given access structure. Since the size of an MSP or the length of an LC corresponds to the communicational complexity of an LSSS, one main motivation to study MSPs or LCs is the lower bound for their sizes or lengths. Therefore, it is one of the most important open problems how to efficiently construct an MSP or LC for a given access structure Γ with the smallest sizes or shortest length. Our contributions are: We extend TANG et al. 's result, showing that, for any given access structure Γ , there exists an MSP or an LC to realize Γ if and only if a system of quadratic equations has solutions; We utilize the relationship between LCs and MSPs to obtain the greatest lower bound on the row size and the column size of MSPs realizing a given Γ , as well as an upper bound on the column size of MSPs; We give an algorithm to construct an MSP with the smallest sizes.