Publicly Verifiable Multi-stage Secret Sharing on General Access Structures

doi:10.3778/j.issn.1673-9418.2109006

Abstract

Abstract: A publicly verifiable secret sharing allows anyone to detect the cheating of dealer or participants only from the public information. In order to expand the application scope of multi-secret sharing, firstly, a publicly verifiable multi-stage secret sharing (PVMSSS) scheme is proposed, and then based on the monotone span program (MSP) and secure multi-party computation, a renewable multi-stage secret sharing scheme that can be publicly verified and used in general access structures is proposed. In the secret distribution stage, the secret share of the participants in the scheme is calculated by each participant, and the dealer does not need to transmit any secret information to the participants. Moreover, each participant only needs to maintain one secret share to realize the reconstruction of multiple secrets. Using bilinear pairing properties, anyone can verify the correctness of the secret shares before and after the update and the validity of the public information, thereby effectively preventing fraud by dealer and participants. In the secret reconstruction phase, the pseudo-share is constructed by using secure multi-party computation to ensure that the real share of each participant will never be exposed, and the versatility of the scheme is realized. In each update of the secret, the dealer only needs to announce the related public information of updated temporary shares to update the participants' secret share. Finally, the correctness and security of the scheme are analyzed. Analysis shows that under the computational Diffie-Hellman and decisional bilinear Diffie-Hellman problems and assumptions, the proposed scheme is provably secure.

Key words: monotone span program (MSP), multi-stage secret sharing, bilinear pairing, computational Diffie-Hellman and decisional bilinear Diffie-Hellman problems, provably secure

摘要： 可公开验证的秘密共享允许任何人仅从公开信息中发现分发者或参与者的欺诈行为。为扩展多秘密共享应用范围，首先提出一个可公开验证的多级秘密共享（PVMSSS）方案模型，而后基于单调张成方案及安全多方计算，构造一般存取结构上可公开验证多用的可更新的多级秘密共享方案。秘密分发阶段，方案中各参与者秘密份额由自己计算，分发者不需向参与者传送任何秘密信息，且每个参与者只需维护一个秘密份额即可实现对多个秘密的重构。利用双线性对的性质，任何人均可验证更新前后秘密份额的正确性及公开信息的有效性，从而有效防止分发者和参与者的欺诈。秘密重构阶段，利用安全多方计算构造伪份额，保证每个参与者的真实份额永远不会暴露，实现了份额的多用性。在秘密的每一次更新中，分发者只需公布更新临时份额的相应公开信息，即可实现对参与者秘密份额的更新。最后对方案的正确性和安全性进行详细分析，在计算Diffie-Hellman和判定双线性Diffie-Hellman问题及假设下，该方案是可证明安全的。

关键词: 单调张成方案（MSP）, 多级秘密共享, 双线性对, 计算Diffie-Hellman和判定双线性Diffie-Hellman问题, 可证明安全

SONG Yun, WANG Ningning, XIAO Menglin, SHAO Zhiyi. Publicly Verifiable Multi-stage Secret Sharing on General Access Structures[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(5): 1189-1200.

宋云, 王宁宁, 肖孟林, 邵志毅. 一般存取结构上可公开验证的多级秘密共享[J]. 计算机科学与探索, 2023, 17(5): 1189-1200.

References

[1] BLAKLEY G R. Safeguarding cryptographic keys[C]//Pro-ceedings of the 1979 International Workshop on Managing Requirements Knowledge, New York, Jun 4-7, 1979. Pisca-taway: IEEE, 1979: 313-317．
[2] SHAMIR A. How to share a secret[J]. Communications of the ACM, 1979, 24(11): 612-613.
[3] JAMSHIDPOUR S, AHMADIAN Z. Security analysis of a dynamic threshold secret sharing scheme using linear sub-space method[J]. Information Processing Letters, 2020, 163: 105994.
[4] HUANG P C, CHANG C C, LI Y H, et al. Enhanced (n, n)-threshold QR code secret sharing scheme based on error correction mechanism[J]. Journal of Information Security and Applications, 2021, 58(11): 102719.
[5] HARN L, XIA Z, HSU C, et al. Secret sharing with secure secret reconstruction[J]. Information Sciences, 2020, 519: 1-8.
[6] 张艳硕, 王泽豪, 杜耀刚, 等. 基于矩阵特征值的可验证无可信中心门限方案[J]. 武汉大学学报(理学版), 2020, 66(2): 135-140.
ZHANG Y S, WANG Z H, DU Y G, et al. Verifiable thres-hold scheme without trusted center based on matrix eigen-value[J]. Journal of Wuhan University (Natural Science Edition), 2020, 66(2): 135-140.
[7] ZHANG E, LI M, YIU S M, et al. Fair hierarchical secret sharing scheme based on smart contract[J]. Information Sciences, 2021, 546: 166-176.
[8] ITO M, SAITO A, NISHIZEKI T. Secret sharing schemes realizing general access structures[J]. Electronics and Communi-cations in Japan (Part III Fundamental Electronic Science), 1989, 72(9): 56-64.
[9] BRICKELL E F. Some ideal secret sharing schemes[C]//LNCS 434: Proceedings of the 1989 Workshop on the Theory and Application of Cryptographic Techniques, Houthalen, Apr 10-13, 1989. Berlin, Heidelberg: Springer, 1989: 468-475.
[10] HARN L, HSU C, ZHANG M, et al. Realizing secret sharing with general access structure[J]. Information Sciences, 2016, 367/368: 209-220.
[11] ERIGUCHI R, KUNIHIRO N. Strong security of linear ramp secret sharing schemes with general access structures[J]. Information Processing Letters, 2020, 164: 106018.
[12] MASHHADI S. Secure publicly verifiable and proactive secret sharing schemes with general access structure[J]. Information Sciences, 2017, 378: 99-108.
[13] LIU Z Q, ZHU G P, DING F, et al. Weighted visual secret sharing for general access structures based on random grids[J]. Signal Processing Image Communication, 2021, 92(4): 116129.
[14] LIN C, HU H, CHANG C C, et al. A publicly verifiable multi-secret sharing scheme with outsourcing secret reconstruction[J]. IEEE Access, 2018, 6: 70666-70673.
[15] KABIRIRAD S, ESLAMI Z. Improvement of (n,n)-multi-secret image sharing schemes based on Boolean operations[J]. Journal of Information Security and Applications, 2019, 47: 16-27.
[16] ZHANG B H, TANG Y S. On the construction and analysis of verifiable multi-secret sharing based on non-homogeneous linear recursion[J]. Journal of Information Science and En-gineering, 2018, 34(3): 749-763.
[17] LI J, WANG X, HUANG Z, et al. Multi-level multi-secret sharing scheme for decentralized e-voting in cloud computing[J]. Journal of Parallel and Distributed Computing, 2019, 130: 91-97.
[18] SONG Y, LI Z H, LI Y M, et al. A new multi-use multi-secret sharing scheme based on the duals of minimal linear codes[J]. Security and Communication Networks, 2015, 8(2): 202-211.
[19] BASIT A, CHANAKYA P, VENKAIAH V C, et al. New multi-secret sharing scheme based on super increasing sequence for level-ordered access structure[J]. International Journal of Communication Networks and Distributed Systems, 2020, 24(1): 357-380.
[20] ORAEI H, DEHKORDI M H. How to construct a verifiable multi-secret sharing scheme based on graded encoding sche-mes[J]. IET Information Security, 2019, 13(4): 343-351.
[21] LI J,?WANG X M,?HUANG Z A, et al. Multi-level multi-secret sharing scheme for decentralized e-voting in cloud com-puting[J]. Journal of Parallel and Distributed Computing, 2019, 130: 91-97.
[22]?BISHT K,?DESHMUKH M. A novel approach for multilevel multi-secret image sharing scheme[J]. Journal of Supercom-puting, 2021, 77(10): 1-35.
[23] YAN X, LI J, PAN Z, et al. Multiparty verification in image secret sharing[J]. Information Sciences, 2021, 562: 475-490.
[24] XIONG L, ZHONG X, YANG C N, et al. Transform domain-based invertible and lossless secret image sharing with au-thentication[J]. IEEE Transactions on Information Forensics and Security, 2021, 16: 2912-2925.
[25] STADLER M. Publicly verifiable secret sharing[C]//LNCS 1070: Proceedings of the 1996 International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, May 12-16, 1996. Berlin, Heidelberg: Springer, 1996: 190-199.
[26] HERZBERG A, JARECKI S, KRAWCZYK H, et al. Proactive secret sharing or: how to cope with perpetual leakage[C]//LNCS 963: Proceedings of the 15th Annual International Cry-ptology Conference, Santa Barbara, Aug 27-31, 1995. Berlin, Heidelberg: Springer, 1995: 339-352.
[27] HARN L, HSU C F. (t, n) Multi-secret sharing scheme based on bivariate polynomial[J]. Wireless Personal Communica-tions, 2017, 95(2): 1495-1504.
[28] MASHHADI S, DEHKORD M H, KIAMARI N. Provably secure verifiable multi-stage secret sharing scheme based on monotone span program[J]. IET Information Security, 2017, 11(6): 326-331.
[29] 张敏, 杜伟章. 可公开验证可定期更新的多秘密共享方案[J]. 计算机工程与应用, 2016, 52(2): 117-126.
ZHANG M, DU W Z. Publicly verifiable and periodically renewable multi-secret sharing scheme[J]. Computer Engi-neering and Applications, 2016, 52(2): 117-126.
[30] 王彩芬, 苏舜昌, 杨小东. 可动态更新的口令授权多秘密共享方案[J]. 计算机工程与科学, 2019, 41(9): 1597-1602.
WANG C F, SU S C, YANG X D. A dynamically updated password authorization multi-secret sharing scheme[J]. Com-puter Engineering and Science, 2019, 41(9): 1597-1602.
[31] CHEN D, LU W, XING W W, et al. An efficient verifiable threshold multi-secret sharing scheme with different stages[J]. IEEE Access, 2019, 7: 107104-107110.
[32] XIAO L L, LIU M L. Linear multi-secret sharing schemes[J]. Science in China Series F: Information Sciences, 2005, 48(1): 125-136.
[33] KARCHMER M, WIGDERSON A. On span programs[C]// Proceedings of the 8th Annual Structure in Complexity Theory Conference, San Diego, May 18-21, 1993. Washington: IEEE Computer Society, 1993: 102-111.
[34] GOLDREICH O, MICALI S, WIGDERSON A. How to play any mental game or a completeness theorem for protocols with honest majority[C]//Proceedings of the 19th Annual ACM Symposium on Theory of Computing. New York: ACM, 1987.
[35] 李大伟, 杨庚, 朱莉. 一种基于身份加密的可验证秘密共享方案[J]. 电子学报, 2010, 38(9): 2059-2065.
LI D W, YANG G, ZHU L. An ID based verifiable secret sharing scheme[J]. Acta Electronica Sinica, 2010, 38(9): 2059-2065.
[36] CRAMER R, DAMGARD I, MAURER U. General secure multi-party computation from any linear secret sharing scheme[C]//LNCS 1807: Proceedings of the 2000 International Con-ference on the Theory and Application of Cryptographic Te-chniques, Bruges, May 14-18, 2000. Berlin, Heidelberg: Sprin-ger, 2000: 316-334.
[37] BONEH D, FRANKLIN M. Identity-based encryption from the Weil pairing[C]//LNCS 2139: Proceedings of the 21st Annual International Cryptology Conference, Santa Barbara, Aug 19-23, 2001. Berlin, Heidelberg: Springer, 2001: 213-229.