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

摘要

Consider the following secret-sharing problem: A file s should be distributed between n servers such that (d - l)-subsets cannot recover the file, (d + l)-subsets can recover the file, and d-subsets should be able to recover s if and only if they appear in some pre-defined list L. The goal is to minimize the information ratio- that is, the number of bits stored on a server per each bit of the secret. We show that for any constant d and any pre-defined list L. if the file is sufficiently long (exponential in n ), the problem can be solved 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 for arbitrary predicates over an 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 special case of d = 2. Moreover, our constructions yield 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 and point out some limitations of existing lower-bound techniques.