On the Power of Computational Secret Sharing
On the Power of Computational Secret Sharing
复制标题
论计算秘密共享的力量
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Kwangjo Kim
中科院分区：
文献类型：
--
作者：
V. Vaikuntanathan;Arvind Narayanan;K. Srinathan;C. Rangan;Kwangjo Kim
秘密共享是密码学和分布式计算中一个非常重要的基础。在这项工作中，我们考虑计算秘密共享（CSS），可证明允许一个较小的份额大小（因此更高的效率）比其信息理论的同行。现有的CSS方案导致简洁的共享大小，并且在少数情况下，如阈值访问结构，是最佳的。然而，一般来说，它们不是有效的（共享大小不是参与者数量n的多项式），因为它们要么假设给定访问结构的有效完美方案（如[10]），要么使用指数（n）数量的公共信息（如[5]）。在本文中，我们的目标是探索其他允许高效CSS的访问结构类别，而不做任何其他假设。我们构造有效的CSS计划的每一个访问结构单调P.截至目前，大多数已知的有效的信息理论计划是访问结构代数NC 2。单调P和代数NC 2在一个不包含另一个的意义上是不可比较的。因此，我们的工作导致秘密共享计划的一类新的访问结构。在本文的第二部分中，我们引入了与半可信第三方秘密共享的概念，并证明了在这个宽松的模型中，有效的CSS方案存在于更广泛的一类访问结构，即单调NP。
Secret sharing is a very important primitive in cryptography and distributed computing. In this work, we consider computational secret sharing (CSS) which provably allows a smaller share size (and hence greater efficiency) than its information-theoretic counterparts. Extant CSS schemes result in succinct share-size and are in a few cases, like threshold access structures, optimal. However, in general, they are not efficient (share-size not polynomial in the number of players n), since they either assume efficient perfect schemes for the given access structure (as in [10]) or make use of exponential (in n) amount of public information (like in [5]). In this paper, our goal is to explore other classes of access structures that admit of efficient CSS, without making any other assumptions. We construct efficient CSS schemes for every access structure in monotone P. As of now, most of the efficient information-theoretic schemes known are for access structures in algebraic NC 2. Monotone P and algebraic NC 2 are not comparable in the sense one does not include other. Thus our work leads to secret sharing schemes for a new class of access structures. In the second part of the paper, we introduce the notion of secret sharing with a semi-trusted third party, and prove that in this relaxed model efficient CSS schemes exist for a wider class of access structures, namely monotone NP.