Asynchronous Secret Reconstruction and Its Application to the Threshold Cryptography

Lein Harn, Changlu Lin

Department of Computer Science Electrical Engineering, University of Missouri-Kansas City, Kansas City, USA.
School of Mathematics and Computer Sciences, Fujian Normal University, Fuzhou, China.

DOI: 10.4236/ijcns.2014.71003                

Abstract

In Shamir’s(t,n) threshold of the secret sharing scheme, a secret is divided into n shares by a dealer and is shared among n shareholders in such a way that (a) the secret can be reconstructed when there are t or more than t shares; and (b) the secret cannot be obtained when there are fewer than t shares. In the secret reconstruction, participating users can be either legitimate shareholders or attackers. Shamir’s scheme only considers the situation when all participating users are legitimate shareholders. In this paper, we show that when there are more than t users participating and shares are released asynchronously in the secret reconstruction, an attacker can always release his share last. In such a way, after knowing t valid shares of legitimate shareholders, the attacker can obtain the secret and therefore, can successfully impersonate to be a legitimate shareholder without being detected. We propose a simple modification of Shamir’s scheme to fix this security problem. Threshold cryptography is a research of group-oriented applications based on the secret sharing scheme. We show that a similar security problem also exists in threshold cryptographic applications. We propose a modified scheme to fix this security problem as well.

Keywords

Shamir’s(t, n)Secret Sharing Scheme; Secret Reconstruction; Threshold Cryptography; Threshold Decryption; Asynchronous Networks

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	G. R. Blakley, “Safeguarding Cryptographic Keys,” Proceedings of Americian Federation of Information Processing Societies (AFIPS’79) National Computer Conference, 25-28 February 1979, California, pp. 313-317.
[2]	A. Shamir, “How to Share a Secret,” Academic Common Market, Vol. 22, No. 11, 1979, pp. 612-613. http://dx.doi.org/10.1145/359168.359176
[3]	M. Mignotte, “How to Share a Secret,” CryptographyProceedings of the Workshop on Cryptography, Burg Feuerstein, 29 March-2 April 1982, pp. 371-375.
[4]	C. A. Asmuth and J. Bloom, “A Modular Approach to Key Safeguarding,” IEEE Transactions on Information Theory, Vol. IT-29, No. 2, 1983, pp. 208-210. http://dx.doi.org/10.1109/TIT.1983.1056651
[5]	Y. Desmedtm, “Society and Group Oriented Cryptography: An New Concept,” Advances in Cryptography—7th Annual International Cryptology Conference (CRYPTO ’87), Santa Barbara, 16-20 August 1987, pp. 120-127.
[6]	B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, “Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults,” Proceedings of the 26th IEEE Symposium on the Foundations of Computer Science, Portland, 21-23 October 1985, pp. 383-395.
[7]	M. H. Dehkordi and S. Mashhad, “New Efficient and Practical Verifiable Multi-SSs,” Information Sciences, Vol. 178, No. 9, 2008, pp. 2262-2274. http://dx.doi.org/10.1016/j.ins.2007.11.031
[8]	J. C. Benaloh, “Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret,” Advances in Cryptology—6th Annual International Cryptology Conference (CRYPTO ‘86), Santa Barbara, 17-21 August 1987, pp. 251-260.
[9]	E. F. Brickle and D. R. Stinson, “The Detection of Cheaters in Threshold Schemes,” Advances in Cryptology—9th Annual International Cryptology Conference (CRYPTO ‘88), Santa Barbara, 21-25 August 1988, pp. 564-577.
[10]	M. Tompa and H. Woll, “How to Share a Secret with Cheaters,” Journal of Cryptology, Vol. 1, No. 3, 1988, pp. 133-138. http://dx.doi.org/10.1007/BF02252871
[11]	T. Rabin and M. Ben-Or, “Verifiable Secret Sharing and Multiparty Protocols with Honest Majority,” Proceedings of the 21st ACM Symposium on the Theory of Computing, Seattle, Washington DC, 14-17 May 1989, pp. 73-85.
[12]	D. Chaum, C. Crepeau and I. Damgard, “Multipary Unconditionally Secure Protocols,” Proceedings of the 20th ACM Symposium on the Theory of Computing, Chicago, 2-4 May 1988, pp. 11-19.
[13]	J. He and E. Dawson, “Shared Secret Reconstruction,” Designs, Codes and Cryptography, Vol. 14, No. 3, 1998, pp. 221-237. http://dx.doi.org/10.1023/A:1008200702849
[14]	D. Chaum, I. Damgard and J. van de Graaf, “Multiparty Computations Ensuring Privacy of Each Party’s Input and Correctness of the Result,” Advances in Cryptography—7th Annual International Cryptology Conference (CRYPTO ’87), Santa Barbara, 16-20 August 1987, pp. 87-119.
[15]	D. Beaver and S. Goldwasser, “Multiparty Computation with Faulty Majority,” Proceedings of the 30th IEEE Symposium on the Foundations of Computer Science, Research Triangle Park, North Carolina, 30 October-1 November 1989, pp. 468-473.
[16]	H. Y. Lin and L. Harn, “Fair Reconstruction of a Secret,” Information Processing Letters, Vol. 55, No. 1, 1995, pp. 45-47. http://dx.doi.org/10.1016/0020-0190(95)00045-E
[17]	J. Pieprzyk and X.-M. Zhang, “Cheating Prevention in Secret Sharing over ” Progress in Cryptology— 2nd International Conference on Cryptology, Chennai, 16-20 December 2001, pp. 79-90.
[18]	J. Pieprzyk and X.-M. Zhang, “On Cheating Immune Secret Sharing,” Discrete Mathematics and Theoretical Computer Science, Vol. 6, No. 2, 2004, pp. 253-264.
[19]	L. Harn, “Group-Oriented (t, n) Threshold Digital Signature Scheme and Digital Multisignature,” IEE Proceedings—Computers and Digital Techniques, Vol. 141, No. 5, 1994, pp. 307-313. http://dx.doi.org/10.1049/ip-cdt:19941293
[20]	C. Delerablee and D. Pointcheval, “Dynamic Threshold Public-Key Encryption,” Advances in Cryptography—28th Annual International Cryptology Conference (CRYPTO ’08), Santa Barbara, 17-21 August 2008, pp. 317-334.
[21]	R. Bendlin and I. Damgard, “Threshold Decryption and Zero-Knowledge Proofs for Lattice-Based Cryptosystems,” Proceedings of 7th Theory of Cryptography Conference (TCC ‘10), Zurich, 9-11 February 2010, pp. 201-218.
[22]	L. Ertaul and W. Lu, “ECC Based Threshold Cryptography for Secure Data Forwarding and Secure Key Exchange in MANET (I),” Proceedings of the 4th IFIP-TC6 International Conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communication Systems, Waterloo, 2-6 May 2005, pp. 102-113.
[23]	Y. Desmedt, “Some Recent Research Aspects of Threshold Cryptography,” Proceedings of the 1st International Workshop (ISW ‘97), Tatsunokuchi, 17-19 September 1997, pp. 158-173.
[24]	Y. Desmedt, “Threshold Cryptosystems,” Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (AUSCRYPT ‘92), Gold Coast, Queensland, 13-16 December 1992, pp. 1-14.
[25]	M. Abdalla, S. Miner and C. Namprempre, “Forwardsecure Threshold Signature Schemes,” Topics in Cryptology—The Cryptographer’s Track at RSA Conference (CT-RSA ‘01), San Francisco, 8-12 April 2001, pp. 441-456.
[26]	J. Baek and Y. Zheng, “Identity-Based Threshold Signature Scheme from the Bilinear Pairings,” Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC ‘04), Las Vegas, 5-7 April 2004, p. 124.
[27]	T. A. ElGamal, “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” IEEE Transactions on Information Theory, Vol. 31, No. 4, 1985, pp. 469-472. http://dx.doi.org/10.1109/TIT.1985.1057074