模型
平安多方计算的平安显然是在有攻击者状况下的平安。在不同情景下，实现平安的难度也不同。最极其的例子是一个平安多方计算协定的所有参与者都是歹意参与者，那么这个协定的安全性就很难保障了。要实现平安，首先应该针对不同的状况建设不同的模型，而后针对这些模型进行钻研。
首先假如有攻击者（Adversary），攻击者能够通过各种伎俩收购或者管制（Corrupt）局部参与者，而参与者一旦被收购或者管制，该参与者的所有通信历史信息和本地信息都会被攻击者把握。攻击者能够理论了解成黑客，他通过黑客伎俩入侵到了参与者的计算机中，获得了参与者计算机的控制权，因而能够把握所有该参与者把握的信息。攻击者也能够了解成竞争公司的人，通过金钱来贿赂参与者，以此获得信息。
那么显然，攻击者可能最大收购的参与者人数，很大水平上影响了协定是否平安。（t，n）门限攻击者构造是指参与者总数是n，攻击者最多可能收购t个参与者。对于攻击者构造，常常会说是图片的攻击者构造指攻击者收购的参与者汇合中的人数小于参与者总人数的 1/2，即𝑡 < 1/2；图片的攻击者构造指攻击者收购的参与者汇合中的人数小于参与者总人数的𝑡 < 1/3。
攻击者模型分为半诚恳攻击者模型和歹意攻击者模型。在半诚恳攻击者模型下，被攻击者收购的参与者恪守协定，不会在协定执行中途退出，也会诚恳地发送本人的计算结果，不会篡改协定计算结果。然而被收购的参与者的所有信息，包含历史通信信息、计算结果等都会被攻击者得悉。在歹意攻击者模型下，被攻击者收购的参与者不会再诚恳地恪守协定，可能会篡改协定计算结果，其发送给其余参与者的信息有可能是虚伪和伪造的。
攻击者的能力还能够依据其计算能力进行划分，在计算意义下平安的模型中，攻击者的计算能力是概率多项式工夫的，意味着攻击者无奈解决常见的艰难问题，即便计算出来，所破费的工夫也曾经超过了信息的有效期，取得的信息曾经是过期的信息。另一种模型为信息论意义下平安的模型，在这种模型下，攻击者的计算能力是有限的。
门限机制和Shamir机密共享
设 t 和 n 为两个正整数，且 t≤n。n个须要共享机密的参与者汇合为𝑃 = {𝑃1,… ,𝑃𝑛 }，一个(t,n)门限机密共享体制是指：假如𝑃1,… ,𝑃𝑛要共享同一个机密s， 将s称为主机密，有一个机密管理中心𝑃0来负责对s进行治理和调配。机密管理中心𝑃0把握有机密调配算法和机密重构算法，这两个算法均满足重构要求和安全性要求。
机密管理中心𝑃0首先通过将主机密s输出机密调配算法，生成n个值，别离为𝑠1,… ,𝑠𝑛，称𝑠1,… ,𝑠𝑛为子机密。而后机密管理中心𝑃0别离将机密调配算法产生的子机密𝑠1,… ,𝑠𝑛通过𝑃0与𝑃𝑖之间的平安通信信道机密地传送给参与者𝑃𝑖，参与者𝑃𝑖不得向任何人泄露本人所收到的子机密𝑠𝑖。
门限值t指的是任意大于或等于t个参与者𝑃𝑖，将各自把握的子机密𝑠𝑖进行共享，任意的一个参与者𝑃𝑖在取得其余𝑡−1个参与者所把握的子机密后，都可独立地通过机密重构算法复原出主机密s。而即便有任意的𝑛−𝑡个参与者失落了各自所把握的子机密，剩下的 t 个参与者仍旧能够通过将各自把握的子机密与其余参与者共享，再应用机密重构算法来重构出主机密s。安全性要求是指任意攻击者通过收购等伎俩获取了少于 t个的子机密，或者任意少于 t 个参与者串通都无奈复原出主机密 s，也无奈失去主机密 s 的信息。
Shamir于1979年，基于多项式插值算法设计了Shamir(t,n)门限机密共享体制，它的机密调配算法如下：
首先假如𝔽𝑞为q元无限域，q是素数且𝑞>𝑛。图片是参与者汇合，P共享主机密𝑠,𝑠∈𝔽𝑞，机密管理中心𝑃0按如下所述的步骤对主机密𝑠进行调配，为了可读性起见，以下公式均略去了模q操作：
参与者𝑃0机密的在无限域𝔽𝑞中随机选取𝑡−1个元素，记为图片，并取以𝑥为变元的多项式𝑓(𝑥)
对于1≤𝑖≤ 𝑛，𝑃0机密计算𝑦𝑖=𝑓(𝑖)
对于1≤𝑖≤𝑛，𝑃0通过平安信道机密地将(𝑖, 𝑦𝑖)调配给𝑃𝑖
Shamir(t,n)门限共享体制的机密重构能够应用艰深的解方程法，即t个方程能够确定t个未知数，而这t个未知数即为包含主机密𝑠在内的多项式𝑓(𝑥)的各项系数。如参与者𝑃1,… ,𝑃𝑡把握了子机密𝑓(1),…,𝑓(𝑡)，解方程：
即可求解出系数。
另一种形式是应用多项式插值法进行重构主机密。假如这 t 个子秘钥别离为(𝑥𝑖 ,𝑦𝑖) ，其中𝑦𝑖=𝑓(𝑥𝑖)，𝑖=1,…, 𝑡且𝑖 ≠ 𝑗 时 𝑥𝑖 ≠ 𝑥𝑗。参与者𝑃1,… ,𝑃𝑡独特计算
显然，ℎ(𝑥)是一个𝑡−1次的多项式，且因为𝑖≠𝑗时𝑥𝑖≠𝑥𝑗，每个加式的分母均不为零，因而对于𝑖=1,…,𝑡，𝑦𝑖=ℎ(𝑥𝑖)=𝑓(𝑥𝑖) 。又依据多项式的性质，如果存在两个最高次均为𝑡−1次的多项式，这两个多项式在𝑡个互不雷同的点所取的值均雷同，那么这两个多项式雷同。即ℎ(𝑥)=𝑓(𝑥)，进而参与者𝑃𝑖计算ℎ(0)=𝑓(0)=𝑠，即可复原主机密𝑠。
对于无限域𝔽𝑞上n-1次的多项式，设为𝑓(𝑥)，存在无限域𝔽𝑞上的n个元，记为𝜆1,…,𝜆𝑛，使得：
称(𝜆1,…,𝜆𝑛)为重组向量(recombinationn vector)，因为证实过程较为繁琐，因而具体证实过程写在最初。
对于矩阵M：
设机密调配多项式为𝑓(𝑥)，参与者𝑃𝑖把握的子机密为𝑓(𝑖)，因为存在重组向量(𝜆1,…,𝜆𝑛)，因而有：
若要计算重组向量，可通过计算矩阵𝑀的逆矩阵图片来计算重组向量(𝜆1,…,𝜆𝑛)：
在取得重组向量后，可构建基于Shamir门限体制的平安多方计算协定。首先假如𝑃={𝑃1,…,𝑃𝑛 }是参与者汇合，𝑃𝑖把握输出𝑥𝑖(1≤𝑖≤𝑛)，须要独特计算的函数为𝑓(𝑥1,…, 𝑥𝑛)。在无限域𝔽𝑞上的𝑆ℎ𝑎𝑚𝑖𝑟(𝑡+1,𝑛)门限体制次要流程为：
输出阶段，每个参与者𝑃𝑖将本人的输出𝑥𝑖，利用𝑆ℎ𝑎𝑚𝑖𝑟(𝑡+1, 𝑛)门限机密共享体制，机密选取最高 t 次的随机多项式𝑓𝑖(𝑥)，满足𝑓𝑖(0)=𝑥𝑖 。而后𝑃𝑖将𝑓𝑖(𝑗)发送给参与者𝑃𝑗。
计算阶段，假如输出的𝑎和𝑏曾经通过至少 t 次的随机多项式𝑓𝑎(𝑥)和𝑓𝑏(𝑥)通过Shamir门限体制共享给了各个参与者，其中是随机的多项式系数。参与者𝑃𝑖把握输出𝑎的子机密𝑎𝑖和输出𝑏的子机密𝑏𝑖。至少t次的起因是多项式的系数是随机产生的，因而t次的系数也有可能是0。
多方计算𝑎+𝑏：每个参与者𝑃𝑖独立计算𝑐𝑖 =𝑎𝑖+𝑏𝑖, 1≤𝑖 ≤𝑛 。𝑐1,…, 𝑐𝑛 即为𝑎+𝑏通过随机多项式共享后的后果，通过多项式插值法或者解方程即可复原机密s。子机密能够间接相加，是因为对于𝑐𝑖=𝑎𝑖+𝑏𝑖=𝑓𝑎(𝑖)+𝑓𝑏(𝑖)= (𝑚𝑡+𝑛𝑡)图片+⋯+ (𝑚1+𝑛1 )𝑖+𝑎+𝑏，多项式的次数并没有发生变化，新的多项式𝑓𝑎(𝑥)+𝑓𝑏(𝑥)的最高次数仍旧为 t，t+1 个参与者共享他们所把握的𝑐𝑖，即可依据t+1个方程解t+1个未知数，解出𝑎+𝑏。或者也可间接应用拉格朗日插值法求解出𝑎+𝑏。
𝑎𝑏：首先每个参与者计算
接着每个𝑃𝑖 单独选取次数为t次的随机𝑛多项式ℎ
。向各个参与者调配𝑑𝑖，且所有参与者调配完结后，𝑃𝑖把握了信息同时𝜆1,…,𝜆𝑛是公开的重组向量，即(𝜆1,…,𝜆𝑛)满足，因而𝑃𝑖可计算
，再利用多项式插值法，即可取得𝑎𝑏。
对于重组向量存在性的证实过程为：设，则，且可被示意为：
思考一个n阶矩阵
因为矩阵𝑀是满秩矩阵，因而存在𝜆1,…,𝜆𝑛∈𝔽𝑞，使得
因而有：
发表回复