如何分享秘密:可驗證金鑰分享

買賣虛擬貨幣

在前面的一篇文章《保護委託人隱私的社交金鑰恢復》中,介紹了一種基於智慧合約的金鑰恢復策略以及PoC實現。這是一種鏈上(Onchain)的方案,巧妙的解決了金鑰丟失的問題,對提高區塊鏈的安全性和可用性有著重要的意義。

實際上,關於如何提供冗餘的抗風險金鑰管理方案,在密碼學中有相當長的研究歷史,最早可以追溯到1979年Shamir(RSA發明人之一)的著名論文《如何分享秘密》,而其中使用的技術更可以追溯到18世紀的多項式插值(polynomial interpolation)。在Shamir之後,金鑰分享的研究有個長足的發展,現在是包括雲端密碼管理、加密貨幣託管錢包等應用的核心元件之一。本文以“如何分享秘密”主題的系列第一篇,文中涉及的工程實踐程式碼放在bitrocks/verifiable-secret-sharing中,歡迎star。

Shamir金鑰分享基本原理

Shamir金鑰分享(Shamir's Secret Sharing,SSS)要解決的問題,可以用一個例子來講述:

自從阿里巴巴和四十大盜的故事流傳出來後,後世的強盜們考慮加強藏寶洞的安保措施,他們找到了一家安保公司,提出這樣一個要求:n個強盜每人都有一把鑰匙,任意k個強盜聚在一起都可以開啟藏寶洞的鎖,k-1或更少的鑰匙都無法開啟。

這個要求其實很巧妙,n個人最壞情況即使丟失了n-k把鑰匙,依舊能夠開啟鎖;而少於k個人聚在一起或者金鑰被竊取,也不會造成財產損失。它既能提供冗餘性,也能防共謀。

Shamir給出的著名方案是這樣的:

形如

的k-1次多項式函式,將要分享的秘密(secret)編碼為常數項a0。

分割金鑰(split):隨機生成a1到ak-1的係數值。在這條k-1次曲線上,任意取n個不同的點{(x1,y1),(x2,y2),...,(xn,yn)},將這些點分配給參與者,每個人拿到的都是一個金鑰分片(secret share)。

恢復金鑰(recover):k個人把金鑰分片聚合在一起,即k個點代入原函式,確定一條唯一的曲線,即確定的{a0, a1, a2..}的值,其中的a0即是隱藏起來的秘密。而過任意k-1個點,在實數域理論上有無數條曲線,不會洩漏出關於a0的任何有用資訊。

格朗日插值

由曲線上的點求原曲線的過程被叫做多項式插值,它有不同的方法,比如用高斯消去法解範德蒙矩陣,複雜度為O(k^3)。不過由於我們實際上只需要求出a0即可,而不是全部的係數,一種更快捷的方案是拉格朗日插值法,它能夠直接根據給出的點座標寫出多項式的函式。

它的構造思路非常巧妙,值得寫一篇數學小品,但不是本文的重點,感興趣的同學可以閱讀這份斯坦福大學的講義。

工程實踐及注意事項

在實際實現中,需要注意:多項式定義在有限域而不是實數域上或自然數域。為什麼這麼選擇呢?這個小問題留給讀者去思考。

以src/simple_sss.rs的實現為例,選擇在素數域上。這樣就涉及到有限域上的算術操作,如求乘法逆元。

SSS的缺點

如果在生產環境中去部署一套金鑰分享服務時,我們發現,SSS方案存在諸多風險。我們將該服務中的角色分為dealer和眾多的player,dealer負責金鑰的分割和聚集恢復,而player作為金鑰分片的持有人。

上圖是一個閾值結構為2/3的Shamir金鑰分享過程,任意兩把金鑰分片可以恢復出原金鑰。可能存在以下風險:

1. Dealer作惡,傳送給三個Player的金鑰分片並不能恢復出一致的金鑰,如給Player1和Player2的分片是正常的,而Palyer3的分片是錯誤的;
2. Player作惡,在恢復階段傳送的分片是錯誤的,這樣恢復的金鑰也是錯誤的;

這意味著使用平凡的Shamir金鑰分享是不安全的。

Feldman的可驗證金鑰分享

可驗證金鑰分享(Verifiable Secret Sharing,VSS)要解決的就是上面的問題,最早由Chor, Goldwasser, Micali, Awerbuch提出,並給出一個基於大數分解難題的常數輪互動方案。

本文介紹的是現在較廣泛應用的Feldman的方案,也是第一個非互動的可驗證金鑰分享。

基礎原理及構造

FeldmanVSS方案基於離散對數問題,在SSS基礎上增加了校驗的過程。

1. 分割金鑰及生成承諾:分割金鑰的過程和SSS類似,同時生成多項式係數的承諾,c(i) = g^a(i),g為迴圈群的生成元(generator),原理和橢圓曲線上由私鑰匯出公鑰類似,commits = {c1,c2,..,ck}公開廣播出去。將share(i) = (xi,yi)分別傳送給Player。
2. 驗證分片:收到分片和承諾後,每個Player可執行下面的計算:

正常情況下,Palyer在不知道多項式係數的情形下可以驗證該等式左右兩邊成立,滿足加法同態;如果Dealer作惡,則收到錯誤分片的Player本地將無法透過這個測試,這由離散對數問題的困難性質保證。

3. 恢復金鑰及驗證正確性:恢復金鑰的過程和SSS類似,Dealer計算出a0後還需要驗證 c0 = g^a0是否成立,避免Player傳送錯誤的分片導致恢復出錯誤的金鑰。

採用FeldmanVSS後的2/3金鑰分享流程如下圖所示。

工程實踐及注意事項

在工程實踐中,可選擇基於橢圓曲線的有限域,計算承諾。以src/feldman_vss.rs實現為例,採用了Secp256k1。需要注意,多項式的係數和取的x值都要轉換成Scalar計算。

應用

FeldmanVSS是SSS的一個非常不錯的改進,在實際生產中有著廣泛的應用:

· 可以直接用於雲服務和區塊鏈託管錢包的金鑰管理;
· 用於模擬一個同步廣播網路,Dealer只有在k個Players的資訊全部收集到的時候才可以揭露出隱藏的秘密,用在諸如秘密競標、選舉等場景;
· 可以用於構造快速的拜占庭容錯協議,或者其他容錯的協議;

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;