A novel threshold changeable secret sharing scheme
Lein HARN1, Chingfang HSU2(), Zhe XIA3
1. Department of Computer Science Electrical Engineering, University of Missouri-Kansas City, Kansas City, MO 64110, USA 2. Computer School, Central China Normal University,Wuhan 430079, China 3. Department of Computer Science, Wuhan University of Technology,Wuhan 430071, China
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.
G R Blakley. Safeguarding cryptographic keys. In: Proceedings of Managing Requirements Knowledge, International Workshop on IEEE Computer Society. 1979 https://doi.org/10.1109/MARK.1979.8817296
L Harn, M Fuyou, C C Chang. Verifiable secret sharing based on the Chinese remainder theorem. Security and Communication Networks, 2014, 7(6): 950–957 https://doi.org/10.1002/sec.807
5
G Fuchsbauer, J Katz, D Naccache. Efficient rational secret sharing in standard communication networks. In: Proceedings of Springer Theory of Cryptography Conference. 2010, 419–436 https://doi.org/10.1007/978-3-642-11799-2_25
6
C Tartary, H X Wang, Y Zhang. 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 https://doi.org/10.1142/S0129054111008775
7
A Herzberg, S Jarecki, H Krawczyk, M Yung. Proactive secret sharing or: how to cope with perpetual leakage. In: Proceedings of Springer Annual International Cryptology Conference. 1995, 339–352 https://doi.org/10.1007/3-540-44750-4_27
8
L Harn, C F Xu. Dynamic threshold secret reconstruction and its application to the threshold cryptography. Information Processing Letters, 2015, 115(11): 851–857 https://doi.org/10.1016/j.ipl.2015.06.014
9
L Harn, C F Xu, Z Xia, J Zhou. How to share secret efficiently over networks. Journal of Security and Communication Networks, 2017, 2017(4): 1–6 https://doi.org/10.1155/2017/5437403
10
K Martin, J Pieprzyk, R Safavi-Naini, H Wang. Changing thresholds in the absence of secure channels. In: Proceedings of Springer Australasian Conference on Information Security and Privacy. 1999, 177–191 https://doi.org/10.1007/3-540-48970-3_15
11
R Steinfeld, H Wang, J Pieprzyk. Lattice-based threshold changeability for standard Shamir secret-sharing schemes. IEEE Transactions on Information Theory, 2007, 53(7): 2542–2559 https://doi.org/10.1109/TIT.2007.899541
12
C A Asmuth, J Bloom. A modular approach to key safeguarding. IEEE Transactions on Information Theory, 1983, 29(2): 208–210 https://doi.org/10.1109/TIT.1983.1056651
13
C Blundo, A De Santis, A Herzberg, S Kutten, U Vaccaro, M Yung. Perfectly-secure key distribution for dynamic conferences. Information and Computation, 1998, 146(1): 1–23 https://doi.org/10.1006/inco.1998.2717
14
R Blom. 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 https://doi.org/10.1007/3-540-39757-4_22
15
J Katz, C Y Koo, R Kumaresan. Improving the round complexity of VSS in point-to point networks. Information and Computation, 2009, 207(8): 889–899 https://doi.org/10.1016/j.ic.2009.03.007
16
R Kumaresan, A Patra, C P Rangan. 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 https://doi.org/10.1007/978-3-642-17373-8_25
17
V Nikov, S Nikova. On proactive secret sharing schemes. In: Proceedings of Springer International Workshop on Selected Areas in Cryptography. 2004, 308–325 https://doi.org/10.1007/978-3-540-30564-4_22
18
Z Zhang, Y M Chee, S Ling, M Liu, H Wang. Threshold changeable secret sharing schemes revisited. Theoretical Computer Science, 2012, 418: 106–115 https://doi.org/10.1016/j.tcs.2011.09.027
19
KM Martin, J Pieprzyk, R Safavi-Nain, H Wang. Changing thresholds in the absence of secure channels. In: Proceedings of Springer Australasian Conference on Information Security and Privacy. 1999, 177–191 https://doi.org/10.1007/3-540-48970-3_15
20
T Lou, C Tartary. Analysis and design of multiple threshold changeable secret sharing. In: Proceedings of Springer International Conference on Cryptology and Network Security. 2008, 196–213 https://doi.org/10.1007/978-3-540-89641-8_14
21
R Steinfeld, J Pieprzyk, H X Wang. Lattice-based threshold changeability for standard CRT secret-sharing schemes. Finite Fields and Their Applications, 2006, 12(4): 653–680 https://doi.org/10.1016/j.ffa.2005.04.007
22
L Yuan, M Li, C Guo, K K R Choo, Y Ren. Novel threshold changeable secret sharing schemes based on polynomial interpolation. PLoS ONE, 2016, 11(10): 1–19 https://doi.org/10.1371/journal.pone.0165512
23
K Meng, F Miao, W Huang, Y Xiong. Threshold changeable secret sharing with secure secret reconstruction. Information Processing Letters, 2020, 157: 105928 https://doi.org/10.1016/j.ipl.2020.105928
24
K Saniee. A simple expression for multivariate lagrange interpolation. Journal of Society for Industrial and Applied Mathematics, 2007, 1–9 https://doi.org/10.1137/08S010025
25
E K Donald. The art of computer programming. Sorting and Searching, 1999, 3: 426–458
26
R L Rivest, A Shamir, L Adleman. A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM, 1978, 21(2): 120–126 https://doi.org/10.1145/359340.359342
27
D E R Denning. Cryptography and Data Security. Massachusetts: Addison Wesley, 1982
