Paper 2008/409

A New $(k,n)$-Threshold Secret Sharing Scheme and Its Extension

Jun Kurihara, Shinsaku Kiyomoto, Kazuhide Fukushima, and Toshiaki Tanaka


In Shamir's $(k,n)$-threshold secret sharing scheme (threshold scheme), a heavy computational cost is required to make $n$ shares and recover the secret. As a solution to this problem, several fast threshold schemes have been proposed. This paper proposes a new (k,n)$-threshold scheme. For the purpose to realize high performance, the proposed scheme uses just EXCLUSIVE-OR(XOR) operations to make shares and recover the secret. We prove that the proposed scheme is a {\it perfect} secret sharing scheme, 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. Moreover, we show that the proposed scheme is an {\it ideal} secret sharing scheme similar to Shamir's scheme, which is a {\it perfect} scheme such that 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. Furthermore, from the aspect of both computational cost and storage usage, we also introduce how to extend the proposed scheme to a new $(k,L,n)$-threshold {\it ramp} scheme similar to the existing {\it ramp} scheme based on Shamir's scheme.

Note: This is a revised version of a paper presented at the ISC 2008 conference. This paper includes a detailed proof which shows that our scheme is ideal as a secret sharing scheme.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Detailed version of a paper presented at the ISC 2008 conference
secret sharing
Contact author(s)
kurihara @ kddilabs jp
2008-10-02: revised
2008-10-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jun Kurihara and Shinsaku Kiyomoto and Kazuhide Fukushima and Toshiaki Tanaka},
      title = {A New $(k,n)$-Threshold Secret Sharing Scheme and Its Extension},
      howpublished = {Cryptology ePrint Archive, Paper 2008/409},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.