Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computations over Small Fields
Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computations over Small Fields
复制标题
DOI：
10.1007/11818175_31
复制
发表时间：
2006-08
期刊：
影响因子：
--
通讯作者：
Hao Chen;R. Cramer
中科院分区：
文献类型：
--
作者：
Hao Chen;R. Cramer
我们介绍了代数几何技术在秘密共享和安全多方计算（MPC）特别。主要结果是一个定义在有限域上的线性秘密共享方案（LSSS），具有以下性质.是的。参与者的数目n可以是，其中C是定义在上的代数曲线C。它是准门限的：它是t-拒绝和t +1+ 2g-接受，但不一定是t +1-接受。因此，它特别是斜坡方案。可以获得较高的信息速率.它对门限敌手结构具有强乘法性，如果。这是一个多线性代数性质的LSSS促进零错误多方乘法，无条件安全防止腐败的积极对手。有限域可以比n小得多。这是通过使用具有多个有理点的代数曲线。例如，对于每一个足够小的ε，存在一个有限域，使得对于无穷多个n，存在一个LSSS，其强乘法满足。Shamir的方案需要n> q且q具有强乘法，它是g = 0的特殊情况。现在考虑在具有安全信道的同步参与者网络中，MPC对主动对手无条件安全（具有零错误概率）的经典（“BGW”）场景。根据已知的结果，现在得出的结论是，在这种情况下存在MPC协议，与已知的基于Shamir的解决方案相比，在网络中交换的字段元素的数量方面实现了相同的通信复杂性。然而，作为将破坏容限降低一小部分ε的回报，q可以显著地小于坦恩。由于MDS码的特性，这种容差减小是不可避免的。该技术扩展到MPC的其他模型。不太专业的LSSS的结果可以从更一般的编码理论参数。
We introduce algebraic geometric techniques in secret sharing and in secure multi-party computation (MPC) in particular. The main result is a linear secret sharing scheme (LSSS) defined over a finite field, with the following properties.1. It isideal. The number of playersncan beas large as, whereCis an algebraic curveCof genusgdefined over.2. It isquasi-threshold: it ist-rejecting andt+1+2g-accepting, but not necessarilyt+1-accepting. It is thus in particular a ramp scheme. High information rate can be achieved.3. It hasstrong multiplicationwith respect to thet-threshold adversary structure, if. This is a multi-linear algebraic property on an LSSS facilitating zero-error multi-party multiplication, unconditionally secure against corruption by an activet-adversary.4. The finite fieldcan bedramatically smaller than n. This is by using algebraic curves with many-rational points. For example, for each small enoughε, there is a finite fieldsuch that for infinitely manynthere is an LSSS overwith strong multiplication satisfying.5. Shamir’s scheme, which requiresn>qand which has strong multiplication for, is a special case by takingg=0.Now consider the classical (“BGW”) scenario of MPC unconditionally secure (with zero error probability) against an activet-adversary with, in a synchronousn-player network with secure channels. By known results it now follows that there exist MPC protocols in this scenario, achieving the same communication complexities in terms of the number of field elements exchanged in the network compared with known Shamir-based solutions. However, in return for decreasing corruption tolerance by a smallε-fraction,qmay be dramatically smaller thann. This tolerance decrease is unavoidable due to properties of MDS codes. The techniques extend to other models of MPC. Results on less specialized LSSS can be obtained from more general coding theory arguments.