里德所罗门秘密共享和作为一个一次性对称密钥？

Question

Shamir的秘密分享只是里德-所罗门的一个特例，它只使用一个系数来存储秘密，而不是整个多项式。

然而，Sarwate建议，后者可以通过牺牲信息论安全性来实现：

第二个方面的里德-所罗门编码方案考虑的麦克利希-萨沃特文件是，它没有必要填补S(x)与m-1随机选择的符号。事实上，秘密可以是所有的m符号s_0,\ldots,s_{m-1}，而不仅仅是s_0。一个优点是我们可以使用一个较小的有限域。比方说，如果秘密是1000位和m=10，那么Shamir的方案将在\mathbb F_{2^{1000}}上运行，并且每个秘密的共享也将是1000位长。需要10千比特(10 1千比特股票)来恢复这个秘密。另一方面，里德-所罗门编码方案可以将秘密划分为10 100-bit符号，并在\mathbb F_{2^{100}}上运行。另外，每个份额都将是100位长，并且，像以前一样，只需要10个这样的空股就可以恢复秘密。外地规模的这种减少确实是以安全方面的代价为代价的。如果只有9共享可供阴谋集团使用，并且他们猜测第十个所需份额的可能值，他们就可以得出一个“短列表”，其中只列出1000-bit秘密可能有的2^{100}值。Shamir的方案在类似的困境中会有一个2^{1000}可能的秘密值列表，从而提供完美的安全性。在降低安全性和易于实现以及存储每个秘密共享之间的权衡是需要对每个应用程序进行评估的。最安全的方案具有与秘密一样长的共享，而里德-所罗门方案可以以降低安全性为代价来减少共享规模。来源

在这件事上还有其他人同意萨瓦特吗？事实证明是真的吗？

假设您有一个10,000-bit秘密，并将其拆分为100 100-bit股票。拥有99的股份，你真的可以不了解任何关于10,000-bit的秘密，即使它的部分是已知的或可以猜测的？复杂度小于2^{100}。

难道这不意味着可以用来加密吗？最后一个共享可以从数据源中保留，并有效地作为其加密密钥。

Answer 1

萨瓦特的评论对我来说似乎毫无争议。它与“打包秘密共享”(参见为什么只有一个秘密价值与Shamir的秘密分享？)的概念有关，也称为“斜坡秘密共享”。

通过点(x_1, y_1), \ldots, (x_n,y_n)回忆多项式插值。多项式具有由下列线性方程组给出的系数p_0, \ldots, p_{n-1}：

`\begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix}      =    \begin{bmatrix}        x_1^0 & x_1^1 & x_1^2 & \cdots & x_1^{n-1} \\       x_2^0 & x_2^1 & x_2^2 & \cdots & x_2^{n-1} \\         \vdots & & & \ddots & \vdots \\       x_n^0 & x_n^1 & x_2^2 & \cdots & x_n^{n-1}    \end{bmatrix}    \begin{bmatrix}        p_0 \\ p_1 \\ p_2 \\ \vdots \\ p_{n-1}    \end{bmatrix} #qcStackCode#`

重要的观察是矩阵是Vandermonde矩阵，因此它具有满秩。事实上，它的任何行子集也都有满秩。

了解多项式上的t共享/点可以告诉您关于p系数的t (独立)线性约束。这就像将向量(p_0, \ldots, p_{n-1})约束到维数n-t的子空间一样。

在正常的Shamir共享中，p_0是秘密有效载荷，p_1, \ldots, p_{n-1}是随机的。在多项式上有t=n点之前，您不会得到关于p_0的信息。

在打包的秘密共享中，您可以让p_0, \ldots, p_{s-1}成为秘密有效载荷和p_s, \ldots, p_{n-1}随机。如果您知道多项式上的n-s点，则没有关于有效载荷的信息。如果您知道多项式上的n-s+1点，那么现在您就知道了包含有效载荷的维度s-1的子空间。如果你知道多项式上的n-s+2点，你就知道维s-2的一个子空间，它包含有效载荷等等。

假设我们有一个秘密值，我们将其写为p_0 \| \cdots \| p_{s-1}。如果已知此值是高度结构化的，那么很有可能通过知道它存在于某个(s-2)-dimensional子空间中而完全了解它的秘密。因此，这种秘密共享只有在有效负载上缺乏足够的结构时才是好的，或者根本不关心在n-s共享被披露后会发生什么。