Paper 2021/285
Quadratic Secret Sharing and Conditional Disclosure of Secrets
Amos Beimel, Hussien Othman, and Naty Peter
Abstract
There is a huge gap between the upper and lower bounds on the share size of secretsharing schemes for arbitrary $n$party access structures, and consistent with our current knowledge the optimal share size can be anywhere between polynomial in $n$ and exponential in $n$. For linear secretsharing schemes, we know that the share size for almost all $n$party access structures must be exponential in $n$. Furthermore, most constructions of efficient secretsharing schemes are linear. We would like to study larger classes of secretsharing schemes with two goals. On one hand, we want to prove lower bounds for larger classes of secretsharing schemes, possibly shedding some light on the share size of general secretsharing schemes. On the other hand, we want to construct efficient secretsharing schemes for access structures that do not have efficient linear secretsharing schemes. Given this motivation, PaskinCherniavsky and Radune (ITC'20) defined and studied a new class of secretsharing schemes in which the shares are generated by applying degree$d$ polynomials to the secret and some random field elements. The special case $d=1$ corresponds to linear and multilinear secretsharing schemes. We define and study two additional classes of polynomial secretsharing schemes: (1) schemes in which for every authorized set the reconstruction of the secret is done using polynomials and (2) schemes in which both sharing and reconstruction are done by polynomials. For linear secretsharing schemes, schemes with linear sharing and schemes with linear reconstruction are equivalent. We give evidence that for polynomial secretsharing schemes, schemes with polynomial sharing are probably stronger than schemes with polynomial reconstruction. We also prove lower bounds on the share size for schemes with polynomial reconstruction. On the positive side, we provide constructions of secretsharing schemes and conditional disclosure of secrets (CDS) protocols with quadratic sharing and reconstruction. We extend a construction of Liu et al. (CRYPTO'17) and construct optimal quadratic $k$server CDS protocols for functions $f:[N]^k\rightarrow \{0,\1}$ with message size $O(N^{(k1)/3})$. We show how to transform our quadratic $k$server CDS protocol to a robust CDS protocol, and use the robust CDS protocol to construct quadratic secretsharing schemes for arbitrary access structures with share size $O(2^{0.705n})$; this is better than the best known share size of $O(2^{0.7576n})$ for linear secretsharing schemes and worse than the best known share size of $O(2^{0.585n})$ for general secretsharing schemes.
Note: A revised version.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in CRYPTO 2021
 Keywords
 secret sharingconditional disclosure of secrets
 Contact author(s)
 amos beimel @ gmail com
 History
 20220224: last of 9 revisions
 20210307: received
 See all versions
 Short URL
 https://ia.cr/2021/285
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/285, author = {Amos Beimel and Hussien Othman and Naty Peter}, title = {Quadratic Secret Sharing and Conditional Disclosure of Secrets}, howpublished = {Cryptology ePrint Archive, Paper 2021/285}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/285}}, url = {https://eprint.iacr.org/2021/285} }