Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups
Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups
复制标题
任意阿贝尔群上的最优黑盒秘密共享
DOI：
10.1007/3-540-45708-9_18
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
S. Fehr
中科院分区：
文献类型：
--
作者：
R. Cramer;S. Fehr
用于门限访问结构TT，n的黑盒秘密共享方案是在任何有限阿贝尔群G上工作的方案。简言之，这种方案与普通的线性秘密共享方案(在给定的有限域上)的不同之处在于，在Z上定义了分布矩阵和重构向量，并且独立于从其采样秘密和份额的群G来设计。这意味着无论选择哪个组G，都能保证完美的完整性和完美的私密性。我们将黑盒秘密共享问题定义为对于任意给定的TT，n，设计一个具有最小扩展因子的方案，即其中份额的全部向量的长度除以玩家数量n是最小的。这类方案与基于具有秘密或难以计算群序的群的分布式密码系统的环境相关。最近的一个例子是黑盒环上的安全通用多方计算。1994年，Desmedt和Frankel提出了一种巧妙的方法来解决黑盒秘密共享问题，该方法部分基于分圆数域上的多项式插值。对于任意给定的TT，n，其中O<；t<；n-1，其方案的展开因子为O(N)。利用Z上存在足够大的Vandermonde矩阵对的低次积分扩张，对于任意给定的TT，n具有O<；t<；n-1，构造了一个扩展因子为O(Logn)的黑盒秘密共享方案，证明了该方案是极小的.
A black-box secret sharing scheme for the threshold access structure Tt,n is one which works over any finite Abelian group G. Briefly, such a scheme differs from an ordinary linear secret sharing scheme (over, say, a given finite field) in that distribution matrix and reconstruction vectors are defined over Z and are designed independently of the group G from which the secret and the shares are sampled. This means that perfect completeness and perfect privacy are guaranteed regardless of which group G is chosen. We define the black-box secret sharing problem as the problem of devising, for an arbitrary given Tt,n, a scheme with minimal expansion factor, i.e., where the length of the full vector of shares divided by the number of players n is minimal.Such schemes are relevant for instance in the context of distributed cryptosystems based on groups with secret or hard to compute group order. A recent example is secure general multi-party computation over black-box rings.In 1994 Desmedt and Frankel have proposed an elegant approach to the black-box secret sharing problem based in part on polynomial interpolation over cyclotomic number fields. For arbitrary given Tt,n with O < t < n - 1, the expansion factor of their scheme is O(n). This is the best previous general approach to the problem.Using certain low degree integral extensions of Z over which there exist pairs of sufficiently large Vandermonde matrices with co-prime determinants, we construct, for arbitrary given Tt,n with O < t < n - 1, a black-box secret sharing scheme with expansion factor O(log n), which we show is minimal.