Paper 2015/1089

Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions

Ronald Cramer, Ivan Bjerre Damgård, Nico Döttling, Serge Fehr, and Gabriele Spini

Abstract

We present a novel method for constructing linear secret sharing schemes (LSSS) from linear error correcting codes and linear universal hash functions in a blackbox way. The main advantage of this new construction is that the privacy property of the resulting secret sharing scheme essentially becomes independent of the code we use, only depending on its rate. This allows us to fully harness the algorithmic properties of recent code constructions such as efficient encoding and decoding or efficient list-decoding. Choosing the error correcting codes and universal hash functions involved carefully, we obtain solutions to the following open problems: - A linear near-threshold secret sharing scheme with both linear time sharing and reconstruction algorithms and large secrets (i.e. secrets of size Omega(n)). Thus, the computational overhead per shared bit in this scheme is constant. - An efficiently reconstructible robust secret sharing scheme for n/3 <= t < (1 - epsilon) n/2 corrupted players (for any constant epsilon > 0) with shares of optimal size O(1 + sec / n) and secrets of size Omega(n + sec), where sec is the security parameter.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in EUROCRYPT 2015
Keywords
Linear Secret Sharing SchemesLinear Time SharingRobust Secret Sharing
Contact author(s)
nico doettling @ cs au dk
History
2015-11-09: revised
2015-11-09: received
See all versions
Short URL
https://ia.cr/2015/1089
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1089,
      author = {Ronald Cramer and Ivan Bjerre Damgård and Nico Döttling and Serge Fehr and Gabriele Spini},
      title = {Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1089},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1089}},
      url = {https://eprint.iacr.org/2015/1089}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.