On the Power of Amortization in Secret Sharing
ACM Transactions on Computation Theory · 31.12.2020 · 12 (4) · 1-21
DOI: 10.1145/3417756 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, online erschienen am 30.09.2020. Verfasst von Benny Applebaum und 1 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 34 Literaturangaben. Gefördert von: H2020 European Research Council.
Abstract (Originalsprache)
Consider the following secret-sharing problem: A file s should be distributed 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 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 d ), 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.
Förderung
- H2020 European Research Council
Zitieren
APA
Applebaum, B., & Arkis, B. (2020). On the Power of Amortization in Secret Sharing. ACM Transactions on Computation Theory, 12(4), 1-21. https://doi.org/10.1145/3417756
Vancouver
Applebaum B, Arkis B. On the Power of Amortization in Secret Sharing. ACM Transactions on Computation Theory. 2020;12(4):1-21. doi:10.1145/3417756
BibTeX
@article{Applebaum2020,
author = {Applebaum, Benny and Arkis, Barak},
title = {On the Power of Amortization in Secret Sharing},
journal = {ACM Transactions on Computation Theory},
year = {2020},
volume = {12},
number = {4},
pages = {1--21},
doi = {10.1145/3417756}
}
EUVIMED