Imperial College London
Portrait Picture

Dr Mahdi Cheraghchi

Faculty of Engineering, Department of Computing

Honorary Senior Lecturer
 
 
 
//

Contact

 

m.cheraghchi Website CV

 
 
//

Location

 

353ACE ExtensionSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Cheraghchi:2019:10.1007/s10623-018-0578-y,
author = {Cheraghchi, M},
doi = {10.1007/s10623-018-0578-y},
journal = {Designs, Codes and Cryptography},
pages = {1777--1796},
title = {Nearly optimal robust secret sharing},
url = {http://dx.doi.org/10.1007/s10623-018-0578-y},
volume = {87},
year = {2019}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - 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.
AU  - Cheraghchi,M
DO  - 10.1007/s10623-018-0578-y
EP  - 1796
PY  - 2019///
SN  - 0925-1022
SP  - 1777
TI  - Nearly optimal robust secret sharing
T2  - Designs, Codes and Cryptography
UR  - http://dx.doi.org/10.1007/s10623-018-0578-y
UR  - http://hdl.handle.net/10044/1/65789
VL  - 87
ER  -
Download