為什麼沙米爾的秘密共享方案需要一個有限域？
我讀了 & 的問題“有限域算術的必要性和 Shamir 的秘密共享方案中的素數 p”，他問為什麼 Shamir 的秘密共享方案在素數的有限域中使用算術。
該問題的答案說明，對於 Shamir 的方案，素數域不是必需的，而是可以使用任何有限域。然而，他們並沒有真正解決問題的另一部分，即為什麼我們需要一個有限域？ 我們不能只使用普通的整數算術來代替嗎？
有人可以解釋（以最簡單的方式）Shamir 的秘密共享方案使用有限域算術的原因嗎？
在 Shamir 的重構方案中必須使用欄位的原因是重構中使用的計算需要將一個“數”除以另一個，而除法沒有定義 $ \mathbb Z $ ，整數集： $ \frac{m}{n} $ 不一定是 $ \mathbb Z $ . 那麼，為什麼不使用 $ \mathbb R $ ， 或者 $ \mathbb Q $ 哪些可以用整數對“實現”？答案再次是電腦使用與實數算術不同的浮點算術或整數算術，如果我們忽略上溢和下溢，則在 $ \mathbb Z_{2^m} $ 這不是一個領域，而是一個環。一個更微妙的問題是 Shamir 方案隱含地假設一個多項式 $ n $ 欄位中的係數不超過 $ n $ 根在域中，該屬性在環中不成立。例如，多項式 $ x^2 - 1 $ 有四個根 $ \pm 1, \pm 4 $ 在環中 $ \mathbb Z_{15} $ 而不是兩個 $ \pm 1 $ 它在諸如 $ \mathbb Z_{17} = \mathbb F_{17} $ .
作為在通用電腦上實現的整數運算可能發生的具體範例，請考慮 使用此公式進行秘密重建
$$ s_0 = (-1)^k (x_1x_2x_3\cdots x_k) \sum_{i=1}^k \frac{y_i}{x_i\cdot c_i} $$ 取自我的另一個答案。這裡， $ s_0 $ 是從股份中重構出來的秘密 $ (x_i,y_i) $ （那是， $ y_i = s(x_i) $ ） 和 $$ c_i = (x_i-x_1)(x_i-x_2)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_k). $$ 現在考慮以下情況 $ k $ 聚集在一起重建秘密的股東都碰巧擁有 $ x_i $ 一個奇數。然後， $ c_i $ 是一個偶數——事實上，它的倍數 $ 2^{k-1} $ - 所以 $ \frac{y_i}{x_i\cdot c_i} $ 不一定是整數。然而，總和 $ s_0 $ 將是一個整數。用電腦上的普通整數算術，小數部分 $ \frac{y_i}{x_i\cdot c_i} $ ，如果有的話，將在計算指示的整數除法時失去，因此 $ s_0 $ 將無法正確計算。這並不是說無法通過仔細程式來解決這個問題，但我們還必須處理計算可能導致溢出或下溢的可能性，這也需要解決。在任何情況下，都可能出現問題，因為通過拉格朗日插值重建的多項式不一定與最初用於構造秘密的多項式相同。敵人的例子，兩者 $ x^2-1 $ 和 $ (x-1)(x-4) = x^2-5x+4 $ 有根 $ 1 $ 和 $ 4 $ 在 $ Z_{15} $ . 由於我們不提前知道哪些份額可用於重建，因此我們無法確定我們是否會在拉格朗日插值過程中重建正確的多項式。因此，秘密恢復過程是否會像環中聲稱的那樣工作是一個懸而未決的問題。保證該過程將在一個領域中工作。
最簡單的答案可能是給出一個在整數上使用 Shamir 的秘密共享時資訊洩露的例子。假設我們建構了一個低度範例，定義 $ q $ 是一個線性多項式 $ q(0)=D $ 和 $ q(1)=a_1 $ . 通過插值，您會發現：
$$ q(x)=(a_1-D)x+D. $$ 假設您在 $ 2 $ ， IE $ q(2) $ . 你可以看到 $ q(2)=2a_1-D $ . 自從 $ a_1 $ 和 $ D $ 是整數，給定這個單一的份額，你學習奇偶性 $ D $ .