Welcome to the resource topic for 2018/001
Title:
On the Power of Amortization in Secret Sharing: d-Uniform Secret Sharing and CDS with Constant Information Rate
Authors: Benny Applebaum, Barak Arkis
Abstract:Consider the following secret-sharing problem. Your goal is to distribute a long file s between n servers such that (d-1)-subsets cannot recover the file, (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 initiate the study of such d-uniform access structures, and view them 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 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 (Gertner et al., JCSS '00) 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 non-constant information ratio which grows asymptotically with n even for the simpler (and widely studied) special case of d=2. Moreover, our results provide a unique example for a natural class of access structures F that can be realized with information rate smaller than its bit-representation length \log |F| (i.e., \Omega( d \log n) for d-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.
ePrint: https://eprint.iacr.org/2018/001
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .