Paper 2018/441
Optimal Linear Multiparty Conditional Disclosure of Secrets Protocols
Amos Beimel and Naty Peter
Abstract
In a $k$party CDS protocol, each party sends one message to a referee (without seeing the other messages) such that the referee will learn a secret held by the parties if and only if the inputs of the parties satisfy some condition (e.g., if the inputs are all equal). This simple primitive is used to construct attribute based encryption, symmetricallyprivate information retrieval, priced oblivious transfer, and secretsharing schemes for any access structure. Motivated by these applications, CDS protocols have been recently studied in many papers. In this work, we study linear CDS protocols, where each of the messages of the parties is a linear function of the secret and random elements taken from some finite field. Linearity is an important property of CDS protocols as many applications of CDS protocols required it. Our main result is a construction of linear $k$party CDS protocols for an arbitrary function $f:[N]^{k}\rightarrow \{0,1\}$ with messages of size $O(N^{(k1)/2})$. By a lower bound of Beimel et al. [TCC 2017], this message size is optimal. We also consider functions with few inputs that return one, and design more efficient CDS protocols for them. CDS protocols can be used to construct secretsharing schemes for uniform access structures, where for some $k$ all sets of size less than $k$ are unauthorized, all sets of size greater than $k$ are authorized, and each set of size $k$ can be either authorized or unauthorized. We show that our results imply that every $k$uniform access structure with $n$ parties can be realized by a linear secretsharing scheme with share size $\min\{ (O(n/k))^{(k1)/2},O(n \cdot 2^{n/2})\}$. Furthermore, the linear $k$party CDS protocol with messages of size $O(N^{(k1)/2})$ was recently used by Liu and Vaikuntanathan [STOC 2018] to construct a linear secretsharing scheme with share size $O(2^{0.999n})$ for any $n$party access structure.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 Secretsharing schemes
 Contact author(s)
 naty @ post bgu ac il
 History
 20180907: revised
 20180514: received
 See all versions
 Short URL
 https://ia.cr/2018/441
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/441, author = {Amos Beimel and Naty Peter}, title = {Optimal Linear Multiparty Conditional Disclosure of Secrets Protocols}, howpublished = {Cryptology ePrint Archive, Paper 2018/441}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/441}}, url = {https://eprint.iacr.org/2018/441} }