CRY:密碼學原語如何應用？走近門限密碼算法

作者：李昊軒

來源：微眾銀行區塊鏈

隱私數據密文控制權只能由單一主體掌控？代表控制權的密鑰如何才能安全地交由多個互不信任的主體協同使用？如何在技術層面保障多方授權的公平公正性？任一參與協作的主體密鑰丟失，如何實現安全可靠的容災恢復？

在業務方案設計中，安全可控地讓多個隱私主體參與數據協作，是隱私保護技術創造新興商業價值的關鍵之一。在這一過程中，代表控制權的密鑰由哪一方來掌握，是影響參與者合作意愿的重要因素。

因為哪一方擁有了密鑰，相當于哪一方就獲得了控制權，未能掌控密鑰的另一方，則可能在合作關系中處于弱勢。這將成為實現公平對等多方協作關系的一個關鍵阻礙。

以多方決策為例，上市公司的一次董事會會議中，需要多數董事對決策項進行簽字才能生效。出于某些影響，會議無法面對面舉行，所有董事必須使用數字簽名來遠程完成這一個簽字過程。為了保證決議過程的機密性和公正性，每位董事不希望其他董事知曉自己的選擇，同時要讓股東團體對最后的決策結果，即聚合后的簽名，進行驗證。

這個過程中，存在三個隱私保護相關的主要功能點：

每位董事的簽名控制權須由自己控制，而不是由中心化的可信第三方來代理行使權力。

代表決策結果的聚合簽名只需多數董事同意，便可生成合法的聲明。

股東團體需要對聚合后的簽名進行驗證，但無需知道具體哪些董事對此進行了簽名。

《衛報》：部分密碼學家對市場使用“Crypto”的方式感到不滿:11月22日消息，據英國《衛報》報道，隨著Crypto在加密貨幣行業使用越來越廣泛，用戶在 Google 上搜索“crypto”會看到大量指向比特幣和以太坊等加密貨幣的熱門搜索結果，但根據韋伯斯特字典對“crypto”的定義，它指的是密碼學，而密碼學又被定義為“信息的計算機編碼和解碼”。“這種詞匯轉變給密碼學家帶來了沉重的負擔，”該報道稱，過去幾年許多密碼學家一直在社交媒體上重復“crypto is cryptography”的口號，但收效甚微。密碼學專家Matt Blaze表示，“我認為將加密貨幣稱為 'crypto' 是一個糟糕的選擇，這對密碼學和加密貨幣都會產生不良后果。”[2021/11/22 22:08:04]

以上功能點涉及在多方協作過程中，如何將原本單個的密鑰安全地打碎成多個密鑰分片，并讓每個主體獨立使用自己的密鑰分片，合作完成所需的密碼學協議過程。解決這一問題的關鍵，就在于門限密碼算法的巧妙構造。

門限密碼算法在多方協作的相關場景中應用十分廣泛，可以實現數據聯合授權、認證、密鑰安全恢復、密鑰安全交換等需求，在諸多分布式多方計算協議中均可見其身影。

本文主要從秘密分享、門限加密、門限簽名三大應用方向，分享門限密碼算法的奇妙之處。

1.秘密分享

1979年，AdiShamir和GeorgeBlakley各自獨立地提出秘密分享的概念，奠定了門限密碼學體系的基礎。

林煌博士：輕模式的隱私應用是密碼學技術在隱私保護實踐中很重要的一步:在今日的《金色深核》線上直播中，針對“假設我們要解決多公司之間數據需要保密且共同使用的問題，三個技術路線如何去做？去年Maskbook火了一下，各位如何看待這種“輕模式”的隱私應用？”Suterusu林煌博士表示關于多個公司之間進行保密數據的安全計算，這個需要結合零知識證明和安全多方計算才能解決。如果我們考慮一種簡單的情況，只有兩方進行安全計算，一方可以將自己的數據用門限同態加密方案的公鑰加密后傳輸給另一方，另一方依據加密自己的數據生成密文，然后在兩個密文上做預定的同態運算，最后雙方合作把完成同態操作的密文解密。零知識證明可用于保證這個過程的計算可靠性（computational integrity），比如如何保證生成的加密密文確實是按照正確加密步驟生成的密文且加秘方知道原始明文呢？我們可以使用零知識證明算法針對加密電路生成能夠驗證明文和密文之間符合加密電路邏輯的證明。輕模式的隱私應用毫無疑問是密碼學技術在隱私保護實踐中很重要的一步，但這個領域還有很多可以做的事情。[2020/3/11]

具體而言，秘密分享是指一種安全地在多個參與者之間分享秘密的方式，其滿足以下特性：

每個參與者都獨立持有一部分關于秘密S的分片，只有將足夠數目的分片組合起來，才能夠重新恢復出秘密S。

當獲得的分片數量不足時，無論采用何種組合策略，不會泄露關于秘密S的任何信息。

動態 | 1999年的密碼學難題被解開，證明被存儲在BTC和BCH區塊鏈上:據bitcoin.com報道，1999年4月，麻省理工學院（MIT）的密碼學家設想了一個預計需要35年才能解決的難題。上個月，自學成才的程序員Bernard Fabrot透露已經破解了該難題。Fabrot的證明過程已于4月20日被標記并儲存在BCH區塊鏈上，并已在此后5天被儲存在BTC區塊鏈上。此后Antpool礦池還在Coinbase的數據中為573138區塊添加了祝賀信息。[2019/5/18]

秘密分享在學術上的價值在于，提供了一種技術手段，將原本單一的密鑰，以密鑰分片的形式，安全地、平等地分配到多個參與者手中，除此之外，還實現了以下額外的安全特性：

容錯高可用：不會因為少量密鑰分片損壞和丟失，而導致密鑰不可用。

抗側信道攻擊：原本固定的密鑰，在密碼學算法工程實現的執行過程中，可能會泄露一部分密鑰的信息，但進行分片之后，成功實施此類攻擊的難度將指數上升。

對于業務應用而言，主要使用的特性是密鑰安全平等分配和容錯高可用，可以用來滿足價值貴重的物品或權利不能由單一主體掌控的業務需求，以此控制盜用、濫用等潛在風險。

例如，董事會的印章不能由單獨的成員持有，銀行保險箱的鑰匙不能由單獨的職員保管。在數字化的場景中，涉及多方隱私數據的業務合作，數據密鑰也不能由單一主體掌管。

聲音 | 楊慶峰：現代密碼學結合區塊鏈技術可基本消除技術層面的安全問題:據澎湃新聞消息，上海大學哲學系教授楊慶峰發文指出，如果說長三角一體化建設過程中數據共享會成為一個問題，數據共享會影響到未來長三角一體化公共服務的落實，那么這個問題就必須嚴肅對待。同時，其表示現代密碼學的方法已完全可以解決這一問題，再加上區塊鏈技術的未來運用的可能性極大，這基本上消除技術層面出現的安全問題。需要擔憂的是倫理方面的問題，諸如隱私保護、被遺忘權等方面的問題。[2019/3/14]

為了實現安全的秘密分享效果，最直接的秘密字符串分片方式并不能保障其安全性，攻擊者無需收集足夠的分片，便可以獲得秘密的部分信息，示例如下：

因此，我們需要引入更為精巧的分片構造方式。

最常見的構造方式利用了拉格朗日多項式插值算法。其核心思想為，t個點可以確定一個t-1階多項式對應的曲線。每一個秘密分片都相當于多項式曲線上的一個點：

只要收集不同點的數目達到t個，就可以通過拉格朗日多項式插值算法求解出多項式中代表秘密的系數值。

如果點的數目不足t個，對應的多項式有無限多個，對應的秘密可能是任意值，對秘密的機密性保護達到了信息論安全。

具體構造方式可以參考ShamirSecretSharing的(t,n)秘密分享方案，即，將秘密分為n份，任意t份都可以完整地恢復出拆分前的秘密。構造過程如下：

金色財經現場報道 Ripple首席密碼學家：Ripple一直非常關注現實世界的支付用例:金色財經現場報道，今日Coindesk 2018共識會議正式在紐約開幕。在有關互操作性競賽的圓桌討論時，Ripple首席密碼學家David Schwartz表示：“我們一直非常關注現實世界的支付用例，這就是為什么Ripple構建了Interledger，這是一個并不關心人們使用什么網絡的簡單協議。”[2018/5/15]

將秘密S作為多項式的第0階常量系數，其余t-1個系數隨機生成，由此構造出一個t-1階的多項式，對應的曲線為C。

在曲線C上隨機選n個不同的點，將其分發給n個參與者。

只要不小于t個參與者同意使用自己的點參與協同運算，便可恢復出曲線C對應的多項式，取其中第0階常量系數，便可獲得秘密S。

秘密分享在分布式密鑰生成、密鑰容災恢復、數字版權管理、數據安全傳輸等業務領域中都有廣泛應用。同時，秘密分享也是用于構造安全多方計算的重要技術之一。

基礎的秘密分享方案可以進一步擴展為可驗證秘密分享、多級多秘密分享、定期更新分片的主動秘密分享、可隨時變更參與者的動態秘密分享、基于身份的秘密分享等方案，滿足多方協作中多樣化的業務需求。

秘密分享是所有門限密碼算法的基礎，解決了算法設計中密鑰控制權安全分發的問題，用技術手段保障了隱私數據多方協作中，權利均衡、平等互信的效果。

2.門限加密

門限加密方案是門限密碼算法常見應用之一，常常體現為一類分布式加解密協議，可以實現如下功能：

任意用戶都可以使用公鑰對數據進行加密。

私鑰的所有權由多個指定的秘密持有者聯合控制，只有滿足數目的秘密持有者合作，將解密分片聚合，才能實現解密。

門限加密方案可以有效保護需要多方授權才能使用的隱私數據。回到之前董事會決策的示例，目前有一份敏感的業務數據需要給董事會成員匯報，由于數據的敏感性，需要確保有足夠數量的董事在場，數據才能被解密。

門限加密方案可以很好地滿足這一需求。傳輸業務數據前，使用門限加密的公鑰對其進行加密，產生的密文只有當數量不少于門限值的董事授權同意之后才能進行解密。

使用門限加密方案的一般流程如下：

初始化：n個參與者約定設置門限值t，并獲取自己的私鑰分片x，聯合計算數據加密公鑰PK并公開。

加密：數據貢獻者使用公鑰PK對數據明文m進行加密，生成密文E(m)。

生成解密分片：參與者分別使用自己的私鑰分片x對密文E(m)進行解密，生成解密分片D_x(m)。

聚合解密分片：參與者將解密分片聚合，只有獲得不小于t個不同的解密分片D_x(m)之后，才可以完成聚合解密，獲得數據明文m。

理論上，門限加密方案可以基于不同的計算困難性問題構造，例如，基于離散對數的ElGamal門限密碼學體系、基于Diffie-Hellman的門限密鑰交換協議、基于大素數分解的RSA門限密碼學體系、基于橢圓曲線離散對數問題的BLS門限密碼學體系等。

工程上，門限加密方案目前已經比較成熟，以經典論文《SimpleandEfficientThresholdCryptosystemfromtheGapDiffie-HellmanGroup》為基礎的開源參考實現為例，在個人計算機上，對單個數據塊進行單次分片聚合和解密的耗時都在微秒級，已經可以滿足大部分業務的商用性能要求。

應用上，除了之前描述的多方授權數據解密之外，門限加密方案在匿名電子投票、數據代理服務、數據外包計算等需要為多個數據貢獻者提供聯合數據使用授權特性的領域，均有廣泛應用前景。

3.門限簽名

門限簽名方案是門限密碼算法最常見的應用。同樣基于秘密分享的核心理念，門限簽名方案通過將私鑰拆分成多個秘密分片，實現了如下效果：

只有當不少于門限值的秘密分片持有者共同協作，才可以生成有效的簽名。

即便部分秘密分片丟失，只要剩余秘密分片不少于門限值，依舊可以生成有效的簽名。

聯合生成的簽名中，并沒有透露具體哪些持有者參與了簽名過程。

在業務應用中，門限簽名方案可以用來構造有效的多方聯合簽名流程。相比傳統數字簽名方案，整個簽名過程消除了由單一主體保管密鑰帶來的系統性單點故障風險，以及跨機構信任問題。

每位秘密分片的持有者對簽名私鑰擁有平等的控制權，門限簽名方案同時提供了私鑰容災恢復功能和外部驗證匿名性。

這類方案可以顯著提高用戶對數據認證的信任，并促進多方平等合作，對于目前使用數字簽名的所有應用場景都適用，可以看作是傳統數字簽名方案在分布式商業環境中的全面升級。

使用門限簽名方案的一般流程如下：

初始化：n個參與者約定設置門限值t，并獲取自己的私鑰分片x，聯合計算數據驗簽公鑰PK并公開。

生成簽名分片：參與者使用私鑰分片x對數據m生成簽名分片sig_x。

聚合并生成簽名：將簽名分片合并，只有不少于t個簽名分片才能生成完整簽名sig。

驗證簽名：驗證者使用公鑰PK，對關于數據m的簽名sig進行驗證。

與門限加密方案類似，門限簽名方案可以基于不同的計算困難性問題來構造實現，例如，可以構造基于SM2國密標準算法的門限簽名方案。

目前較為常見的開源實現，主要是基于BLS的簽名算法。該方案驗證效率尚可，但在簽名聚合環節，生成簽名的耗時會隨參與者數量的增加而顯著增加，可以達到毫秒級，比傳統的數字簽名方案慢幾個數量級。

除此之外，目前的門限簽名方案在初始化過程中，如果不依賴可信第三方，會面臨交互輪數過多、構造復雜等問題。以上工程問題對需要進行高頻簽名操作的應用來說，可能會帶來一定性能上的挑戰，但對于一般應用來講，應該不會成為性能瓶頸。

總體而言，門限密碼學方案提供了一系列高效、易用的隱私保護分布式數據協作技術。隨著其應用越來越廣泛，NIST于2019年提議對門限密碼學相關的密碼學原語進行標準化，分別從單一主體使用和多方協作使用兩個方向，對門類眾多的門限密碼學方案進行歸類和標準化嘗試。

在標準化完成之前，根據具體的業務需求，門限密碼學方案的基礎技術選型可以參考下圖：

正是：多方協作密鑰誰掌控，門限密碼分權眾做主！

門限密碼學方案通過對隱私保護方案中的密鑰進行分片，使得對于密鑰所代表的數據控制權進行按需分配成為了可能。對于源自多方的隱私數據，門限密碼學方案提供了安全、平等、高效的協同認證和計算工具，可以用來解決現代分布式商業環境中，所面臨的多方數據認證、可信數據交換等核心業務挑戰。

多方數據協作場景中，基于可信硬件的解決方案也是目前行業研究的熱點，其背后涉及哪些原理，欲知詳情，敬請關注下文分解。

本文鏈接：https://www.8btc.com/media/608236

轉載請注明文章出處

Tags：CRYPTCRYCRYPCRYPTOEncryption AICRYPL幣CryptoTankscryptozoic

KuCoin