Dynamic threshold and cheater resistance for shamir secret sharing scheme

Christophe Tartary; Huaxiong Wang

Dynamic threshold and cheater resistance for shamir secret sharing scheme

Christophe Tartary^*, Huaxiong Wang

^*Corresponding author for this work

Department of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

13 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Information Security and Cryptology - Second SKLOIS Conference, Inscrypt 2006, Proceedings
Editors	Helger Lipmaa, Moti Yung, Dongdai Lin
Place of Publication	Berlin; Heidelberg
Publisher	Springer, Springer Nature
Pages	103-117
Number of pages	15
Volume	4318 LNCS
ISBN (Print)	3540496084, 9783540496083
Publication status	Published - 2006
Event	2nd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2006 - Beijing, China Duration: 29 Nov 2006 → 1 Dec 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4318 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	2nd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2006
Country	China
City	Beijing
Period	29/11/06 → 1/12/06

Access to Document

Link to publication in Scopus

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

Tartary, C., & Wang, H. (2006). Dynamic threshold and cheater resistance for shamir secret sharing scheme. In H. Lipmaa, M. Yung, & D. Lin (Eds.), Information Security and Cryptology - Second SKLOIS Conference, Inscrypt 2006, Proceedings (Vol. 4318 LNCS, pp. 103-117). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4318 LNCS). Springer, Springer Nature.

Tartary, Christophe ; Wang, Huaxiong. / Dynamic threshold and cheater resistance for shamir secret sharing scheme. Information Security and Cryptology - Second SKLOIS Conference, Inscrypt 2006, Proceedings. editor / Helger Lipmaa ; Moti Yung ; Dongdai Lin. Vol. 4318 LNCS Berlin; Heidelberg : Springer, Springer Nature, 2006. pp. 103-117 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4d88a30843bb46ebb94f46924aa0f492,

title = "Dynamic threshold and cheater resistance for shamir secret sharing scheme",

abstract = "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.",

author = "Christophe Tartary and Huaxiong Wang",

year = "2006",

language = "English",

isbn = "3540496084",

volume = "4318 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "103--117",

editor = "Helger Lipmaa and Moti Yung and Dongdai Lin",

booktitle = "Information Security and Cryptology - Second SKLOIS Conference, Inscrypt 2006, Proceedings",

address = "United States",

note = "2nd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2006 ; Conference date: 29-11-2006 Through 01-12-2006",

}

Tartary, C & Wang, H 2006, Dynamic threshold and cheater resistance for shamir secret sharing scheme. in H Lipmaa, M Yung & D Lin (eds), Information Security and Cryptology - Second SKLOIS Conference, Inscrypt 2006, Proceedings. vol. 4318 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4318 LNCS, Springer, Springer Nature, Berlin; Heidelberg, pp. 103-117, 2nd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2006, Beijing, China, 29/11/06.

Dynamic threshold and cheater resistance for shamir secret sharing scheme. / Tartary, Christophe; Wang, Huaxiong.

Information Security and Cryptology - Second SKLOIS Conference, Inscrypt 2006, Proceedings. ed. / Helger Lipmaa; Moti Yung; Dongdai Lin. Vol. 4318 LNCS Berlin; Heidelberg : Springer, Springer Nature, 2006. p. 103-117 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4318 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Dynamic threshold and cheater resistance for shamir secret sharing scheme

AU - Tartary, Christophe

AU - Wang, Huaxiong

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33845927130&partnerID=8YFLogxK

M3 - Conference proceeding contribution

AN - SCOPUS:33845927130

SN - 3540496084

SN - 9783540496083

VL - 4318 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 103

EP - 117

BT - Information Security and Cryptology - Second SKLOIS Conference, Inscrypt 2006, Proceedings

A2 - Lipmaa, Helger

A2 - Yung, Moti

A2 - Lin, Dongdai

PB - Springer, Springer Nature

CY - Berlin; Heidelberg

T2 - 2nd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2006

Y2 - 29 November 2006 through 1 December 2006

ER -

Tartary C, Wang H. Dynamic threshold and cheater resistance for shamir secret sharing scheme. In Lipmaa H, Yung M, Lin D, editors, Information Security and Cryptology - Second SKLOIS Conference, Inscrypt 2006, Proceedings. Vol. 4318 LNCS. Berlin; Heidelberg: Springer, Springer Nature. 2006. p. 103-117. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).