用一個簡單的例子理解 Feldman 的 VSS
我正在嘗試了解Feldman 的 VSS 方案。該方案的基本思想是，一個人使用 Shamir 秘密共享來共享一個秘密和多項式係數的承諾，以允許另一方驗證他們收到的共享是有效的。我在維基百科頁面之後的程式碼中實現了它，但我的驗證功能不起作用。下面是一個簡單的失敗範例：
我們將在該領域工作 $ \mathbb{Z}_{11} $ 帶發電機 $ g=3 $ . 讓 $ f(x)=5+3x+8x^2 $ 成為我們的 Shamir 多項式。因此 $ f(1)=5 $ . 所以讓 $ s_1=5 $ 成為那一方的份額 $ p_1 $ 得到。
經銷商還必須承諾係數。所以承諾是 $ 3^5=1, 3^3=5, 3^8=5 $ . （這些計算為 $ g^c $ 對於每個係數 $ c $ 多項式）。
為了驗證 $ s_1 $ 是正確的，我們計算 $ g^{s_1}=3^5=1 $ 並將其與 $ 155=3 $ （指數都是 $ 1 $ 自從 $ i=1 $ , 否則這一步完成為 $ k^{i^j} $ 在哪裡 $ k $ 是承諾， $ j $ 是承諾的指數）。自從 $ 1\neq3 $ ，驗證失敗。但為什麼？假設我做對了，它應該會通過。
更新
所以更詳細地計算數學：
$ g^{s_1}=1 $ 和 $ g^5 g^{3^{1^1}} g^{8^{1^2}}= g^{5+3^{1^1}+8^{1^2}}= g^{5+3\cdot 1^1 + 8\cdot 1^2} = g^{16} = g^6 = 3 $ 和 $ 1\neq 3 $ .
請注意，指數是 $ f(1) $ . 維基百科提供了一個小提示：
（通常，需要一個子組 $ \mathbb{Z}_q^* $ ， 在哪裡 $ q $ 是一個素數，使得 $ q $ 劃分 $ p-1 $ .
我的問題是我沒有在這樣的小組中工作嗎？如果是這樣，為什麼它通常不適用於 $ \mathbb{Z}_p $ （維基百科只說通常在這個子組中工作）？有沒有建立這樣一個子組的標準方法？
它與您使用的模數有關。你做了所有的算術模 11。但是，當使用 Feldman 的 VSS 時，你必須使用兩個不同的模數（在適當的位置使用每個模數）。在你的例子中，你不應該做所有的算術模11。相反，你應該做一些算術模11和一些算術模5（的順序 $ g $ 在這種情況下）。如果你這樣做，一切都會好起來的。
一般來說，你需要選擇素數 $ p,q $ 這樣 $ q | p-1 $ . 然後，一些算術是模 $ p $ , 並且一些算術是模完成的 $ q $ . 尤其：
- 多項式 $ f(x) $ 被模數處理 $ q $ ，所以當你計算份額時，你需要做算術模 $ q $ .
- 承諾和所有帶有承諾的計算都被模處理 $ p $ ，所以當你驗證你得到正確的份額時，你工作模數 $ p $ .
我們這樣做的原因是在進行類似的計算時 $ 3^{15} $ （模組 $ 11 $ )，我們可以減少模 11 的基數，但我們必須減少模 10 的指數。粗略地說，承諾在基數中，而多項式的值（份額；多項式的係數）在指數中 - - 所以你必須為這兩種不同的值使用不同的模數。
我們可以修改您的範例以考慮到這一點。我們可以採取 $ p=11 $ , $ q=5 $ , 和生成器 $ g=3 $ 階子群的 $ q $ 的 $ (\mathbb{Z}/p\mathbb{Z})^* $ . 但是，您不能再擁有多項式 $ f(x)=5+3x+8x^2 $ : 多項式被模解釋 $ q $ ，所以所有係數都必須在範圍內 $ 0..4 $ . 這意味著我們需要稍微改變一下。
所以，這是一個更正的例子。你可以使用多項式 $ f(x)=0+3x+3x^2 $ . 自從 $ f(1)=1 $ , 你會得到份額 $ s_1=1 $ . 承諾是 $ 3^0=1 $ , $ 3^3=5 $ ， 和 $ 3^3=5 $ .
為了驗證共享的正確性，我們首先計算 $ 3^{s_1}=3^1=3 $ . 接下來，我們計算校驗值 $ 1 \times 5^1 \times 5^{1^2} = 3 $ . 你可以看到 $ 3^{s_1} $ 等於校驗值，所以一切都驗證了，共享是正確的。