Shamir 秘密共享的份額是均勻分佈的隨機數嗎？
讓 $ t $ 是 Shamir 秘密共享 (SSS) 方案中的一個門檻值。
假設我們知道 $ t’<t $ 分享。假設我們從與 SSS 中使用的欄位相同的欄位中統一選擇了一些隨機值。
問題：我們能否以不可忽略的機率將隨機值與股票區分開來？
度數的每個值 $ t-1 $ 全 SSS 多項式 $ P $ 在任何評估 $ x $ 在有限域中 $ F $ 它被定義為均勻分佈在 $ F $ . 例如，請參閱此答案。
現在假設 $ t’<t $ 股份被披露，說他們是 $ S’={(x_1,P(x_1)),\ldots,(x_{t’},P(x_{t’}))}. $
如果原始股份集是 $ S $ 非空集 $ T=S\setminus S’ $ 現在以通常的方式唯一地確定一個有效的拉格朗日插值多項式 $ t-t’-1 $ 給定任何 $ t-t’ $ 積分 $ x $ 在 $ K \setminus {x_1,\ldots,x_{t’}} $ .
**區分算法：**讓 $ k>t-t’ $ 並讓認領股份 $$ C={(x_j,y_j):1\leq j \leq k} $$ 被給予。如果這些是真正的股票 $ t-t’ $ 它們將給出與任何其他相同大小的此類子集相同的拉格朗日插值多項式。如果 $ y_j $ 是隨機的，兩個不同的拉格朗日插值說兩個支持 $$ A={x_1,\ldots,x_{t-t’}} $$ 和上 $$ A’={x_2,\ldots,x_{t-t’},x_{t-t’+1}} $$ 將給出具有機率的不同拉格朗日插值多項式$$ 1-\frac{1}{q} $$ 在哪裡 $ q $ 是我們正在使用的欄位的大小。
事實上，即使只有一股 $ A \bigcup A’ $ 是隨機的，該屬性將成立，因為至少有一個插值將產生一個隨機多項式。
假設我們知道 $ t’<t $ 分享。假設我們從與 SSS 中使用的欄位相同的欄位中統一選擇了一些隨機值。
問題：我們能否以不可忽略的機率將隨機值與股票區分開來？
這取決於。
現在，有兩種可能的方法來解釋您的問題（雖然兩者的答案相同，但邏輯略有不同）。以下是我看到的方式：
- 這些 $ r $ “隨機值”將被同時視為潛在份額；也就是說，對手總共獲得了 $ t’ + r $ 分享， $ t’ $ 其中是真實股份，以及 $ r $ 其中可能是隨機值，或者（就對手而言）也可能是真實份額。如果是這種情況，請遵循以下邏輯。
- 這些 $ r $ “隨機值”是缺失份額的所有可能性。那是， $ r-1 $ 其中是隨機值（攻擊者知道這一點），最後一個值也可能是隨機值，或者它可能是真實值 - 攻擊者不知道哪個，他也不知道哪個可能是真正的價值。如果是這種情況，請遵循以下邏輯，但使用 $ r=1 $ ，並迭代誠實分享的各種可能性。
我還將假設攻擊者對共享秘密可能是什麼有所了解；他可能不知道確切的值，但他可能知道該值是一小部分可能性之一（或者至少，知道有一大組不可能的值）。
在這種情況下，如果 $ t’ + r < t $ ，那麼對手無法確定任何事情；所有這些股票看起來都是隨機的。也就是說，對於已知份額的任何值和共享秘密的任何值，未知多項式都有可能的係數，這將導致觀察值（事實證明，有相同數量的可能性獨立於觀察值，因此對手甚至無法獲得任何機率資訊）。
另一方面，如果 $ t’ + r \ge t $ ，那麼對手確實有辦法；他可以獲取他所擁有的股份（包括已知的好股份，以及那些有問題的股份），並重建他們所暗示的共享秘密；然後，他會檢查該共享秘密是否可行。如果這不是可能的值之一，他就知道他使用的某些份額是不正確的。