Dynamic Threshold and Cheater Resistance for Shamir Secret Sharing Scheme

  • Christophe Tartary
  • Huaxiong Wang
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4318)


In this paper, we investigate the problem of increasing the threshold parameter of the Shamir (t,n)-threshold scheme without interacting with the dealer. Our construction will reduce the problem of secret recovery to the polynomial reconstruction problem which can be solved using a recent algorithm by Guruswami and Sudan.

In addition to be dealer-free, our protocol does not increase the communication cost between the dealer and the n participants when compared to the original (t,n)-threshold scheme. Despite an increase of the asymptotic time complexity at the combiner, we show that recovering the secret from the output of the previous polynomial reconstruction algorithm is still realistic even for large values of t. Furthermore the scheme does not require every share to be authenticated before being processed by the combiner. This will enable us to reduce the number of elements to be publicly known to recover the secret to one digest produced by a collision resistant hash function which is smaller than the requirements of most verifiable secret sharing schemes.


secret sharing scheme polynomial reconstruction problem threshold changeability insecure network cheater resistance 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Blakley, G.R.: Safeguarding cryptographic keys. In: AFIPS 1979, pp. 313–317 (1979)Google Scholar
  2. 2.
    Bleichenbacher, D., Nguyen, P.Q.: Noisy polynomial interpolation and noisy chinese remaindering. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 53–69. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  3. 3.
    Blundo, C., Cresti, A., De Santis, A., Vaccaro, U.: Fully dynamic secret sharing schemes. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 110–125. Springer, Heidelberg (1994)Google Scholar
  4. 4.
    Dai, W.: Crypto++ 5.2.1 benchmarks (July 2004)Google Scholar
  5. 5.
    Desmedt, Y.: Society and group oriented cryptography: A new concept. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 120–127. Springer, Heidelberg (1988)Google Scholar
  6. 6.
    Desmedt, Y., Jajodia, S.: Redistributing secret shares to new access structures and its application. Technical Report ISSE TR-97-01, George Mason university (1997)Google Scholar
  7. 7.
    Desmedt, Y., King, B.: Verifiable democracy a protocol to secure an electronic legislature. In: Traunmüller, R., Lenk, K. (eds.) EGOV 2002. LNCS, vol. 2456, pp. 460–463. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  8. 8.
    Desmedt, Y., Kurosawa, K., Van Le, T.: Error correcting and complexity aspects of linear secret sharing schemes. In: Boyd, C., Mao, W. (eds.) ISC 2003. LNCS, vol. 2851, pp. 396–407. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  9. 9.
    Frankel, Y., Gemmel, P., MacKenzie, P.D., Yung, M.: Optimal-resilience proactive public-key cryptosystems. In: FOCS 1997, pp. 384–393. IEEE Press, Los Alamitos (1997)Google Scholar
  10. 10.
    Galil, Z., Haber, S., Yung, M.: Cryptographic computation: Secure fault-tolerant protocols and the public-key model (extended abstract). In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 135–155. Springer, Heidelberg (1988)Google Scholar
  11. 11.
    Ghodosi, H., Pieprzyk, J.: Democratic systems. In: Varadharajan, V., Mu, Y. (eds.) ACISP 2001. LNCS, vol. 2119, pp. 392–402. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  12. 12.
    Guruswami, V.: List Decoding of Error-Correcting Codes. Springer, Heidelberg (2004)zbMATHGoogle Scholar
  13. 13.
    Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Trans. on Information Theory 45(6), 1757–1767 (1999)zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Harn, L.: Group-oriented (t, n)-threshold digital signature scheme and digital multisignature. IEE Proceedings - Computers and Digital Techniques 141(5), 307–313 (1994)zbMATHCrossRefGoogle Scholar
  15. 15.
    Juels, A., Sudan, M.: A fuzzy vault scheme. In: ISIT 2002, p. 408. IEEE Press (July 2002); Extended version avaliable at:
  16. 16.
    Karlof, C., Sastry, N., Li, Y., Perrig, A., Tygar, J.D.: Distillation codes and applications to DoS resistant multicast authentication. In: NDSS 2004 (February 2004)Google Scholar
  17. 17.
    Karnin, E.D., Greene, J.W., Hellman, M.E.: On secret sharing systems. IEEE Transactions on Information Theory 29(1), 35–41 (1983)zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    Li, Q., Wang, Z., Niu, X., Sun, S.: A non-interactive modular verifiable secret sharing scheme. In: International Conference on Communications, Circuits and Systems, pp. 84–87. IEEE Press, Los Alamitos (2005)Google Scholar
  19. 19.
    Lysyanskaya, A., Tamassia, R., Triandopoulos, N.: Multicast authentication in fully adversarial networks. In: IEEE Symp. on Security and Privacy (November 2003)Google Scholar
  20. 20.
    Maeda, A., Miyaji, A., Tada, M.: Efficient and unconditionally secure verifiable threshold changeable scheme. In: Varadharajan, V., Mu, Y. (eds.) ACISP 2001. LNCS, vol. 2119, pp. 402–416. Springer, Heidelberg (2001)Google Scholar
  21. 21.
    Martin, K.: Untrustworthy participants in secret sharing schemes. In: Cryptography and Coding III, pp. 255–264. Oxford University Press, Oxford (1993)Google Scholar
  22. 22.
    Martin, K., Pieprzyk, J., Safavi-Naini, R., Wang, H.: Changing thresholds in the absence of secure channels. Australian Computer Journal 31, 34–43 (1999)zbMATHGoogle Scholar
  23. 23.
    Martin, K., Safavi-Naini, R., Wang, H.: Bounds and techniques for efficient redistribution of secret shares to new access structures. The Computer Journal 42(8), 638–649 (1999)zbMATHCrossRefGoogle Scholar
  24. 24.
    McEliece, R.J., Sarwate, D.V.: On sharing secrets and Reed-Solomon codes. Communications of the ACM 24(9), 583–584 (1981)CrossRefMathSciNetGoogle Scholar
  25. 25.
    Parvaresh, F., Vardy, A.: Correcting errors beyond the Guruswami-Sudan radius in polynomial time. In: 46th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, USA, pp. 285–294. IEEE Computer Society, Los Alamitos (2005)CrossRefGoogle Scholar
  26. 26.
    Pieprzyk, J., Hardjono, T., Seberry, J.: Fundamentals of Computer Security. Springer, Heidelberg (2003)zbMATHGoogle Scholar
  27. 27.
    Pieprzyk, J., Zhang, X.M.: Cheating prevention in secret sharing over GF(p t). In: Pandu Rangan, C., Ding, C. (eds.) INDOCRYPT 2001. LNCS, vol. 2247, pp. 79–90. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  28. 28.
    Pieprzyk, J., Zhang, X.M.: Constructions of cheating immune secret sharing. In: Kim, K.-c. (ed.) ICISC 2001. LNCS, vol. 2288, pp. 226–243. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  29. 29.
    Pieprzyk, J., Zhang, X.M.: On cheating immune secret sharing. Discrete Mathematics and Theoretical Computer Science 6, 253–264 (2004)zbMATHMathSciNetGoogle Scholar
  30. 30.
    Schnorr, C.P.: A hierarchy of polynomial lattice basis reduction algorithms. Theoretical Computer Science 53, 201–224 (1987)zbMATHCrossRefMathSciNetGoogle Scholar
  31. 31.
    Schnorr, C.P., Euchner, M.: Lattice basis reduction: Improved practical algorithms and solving subset sum problem. Math. Programming 66(1-3), 181–199 (1994)CrossRefMathSciNetzbMATHGoogle Scholar
  32. 32.
    Schoenmakers, B.: A simple publicly verifiable secret sharing scheme and its application to electronic voting. In: Wiener, M.J. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 148–164. Springer, Heidelberg (1999)Google Scholar
  33. 33.
    Shamir, A.: How to share a secret. Communication of the ACM 22(11), 612–613 (1979)zbMATHCrossRefMathSciNetGoogle Scholar
  34. 34.
    Shoup, V.: Number Theory Library (NTL), Available online at:
  35. 35.
    Steinfeld, R., Wang, H., Pieprzyk, J.: Lattice-based threshold-changeability for standard Shamir secret-sharing schemes. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 170–186. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  36. 36.
    Stinson, D.R.: Cryptography: Theory and Practice. CRC Press, Boca Raton (1995)zbMATHGoogle Scholar
  37. 37.
    Stinson, D.R., Zhang, S.: Algorithms for detecting cheaters threshold schemes (January 2006), Available online at:
  38. 38.
    Tang, C., Liu, Z., Wang, M.: A verifiable secret sharing scheme with statistical zero-knowledge (October 2003), Avaliable onlne at:
  39. 39.
    Tartary, C., Wang, H.: Efficient multicast stream authentication for the fully adversarial network. In: Song, J.-S., Kwon, T., Yung, M. (eds.) WISA 2005. LNCS, vol. 3786, pp. 108–125. Springer, Heidelberg (2006)CrossRefGoogle Scholar
  40. 40.
    Tompa, M., Woll, H.: How to share a secret with cheaters. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 261–265. Springer, Heidelberg (1987)Google Scholar
  41. 41.
    Zhang, X.M., Pieprzyk, J.: Cheating immune secret sharing. In: Qing, S., Okamoto, T., Zhou, J. (eds.) ICICS 2001. LNCS, vol. 2229, pp. 144–149. Springer, Heidelberg (2001)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Christophe Tartary
    • 1
  • Huaxiong Wang
    • 2
  1. 1.Centre for Advanced Computing, Algorithms and Cryptography, Department of ComputingMacquarie UniversityAustralia
  2. 2.Division of Mathematical Sciences, School of Physical and Mathematical SciencesNanyang Technological UniversitySingapore

Personalised recommendations