Secret-Sharing

在shamir秘密共享方案中,為什麼秘密不能是中間係數,只有第一個或最後一個?

  • December 16, 2019

在shamir秘密共享方案中,Secret s被設置為方程中的常數

$ y_p = s+ \sum_{i=0}^{i = t-1} a_i * x_p^i $

s 只能是常數項或最後一個係數,否則可能會洩露秘密。這也是以下問題:

Shamir 秘密共享方案中的係數

我怎樣才能以數學的方式嚴格地證明這一點?在提供的答案中僅給出了一個範例。


更新:

我目前必須展示的數學方法是針對 (t,n) 系統的情況,其中 t = 3,在兩個人之間共享,並且 y 定義為

$ y_1 = a_0 + sx_1 + a_1x_1^2 $ 模P

$ y_2 = a_0 + sx_2 + a_1x_2^2 $ 模P

然後通過重新排列(或通過逆矩陣)我們有

$ s = (y_2 - y_1)(x_2 - x_1) ^{-1} - a_1(x_2+x_1) $ 模P

我們得到了 S 被揭示的情況 $ (x_2+x_1) $ 模 P = 0。

對於 t>=3, t-1 份額,我們如何使用相似(或不同)的論點來證明當 s 是常數或最後一個係數時我們不會有類似的情況?

這是處理這個問題的一種方法:如果我們有一個 $ (n, t) $ Shamir 秘密共享系統,我們有 $ t-1 $ 分享 $ (x_0, y_0), (x_1, y_1), …, (x_{t-2}, y_{t-2}) $ ,那麼我們可以推斷出秘密多項式的形式為:

$$ P(x) + c \prod_{i=0}^{t-2}(x - x_i) $$

在哪裡 $ P(x) $ 是一個可計算的多項式(該多項式的確切含義取決於已知份額),並且 $ c $ 是一個未知常數(我們沒有關於它的資訊)。

所以,問題是:假設多項式是這種形式(對於某些 $ c $ ),我們想要的秘密是 $ j $ 係數,我們可以推導出我們感興趣的秘密係數嗎?

我們知道 $ j $ 係數為 $ P(x) $ , 所以這就歸結為我們是否知道 $ j $ 係數 $ c \prod_{i=0}^{t-2}(x - x_i) $ ; 我們可以當且僅當 $ j $ 多項式的第 th 係數 $ \prod_{i=0}^{t-2}(x - x_i) $ 是0。如果是0,那麼(無論如何 $ c $ 是個 $ j $ 整個多項式的第 th 係數將是 $ j $ 係數 $ P(x) $ (我們知道);如果它是非零的,那麼(取決於什麼 $ c $ 是)它可以是任何值。

對於線性項 ( $ j=0 $ ),這個係數是 $ \prod_{i=0}^{t-2}-x_i $ ,其中(因為我們在一個欄位中)當且僅當所有 $ x_i $ 值是非零的(它們在 Shamir 的方案中)。

對於最高期限( $ j=t-2 $ ),這個係數結果是 1,因此秘密永遠不會洩露(即使共享 $ x_i=0 $ 發出)。

對於第二個學期( $ j=1 $ ),這個係數原來是 $ -\sum_{i=0}^{t-2}x_i $ ,也就是說,如果秘密被洩露 $ x_0 + x_1 + … + x_{t-2} = 0 $ ,其中(對於這種情況 $ t=3 $ ) 是你想出的。進一步注意,如果我們處於偶數特徵場( $ 1+1=0 $ ), 然後 $ x_0 + x_1 \ne 0 $ (除非 $ x_0 = x_1 $ ,這不可能發生),因此在這種特定情況下,秘密不會被洩露。

自從我寫了原始答案以來,我發現了另一個安全的角落案例;如果欄位順序是 $ p^z $ (也就是說,該欄位有那麼多元素),如果 $ t = p^z-1 $ , 和份額 $ x_i = 0 $ 未發布,則所有係數都是安全的。那是因為,對於任何 $ k $ $ (k $ 作為未透露的份額),我們有 $ \prod_{i \in GF(p^z), i \ne 0, k}(x - x_i) = (x^{t} - 1) / (x - k) $ ,並且沒有任何 0 係數。當然,這確實是一個極端情況,因為只有 $ t $ 可能的股份,我們需要所有 $ t $ ,因此這是一個 $ (t, t) $ 秘密共享方案(如果是這樣,我們為什麼還要打擾 Shamir;有更簡單的方法)。

除了這些情況,我有理由推測(儘管我沒有證據)對於任何中間係數,可以找到一個集合 $ x_0, x_1, …, x_{t-2} $ 這確實洩露了秘密,假設對手可以選擇他獲得的份額(這類似於 CPA 假設)。

引用自:https://crypto.stackexchange.com/questions/76471