A Fast (k,L,n)-Threshold Ramp Secret Sharing Scheme

Jun KURIHARA  Shinsaku KIYOMOTO  Kazuhide FUKUSHIMA  Toshiaki TANAKA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A   No.8   pp.1808-1821
Publication Date: 2009/08/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.1808
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Theory
secret sharing scheme,  threshold scheme,  threshold ramp scheme,  exclusive-or,  random number,  

Full Text: PDF>>
Buy this Article

Shamir's (k,n)-threshold secret sharing scheme (threshold scheme) has two problems: a heavy computational cost is required to make shares and recover the secret, and a large storage capacity is needed to retain all the shares. As a solution to the heavy computational cost problem, several fast threshold schemes have been proposed. On the other hand, threshold ramp secret sharing schemes (ramp scheme) have been proposed in order to reduce each bit-size of shares in Shamir's scheme. However, there is no fast ramp scheme which has both low computational cost and low storage requirements. This paper proposes a new (k,L,n)-threshold ramp secret sharing scheme which uses just EXCLUSIVE-OR(XOR) operations to make shares and recover the secret at a low computational cost. Moreover, by proving that the fast (k,n)-threshold scheme in conjunction with a method to reduce the number of random numbers is an ideal secret sharing scheme, we show that our fast ramp scheme is able to reduce each bit-size of shares by allowing some degradation of security similar to the existing ramp schemes based on Shamir's threshold scheme.