## CryptoDB

### Paper: On the Power of Amortization in Secret Sharing: d-Uniform Secret Sharing and CDS with Constant Information Rate

Authors: Benny Applebaum Barak Arkis DOI: 10.1007/978-3-030-03807-6_12 Search ePrint Search Google TCC 2018 Consider the following secret-sharing problem. Your goal is to distribute a long file s between n servers such that $(d-1)$ (d-1)-subsets cannot recover the file, $(d+1)$ (d+1)-subsets can recover the file, and d-subsets should be able to recover s if and only if they appear in some predefined list L. How small can the information ratio (i.e., the number of bits stored on a server per each bit of the secret) be?We advocate the study of such d-uniform access structures as a useful scaled-down version of general access structures. Our main result shows that, for constant d, any d-uniform access structure admits a secret sharing scheme with a constant asymptotic information ratio of $c_d$ cd that does not grow with the number of servers n. This result is based on a new construction of d-party Conditional Disclosure of Secrets (CDS) for arbitrary predicates over n-size domain in which each party communicates at most four bits per secret bit.In both settings, previous results achieved a non-constant information ratio that grows asymptotically with n, even for the simpler (and widely studied) special case of $d=2$ d=2. Moreover, our multiparty CDS construction yields the first example of an access structure whose amortized information ratio is constant, whereas its best-known non-amortized information ratio is sub-exponential, thus providing a unique evidence for the potential power of amortization in the context of secret sharing.Our main result applies to exponentially long secrets, and so it should be mainly viewed as a barrier against amortizable lower-bound techniques. We also show that in some natural simple cases (e.g., low-degree predicates), amortization kicks in even for quasi-polynomially long secrets. Finally, we prove some limited lower-bounds, point out some limitations of existing lower-bound techniques, and describe some applications to the setting of private simultaneous messages.
##### BibTeX
@inproceedings{tcc-2018-28989,
title={On the Power of Amortization in Secret Sharing: d-Uniform Secret Sharing and CDS with Constant Information Rate},
booktitle={Theory of Cryptography},
series={Theory of Cryptography},
publisher={Springer},
volume={11239},
pages={317-344},
doi={10.1007/978-3-030-03807-6_12},
author={Benny Applebaum and Barak Arkis},
year=2018
}