Paper 2018/001

On the Power of Amortization in Secret Sharing: $d$-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 $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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
secret sharinginformation-theoretic cryptography
Contact author(s)
benny applebaum @ gmail com
History
2018-09-23: revised
2018-01-02: received
See all versions
Short URL
https://ia.cr/2018/001
License
Creative Commons Attribution
CC BY

BibTeX

@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},
      note = {\url{https://eprint.iacr.org/2018/001}},
      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.