Title | Secret-Sharing Schemes for General and Uniform Access Structures |
---|---|

Booktitle | Advances in Cryptology – EUROCRYPT 2019 |

Volume | 11478 |

Pages | 441-471 |

Year | 2019 |

URL | Search for the paper |

DOI | 10.1007/978-3-030-17659-4_15 (link) |

Author | Benny Applebaum |

Author | Amos Beimel |

Author | Oriol Farràs |

Author | Oded Nir |

Author | Naty Peter |

Abstract | A secret-sharing scheme allows some authorized sets of parties to reconstruct a secret; the collection of authorized sets is called the access structure. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size $$2^{n-o(n)}$$ and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to $$O(2^{0.994n})$$. Our first contribution is improving the exponent of secret sharing down to 0.892. For the special case of linear secret-sharing schemes, we get an exponent of 0.942 (compared to 0.999 of Liu and Vaikuntanathan).Motivated by the construction of Liu and Vaikuntanathan, we study secret-sharing schemes for uniform access structures. An access structure is k-uniform if all sets of size larger than k are authorized, all sets of size smaller than k are unauthorized, and each set of size k can be either authorized or unauthorized. The construction of Liu and Vaikuntanathan starts from protocols for conditional disclosure of secrets, constructs secret-sharing schemes for uniform access structures from them, and combines these schemes in order to obtain secret-sharing schemes for general access structures. Our second contribution in this paper is constructions of secret-sharing schemes for uniform access structures. We achieve the following results:A secret-sharing scheme for k-uniform access structures for large secrets in which the share size is $$O(k^2)$$ times the size of the secret.A linear secret-sharing scheme for k-uniform access structures for a binary secret in which the share size is $$\tilde{O}(2^{h(k/n)n/2})$$ (where h is the binary entropy function). By counting arguments, this construction is optimal (up to polynomial factors).A secret-sharing scheme for k-uniform access structures for a binary secret in which the share size is $$2^{\tilde{O}(\sqrt{k \log n})}$$. Our third contribution is a construction of ad-hoc PSM protocols, i.e., PSM protocols in which only a subset of the parties will compute a function on their inputs. This result is based on ideas we used in the construction of secret-sharing schemes for k-uniform access structures for a binary secret. |

@article{eurocrypt-2019-29393, title={Secret-Sharing Schemes for General and Uniform Access Structures}, booktitle={Advances in Cryptology – EUROCRYPT 2019}, series={Advances in Cryptology – EUROCRYPT 2019}, publisher={Springer}, volume={11478}, pages={441-471}, doi={10.1007/978-3-030-17659-4_15}, author={Benny Applebaum and Amos Beimel and Oriol Farràs and Oded Nir and Naty Peter}, year=2019 }