A Novel Verifiable Secret Sharing with Detection and Identification of Cheaters' Group

Full Text (PDF, 489KB), PP.1-13

Views: 0 Downloads: 0


Qassim Al Mahmoud 1

1. Faculty of Mathematics and Computer Science, the University of Bucharest, Romania

* Corresponding author.

DOI: https://doi.org/10.5815/ijmsc.2016.02.01

Received: 13 Jan. 2016 / Revised: 5 Feb. 2016 / Accepted: 1 Mar. 2016 / Published: 8 Apr. 2016

Index Terms

Secret sharing, verifiable secret sharing, honest participants, dishonest participants, single cheater, cheaters' group


Shamir's (t, n)-SS scheme is very simple to generate and distribute the shares for a secret among n participants by using such polynomial. We assume the dealer a mutually trust parity when he distributes the shares to participants securely. In addition when the participants pooling their shares in the secret reconstruction phase a honest participants can always reconstruct the real secret by Pooling areal shares. The property of verifiability enables participants to verify that their shares are consistent. Tompa and Woll suggested an important cheating scenario in Shamir's secret reconstruction. They found a solution to remove a single cheater with small probability, unfortunately, their scheme is based on computational assumptions. In addition each participants will receive a huge number of shares. In this paper we will construct scheme to be information-theoretically secure verifiable secret sharing which does not contain a single cheater. On the other hand we will eliminate these problems in Tompa and Woll scheme. Our proposed scheme is not only to detect and identify a cheater, but to prevent him from recovering the secret when the honest participants cannot.

Cite This Paper

Qassim Al Mahmoud,"A Novel Verifiable Secret Sharing with Detection and Identification of Cheaters' Group", International Journal of Mathematical Sciences and Computing(IJMSC), Vol.2, No.2, pp.1-13, 2016.DOI: 10.5815/ijmsc.2016.02.01


[1]G.R. Blakley, Safeguarding cryptographic keys, Proceedings of the AFIPS'79 National Computer Conference, vol. 48, AFIPS Press, 1979, pp. 313–317.

[2]Shamir, How to share a secret, Communications of the ACM 22 (11) (1979) 612–613.

[3]B. Chor, S. Goldwasser, S. Micali, B. Awerbuch, Verifiable secret sharing and achieving simultaneity in the presence of faults, Proceedings of the 26th IEEE Symposium on Foundations of Computer Science, 21–23 October, Oregon, Portland, IEEE Computer Society, 1985, pp. 383–395.

[4]Feldman, P., 1987. A practical scheme for non-interactive verifiable secret sharing. In: Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, 27–29 October. IEEE Computer Society, Los Angeles, California, pp. 427–437.

[5]Nikov, V., Nikova, S., 2005. On a Relation Between Verifiable Secret Sharing Schemes and a Class of Error-Correcting Schemes, Cryptology e-print archive 2003/210.

[6]Pedersen, T.P., 1992. Non-interactive and information-theoretic secure verifiable secret sharing. In: Advances in Cryptology-CRYPTO'91, LNCS, vol. 576. Springer- Verlag, Berlin, pp. 129–140.

[7]Tompa M., Woll H.: How to share a secret with cheaters. J. Cryptol. 1(3), 133–138 (1989).

[8]Araki T.: Efficient (k, n) threshold secret sharing schemes secure against cheating from n − 1 cheaters.In: Proceedings of ACISP'07, LNCS, vol. 4586, pp. 13–142. Springer-Verlag (2007).

[9]CarpentieriM., De Santis A., Vaccaro U.: Size of shares and probability of cheating in threshold schemes.In: Proceedings of Eurocrypt'93, LNCS, vol. 765, pp. 118–125. Springer-Verlag (1994).

[10]Kurosawa K., Obana S., Ogata W.: t-cheater identifiable (k, n) secret sharing schemes. In: Proceedings of Crypto'95, LNCS, vol. 963, pp. 410–423. Springer-Verlag (1995).

[11]Rabin T., Ben-Or M.: Verifiable secret sharing and multiparty protocols with honest majority. In: Proceedings of the 21st Annual ACM Symposium on the Theory of Computing, pp. 73–85 (1989).

[12]Bhndo C., De Santis A., Gargano L., Vaccaro U.: Secret sharing schemes with veto capabilities. In: Proceedings of the First French-Israeli Workshop on Algebraic Coding, LNCS, vol. 781, pp. 82–89. Springer-Verlag (1993).

[13]McEliece R.J., Sarwate D.V.: On sharing secrets and Reed-Solomon codes. Comm. ACM 24, 583–584(1981).

[14]Charnes C., Pieprzyk J., Safavi-Naini R.: Conditionally secure secret sharing scheme with disenrolment capability. In: Proceedings of CCS'94, pp. 89–95. ACM (1994).

[15]Lin H.Y., Harn L.: A generalized secret sharing scheme with cheater detection. In: Proceedings of Asiacrypt'91, LNCS, vol. 739, pp. 149–158. Springer-Verlag (1991).

[16]Tartary C., Wang H.: Dynamic threshold and cheater resistance for shamir secret sharing scheme. In:Proceedings of Inscrypt'06, LNCS, vol. 4318, pp. 103–117. Springer-Verlag (2006).

[17]T.-C. Wu and T.-S. Wu, Cheating detection and cheater identification in secret sharing schemes, IEE Transactions on Computers and Digital Techniques 142 (1995), 367-369.