Shamir 的秘密共享計劃安全證明中的漏洞
我試圖理解 Shamir 的秘密共享方法的安全證明，因為我想稍微調整多項式的創建，並且我發現我可用的證明非常模糊或有漏洞。
一些命名法
給了一個秘密小號 $ S $ 在有限域中Fp $ \mathbb{F}_p $ 為一個(ķ,n) $ (k,n) $ 門檻值方案 Shamir 的秘密共享方法生成係數
一個1,…,一個ķ-1 $ a_1, \dots, a_{k-1} $ 隨機且均勻地Fp $ \mathbb{F}_p $ 生成多項式
q(X)=小號+一個1X1+⋯+一個ķ-1Xķ-1 $ q(x)=S + a_1x^1 + \dots + a_{k-1}x^{k-1} $ .n $ n $ 分享(X一世,是的一世) $ (x_i,y_i) $ 是通過選擇成對不同的X1,…,Xn $ x_1, \dots, x_n $ ， 每個Xj≠0 $ x_j\neq 0 $ （通常Xj: =j $ x_j:=j $ ) 和計算是的j: =q(Xj) $ y_j:=q(x_j) $ . 多項式q $ q $ 可以通過多項式插值恢復使用任何ķ $ k $ 共享和通過計算恢復的秘密q(0)=小號 $ q(0)=S $ .
現在來證明
**從Shamir 的原始論文**開始，它只是聲明（適應上述命名法）：“對於每個候選值小號’ $ S’ $ 在Fp $ \mathbb{F}_p $ 一個n○pp○nen噸
$$ an opponent $$可以構造一個且只有一個多項式q’(X) $ q’(x) $ 學位ķ-1 $ k-1 $ 這樣q’(0)=小號’ $ q’(0)=S’ $ 和q’(X一世)=是的一世 $ q’(x_i)=y_i $ 為了ķ-1 $ k-1 $ 給定的論點。通過施工，這些p $ p $ 可能的多項式是等可能的，因此對手絕對無法推斷出小號 $ S $ .” Shamir 沒有解釋為什麼這些多項式同樣可能，也沒有解釋為什麼沒有關於秘密的資訊小號 $ S $ 被揭示。 另一個經常陳述的解釋也有類似的情況：鑑於ķ-1 $ k-1 $ 分享(X1,是的1),…,(Xķ-1,是的ķ-1) $ (x_1,y_1), \dots, (x_{k-1},y_{k-1}) $ 您可以通過選擇最後一個共享來自由選擇恢復過程計算的秘密(Xķ,是的’ķ) $ (x_{k},y_{k}’) $ 適當地。看看恢復方程（它利用拉格朗日多項式插值）：小號=q(0)=∑ķj=1是的ķ∏ķ米=1,米≠jX米X米-Xj $ S=q(0)=\sum_{j=1}^{k}y_k\prod_{m=1, m\neq j}^{k}\frac{x_m}{x_m-x_j} $ . 通過重新排列方程，您可以計算份額是的ķ $ y_k $ 產生任何想要的小號’ $ S’ $ . （這個等式很混亂，並沒有真正提供更多的洞察力：是的’ķ: =小號’-∑ķj=1是的ķ∏ķ米=1,米≠jX米X米-Xj∏ķ-1米=1X米X米-Xķ $ y_k’:=\frac{S’-\sum_{j=1}^{k}y_k\prod_{m=1, m\neq j}^{k}\frac{x_m}{x_m-x_j}}{\prod_{m=1}^{k-1}\frac{x_m}{x_m-x_k}} $ )
我發現上述論點沒有說服力，因為它沒有直接論證第一個ķ-1 $ k-1 $ share 必然不能透露任何資訊，甚至不使用參數中多項式的構造方式。例如，假設我不選擇多項式q $ q $ 通過選擇係數一個1,…,一個ķ-1 $ a_1,\dots,a_{k-1} $ ，而是通過選擇是的1,…,是的ķ-1 $ y_1,\dots,y_{k-1} $ 並重建多項式q $ q $ 在……之外(0,小號),(X1,是的1),…,(Xķ-1,是的ķ-1) $ (0,S), (x_1,y_1), \dots, (x_{k-1},y_{k-1}) $ . 現在轉折：我選擇所有上述是的一世 $ y_i $ 隨機除外是的2 $ y_2 $ ，我惡意定義為是的2: =小號-是的1 $ y_2:=S-y_1 $ . 以上所有關於任何最後一個共享如何有權定義秘密值的陳述小號’ $ S’ $ 仍然成立，但通過計算，可以用前兩股輕鬆打破該計劃小號=是的2-是的1 $ S=y_2-y_1 $ .
選擇多項式的方式至關重要的另一個例子來自這個問題Coefficients in Shamir’s Secret Sharing Scheme，這表明使用常數係數來表示秘密是至關重要的。
Buchmann在 die Kryptographie 中的 Einführung通過使用計數參數走另一條路線：假設米<ķ $ m<k $ 秘密載體走到了一起。對於每一個可能的秘密小號’∈Fp $ S’\in \mathbb{F_p} $ 有pķ-米-1 $ p^{k-m-1} $ 多項式q’(X) $ q’(x) $ 學位ķ-1 $ k-1 $ 和q’(0)=小號 $ q’(0)=S $ 和q’(X一世)=是的一世 $ q’(x_i)=y_i $ 為了1≤一世≤米 $ 1\leq i \leq m $ . 與 Shamir 類似，它現在聲明沒有透露任何資訊，因為多項式的所有常數項都具有相同的可能性，但沒有進一步證明為什麼會出現這種情況。
如何最終證明 Shamir 的秘密共享的安全性？
有助於理解證明的核心見解是，描述多項式自由度的所有不同方式都是一一對應的。多項式ķ-1 $ k-1 $ 有ķ $ k $ 自由度可以描述為ķ $ k $ 多項式的係數，或（對於ķ $ k $ 給定X $ x $ -座標）由ķ $ k $ 它必須通過的高度。從係數到次數多項式的映射ķ-1 $ k-1 $ 並到是的 $ y $ -座標都是雙射的。（它們甚至是同構ķ $ k $ 維向量空間。）
讓我們將其形式化：目前我們將秘密作為一個特殊參數省略，並像對待任何其他係數一樣對待它，即一個0: =小號 $ a_0:=S $ . 我們修復ķ $ k $ （成對不同）X $ x $ -座標。不失一般性，它們應表示為X1,…,Xķ $ x_1,\dots,x_k $ . 我們定義函式F $ f $ 從係數映射一個0,…,一個ķ-1 $ a_0,\dots,a_{k-1} $ 多項式的q $ q $ 到ķ $ k $ 高度（是的 $ y $ -值）的多項式在X $ x $ -座標。係數都是Fp $ \mathbb{F}_p $ 所以域F $ f $ 是(Fp)ķ $ (\mathbb{F}_p)^{k} $ . 對所有的都是如此ķ $ k $ 高度 （是的 $ y $ -組件）的固定X $ x $ -座標，所以codomain也是(Fp)ķ $ (\mathbb{F}_p)^{k} $ . 計算單是的一世 $ y_i $ 就像將其插入多項式一樣簡單：
是的一世: =q(X一世)=一個0+一個1X1一世+⋯+一個ķ-1Xķ-1一世為了 1≤一世≤ķ $ y_i:=q(x_i)=a_0 + a_1 x_i^1 + \dots + a_{k-1}x_i^{k-1} \qquad \text{for } 1\leq i\leq k $
和F $ f $ 定義為
F：(Fp)ķ→(Fp)ķ $ f: (\mathbb{F}_p)^{k} \rightarrow (\mathbb{F}_p)^{k} $
(一個0,…,一個ķ-1)↦(是的1,…,是的ķ) $ (a_0,\dots,a_{k-1})\mapsto(y_1,\dots,y_{k}) $ .
顯示雙射性F $ f $ 顯示它的單射性就足夠了，因為域和共域具有相同的有限大小。高級別的觀點是ķ-1 $ k-1 $ 次數多項式由它的唯一描述ķ $ k $ -係數，並且它也可以唯一地描述為ķ $ k $ 它通過的點。因此，如果兩個係數列表描述了通過相同點的兩個多項式，則這兩個多項式必須相同，因此係數列表必須相同（因此F $ f $ 是單射的）。作為對該問題的更基本的看法，請列出兩個係數列表(一個0,…,一個n-1) $ (a_0,\dots,a_{n-1}) $ 和(b0,…,bn-1) $ (b_0,\dots,b_{n-1}) $ 映射到相同的高度(是的1,…,是的ķ) $ (y_1,\dots,y_{k}) $ . 將兩個多項式相減得到多項式r(X): =(一個0-b0)+(一個1-b1)X1+⋯+(一個ķ-1-bķ-1)Xķ-1 $ r(x):=(a_0-b_0) + (a_1-b_1) x^1 + \dots + (a_{k-1}-b_{k-1})x^{k-1} $ 所有的都為零ķ $ k $ 給定X $ x $ - 座標：r(X一世)=0 為了 1≤一世≤ķ $ r(x_i)=0 \text{ for } 1\leq i\leq k $ . 因此它必須是零多項式並且一個j-bj=0 $ a_j-b_j=0 $ 對所有人0≤j<ķ $ 0\leq j < k $ ，這意味著兩個係數列表是相同的。它遵循F $ f $ 是單射的，因此是雙射的。
（此外，F $ f $ 是線性的，因此是同構的。）
**從秘密共享的角度看：**您現在可以在一側固定自由度，並在另一側降低各自的自由度。具體來說，如果你修復ķ-1 $ k-1 $ 自由度，你還剩下 1 度。此外，您修復第一個的方式ķ-1 $ k-1 $ 自由度不能與剩餘的自由度相互作用。（對我來說，這更直覺，如果我將自由度理解為向量空間中的維度。如果我修復ķ-1 $ k-1 $ 高度向量空間中的維度 (是的 $ y $ - 座標到固定X $ x $ - 座標）我還剩下 1 個維度和這些選項ķ-1 $ k-1 $ 高度與我選擇的最後一個高度無關。）正如沙米爾所說，最後一個自由度（最後一個維度）仍然能夠完全確定秘密，反之亦然。現在，如果最後一個自由度，秘密小號 $ S $ , 會像所有其他人一樣隨機抽取, 更容易爭辯說, 的分佈的均勻性小號 $ S $ 最後延續到高度的均勻性X $ x $ -座標（的值是的 $ y $ -座標，即最後一個共享），反之亦然。作為小號 $ S $ 在實際應用中不是（統一）隨機的，我更喜歡另一種觀點來展示該方案的安全性：
**我首選的安全證明。**作為第一步，讓我們修復小號 $ S $ ，因為這也在實際應用中發生。我們來看一組固定但任意的ķ-1 $ k-1 $ 秘密持有者，這意味著我們修復ķ-1 $ k-1 $ X $ x $ -座標。不失一般性，我們用X1,…,Xķ-1 $ x_1, \dots, x_{k-1} $ . 我想展示的是高度（是的 $ y $ -座標）是獨立的值小號 $ S $ . 這意味著均勻分佈ķ-1 $ k-1 $ 隨機選擇的係數會延續到結果中是的 $ y $ -座標。如果係數和高度之間存在一對一的關係，則必須如此。為了顯示一對一的關係，讓我們修改上面的F $ f $ 進入以下函式G $ g $ , 其中常數係數一個0 $ a_0 $ 固定為小號 $ S $ ： 選擇是的一世 $ y_i $ 為了1≤一世≤ķ-1 $ 1\leq i\leq k-1 $ 如下（注意我們只有ķ-1 $ k-1 $ 現在的高度）：
是的一世: =q(X一世)=小號+一個1X1一世+⋯+一個ķ-1Xķ-1一世為了 1≤一世≤ķ-1 $ y_i:=q(x_i)=S + a_1 x_i^1 + \dots + a_{k-1}x_i^{k-1} \qquad \text{for } 1\leq i\leq k-1 $
和G $ g $ 定義為
G：(Fp)ķ-1→(Fp)ķ-1 $ g: (\mathbb{F}_p)^{k-1} \rightarrow (\mathbb{F}_p)^{k-1} $
(一個1,…,一個ķ-1)↦(是的1,…,是的ķ-1) $ (a_1,\dots,a_{k-1})\mapsto(y_1,\dots,y_{k-1}) $
有一個類似的論點，就像我們使用的那樣F $ f $ 我們可以證明G $ g $ 是單射的，因此是雙射的：假設我們有兩個映射到相同的係數列表ķ-1 $ k-1 $ 高度（是的 $ y $ - 固定座標X $ x $ -座標）。因此，兩個係數列表的相應多項式通過相同的ķ-1 $ k-1 $ 已經點了。此外，兩者都通過(0,小號) $ (0,S) $ 通過施工。因此，因為它們是度多項式ķ-1 $ k-1 $ 並分享ķ $ k $ 它們都經過的點，兩個多項式必須相同。因此G $ g $ 是單射的，因此是雙射的，因為域和共域具有相同的有限大小。
結果我們知道，ķ-1 $ k-1 $ 秘密股份不能透露任何關於小號 $ S $ 因為它們完全由係數的（均勻）隨機選擇決定一個1,…,一個ķ-1 $ a_1, \dots, a_{k-1} $ 並且因此可以將它們本身解釋為在可能的高度集合中均勻隨機地選擇。
對於任何有限（加法）群G $ G $ 和任何元素G∈G $ g\in G $ 數量G+一個 $ g+a $ 是均勻的，如果一個 $ a $ 接受每個值G $ G $ 等機率1/|G|. $ 1/|G|. $
*證明：*列表{一個+G}一個∈G $ {a+g}_{a \in G} $ 沒有重複，只是元素的排列G. $ G. $ 如果我們有一個+G=一個’+G $ a+g=a’+g $ 和一個≠一個’ $ a\neq a’ $ 我們可能會與身份元素的唯一性相矛盾，因為一個-一個’ $ a-a’ $ 將是另一個身份元素。最後，由於列表沒有重複，列表中每個元素的機率為1/|G|. $ 1/|G|. $
您答案中的所有論點都可以直接轉換為此上下文。拿G=GF(q) $ G=GF(q) $ 考慮多項式環GF(q) $ GF(q) $ 以及您或對手修復的任何變數/係數，在所有固定選擇的情況下，隔離尚未指定的變數並得出其均衡分佈。固定變數和係數的所有復雜性都可以吸收到這個固定任意值的選擇中G $ g $ .