沙米尔股份独立吗？

Question

假设我们有一个秘密的s \in Z_p。我们根据\{ (x_i, s_i) \}_{i=1}^{N}的一种(N,k) Shamir方案生成秘密共享的集合。这些评价是根据下列随机多项式生成的：

f(x) = s + \sum_{l=1}^{k-1} t_i x^l

其中t_i \gets Z_p在Z_p中是一致随机的。

我对股票s_i的统计属性感兴趣。我们是否可以声称它们是独立的和一致随机的？另外，我们是否也可以声称它们的任何k-1的联合分发？

Answer 1

如果是N>k，那么完整的股票集是相关的，因为给定它们的任何k，您可以找到s，从它可以找到另一个N-k。

如果你取任何k股票，就会有p^k可能多项式和p^k可能的股票元组，它们都唯一地决定了一个多项式，所以股票价值的分布是多项式分布的排列。如果你对s一无所知，即你把它建模成像t_i一样的均匀分布，那么所有多项式都是等概率的，因此股票的可能值也是一样的(这也意味着它们是不相关的)。如果您有关于s的信息，那么这些股票并不是不相关的--最明显的是，如果您知道s，那么任何股票的价值都是由其他股票决定的。

如果您接受任何k-1股票，那么对于任何固定的s，同样的论点意味着这些股票是均匀分布的(并且是不相关的)。对于任意分布的s，股票的分布是均匀分布的加权平均，是一致的。