門限秘密共享及其典型應用

摘 要： 秘密共享技術是密碼學的重要分支，目前已經有了大量的理論與應用研究成果。（k，n）門限秘密共享方案將秘密信息分成n份無意義的子秘密，只有擁有至少k份子秘密才能恢復秘密信息，可以有效提升其安全性。在介紹了基本的門限秘密共享方案的基礎上，對其在密碼學幾個重要分支如數字簽名、基于身份加密、基于屬性加密以及圖像加密中的典型應用進行了全面的歸納與總結，分析了當前存在的問題，并對未來的研究趨勢進行展望。

關鍵詞： 秘密共享方案； 數字簽名； 身份密碼學； 屬性加密； 圖像加密； 視覺密碼學

中圖分類號： TN918.4?34 文獻標識碼： A 文章編號： 1004?373X（2015）13?0071?05

Abstract： Since secret sharing technology is an important branch in cryptography， it has plenty of research results in theory and application currently. （k，n） threshold secret sharing scheme divides secret information into n meaningless sub?secrets. Threshold secret information owns at least k sub?secrets， secret information can be recovered and its security can be enhanced greatly. On the basis of introducing the basic threshold secret sharing schemes， the typical applications in several important branches of cryptography， such as digital signature， based on identity encryption， based on attribute encryption and image encryption are concluded and summarized completely. Current problems of these applications are analyzed， and future research trends are prospected.

Keywords： secret sharing scheme； digital signature； identity cryptography； attribute encryption； image encryption； visual cryptography

0 引 言

隨著計算機與網絡技術的迅速發展，信息安全已經成為日益嚴峻的問題。密碼技術可以用來實現安全的數據通信與存儲，是信息安全技術的基礎。由于所有密碼體制的安全性都依賴于密鑰的保密性，因此如何實現安全的密鑰管理成為信息安全領域頭等重要的大事。

秘密共享技術將一個秘密值分成若干份，由不同的實體進行分散保存以提高安全性，可以用來實現安全的密鑰管理。1979年，Shamir和Blakley分別用代數學和幾何學的方法給出了最早的門限秘密共享算法[1?2]。其基本實現思想如下：給定正整數k和n，其中k≤n，一個（k，n）門限秘密共享方案指的是將秘密信息D分成n份子秘密，其中的任意k份或更多的子秘密可以重構秘密信息D，而任意k-1份或更少的子秘密則無法得到D的任何信息，稱k為門限值。

利用門限秘密共享方案可以實現密鑰的分布式管理，即將密鑰SK分成n個不同的子密鑰，將其分發給不同的用戶，任意k個用戶將其所持有的k份子密鑰進行共享即可以恢復出密鑰SK。門限秘密共享實現密鑰管理的優勢在于：

（1） 有利于限制合法用戶的權利，即少于k個合法用戶無法得到SK；

（2） 有利于提高系統安全性，攻擊者即使得到了k-1份子秘密，仍然不能得到有關SK的任何信息；

（3） 有利于提高系統健壯性，攻擊者即使破壞了n-k份子秘密，余下的[k]份子秘密仍然能夠恢復出SK。

門限秘密共享自提出以來吸引了眾多的研究者，產生了大量的研究成果[3?4]，在密碼學的很多分支都有著廣泛的應用。本文在回顧基本門限秘密共享方案的基礎上，對其當前最主要的應用進行歸納和總結，并進一步展望其未來的發展方向。

1 門限秘密共享方案

1.1 Shamir的門限秘密共享方案

Shamir使用多項式插值實現了基本的（k，n）門限秘密共享方案，該方案具體由以下三個階段構成：

（1） Initial Phase，選擇有限域Fq，其中[q?n。]設參與者集合為P={P1，P2，…，Pn}，k為門限值，秘密信息[s∈Fq]。選擇[Fq]上的n個互不相同的非零元素x1，x2，…，xn，將這些元素公開。

（2） Sharing Phase，隨機選擇Fq上的k-1次多項式[g（x）=a0+a1x+…+ak-1xk-1，]其中a0=s，其余的ai隨機的選自Fq。分別計算[si=g（xi）， i=1，2，…，n，]將（xi，si）作為子秘密分發給成員Pi。

（3） Construction Phase，任意k個成員可以將其持有的子秘密進行共享，從而通過Lagrange插值公式恢復出秘密信息[s。]設這[k]個成員為[P={Pi1，Pi2，…，Pik}，]他們共享的子秘密為[{（xi1，si1），（xi2，si2），…，（xik，sik）}]，則Lagrange插值公式如下所示：

[g（x）=r=1ksirt=1t≠rkx-xitxir-xit]

顯然對于任意的[xij，]j=1，2，…，k，上式右端計算的結果恰好等于[sij，]由多項式理論可知，若兩個k-1次多項式在變量的k個不同取值處得到的函數值相等，則這兩個多項式必定相等，于是上式成立。由此可以計算出[s=a0=g（0）]。

1.2 Blakley的門限秘密共享方案

Blakley使用幾何學的方法給出了另一個（k，n）門限秘密共享的方案。其基本思想是將秘密值看成一個k維空間中的點，分發給不同參與者的子秘密是不同的k-1維子空間，當k個參與者將其子秘密進行共享時，可以得到這些子空間的惟一交點，從而得到秘密值。具體描述如下：

選擇有限域Fq，其中[q?n。]設參與者集合為P={P1，P2，…，Pn}，k為門限值，秘密信息[s∈Fkq]。選擇Fq上的k元線性方程組為：

[a11x1+a12x2+…a1kxk=b1a21x1+a22x2+…a2kxk=b2…an1x1+an2x2+…ankxk=bn]

分別記：

[A=a11 a12 … a1ka21 a22 … a2k? ? ?an1 an2 … ank，B=b1b2?bn，X=x1x2?xk]

則方程組可寫成[AX=B。]選擇矩陣[A]時需要滿足兩個條件：

（1） [A]的任意k行線性無關；

（2） 秘密值s是以上線性方程組的解。

每一個方程可以看作一個k-1維的子空間，為每一個參與者分發這樣的一個方程，當其中k個參與者共享其方程時可以得到一個滿秩的k元線性方程組，可以解出惟一的值，即秘密值s。而任意k-1個方程聯立則無法得到惟一解。

2 門限秘密共享在數字簽名中的應用

數字簽名用來實現消息的完整性保護和簽名者的不可否認服務，是信息安全重要的組成部分。當需要對消息m進行簽名時，簽名者用自己的私鑰SK對消息的Hash值進行簽名運算，驗證者驗證簽名時需要用簽名者的公鑰PK進行。一個（k，n）門限數字簽名算法指的是利用門限秘密共享的方法實現簽名運算。即將簽名私鑰SK作為秘密值分成n個子密鑰交由n個用戶保管，只有至少k個用戶的子密鑰共享后才可以進行簽名運算。門限數字簽名的算法框架如圖1所示。

門限數字簽名的重要應用場合是在公鑰基礎設施[5]（Public Key Infrastructure，PKI）中實現分布式的證書中心（Certificate Authority，CA）。PKI是以用戶公鑰數字證書為中心的一整套公鑰管理機制，可信的CA是其核心組件，主要實現對用戶公鑰數字證書的管理。公鑰數字證書將用戶的身份與其公鑰進行捆綁，由CA的私鑰進行簽名以保證其有效性。由于CA的獨特地位，往往成為PKI系統的安全瓶頸與性能瓶頸。因此利用門限秘密共享技術保護CA私鑰的分布式CA有著重要的理論與實際意義。

在分布式CA模型中，由n個指定的用戶（稱為服務者）秘密保存CA私鑰，將CA的私鑰看作秘密值分成n個子密鑰分別由這n個服務者保管。當某用戶需要證書服務時，服務者中的任意[k（≤n）]個相互合作即可以完成一份合法的證書簽名，而k-1或者更少的服務者即使相互共享了子密鑰也無法完成合法簽名。分布式CA如圖2所示。

一般來講直接采用門限秘密共享實現分布式CA是不安全的，因為k個服務者進行一次證書簽名就會計算CA的私鑰，他們以后就可以獨自進行證書簽名。為了彌補這一缺陷，分布式CA往往采用更實用的技術，即k個服務者進行證書簽署時不恢復CA私鑰，而是分別獨立用各自的子密鑰對證書進行部分簽名運算，用戶利用部分簽名值計算完整的證書簽名。這樣可以有效保護CA私鑰與服務者子密鑰不泄露，提高分布式CA的安全性。目前該領域主要的研究內容包括如何降低服務者節點的通信負擔，提高整個分布式CA系統的實現效率。

3 門限秘密共享在IBC中的應用

為了降低PKI體系中公鑰證書管理的巨大開銷，Shamir提出了基于身份的公鑰密碼體制[6]（Identity Based Cryptography，IBC）。在IBC體制中，用戶的公鑰PK是根據其公開身份信息如姓名、地址、郵箱等進行計算得到的，而用戶的私鑰SK則由可信的私鑰生成中心（Private Key Generator，PKG）根據系統的主密鑰以及用戶公鑰PK計算得出。要獲得一個用戶的公鑰，只需要知道其身份以及系統公開參數而無需驗證公鑰證書，從而避免了證書管理的開銷，大大減輕了密鑰管理的沉重負擔。美國國家標準技術研究所（National Institute of Standards and Technology，NIST）密鑰管理工作組在密鑰管理總結報告中明確指出了IBC在密鑰管理中的地位與優勢[7]。

盡管IBC體制有著明顯的優勢，但其仍存在缺陷，即用戶必須無條件相信PKG，這就導致PKG成為系統的安全瓶頸，也往往成為攻擊者首選的攻擊目標。一旦PKG被攻擊者攻陷，整個IBC體制就沒有安全性可言，因此PKG的私鑰安全是整個IBC體制中的核心。將秘密共享技術用于IBC可以實現分布式的PKG（Distributed PKG，DPKG），能夠有效提升系統安全。

DPKG的基本實現思想如下：將PKG的私鑰SK作為秘密值利用（k，n）門限秘密共享技術分給n個可靠的服務者，只有k個服務者合作才能行使PKG功能，利用用戶的身份公鑰信息為用戶生成合法的私鑰。任意少于k個的服務者無法恢復PKG私鑰，也無法計算出用戶私鑰，從而有效避免了傳統PKG的缺陷。

采用DPKG的IBC體制如圖3所示。

DPKG自從提出以來就得到了廣泛的研究，主要成果有：Zhang和Fang等人將IBC用于Ad Hoc網絡[8?9]。Ren提出的方案[10]通過DPKG在公開信道對用戶進行認證來消除對秘密信道的依賴，缺點是導致存儲與通信負擔過重。Chan基于可驗證秘密共享技術提出的DPKG方案[11]摒棄了單一實體，增強了PKG本身以及IBC系統的安全性。Da Silva等人提出了用于Ad Hoc網絡的完全自組織IBC密鑰管理方案[12]，解除了對PKG的依賴。

目前該領域的主要研究內容包括：

（1） 如何降低服務者節點的通信負擔，特別在Ad Hoc網絡中，節點通信與計算能力均較弱，這一問題尤為突出；

（2） 用戶的身份公鑰撤銷問題。IBC系統中的身份公鑰撤銷往往較難實現，在采用DPKG的IBC中更是如此。如何在不增加DPKG系統復雜性的前提下實現安全高效的身份公鑰撤銷是目前的研究熱點[13]。

4 門限秘密共享在ABE中的應用

基于屬性的加密方案（Attribute Based Encryption，ABE）可以看作基于身份加密方案的推廣，其中用戶的惟一身份被多個屬性所替代，用戶擁有與其屬性相對應的屬性私鑰集，其解密能力完全由用戶所擁有的屬性值而非其身份所確定。

最早的ABE是Sahai與Waters于2005年提出的門限式ABE[14]，在該方案中，用戶能夠解密密文當且僅當他所持有的屬性私鑰數達到預設的門限值。此后陸續出現的密鑰策略的ABE[15]（KP?ABE）和密文策略的ABE[16]（CP?ABE）是將門限秘密共享推廣到一般訪問結構的秘密共享而得到的ABE，具有更細致的訪問控制能力，應用場合也更廣。

典型的（k，n）門限式ABE的算法構成如下：

（1） Setup，初始化算法，由屬性中心（Attributes Authority，AA）生成系統的各項參數。包括全屬性集合[At=]{1，2，…，n}，系統的主私鑰集合MK，公開參數集合PK等。

（2） Key Generation，私鑰生成算法，由AA為一個屬性子集[ω?At]生成私鑰集合。這個屬性子集對應于一個合法用戶[U]所擁有的所有屬性，U提交私鑰申請和自己的ID號、屬性集合，該算法將生成的私鑰集合[{Dii∈ω}]分發給用戶U。

（3） Encryption，加密算法，由加密方運行，用戶V使用一個屬性集合[ω?At]對明文消息m進行加密，得到密文[c。]

（4） Decryption，解密算法，由解密方運行，用戶[U]能夠解密密文[c，]當且僅當他所擁有的屬性集合ω與加密屬性集合[ω]的交集包含至少k個屬性，即[ω?ω ≥k。]

算法流程如圖4所示。

目前ABE的主要研究內容與發展趨勢包括：使用更一般的秘密共享技術將門限式ABE推廣至一般訪問結構的ABE；可變門限式ABE技術，即用戶的解密屬性門限可以在每次加密時動態指定；用戶的屬性撤銷問題，與IBC類似，這也是一個研究熱點。

5 門限秘密共享在圖像加密中的應用

隨著多媒體處理技術的發展，數字圖像的地位日益重要。數字圖像蘊含的大量信息使其安全性成為當前信息安全研究中重點關注的對象。典型的數字圖像加密技術包括基于矩陣變換的圖像加密與基于混沌映射的圖像加密[17]，前者的缺陷是密鑰空間太小，難以抵抗窮舉攻擊；后者的缺陷是算法安全性依賴混沌映射的數學特征，難以實現完善保密性。將秘密共享技術引入圖像加密領域可以得到一大類安全性更高的算法，目前已經有了大量的研究成果。

5.1 基本的圖像秘密分存加密算法

基于秘密分存的圖像加密算法根據門限秘密共享的理論而設計，其基本實現思想為：將待加密圖像按照某種規則分成n幅雜亂無章的子圖像，將它們分發給n個用戶保管；每幅子圖像本身不表示任何信息，其中任意k幅或更多子圖像可重構原始圖像，但少于k幅則得不到原始圖像的任何信息，從而達到保護圖像的目的。

下面給出一個典型的灰度圖（4，4）秘密分存加密算法。設待加密灰度圖像為M，將其灰度值排列成一個二進制串，長度為l（M），則加解密的過程如下：

（1） 隨機選擇3個二進制串R，S，T，要求l（R）=l（S）=

l（T）=l（M）；

（2） 將這4個二進制串進行逐比特異或，得到[U=M⊕R⊕S⊕T；]

（3） 將R，S，T，U作為4個子圖像分別發給不同的4個用戶；

（4） 4個用戶將其所持有的子圖像共享，可以重構出秘密圖像M=R⊕S⊕T⊕U，而任意3個用戶的子圖像無法得到秘密圖像的任何信息。

實驗結果如圖5，圖6所示。

5.2 視覺密碼學

視覺密碼學（Visual Cryptography Scheme，VCS）是1994年Naor和Shamir在歐密會上提出的一種新的圖像加密技術[18]，它基于秘密共享的思想，將需要保護的秘密圖像分解成若干幅無意義的分享圖像（shares）。解密時無需算法支持，只需找到若干幅滿足條件的分享圖像，直接利用人的視覺進行合成解密就可以得到原始的秘密圖像。視覺密碼學可以實現完善保密性，近年來發展十分迅速[19?21]。

二值圖的（2，2）VCS方案的加密過程是將秘密二值圖像分成兩個隨機的二值分享圖像，每一個像素進行4倍的像素擴張，并以隨機的形式選擇擴張結果；解密過程是直接將兩個分享圖像進行疊加，若同為白色像素則疊加結果是白色，若至少有一個是黑色像素則疊加結果是黑色。單個像素的加解密規則如表1所示。

加解密的實驗結果如圖7所示。

該領域的研究內容與發展趨勢有：基于門限結構的灰度圖像VCS與彩色圖像VCS；基于一般訪問結構秘密共享的VCS；可進行多幅秘密圖像分享的VCS；分享的子圖像為有意義圖像的VCS。

6 結 語

門限秘密共享技術是密碼學的重要分支之一，經過30多年的發展，目前已經在多個領域有了廣泛的應用。本文在回顧了Shamir和Blakley基本門限秘密共享方案的基礎上，介紹了目前門限秘密共享方案最主要的幾個典型應用，包括門限簽名與分布式CA、分布式PKG、門限式ABE、圖像秘密分存與視覺密碼學等重要的密碼學前沿領域。對于每一種應用，給出了基本的實現思想與算法概述，并對該領域的研究現狀與未來發展趨勢進行了介紹。研究表明，門限秘密共享作為重要的秘密分享技術，其理論與應用在密碼學中占據重要的地位。

參考文獻

[1] SHAMIR A. How to share a secret [J]. Communications of the ACM， 1979， 22（11）： 612?613.

[2] BLAKLEY G R. Safeguarding cryptographic keys [C]// Proceedings of 1979 AFIPS National Computer Conference. [S.l.]： AFIPS， 1979： 313?317.

[3] FARRAS O， PADRO C. Ideal hierarchical secret sharing schemes [J]. IEEE Transactions on Information Theory， 2012， 58（5）： 3273?3286.

[4] TIAN Youliang， MA Jianfeng， PENG Changgen， et al. Fair （t，n） threshold secret sharing scheme [J]. IET Information Security， 2013， 7（2）： 106?112.

[5] MAO Wenbo. Modern cryptography： theory and practice [M]. Upper Saddle River， USA： Prentice Hall， 2004.

[6] SHAMIR A. Identity?based cryptosystems and signature schemes [C]// Proceedings of 1984 CRYPTO on Advances in Cryptology. Berlin： CRYPTO， 1984： 47?53.

[7] ELAINE B， DENNIS B， SANTOSH C， et al. Cryptographic key management workshop summary [R]. USA： NIST， 2009.

[8] ZHANG Y， LIU W， LOU W， et al. Securing mobile ad hoc networks with certificateless public keys [J]. IEEE Transactions on Dependable and Secure Computing， 2006， 3（4）： 386?399.

[9] FANG Y， ZHU X， ZHANG Y. Securing resource?constrained wireless ad hoc networks [J]. IEEE Wireless Communications， 2009， 16（2）： 24?30.

[10] REN Y， WANG J， ZHANG Y， et al. Identity?based key issuing protocol for ad hoc networks [C]// 2007 IEEE International Conference on Computational Intelligence and Security. Harbin： IEEE， 2007： 917?921.

[11] CHAN A. Distributed private key generation for identity based cryptosystems in Ad Hoc networks [J]. IEEE Wireless Communication Letters， 2012， 1（1）： 46?48.

[12] DA S E， ALBINI L C P. Towards a fully self?organized identity?based key management system for MANETs [C]// 2013 IEEE the 9th International Conference on Wireless and Mobile Computing， Networking and Communications. [S.l.]： IEEE， 2013： 717?723.

[13] LIU S， LONG Y， CHEN K. Key updating technique in identity?based encryption [J]. Information Sciences， 2011， 181（11）： 2436?2440.

[14]SAHAI A， WATERS B. Fuzzy identity based encryption [C]// Proceedings of 2005 CRYPTO on Advances in Cryptology. Berlin： CRYPTO， 2005： 457?473.

[15] GOYAL V， PANDEY O， SAHAI A， et al. Attribute?based encryption for fine?grained access control of encrypted data [C]// Proceedings of 2006 ACM Conference on Computer and Communications Security. [S.l.]： ACM， 2006： 89?98.

[16] WATERS B. Ciphertext?policy attribute?based encryption： an expressive， efficient， and provably secure realization [C]// Proceedings of 2011 International Conference on Practice and Theory in Public Key Cryptography. Taomina： PKC， 2011： 53?70.

[17] PATEL K D， BELANI S. Image encryption using different techniques a review [J]. International Journal of Emerging Technology and Advanced Engineering， 2011， 1（1）： 30?34.

[18] NAOR M， SHAMIR A. Visual cryptography [C]// Proceedings of 1994 Workshop on the Theory and Application of Cryptographic Techniques. Perugia： EUROCRYPT， 1995： 1?12.

[19] YU B， XU X， FANG L. Multi?secret sharing threshold visual cryptography scheme [C]// 2007 IEEE International Conference on Computational Intelligence and Security Workshops. Harbin： IEEE， 2007： 815?818.

[20] YANG C N， WANG D S. Property analysis of XOR?based visual cryptography [J]. IEEE Transactions on Circuits and Systems for Video Technology， 2014， 24（2）： 189?197.

[21] HOU Y C， WEI S C， LIN C Y. Random?grid?based visual cryptography schemes [J]. IEEE Transactions on Circuits and Systems for Video Technology， 2014， 24（5）： 733?744.