分享而不把秘密交給每個人
秘密只有一份可能遺失;每人都有副本,任何一人便能洩露。門檻方案處理另一個問題:分發份額,使足夠大的群組能重建秘密,而較小群組不能從份額獲得秘密的資訊。
定義 8.1.1
(多項式門檻方案)
令 為質數,並取整數 。在域 中運算;公開的參與者標識為 ,它們在該域中互異且非零。秘密 可以有任何分佈。與 獨立地,從 均勻且獨立地選取係數 。定義
參與者 收到份額 。
多項式次數至多為 :最高次係數可以為零。所有運算都模 。
常見錯誤
(標識是域元素,不是整數)
條件 正是保證標識 模 互異且非零的原因。在 中,標識 與 是同一個域元素,所以這兩個份額只是一個插值點;標識 則是被禁止的點 ,其份額就是 。
任意 份的重建
定理 8.1.2
(門檻重建)
任意 個不同參與者的份額唯一決定 ,因而決定 。
證明
(以根數得唯一性,以 Lagrange 插值得存在性)
若兩個次數至多為 的多項式在 個互異域元素處相同,它們的差有 個根,次數卻至多為 ,故差必為零。存在性由 Lagrange 插值給出:對 的 ,其中 互異,
每個分母都非零,因而在域中可逆。代入 便得秘密。多於 個誠實份額必含這樣的子集。
例題 8.1.3
( 上四人中的三人方案)
取 、、,並僅為示範取 、、。則 給出份額 。由前三份,在零處的 Lagrange 權重為 、 和 ,因此
這些具體係數只用來核對計算;實際分發者必須每次重新均勻抽取,而不能預先固定。
例題 8.1.4
(另一組三份與另一組權重)
由標識 的份額,在零處的權重為 、 和 ;三者之和為 ,正如能重現常數多項式的權重所必須的。於是
與唯一性的要求一致,得到同一個秘密。
常見錯誤
(Lagrange 權重屬於特定的子集)
權重取決於所用的標識。把子集 的權重 套用到標識 的份額,得 ,而不是秘密 。每換一組份額,都要重新計算權重。
為何較少份額不洩露資訊
定理 8.1.5
(完全保密)
對任意固定的 個參與者標識及任意 ,以下固定秘密的試驗給出 上均勻的份額值向量:令 ,並如上抽取係數。因此對 的任何先驗分佈,該向量都與 獨立。
證明
(每個觀察值對應同樣多的係數向量)
時結論顯然。對 ,固定候選秘密 及係數 的任意值。 個互異非零標識 處的方程唯一決定 。其係數矩陣 的行列式為
它非零。因此每個指定的份額向量恰好對應 個係數向量中的 個,在秘密固定為 的試驗中概率為 。這些相同的固定秘密分佈給出任何先驗下的獨立性。對概率為正的觀察份額事件,由 Bayes 法則, 的先驗分佈保持不變;它不會使非均勻先驗變成均勻。
證明透視
可能性不等於概率
只說每個候選秘密都與觀察到的份額相容並不足夠。關鍵一步是固定觀察者看不到的 個係數,再解出其餘 個:這把概率問題變成數等可能的係數向量,而對每個觀察值和每個候選秘密,數目都是同一個 。係數均勻且獨立這一假設正是在這裏使用,把計數轉成概率。標識互異且非零用於行列式非零:零標識給出零行,而它的份額就是秘密本身。由於份額分佈是在 固定時計算的,論證無需對 的先驗作任何假設便告完成。
例題 8.1.6
(兩份份額同樣地符合每個秘密)
對例子中的兩份 ,每個候選 恰與一個多項式 相容。由方程 與 得 ,從而 ,故模七下 、。例如 給出 ,而 給出原多項式。對每個固定的候選秘密,相應係數對被抽中的概率都是 ;觀察者的後驗仍取決於其先驗。
反例模式
不能重用隨機性
若兩個秘密使用相同的非常數係數,同一參與者把兩個份額值相減,便得到兩個秘密之差。在 上取 ,並對秘密 與 重用 :參與者 持有 和 ,而 。雖然每次分享只見 份,卻已洩露了差。單次分享的保證本身並不蘊含多次分享之間的保密性;重新獨立抽取係數可避免這種重用洩露。份額還需要安全的分發與儲存;這個構造本身不認證份額,也不能阻止惡意參與者提交假份額。
習題
快速檢查
(在 上,取 、、 及 。求各份額,並由前兩份重建秘密。)
解答 · 答案
份額為 。直線滿足 (模十一)。
快速檢查
(設 、,固定秘密 ,並如上抽取係數。兩個固定參與者標識處出現任一指定份額值對的概率是多少?)
解答 · 答案
由計數證明,對每個秘密都是 。
快速檢查
(為何禁止標識 ?為何標識必須互異?)
解答 · 答案
標識 的份額直接等於 。重複的標識不能提供互異插值點,也違反行列式論證。
快速檢查
(看到少於 份份額,會否令對 嚴重偏斜的先驗變得均勻?試解釋。)
解答 · 答案
不會。份額向量與 獨立,所以只要觀察事件的概率為正,後驗就等於先驗。
延伸閱讀
Adi Shamir, “How to Share a Secret” (1979) 提出多項式門檻構造。