Dynamic threshold and cheater resistance for shamir secret sharing scheme

Christophe Tartary*, Huaxiong Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

13 Citations (Scopus)


In this paper, we investigate the problem of increasing the threshold parameter of the Sharnir (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.

Original languageEnglish
Title of host publicationInformation Security and Cryptology - Second SKLOIS Conference, Inscrypt 2006, Proceedings
EditorsHelger Lipmaa, Moti Yung, Dongdai Lin
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Number of pages15
Volume4318 LNCS
ISBN (Print)3540496084, 9783540496083
Publication statusPublished - 2006
Event2nd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2006 - Beijing, China
Duration: 29 Nov 20061 Dec 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4318 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Other2nd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2006

Fingerprint Dive into the research topics of 'Dynamic threshold and cheater resistance for shamir secret sharing scheme'. Together they form a unique fingerprint.

Cite this