Monotone Span Program vs. Linear Code. Issue 6 (1st November 2016)

• Record Type: Journal Article
• Authors: Tang, Chunming; Chen, Yuenai; Gao, Xuhong
• Is Part Of: Chinese journal of electronics. Volume 25:Issue 6(2016)
• Page Start: 991
• Page End: 998
• Publication Date: 2016-11-01
• Subjects: Cryptography -- Secret sharing scheme -- Monotone span program -- Linear code -- Size; cryptography -- quadratic programming; monotone span program -- linear code -- MSP -- LC -- linear secret sharing scheme -- LSSS -- communicational complexity -- access structure -- quadratic equations; Electronics -- Periodicals; Electronics -- China -- Periodicals; Electronics; China; Periodicals; 621.38105
• DOI: 10.1049/cje.2016.10.025
• Languages: English
• ISSNs: 1022-4653

Abstract

Abstract : 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.