A new multi-stage secret sharing scheme using one-way function

ABSTRACT

He and Dawson proposed a multi-stage secret sharing scheme based on one-way function. In that scheme, many secrets are reconstructed stage-by-stage in the dealer's predetermined order, and only one secret shadow is kept by every participant. When all the secrets have been reconstructed, the dealer needs not redistribute fresh shadows to every participant. Later, Harn further improved the He-Dawson scheme to reduce the total number of public values. However, in this paper, we will show that both the He-Dawson scheme and Harn's scheme are one-time-use schemes and that many secrets cannot in fact be reconstructed stage-by-stage. At the same time, we shall also modify the He-Dawson scheme to improve the drawbacks above and show the improved scheme can be applied.

REFERENCES

• 1: G. R. Blakley. Safeguarding cryptographic keys. In AFIPES 1797 Natl. Comput. Conf., volume 48, pages 165--172, New York, 1979.
• 2: Carlo Blundo , Antonella Cresti , Alfredo De Santis , Ugo Vaccaro, Fully Dynamic Secret Sharing Schemes, Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology, p.110-125, August 22-26, 1993
• 3: C. C. Chang and R. J. Hwang. Efficient cheater identification method for threshold schemes. IEE Proc. Comput. Digit. Tech., 144(1):23--27, 1996.
• 4: Ting-Yi Chang, Chou-Chen Yang, and Min-Shiang Hwang. Threshold untraceable signature for group communications. IEE Proceedings - Communications, accepted (July 26, 2003) and to appear.
• 5: Ting-Yi Chang , Chou-Chen Yang , Min-Shiang Hwang, A threshold signature scheme for group communications without a shared distribution center, Future Generation Computer Systems, v.20 n.6, p.1013-1021, August 2004 [doi>10.1016/j.future.2003.09.005]
• 6: Hung-Yu Chien, Jinn-Ke Jan, and Yuh-Min Tseng. A practical (t, n) multi-secret sharing scheme. IEICE TRANS. FUNDAMENTALS, E83-A(12):2762--2765, DECEMBER 2000.
• 7: L. Harn. Comment: Multistage secret sharing based on one-way function. Electronics Letters, 31(4):262, 1995.
• 8: L. Harn. Efficient sharing (broadcasting) of multiple secret. Proc. IEE-Comput. Digit. Tech., 142(3):237--240, May 1995.
• 9: Chi-Sung Laih , Lein Harn , Jau-Yien Lee , Tzonelih Hwang, Dynamic Threshold Scheme Based on the Definition of Cross-Product in an N-Dimentional Linear Space, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.286-298, August 20-24, 1989
• 10: J. He and E. Dawson. Multistage secret sharing based on one-way function. Electronics Letters, 30(19):1591--1592, 1994.
• 11: J. He and E. Dawson. Multisecret-sharing scheme based on one-way function. Electronics Letters, 31(2):93--95, 1995.
• 12: M. S. Hwang , C. C. Chang , K. F. Hwang, An ElGamal-Like Cryptosystem for Enciphering Large Messages, IEEE Transactions on Knowledge and Data Engineering, v.14 n.2, p.445-446, March 2002 [doi>10.1109/69.991728]
• 13: Min-Shiang Hwang, Cheng-Chi Lee, and Ting-Yi Chang. Broadcasting cryptosystem in computer networks using geometric properties of lines. Journal of Information Science and Engineering, 18(3):373--378, 2002.
• 14: Min-Shiang Hwang, Cheng-Chi Lee, and Eric Jui-Lin Lu. Cryptanalysis of the batch verifying multiple DSA-type digital signatures. Pakistan Journal of Applied Sciences, 1(3):287--288, 2001.
• 15: Ren-Junn Hwang , Wei-Bin Lee , Chin-Chen Chang, A concept of designing cheater identification methods for secret sharing, Journal of Systems and Software, v.46 n.1, p.7-11, April 1, 1999 [doi>10.1016/S0164-1212(98)10084-5]
• 16: Wen-Ai Jackson , Keith M. Martin , Christine M. O'Keefe, On Sharing Many Secrets (Extended Abstract), Proceedings of the 4th International Conference on the Theory and Applications of Cryptology: Advances in Cryptology, p.42-54, November 28-December 01, 1994
• 17: CORPORATE NIST, The digital signature standard, Communications of the ACM, v.35 n.7, p.36-40, July 1992 [doi>10.1145/129902.129904]
• 18: Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
• 19: T. P. Pedersen. A threshold cryptosystem without a trusted party. In Advances in Cryptology, CRYPTO'91, pages 522--526, 1991.
• 20: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 21: Hung-Min Sun , Shiuh-Pyng Shieh, On dynamic threshold schemes, Information Processing Letters, v.52 n.4, p.201-206, Nov. 25, 1994 [doi>10.1016/0020-0190(94)90127-9]
• 22: T. C. Wu and T. S. Wu. Cheating detection and cheater identification in secret shairng schemes. IEE Proc. Comput. Digit. Tech., 142(5):367--369, 1995.
• 23: Chou-Chen Yang, Ting-Yi Chang, and Min-Shiang Hwang. A (t, n) multi-secret sharing scheme. Applied Mathematics And Computation, accepted (March 31, 2003) and to appear.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Formal models of communication

General Terms:
Algorithms, Security

Keywords:
cryptography, multi-stage, one-way function, secret sharing, threshold scheme