Secret-Sharing Schemes for General and Uniform Access Structures
Secret-Sharing Schemes for General and Uniform Access Structures
复制标题
DOI：
10.1007/978-3-030-17659-4_15
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Benny Applebaum;A. Beimel;O. Farràs;O. Nir;Naty Peter
中科院分区：
文献类型：
--
作者：
Benny Applebaum;A. Beimel;O. Farràs;O. Nir;Naty Peter
一个秘密共享方案允许一些被授权的各方集合来重建一个秘密;被授权集合的集合被称为访问结构。30多年来，人们都知道，任何（单调）收集的授权集可以实现的秘密共享计划，其份额的大小，直到最近没有更好的计划是已知的。在最近的一次突破中，Liu和Vaikuntanathan（STOC 2018）将股票规模降至。我们的第一个贡献是将秘密共享的指数降低到0.892。对于特殊的线性秘密共享方案，我们得到了0.942的指数（Liu和Vaikuntanathan的指数为0.999）.受Liu和Vaikuntanathan构造秘密共享方案的启发，我们研究了一致访问结构下的秘密共享方案.一个访问结构是一致的，如果所有的大小较大的thank集都是授权的，所有的大小较小的thank集都是未授权的，并且每个大小k集可以是授权的或未授权的。Liu和Vaikuntanathan从有条件的秘密公开协议出发，构造了统一访问结构的秘密共享方案，并将这些方案结合起来，得到了一般访问结构的秘密共享方案。本文的第二个贡献是构造了统一访问结构的秘密共享方案。我们得到了如下结果：对于大秘密，一个秘密共享方案具有分叉-一致访问结构，其中共享大小是秘密大小的倍;对于二进制秘密，一个线性秘密共享方案具有分叉-一致访问结构，其中共享大小是（其中是二进制熵函数）.通过计算参数，这种构造是最优的（直到多项式因子）。一个秘密共享方案fork-uniform访问结构的二进制秘密，其中的份额大小为。我们的第三个贡献是ad-hoc PSM协议的构造，即，PSM协议，其中只有一个子集的各方将计算其输入的函数。这一结果是基于我们在构建秘密共享方案中使用的思想，即二进制秘密的分叉统一访问结构。
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 sizeand until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to. 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 isk-uniform if all sets of size larger thankare authorized, all sets of size smaller thankare unauthorized, and each set of sizekcan 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 fork-uniform access structures for large secrets in which the share size istimes the size of the secret.A linear secret-sharing scheme fork-uniform access structures for a binary secret in which the share size is(wherehis the binary entropy function). By counting arguments, this construction is optimal (up to polynomial factors).A secret-sharing scheme fork-uniform access structures for a binary secret in which the share size is.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 fork-uniform access structures for a binary secret.