Paper 2008/409

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

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

Abstract

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)thresholdscheme.Forthepurposetorealizehighperformance,theproposedschemeusesjustEXCLUSIVEOR(XOR)operationstomakesharesandrecoverthesecret.Weprovethattheproposedschemeisaperfectsecretsharingscheme,everycombinationofkormoreparticipantscanrecoverthesecret,buteverygroupoflessthankparticipantscannotobtainanyinformationaboutthesecret.Moreover,weshowthattheproposedschemeisanidealsecretsharingschemesimilartoShamirsscheme,whichisaperfectschemesuchthateverybitsizeofsharesequalsthatofthesecret.Wealsoevaluatetheefficiencyofthescheme,andshowthatourschemerealizesoperationsthataremuchfasterthanShamirs.Furthermore,fromtheaspectofbothcomputationalcostandstorageusage,wealsointroducehowtoextendtheproposedschemetoanew(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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Detailed version of a paper presented at the ISC 2008 conference
Keywords
secret sharing
Contact author(s)
kurihara @ kddilabs jp
History
2008-10-02: revised
2008-10-02: received
See all versions
Short URL
https://ia.cr/2008/409
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/409,
      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},
      url = {https://eprint.iacr.org/2008/409}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.