從《鹿鼎記》說起，看如何分攤秘密

知識 06-12

分攤秘密的方法有許多值得注意的性質，各種性質都和它的實用性有關。尋找符合某些要求的分攤秘密的方法，是這方面的重要課題。

文 / 安安以遷遷

了解前文

點擊閱讀

Shamir分攤法的特點

我們可以列舉一些Shamir分攤法的特點，作為比較，我們稱第七節中的分攤法為「准入集分攤法」。

Shamir分攤法具有和准入集分攤法同樣的安全性。我們從理論上證明了這樣的分攤方法不可能在不具備揭開秘密的條件時泄露關於秘密的任何信息。這樣的安全性被稱為完善保密性。

然後當然是它的高效性。我們已經看到，它克服了第八節中提到的組合爆炸問題。無論n和k是什麼，每位分攤者都只需分攤和秘密可能範圍一樣大小的部分。這是准入集分攤法所沒有的。

接下去的一些特點則相當有趣。

最初分攤秘密時必須有個組織人員，他知道整個秘密（如《鹿鼎記》中的攝政王多爾袞），並由他來產生Shamir分攤法中的那個多項式P(x)。這個人有超然的地位，不屬於我們講的分攤秘密的參與者。如果他決定要增加一個參與分攤秘密的人員，也就是原來打算在n人中分攤秘密，現在打算在n+1人中分攤秘密，而保持「其中k人或以上同意則可揭開秘密」中的k不變。那麼使用准入集分攤法的話，就會增加不少准入集，需為這些准入集準備獨立的秘密分拆，並將這些分拆分別交給准入集中的每個人保管。這樣，原來的n個人中的每個人都會收到新的需要掌握的秘密。

而使用Shamir分攤法的話，事情就簡單多了。那個組織人員只需用原有的P(x)來對一個GF(N)中從未使用過的新值（同餘類）[m]來計算P([m])，並把[m]和P([m])交給新人保管即可，原先參與分攤的人員沒有任何新秘密需要接收。

同樣地，如果組織人員需要在原參與分攤秘密的人員中去掉一個人，用Shamir分攤法的話，只需這個人放棄原來他分攤的秘密即可，其他人持有的秘密則無需變動。相反，在准入集分攤法下，則需要所有人都放棄和包含此人的准入集有關的秘密。這是Shamir分攤法的靈活性。

上面所說的「放棄原來分攤的秘密」，往往是可能做到的。比如第八節中計算的藏寶圖大小約為412MB，只能儲存在如快閃記憶體盤之類的介質中，而不能記在人腦中。當此人要放棄原來分攤的秘密時，只需毀去儲存介質中的文件即可。但是一個很自然的問題就是，如果做不到這點怎麼辦？快閃記憶體盤中的信息是可以被拷貝的，如何保證此人沒有暗地裡另拷一份？所以如果沒有辦法保證原來被分攤的這部分秘密能夠真正被放棄，這種利用Shamir分攤法的靈活性來「去掉一個人」的辦法還是不用為好。

那麼如何正確地「去掉一個人」呢？或者更一般地，如果有類似韋小寶的局外人得到了一份或多份秘密（當然份數還沒達到揭開秘密的程度），該怎麼辦？一個直接的方法當然是讓那個知道整個秘密的組織人員再重新獨立地生成需要分攤的秘密，並交給分攤秘密的諸人，這些人則銷毀原來掌握的秘密。可是如果那個知道整個秘密的組織人員不存在了呢？（比如攝政王多爾袞早死了。）按照上面的方法，也許可以選出一個大家信得過的人做那個知道整個秘密的組織人員，先把各人的秘密都寄給他，合起來揭示出原始秘密，再生成需要分攤的秘密。

可是這個方法的缺點是顯而易見的。現在會重新出現一個知道整個秘密的人，這往往是不可接受的。另外，這個過程中老的和新的被分攤的秘密需要被寄送，寄送過程也要冒泄密的可能。怎樣做才能避免這些問題？

我們重新回憶一下上一節中Shamir分攤法的做法：對n個人，用隨機數產生器產生出一個係數在GF(N)內的多項式P(x)，而P([0])就是那個需要被分攤的秘密。接著對n個GF(N)中的點（為簡單起見設它們是[1]，[2]，……，[n]）計算出相應的P的值，並把這n個點和與每點相對應的P的值分別分攤給這n人。

現在選一個人（這個人可以選誰下面再討論），把同餘類[0]當作秘密，用Shamir分攤法來產生一個多項式Q(x)（於是Q([0])=[0]），並對參與分攤的每個人計算他對應的那個GF(N)中的點[t]的Q([t])的值，然後將這個值分別寄送給相應的參與分攤人員。每個參與分攤人員收到寄來的值後，將它和原來掌握的那個值相加，作為新的秘密保存，並銷毀原來的秘密。現在每個人手中的掌握的秘密（假設此人對應的GF(N)中的值是[t]）是P([t])+Q([t])，也就是多項式P (x)=P(x)+Q(x)在[t]點的值P ([t])。當有足夠多的人同意恢復原始秘密時，他們就可以使用拉格朗日插值法來恢復出P (x)來。雖然他們再也不能知道原來的P(x)是什麼，但這並不重要，重要的是原始秘密P([0])。可是P ([0])=P([0])+Q([0])=P([0])+[0]=P([0])，用P (x)也同樣可以知道原始秘密。這個方法使得最終效果看上去好像原來選取的的多項式其實是P (x)。

這就把前面提到的「先恢復原始秘密再重新生成多項式」方法的缺點完全克服了。用具體的例子可以更清楚地說明，仍以10人分攤秘密需至少8人同意才能揭曉秘密為例子。

首先用隨機數產生器產生出一個係數在GF(N)內的多項式P(x)，P([0])為需要被分攤的秘密。10個人分別拿到P([1])，P([2])，……，P([10])。現在懷疑有某些人掌握的秘密已被外人所知。於是選一個人，用隨機數產生器產生出一個係數在GF(N)內的多項式Q(x)，並且有Q([0])=[0]。計算出Q([1])，Q([2])，……，Q([10])，分別寄送給相關各人。各人分別計算P([1])+Q([1])=P ([1])，P([2])+Q([2])=P ([2])，……，P([10])+Q(10)=P ([10])並保存，銷毀原來各P值和新得到的各Q值。

如果原先有惡意的外人已經掌握了比如P([1])，P([2])和P([3])，在上面的寄送過程中又截獲了Q([3])，Q([4])和Q([5])，那麼他只能計算出P ([3])=P([3])+Q([3])，而P([1])，P([2])，Q([4])及Q([5])都毫無用處：和P([1])，P([2])（及P([3])）一起配套使用的其他P值已經不存在，要和它們配套計算P ([1])和P ([2])的Q([1])和Q([2])也不存在了；而沒有P([4])和P([5])，則Q([4])及Q([5])顯然也毫無用處。於是這個過程就讓外人原來掌握的3個值作廢了2個，剩下的1個也是因為另化代價截獲了新的對應信息才繼續保持有效。在最極端的情況下，就算所有寄送的Q值都被截獲了，那麼此外人原先掌握3個值，現在也還是掌握3個值。但外人要截獲信息，顯然要付出不菲的代價。而分攤秘密諸人付出的代價，則只是產生和寄收諸Q值而已。

既然這個方法能如此低價而有效地堵住已經泄密的漏洞，於是有條件的話，即使沒有泄密的跡象，也可以時不時地實施一下，誰知道是不是真的沒有某處泄密了呢？這就是主動防禦。

選取產生Q(x)的那個人，可以是分攤秘密眾人中的一個，也可以是某個大家都信得過但不參與分攤秘密的人。另外既然此法代價不大，也可同時讓幾個人產生獨立的幾個Q(x)，相當於一下子實行好幾次主動防禦。

值得一提的是准入集分攤法也能採取類似的主動防禦行動，即產生對[0]的分攤秘密並寄送給各人，各人收到後和原先掌握的秘密相加。但考慮到每次寄送的信息的規模都和單獨一次分攤秘密所需寄送的信息的規模一樣，會有組合爆炸問題的准入集分攤法在主動防禦方面也是低效的。

當然，Shamir分攤法和准入集分攤法相比也並不是沒有缺點。准入集分攤法中揭開秘密的組合條件是相當靈活的，而Shamir分攤法則局限於「n人分攤秘密需至少k人同意」這樣的形式。在某些情況下，用Shamir分攤法也可以處理一些其他的組合條件。比如A，B，C，D四人分攤秘密，允許揭開秘密的情況是A與其他任何一人同意，或是BCD三人同意。那麼我們可以用「5人分攤秘密需至少3人同意」的Shamir分攤法產生5份分攤秘密，並由A持有2份，其他3人分別持有1份的方法來完成這個分攤。但更一般的組合則無法用Shamir分攤法來模擬。

結語

在上節中我們看到，分攤秘密的方法有許多值得注意的性質，各種性質都和它的實用性有關。尋找符合某些要求的分攤秘密的方法，是這方面的重要課題。

比如說，在本文討論中，我們都假設參與分攤秘密的各方有可能是好奇的，也就是暗中希望獲得其他人掌握分攤的秘密，但總是誠實的，即當需要揭示秘密的那一刻到來時，各方都會把他掌握的那份秘密原樣地拿出來以合成原秘密。但在實際中並不總是如此。一個心懷鬼胎的秘密分攤方，有可能偽造他掌握的那份秘密，從而在合成秘密時向其他方揭示出一個錯誤的秘密，而在暗地裡獨自合成出真實的秘密。這就牽涉到找到能夠驗證信息完整性的秘密分攤法。諸如此類的特別性質還有很多，但本篇小文，則就在這裡結束了。

參考資料

[1] Beimel Amos, Secret-sharing schemes: a survey. Proceedings of the Third International Conference on Coding and Cryptology, IWCC』11, pp. 11–46. Springer, Berlin, Heidelberg (2011).

[2] 金庸, 《鹿鼎記》, 明河社出版有限公司 (1981).

[3] Adi Shamir, How to share a secret, Communications of the ACM, 22(11):612–613 (1979).

安安以遷遷| 簡書作者

從《鹿鼎記》說起，看如何分攤秘密