On the Power of Amortization in Secret Sharing: -Uniform Secret Sharing and CDS with Constant Information Rate
Benny Applebaum and Barak Arkis
Abstract
Consider the following secret-sharing problem. Your goal is to distribute a long file between servers such that -subsets cannot recover the file, -subsets can recover the file, and -subsets should be able to recover if and only if they appear in some predefined list . How small can the information ratio (i.e., the number of bits stored on a server per each bit of the secret) be?
We initiate the study of such -uniform access structures, and view them as a useful scaled-down version of general access structures. Our main result shows that, for constant , any -uniform access structure admits a secret sharing scheme with a *constant* asymptotic information ratio of that does not grow with the number of servers . This result is based on a new construction of -party Conditional Disclosure of Secrets (Gertner et al., JCSS '00) for arbitrary predicates over -size domain in which each party communicates at most four bits per secret bit.
In both settings, previous results achieved non-constant information ratio which grows asymptotically with even for the simpler (and widely studied) special case of . Moreover, our results provide a unique example for a natural class of access structures that can be realized with information rate smaller than its bit-representation length (i.e., for -uniform access structures) showing that amortization can beat the representation size barrier.
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.
@misc{cryptoeprint:2018/001,
author = {Benny Applebaum and Barak Arkis},
title = {On the Power of Amortization in Secret Sharing: $d$-Uniform Secret Sharing and {CDS} with Constant Information Rate},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/001},
year = {2018},
url = {https://eprint.iacr.org/2018/001}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.