Monotone Span Program vs. Linear Code

作     者：TANG Chunming CHEN Yuenai GAO Xuhong 

作者机构：School of Mathematics and Information SciencesGuangzhou University Key Laboratory of Mathematics and Interdisciplinary Sciences of Guangdong Higher Education InstitutesGuangzhou University Department of Mathematical SciencesClemson University 

出 版 物：《Chinese Journal of Electronics》 (电子学报(英文))

年 卷 期：2016年第25卷第6期

页      面：991-998页

核心收录：

学科分类：11[军事学] 1105[军事学-军队指挥学] 110505[军事学-密码学] 

基　　金：supported by the National Natural Science Foundation of China (No.11271003) the Joint Specialized Research Fund for the Doctoral Program of Higher Education (No.20134410110003) Project of Department of Education of Guangdong Province (No.2013KJCX0146) Science Research Project of Education Bureau in Guangzhou(No.2012A004) Basic Research Major Projects of Department of Education of Guangdong Province (No.2014KZDXM044) 

主　　题：Cryptography Secret sharing scheme Monotone span program Linear code Size 

摘      要：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.