TANG Chunming, CHEN Yuenai, GAO Xuhong, “Monotone Span Program vs. Linear Code,” Chinese Journal of Electronics, vol. 25, no. 6, pp. 991-998, 2016, doi: 10.1049/cje.2016.10.025
Citation: TANG Chunming, CHEN Yuenai, GAO Xuhong, “Monotone Span Program vs. Linear Code,” Chinese Journal of Electronics, vol. 25, no. 6, pp. 991-998, 2016, doi: 10.1049/cje.2016.10.025

Monotone Span Program vs. Linear Code

doi: 10.1049/cje.2016.10.025
Funds:  This work is 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), and Basic Research Major Projects of Department of Education of Guangdong Province (No.2014KZDXM044).
  • Received Date: 2014-08-18
  • Rev Recd Date: 2015-04-19
  • Publish Date: 2016-11-10
  • 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.
  • loading
  • G.R. Blakley, "Safeguarding cryptographic keys", Proc. of the National Computer Conference, America, pp.313-317, 1979.
    A. Shamir, "How to share a secret", Communications of the ACM, Vol.22, No.1979, pp.612-613, 1979.
    R.J. McEliece and D.V. Sarwate, "On sharing secrets and Reed-Solomon codes", Communications of the ACM, Vol.24, No.1981, pp.583-584, 1981.
    J.L. Massey, "Minimal codewords and secret sharing", Proc. of the 6th Joint Swedish-Russian Workshop on Information Theory, pp.276-279, 1993.
    J.L. Massey, "Some applications of coding theory", in Cryptography, Codes and Ciphers:Cryptography and Coding IV, Esses, England, pp.33-47, 1995.
    J.L. Massey, "Three coding problems", Report in Trondhjemsgade 3, 2TH DK-2100 Copenhagen, Denmark, 2009.
    C.M. Tang, S.H. Gao and C.L. Zhang, "The optimal linear secret sharing schemes for any given access structure", Journal of Systems Science & Complexity, Vol.26, No.4, pp.634-649, 2013.
    M. Ito, A. Saito and T. Nishizeki, "Secret sharing scheme realizing any access structure", Proc. of IEEE Globecom 87, pp.99-102, 1987.
    L. Csirmaz, "The dealer's random bits in perfect secret sharing schemes", Studia Scientiarum Mathematicarum Hungarica, Vol.32, No.3, pp.1-10, 1996.
    M. Karchmer and A. Wigderson, "On span programes", Proc. of the 8-th Annual Structure in Complexity Theory Conference, San Diego, CA, USA, pp.102-111, 1993.
    R. Cramer, I. Damgard and U. Maurer, "General secure multiparty computationfrom any linear secret-sharing scheme", Advances in Cryptology-EUROCRYPT 2000 Lecture Notes in Computer Science, Vol.1807, No.2000, pp.316-334, 2000.
    A. Beimel, A. Gal and M. Paterson, "Lower bounds for monotone span programs", Computational Complexity, Vol.6, No.1, pp.29-45, 1996.
    L. Babai, A. Gal and A. Wigderson, "Superpolynomial lower bounds for monotone span programs", Combinatorica, Vol.19, No.3, pp.301-319, 1999.
    A. Gal, "Combinatorial methods in boolean functions complexity", Ph.D. Thesis, University of Illinois at Chicago, USA, 1995.
    A. Gal, "A characterization of span program size an improved lower bounds for monotone span programs", Computational Complexity, Vol.10, No.4, pp.277-296, 2001.
    V. Nikov, S. Nikova and B. Preneel, "On the size of monotone span programs", Security in Communication Networks, Lecture Notes in Computer Science Vol.3352, No.2005, pp.249-262, 2005.
    R. Cramer and S. Fehr, "Optimal blach-box secret sharing over arbitrary abelian groups", Advances in Cryptology CRYPTO 2002, Lecture Notes in Computer Science, Vol.2442, No.2002, pp.272-287, 2002
    M. Dijk, "Secret key sharing and secret key generation", Ph.D. Thesis, TU Eindhoven, Netherlands, 1997.
  • 加载中


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (618) PDF downloads(798) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint