Multilevel Threshold Secret Sharing based on the Chinese Remainder Theorem

Year 2019, Volume: 8 Issue: 2, 17 - 29, 01.06.2019

Oguzhan Ersoy Kamer Kaya Kerem Kaskaloglu

Abstract

In multilevel secret sharing, a secret is shared among a set of hierarchically organized participants in a way that the members of the superior compartments are more powerful and can replace the participants of an inferior one to form an authorized coalition during secret reconstruction. In this work, we first show that the only existing multilevel threshold secret sharing scheme based on the Chinese Remainder Theorem CRT is not secure and fails to work with certain natural threshold settings on compartments. As the main contribution, we propose a secure CRTbased scheme that works for all threshold settings. In the proposed scheme, we employ a refined version of Asmuth-Bloom secret sharing with a special and generic Asmuth-Bloom sequence called the anchor sequence. Based on this novel idea, we also propose the first multilevel conjunctive threshold secret sharing scheme based on the Chinese Remainder Theorem.

Keywords

—Secret sharing, multilevel cryptography, Chinese Remainder Theorem

References

• [1] Charles Asmuth and John Bloom. A modular approach to key safeguarding. IEEE Transactions on Information Theory, 30(2):208–210, 1983.
• [2] Amos Beimel. Secret-sharing schemes: A survey. volume 6639 of Coding and Cryptology, pages 11–46. 2011.
• [3] Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security, CCS ’93, pages 62–73, New York, NY, USA, 1993. ACM.
• [4] George Robert Blakley. Safeguarding cryptographic keys. volume 48 of Proceedings of the National Computer Conference, pages 313–317, 1979.
• [5] Ilker Nadi Bozkurt, Kamer Kaya, and Ali Aydın Selc¸uk. Secret sharing for general access structures. 4th International Conference on Information Security and Cryptology, Ankara, Turkey, 2010.
• [6] Oguzhan Ersoy, Thomas Brochmann Pedersen, Kamer Kaya, ˘ Ali Aydin Selc¸uk, and Emin Anarim. A crt-based verifiable secret sharing scheme secure against unbounded adversaries. Security and Communication Networks, 9(17):4416–4427, 2016.
• [7] Hossein Ghodosi, Josef Pieprzyk, and Rei Safavi-Naini. Secret sharing in multilevel and compartmented groups. Information Security and Privacy, pages 367–378, 1998.
• [8] Cheng Guo and Chin-Chen Chang. An authenticated group key distribution protocol based on the generalized chinese remainder theorem. International Journal of Communication Systems, 27(1):126–134, 2014.
• [9] Lein Harn and Miao Fuyou. Multilevel threshold secret sharing based on the chinese remainder theorem. Information Processing Letters, 114(9):504–509, 2014.
• [10] Sorin Iftene. Compartmented secret sharing based on the chinese remainder theorem. IACR Cryptology ePrint Archive, 2005:408, 2005.
• [11] Sorin Iftene. General secret sharing based on the chinese remainder theorem with applications in e-voting. Electronic Notes in Theoretical Computer Science, 186:67–84, 2007.
• [12] Mitsuru Ito, Akira Saito, and Takao Nishizeki. Secret sharing scheme realizing general access structure. Proc. of the IEEE Global Telecom. Conf., Globecom 87, pages 99–102, 1987.
• [13] Kamer Kaya and Ali Aydın Selc¸uk. A verifiable secret sharing scheme based on the Chinese Remainder Theorem. volume 5365 of Progress in Cryptology - INDOCRYPT 2008, pages 414–425. 2008.
• [14] Kamer Kaya and Ali Aydın Selc¸uk. Threshold cryptography based on Asmuth-Bloom secret sharing. Information Sciences, 177(19):4148–4160, 2007.
• [15] Kamer Kaya and Ali Aydin Selc¸uk. Sharing DSS by the chinese remainder theorem. J. Computational Applied Mathematics, 259:495–502, 2014.
• [16] Yanjun Liu, Lein Harn, and Chin-Chen Chang. An authenticated group key distribution mechanism using theory of numbers. International Journal of Communication Systems, 27(11):3502– 3512, 2014.
• [17] Yanjun Liu, Lein Harn, and Chin-Chen Chang. A novel verifiable secret sharing mechanism using theory of numbers and a method for sharing secrets. International Journal of Communication Systems, 28(7):1282–1292, 2015. IJCS-13- 0526.R3.
• [18] Maurice Mignotte. How to share a secret. Cryptography, pages 371–375. 1983.
• [19] Michael Quisquater, Bart Preneel, and Joos Vandewalle. On ¨ the security of the threshold scheme based on the Chinese Remainder Theorem. Public Key Cryptography, pages 199–210, 2002.
• [20] Adi Shamir. How to share a secret. Communications of the ACM, 22(11):612–613, 1979.
• [21] Gustavus J Simmons. How to (really) share a secret. Proceedings on Advances in Cryptology, pages 390–448, 1990.
• [22] Tamir Tassa. Hierarchical threshold secret sharing. Theory of cryptography, pages 473–490. Springer, 2004.