A novel threshold changeable secret sharing scheme

Abstract

A (t, n) threshold secret sharing scheme is a fundamental tool in many security applications such as cloud computing and multiparty computing. In conventional threshold secret sharing schemes, like Shamir’s scheme based on a univariate polynomial, additional communication key share scheme is needed for shareholders to protect the secrecy of their shares if secret reconstruction is performed over a network. In the secret reconstruction, the threshold changeable secret sharing (TCSS) allows the threshold to be a dynamic value so that if some shares have been compromised in a given time, it needs more shares to reconstruct the secret. Recently, a new secret sharing scheme based on a bivariate polynomial is proposed in which shares generated initially by a dealer can be used not only to reconstruct the secret but also to protect the secrecy of shares when the secret reconstruction is performed over a network. In this paper, we further extend this scheme to enable it to be a TCSS without any modification. Our proposed TCSS is dealer-free and non-interactive. Shares generated by a dealer in our scheme can serve for three purposes, (a) to reconstruct a secret; (b) to protect the secrecy of shares if secret reconstruction is performed over a network; and (c) to enable the threshold changeable property.

Keywords

cryptography 94A60 / authentication and secret cryptography 94A60 / authentication and secret

References

[1] Shamir A. How to share a secret. Communications of the ACM, 1979, 22(11): 612–613

[2] Blakley G R. Safeguarding cryptographic keys. In: Proceedings of Managing Requirements Knowledge, International Workshop on IEEE Computer Society. 1979

[3] Harn L, Lin C. Strong (n, t, n) verifiable secret sharing scheme. Information Sciences, 2010, 180(16): 3059–3064

[4] Harn L, Fuyou M, Chang C C. Verifiable secret sharing based on the Chinese remainder theorem. Security and Communication Networks, 2014, 7(6): 950–957

[5] Fuchsbauer G, Katz J, Naccache D. Efficient rational secret sharing in standard communication networks. In: Proceedings of Springer Theory of Cryptography Conference. 2010, 419–436

[6] Tartary C, Wang H X, Zhang Y. An efficient and information theoretically secure rational secret sharing scheme based on symmetric bivariate polynomials. International Journal of Foundations of Computer Science, 2011, 22(6): 1395–1416

[7] Herzberg A, Jarecki S, Krawczyk H, Yung M. Proactive secret sharing or: how to cope with perpetual leakage. In: Proceedings of Springer Annual International Cryptology Conference. 1995, 339–352

[8] Harn L, Xu C F. Dynamic threshold secret reconstruction and its application to the threshold cryptography. Information Processing Letters, 2015, 115(11): 851–857

[9] Harn L, Xu C F, Xia Z, Zhou J. How to share secret efficiently over networks. Journal of Security and Communication Networks, 2017, 2017(4): 1–6

[10] Martin K, Pieprzyk J, Safavi-Naini R, Wang H. Changing thresholds in the absence of secure channels. In: Proceedings of Springer Australasian Conference on Information Security and Privacy. 1999, 177–191

[11] Steinfeld R, Wang H, Pieprzyk J. Lattice-based threshold changeability for standard Shamir secret-sharing schemes. IEEE Transactions on Information Theory, 2007, 53(7): 2542–2559

[12] Asmuth C A, Bloom J. A modular approach to key safeguarding. IEEE Transactions on Information Theory, 1983, 29(2): 208–210

[13] Blundo C, De Santis A, Herzberg A, Kutten S, Vaccaro U, Yung M. Perfectly-secure key distribution for dynamic conferences. Information and Computation, 1998, 146(1): 1–23

[14] Blom R. An optimal class of symmetric key generation systems. In: Proceedings of Springer Workshop on the Theory and Application of of Cryptographic Techniques. 1984, 335–338

[15] Katz J, Koo C Y, Kumaresan R. Improving the round complexity of VSS in point-to point networks. Information and Computation, 2009, 207(8): 889–899

[16] Kumaresan R, Patra A, Rangan C P. The round complexity of verifiable secret sharing: the statistical case. In: Proceedings of Springer International Conference on the Theory and Application of Cryptology and Information Security. 2010, 431–447

[17] Nikov V, Nikova S. On proactive secret sharing schemes. In: Proceedings of Springer International Workshop on Selected Areas in Cryptography. 2004, 308–325

[18] Zhang Z, Chee Y M, Ling S, Liu M, Wang H. Threshold changeable secret sharing schemes revisited. Theoretical Computer Science, 2012, 418: 106–115

[19] Martin KM, Pieprzyk J, Safavi-Nain R,Wang H. Changing thresholds in the absence of secure channels. In: Proceedings of Springer Australasian Conference on Information Security and Privacy. 1999, 177–191

[20] Lou T, Tartary C. Analysis and design of multiple threshold changeable secret sharing. In: Proceedings of Springer International Conference on Cryptology and Network Security. 2008, 196–213

[21] Steinfeld R, Pieprzyk J, Wang H X. Lattice-based threshold changeability for standard CRT secret-sharing schemes. Finite Fields and Their Applications, 2006, 12(4): 653–680

[22] Yuan L, Li M, Guo C, Choo K K R, Ren Y. Novel threshold changeable secret sharing schemes based on polynomial interpolation. PLoS ONE, 2016, 11(10): 1–19

[23] Meng K, Miao F, Huang W, Xiong Y. Threshold changeable secret sharing with secure secret reconstruction. Information Processing Letters, 2020, 157: 105928

[24] Saniee K. A simple expression for multivariate lagrange interpolation. Journal of Society for Industrial and Applied Mathematics, 2007, 1–9

[25] Donald E K. The art of computer programming. Sorting and Searching, 1999, 3: 426–458

[26] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM, 1978, 21(2): 120–126

[27] Denning D E R. Cryptography and Data Security. Massachusetts: Addison Wesley, 1982

RIGHTS & PERMISSIONS

2022 Higher Education Press