A proactive secret sharing scheme based on Chinese remainder theorem

Abstract

If an adversary tries to obtain a secret s in a (t, n) threshold secret sharing (SS) scheme, it has to capture no less than t shares instead of the secret s directly. However, if a shareholder keeps a fixed share for a long time, an adversary may have chances to filch some shareholders’ shares. In a proactive secret sharing (PSS) scheme, shareholders are supposed to refresh shares at fixed period without changing the secret. In this way, an adversary can recover the secret if and only if it captures at least t shares during a period rather than any time, and thus PSS provides enhanced protection to long-lived secrets. The existing PSS schemes are almost based on linear SS but no Chinese Remainder Theorem (CRT)-based PSS scheme was proposed. This paper proposes a PSS scheme based on CRT for integer ring to analyze the reason why traditional CRT-based SS is not suitable to design PSS schemes. Then, an ideal PSS scheme based on CRT for polynomial ring is also proposed. The scheme utilizes isomorphism of CRT to implement efficient share refreshing.

Keywords

proactive secret sharing / Chinese remainder theorem / polynomial ring / integer ring / isomorphism

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 the National Computer Conference. 1979, 313–317

[3] Harn L, Lin C. Authenticated group key transfer protocol based on secret sharing. IEEE Transactions on Computers, 2010, 59(6): 842–846

[4] Lv X, Li H, Wang B. Identity-based key distribution for mobile Ad Hoc networks. Frontiers of Computer Science, 2011, 5(4): 442–447

[5] Harn L. Group-oriented (t, n) threshold digital signature scheme and digital multisignature. IEE Proceedings-Computers and Digital Techniques, 1994, 141(5): 307–313

[6] Tang S. Simple secret sharing and threshold RSA signature schemes. Journal of Information and Computational Science, 2004, 1(2): 259–262

[7] Kamal A A A M, Iwamura K. Conditionally secure multiparty computation using secret sharing scheme for n<2k− 1. In: Proceedings of the 15th Annual Conference on Privacy, Security and Trust. 2017, 225–230

[8] Patra A, Choudhury A, Rangan C P. Efficient asynchronous verifiable secret sharing and multiparty computation. Journal of Cryptology, 2015, 28(1): 49–109

[9] Song Y, Li Z, Li Y, Xin R. The optimal information rate for graph access structures of nine participants. Frontiers of Computer Science, 2015, 9(5): 778–787

[10] Jia X, Wang D, Nie D, Luo X, Sun J Z. A new threshold changeable secret sharing scheme based on the Chinese Remainder Theorem. Information Sciences, 2019, 473: 13–30

[11] McEliece R J, Sarwate D V. On sharing secrets and Reed-Solomon codes. Communications of the ACM, 1981, 24(9): 583–584

[12] Mignotte M. How to share a secret. In: Proceedings of Workshop on Cryptography. 1982, 371–375

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

[14] Ning Y, Miao F, Huang W, Meng K, Xiong Y, Wang X. Constructing ideal secret sharing schemes based on Chinese Remainder Theorem. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. 2018, 310–331

[15] Ostrovsky R, Yung M. How to withstand mobile virus attacks. In: Proceedings of the 10th ACM Conference on Principles of Distributed Systems. 1991, 51–59

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

[17] Dehkordi M H, Mashhadi S, Oraei H. A proactive multi stage secret sharing scheme for any given access structure. Wireless Personal Communications, 2019, 104(1): 491–503

[18] Mashhadi S. Secure publicly verifiable and proactive secret sharing schemes with general access structure. Information Sciences, 2017, 378: 99–108

[19] Nikov V, Nikova S, Preneel B, Vandewalle , J. Applying general access structure to proactive secret sharing schemes. IACR Cryptology ePrint Archive, 2002, 2002: 141

[20] Zou H, Wang J. Multi-level threshold multi-secret sharing scheme with proactive security. Journal of Computer Applications, 2009

[21] Feng B, Guo C, Li M, Wang Z. A novel proactive multi-secret sharing scheme. International Journal of Network Security, 2015, 17(2): 123–128

[22] Cachin C, Kursawe K, Lysyanskaya A, Strobl R. Method of verifiably sharing a secret in potentially asynchronous networks. U.S. Patent 7,389–416. 2008-6-17

[23] Zhou L, Schneider F B, Van Renesse R. APSS: proactive secret sharing in asynchronous systems. ACM Transactions on Information and System Security, 2005, 8(3): 259–286

[24] Schultz D A, Liskov B, Liskov M. MPSS: mobile proactive secret sharing. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing. 2008, 458

[25] Baron J, El Defrawy K, Lampkins J, Ostrovsky R. Communication- optimal proactive secret sharing for dynamic groups. In: Proceedings of International Conference on Applied Cryptography and Network Security. 2015, 23–41

[26] Numao M. A secure key registration system based on proactive secretsharing scheme. In: Proceedings of the 4th International Symposium on Autonomous Decentralized Systems–Integration of Heterogeneous Systems. 1999, 230–237

[27] Yang J P, Rhee K H, Sakurai K. A proactive secret sharing for server assisted threshold signatures. In: Proceedings of International Conference on High Performance Computing and Communications. 2006, 250–259

[28] Ribet S A F W G K A. Graduate Texts in Mathematics 111. USA: Springer, 1987

[29] Capocelli R M, De Santis A, Gargano L, Vaccaro U. On the size of shares for secret sharing schemes. Journal of Cryptology, 1993, 6(3): 157–167

[30] Feldman P. A practical scheme for non-interactive verifiable secret sharing. In: Proceedings of the 28th Annual Symposium on Foundations of Computer Science. 1987, 427–438

[31] Pedersen T P. Non-interactive and information-theoretic secure verifiable secret sharing. In: Proceedings of Annual International Cryptology Conference. 1991, 129–140

RIGHTS & PERMISSIONS

2020 Higher Education Press