Nearly optimal robust secret sharing
File(s)
Published version
Author(s)
Cheraghchi, M
Type
Journal Article
Abstract
We prove that a known general approach to improve Shamir’s celebrated secret sharing scheme; i.e., adding an information-theoretic authentication tag to the secret, can make it robust for n parties against any collusion of size δn, for any constant δ∈ (0 , 1 / 2). Shamir’s original scheme is robust for all δ∈ (0 , 1 / 3). Beyond that, we employ the best known list decoding algorithms for Reed-Solomon codes and show that, with high probability, only the correct secret maintains the correct information-theoretic tag if an algebraic manipulation detection (AMD) code is used to tag secrets. This result holds in the so-called “non-rushing” model in which the n shares are submitted simultaneously for reconstruction. We thus obtain a fully explicit and robust secret sharing scheme in this model that is essentially optimal in all parameters including the share size which is k(1 + o(1)) + O(κ) , where k is the secret length and κ is the security parameter. Like Shamir’s scheme, in this modified scheme any set of more than δn honest parties can efficiently recover the secret. Using algebraic geometry codes instead of Reed-Solomon codes, the share length can be decreased to a constant (only depending on δ) while the number of shares n can grow independently. In this case, when n is large enough, the scheme satisfies the “threshold” requirement in an approximate sense; i.e., any set of δn(1 + ρ) honest parties, for arbitrarily small ρ> 0 , can efficiently reconstruct the secret. From a practical perspective, the main importance of our result is in showing that existing systems employing Shamir-type secret sharing schemes can be made much more robust than previously thought with minimal change, essentially only involving the addition of a short and simple checksum to the original data.
Date Issued
2019-08
Date Acceptance
2018-10-25
Citation
Designs, Codes and Cryptography, 2019, 87 (8), pp.1777-1796
ISSN
0925-1022
Publisher
Springer Verlag
Start Page
1777
End Page
1796
Journal / Book Title
Designs, Codes and Cryptography
Volume
87
Issue
8
Copyright Statement
© The Author(s) 2018. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Subjects
Science & Technology
Technology
Physical Sciences
Computer Science, Theory & Methods
Mathematics, Applied
Computer Science
Mathematics
Coding and information theory
Cryptography
Algebraic coding theory
SCHEMES
CODES
Computation Theory & Mathematics
0101 Pure Mathematics
0802 Computation Theory and Mathematics
0906 Electrical and Electronic Engineering
Publication Status
Published
Date Publish Online
2018-11-01