IEICE TRANSACTIONS on Fundamentals
On a Fast (k,n)-Threshold Secret Sharing Scheme
Summary :
In Shamir's (k,n)-threshold secret sharing scheme (threshold scheme)[1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. However, there is no fast ideal (k,n)-threshold scheme, where k and n are arbitrary. This paper proposes a new fast (k,n)-threshold scheme which uses just EXCLUSIVE-OR(XOR) operations to make n shares and recover the secret from k shares. We prove that every combination of k or more participants can recover the secret, but every group of less than k participants cannot obtain any information about the secret in the proposed scheme. Moreover, the proposed scheme is an ideal secret sharing scheme similar to Shamir's scheme, in which every bit-size of shares equals that of the secret. We also evaluate the efficiency of the scheme, and show that our scheme realizes operations that are much faster than Shamir's.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2365-2378
- Publication Date
- 2008/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e91-a.9.2365
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Jun KURIHARA, Shinsaku KIYOMOTO, Kazuhide FUKUSHIMA, Toshiaki TANAKA, "On a Fast (k,n)-Threshold Secret Sharing Scheme" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 9, pp. 2365-2378, September 2008, doi: 10.1093/ietfec/e91-a.9.2365.
Abstract: In Shamir's (k,n)-threshold secret sharing scheme (threshold scheme)[1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. However, there is no fast ideal (k,n)-threshold scheme, where k and n are arbitrary. This paper proposes a new fast (k,n)-threshold scheme which uses just EXCLUSIVE-OR(XOR) operations to make n shares and recover the secret from k shares. We prove that every combination of k or more participants can recover the secret, but every group of less than k participants cannot obtain any information about the secret in the proposed scheme. Moreover, the proposed scheme is an ideal secret sharing scheme similar to Shamir's scheme, in which every bit-size of shares equals that of the secret. We also evaluate the efficiency of the scheme, and show that our scheme realizes operations that are much faster than Shamir's.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.9.2365/_p
Copy
@ARTICLE{e91-a_9_2365,
author={Jun KURIHARA, Shinsaku KIYOMOTO, Kazuhide FUKUSHIMA, Toshiaki TANAKA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On a Fast (k,n)-Threshold Secret Sharing Scheme},
year={2008},
volume={E91-A},
number={9},
pages={2365-2378},
abstract={In Shamir's (k,n)-threshold secret sharing scheme (threshold scheme)[1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. However, there is no fast ideal (k,n)-threshold scheme, where k and n are arbitrary. This paper proposes a new fast (k,n)-threshold scheme which uses just EXCLUSIVE-OR(XOR) operations to make n shares and recover the secret from k shares. We prove that every combination of k or more participants can recover the secret, but every group of less than k participants cannot obtain any information about the secret in the proposed scheme. Moreover, the proposed scheme is an ideal secret sharing scheme similar to Shamir's scheme, in which every bit-size of shares equals that of the secret. We also evaluate the efficiency of the scheme, and show that our scheme realizes operations that are much faster than Shamir's.},
keywords={},
doi={10.1093/ietfec/e91-a.9.2365},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - On a Fast (k,n)-Threshold Secret Sharing Scheme
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2365
EP - 2378
AU - Jun KURIHARA
AU - Shinsaku KIYOMOTO
AU - Kazuhide FUKUSHIMA
AU - Toshiaki TANAKA
PY - 2008
DO - 10.1093/ietfec/e91-a.9.2365
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2008
AB - In Shamir's (k,n)-threshold secret sharing scheme (threshold scheme)[1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. However, there is no fast ideal (k,n)-threshold scheme, where k and n are arbitrary. This paper proposes a new fast (k,n)-threshold scheme which uses just EXCLUSIVE-OR(XOR) operations to make n shares and recover the secret from k shares. We prove that every combination of k or more participants can recover the secret, but every group of less than k participants cannot obtain any information about the secret in the proposed scheme. Moreover, the proposed scheme is an ideal secret sharing scheme similar to Shamir's scheme, in which every bit-size of shares equals that of the secret. We also evaluate the efficiency of the scheme, and show that our scheme realizes operations that are much faster than Shamir's.
ER -
English
