On a Fast (k,n)-Threshold Secret Sharing Scheme

Toshiaki TANAKA

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A    No.9    pp.2365-2378
Publication Date: 2008/09/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.9.2365
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
secret sharing scheme,  threshold scheme,  exclusive-or,  entropy,  random number,  ideal secret sharing scheme,  

Full Text: PDF>>
Buy this Article

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.