为什么Shamir Secret Sharing无法针对现成的主动攻击者提供安全保护？

#1 楼

这是对现成的SSS隐私的主动攻击。对于此攻击，我们假设允许攻击者（没有有效的共享）（与具有诚实密钥共享的$ T-1 $朋友）一起使用，共同使用协议来恢复“共享的机密”（可能不会是真正的共享秘密）；我们假定此共享机密恢复过程是通过某种MPC安全方法完成的，因此攻击者除了最终值外什么也不会学。我们还假定每个人的$ x $坐标都是公开的。

首先，攻击者选择一个值$ x_a $，它是一个$ x $坐标，而不是任何人共享的$ x $坐标。其他。如果交易商要生成具有$ x_a $值的股票，则会生成$ y $坐标，我们称其为$ y_a $；显然，攻击者并不知道$ y_a $的值。

然后，攻击者得到了一组$ T-1 $朋友，并让他们使用自己的份额恢复共享的秘密值（和攻击者将贡献值$（x_a，0）$;（实际上，$ y $坐标的非零值会起作用，但会使解释更加复杂）；他们将通过SSS恢复过程，并获得我们将其表示为$ S_0 $的值。

如果我们调用真实的共享机密$ S $，那么攻击者可以做的就是得出一个值$ T_0 $（取决于$ x $-他和他的朋友的坐标），并得出线性方程：

$$ S = T_0 y_a + S_0 $$

这是一个分为两个的线性方程未知数（$ S，y_a $）和$ T_0 \ ne 0 $，因此攻击者无法从中获取有关$ s $的任何信息，也可以从SSS的安全属性（攻击者及其$ T）中获取-1 $朋友只有$ T-1 $有效股份，因此他们当然无法恢复$ S $。

攻击者随后要做的是将一组不同的$ T-1 $朋友聚在一起（可以有一些重叠，但必须至少有一个区别），然后再次执行相同的操作（攻击者使用相同的$（ x_a，0）$ share。他们做同样的事情，得出“共享秘密”值$ S_1 $，攻击者最终得到第二个线性方程式：

$$ S = T_1 y_a + S_1 $$

现在，如果$ T_0 \ ne T_1 $（如果两组朋友是不同的，则很可能），攻击者在两个未知数中有两个线性方程；对于$而言，这很简单新币。

#2 楼

这是不诚实的参与者可以破坏Shamir的秘密共享的另一种方式：

让我们简要回顾一下Shamir的$（k，n）$秘密共享中的秘密重建是如何工作的。给定$ k $参与者$（x_1，x_2，\ dots，x_k）$的$ x $坐标，一种重构秘密的方法是计算拉格朗日基多项式：$$ \ ell_j（x）= \ prod_ { 1 \ le i \ le k，i \ ne j}（x-x_i）\，（x_j-x_i）^ {-1}，$$具有$ \ ell_j（x_j）= 1 $和$对于所有$ i \ ne j $ \ ell_j（x_i）= 0 $。然后可以将插值股份$（x_i，y_i）$的多项式$ p（x）$计算为线性组合：$$ p（x）= \ sum_ {1 \ le j \ le k} y_j \，\ ell_j（x），$$和秘密恢复为$ S = p（0）$。等效地，我们也可以首先在原点处评估基本多项式以获得系数$ c_j = \ ell_j（0）$，然后简单地将机密重构为份额的线性组合：$$ S = \ sum_ {1 \现在，假设$ x $坐标是公开的（或在重建过程中显示，因为它们最终必须是公开的），任何参与者$ j $可以在显示任何$ y $坐标之前预先计算自己的系数$ c_j $。

特别是，这意味着，如果单个不诚实的参与者$ j $揭示了假$ y $坐标$ y'_j = y_j + \ delta $而不是其真实坐标$ y_j $，则重建的秘密最终将是$ s'= s + \ delta \，c_j $而不是真实秘密$ j $。知道$ \ delta $之后，这个不诚实的参与者便可以恢复真正的秘密$ s = s'-\ delta \，c_j $，而所有其他参与者都只剩下假值$ s'$，而无法重建$ s $。

此外，不诚实的参与者只需将其份额调整为$ \ delta =（s'-s）\，c_j ^ {-1}，就可以轻松地选择真实秘密$ s $和恢复的秘密$ s'$之间的差。 $。如果他们能够以某种方式猜测出真正的秘密，那甚至可以让他们准确选择所揭示的伪造秘密。

如果共享过程中确实有$ k $参与者，那么这种操纵将不可检测。当参与者超过$ k $时，该操作仍将起作用，但是（除非有多个不诚实的参与者合在一起），所得插值多项式通常将比预期的$ k-1 $高一个度，这应该会引起一些警报钟声。

#3 楼

在您的示例中，我们假设秘密共享方案是一个$（k，n）$阈值共享方案，其中$ k = \ frac {n + 1} {2} $，因为您只能说“诚实多数”

如果随后$ n $协议遵循方将其信息发布给该组，那么对抗参与者就可以构建整个秘密，因为他们拥有共享，而无需将共享共享给其他人派对。这样，对手就拥有了秘密，但是遵循协议的各方却没有。

这违反了计划的公平性，因为对抗行为使一方获得了优势-他们可以计算秘密，而其他人则不能。

根据RHUL的幻灯片，对手扣留了他的股份并发布了虚假的股份，其不良后果包括：


防止诚实的参与者学习正确的秘密
未能提醒其他参与者他们没有重构正确的秘密
允许对手学习正确的秘密。

#4 楼

Shamir SS完全专注于从少于$ t $的子集中了解有关秘密$ s $的问题。由于其子集的构造，该子集根本不会泄漏任何内容。

Shamir SS基本版本的两个局限性涉及各方（交易商和股东），遵守协议：


在交易期间，交易商可以交易不一致的股票。
在重建阶段，一个或一些股东发送了不正确的股份（不是交易商所分配的股份）。

问题不是保密，而是证明一致的困难。涉及的价值。例如，假设$ s $是以下协议的秘密密钥：


发牌人生成$ s $和相应的公用密钥$ p $。
$ p $已发布。
交易者交易股票。
交易者删除$ s $。
第三方加密发送给$ p $的消息。
$ t $的股东执行重建协议。
重建后的秘密$ s * $用于解密第5步中产生的消息。步骤6将失败。如果任何股东发送了错误的份额，则步骤6将失败。在这两种情况下，原始机密都会丢失，并且无法解密在第5步中发送的消息。

想象一下该协议用于在线投票，因为它很常见MPC的应用。如果对这种错误的投票解密和计数失败，那么重复该过程将不是选民喜欢的选择。 VSS的想法是确保过程的一致性：如果所交易的股份“不合理”（例如与公钥无关），或者其中一位股东发送了假股份，则协议将暂停并能够及时跟踪故障。