基于環(huán)境感知的防泄漏多秘密共享方案

秦華旺，朱曉華，戴躍偉

?

基于環(huán)境感知的防泄漏多秘密共享方案

秦華旺，朱曉華，戴躍偉

(南京理工大學自動化學院 南京 210094)

提出了一種基于環(huán)境感知的防泄漏多秘密共享方案。在該方案中，可信中心利用中國剩余定理將多個秘密合并成一個秘密，根據拉格朗日插值多項式為各個參與者分配秘密子份額；在秘密重構時，參與者利用雙線性映射，根據其秘密子份額和當前環(huán)境信息計算偽子份額；驗證機構利用拉格朗日插值和雙線性映射計算出驗證信息，來驗證參與者提交的偽子份額的有效性。該方案中參與者的子份額以及共享秘密均具有防泄漏特性，因而可以被重復使用。基于環(huán)境感知的動態(tài)性可以極大提高該方案對移動攻擊者的攻擊難度。該方案尤其適用于無線傳感器網絡、多機器人等野外工作的系統(tǒng)，可以有效提高這些系統(tǒng)的使用效率和安全性。

密碼學; 環(huán)境感知; 防泄漏; 多秘密共享; 秘密共享

秘密共享是密碼學中的重要研究內容，最早的秘密共享方案由文獻[1]提出，其通過拉格朗日插值，實現了(,)秘密共享。該方案將秘密分為個子份額并分發(fā)給個參與者，個參與者中的任意個合作可以重構出共享秘密，而少于個參與者則不能獲取有關共享秘密的任何信息。雖然目前已有多種不同形式的秘密共享，如針對訪問結構的[2]、可驗證的[3-4]、先應式的[5-6]、有權重的[7-8]、多秘密共享的[9-10]等，但這些方案在實際應用中仍然存在以下兩點不足：

1) 在共享秘密的重構過程中，秘密生成者會得到原始的共享秘密，因此共享秘密只能被使用一次，而不能被重復使用；2) 參與者不能根據其感知的當前環(huán)境來動態(tài)改變其提交的子份額或偽子份額，以提高攻擊者獲取有效子份額的難度。

針對上述問題，本文提出一種基于環(huán)境感知的防泄漏多秘密共享方案，該方案中，參與者可以根據其當前感知的環(huán)境信息，如時間、溫度、濕度、氣壓等，來動態(tài)改變其提交的偽子份額。每次提交的偽子份額均有一定的有效期，超出有效期的偽子份額將不可用，即使攻擊者獲取了某個授權子集中全部參與者的過期偽子份額，攻擊者也不能獲取共享秘密的任何信息，由此可以極大提高攻擊者的攻擊難度。在重構共享秘密的過程中，不論是各個參與者、秘密生成者還是共享秘密的驗證機構，均不能直接獲取原始的共享秘密，而只能由可信的驗證機構對秘密生成者提供的關于共享秘密的驗證信息進行有效性驗證，因此共享秘密可以被重復使用，從而有效提高系統(tǒng)的使用效率。此外，本文方案還利用中國剩余定理實現了多秘密共享。與傳統(tǒng)的先應式秘密共享方案相比，本文方案不需要通過參與者間大量的信息交互進行子份額更新，因而也就不需要在參與者間采用復雜的數據同步和交互協議，可以極大降低系統(tǒng)設計的復雜度，并提高系統(tǒng)運行的魯棒性。

本文提出的基于環(huán)境感知的防泄漏多秘密共享方案在實際中具有重要的應用價值，如在野外的無線傳感器網絡、多機器人等系統(tǒng)中，通常在投放前對系統(tǒng)進行共享秘密分發(fā)，這些節(jié)點將在野外長期工作，如果此時再對系統(tǒng)進行共享秘密的分發(fā)將極其麻煩。因此，如果系統(tǒng)的共享秘密，或者參與者的子份額只能被使用一次，而不能被重復使用，將嚴重影響系統(tǒng)的工作效率。使用本文提出的基于環(huán)境感知的防泄漏秘密共享方案，無線傳感器或機器人可通過感知的環(huán)境信息動態(tài)更新其提交的偽子份額，提高攻擊者同時獲取多個有效偽子份額的難度，并使原始的共享秘密在重構過程中不被泄漏，可以被重復使用，極大提高了系統(tǒng)的使用效率和安全性。此外，在基于互聯網的秘密共享系統(tǒng)中，共享秘密的分發(fā)也是一件繁瑣的工作，需要采用高可靠性的加密措施或維護一些高安全性的秘密通道。在這類系統(tǒng)中使用本文提出的基于環(huán)境感知的防泄漏秘密共享方案，同樣將有效提高系統(tǒng)的使用性能。

1 相關工作

(,)門限秘密共享方案最早由文獻[1,11]提出，規(guī)定個參與者中的任意個合作可以重構出共享秘密。文獻[1]方案基于拉格朗日插值，而文獻[11]的方案則基于共點超平面。為了拓寬秘密共享的應用范圍，文獻[2]又提出了訪問結構上的秘密共享方案，在該方案中，參與者集合可以劃分為若干個數量不等的授權子集，并規(guī)定只有授權子集中的參與者合作才能得到共享秘密。此外，針對實際中可能出現的各個參與者重要程度不同的應用需求，又出現了參與者有權重的秘密共享方案[7-8]，這些方案的構造，可以在(,)秘密共享的基礎上通過給權重不同的參與者分配數量不同的子份額實現[7]，也可以通過采用分解結構[8]實現。

除了門限結構外，秘密共享在其他方面也取得了豐富的研究成果。比較典型的有文獻[3-4]的可驗證秘密共享，可以對參與者在秘密重構中提交的子份額進行公開驗證，以防止參與者的欺騙行為。文獻[5]的先應式秘密共享通過周期性更新各個參與者的子份額，提高方案對移動攻擊的防御能力。文獻[6]的動態(tài)先應式秘密共享在更新子份額時還可以改變秘密共享的門限結構，從而提高了方案在應用中的靈活性。文獻[9]的多秘密共享只需要一次分發(fā)，就可以同時共享多個秘密。文獻[12]的無可信中心的秘密共享中的各個參與者同時也是秘密的分發(fā)者，可以避免系統(tǒng)的單點失效問題。

近期還有其他一些新穎的秘密共享方案被提出，如文獻[13]的分級秘密共享，可以將整個參與者集合分成若干個等級，不同級別的門限值也不同。文獻[14]的空間高效秘密共享，利用多重的多項式插值，使各個參與者只需保存接近于理論上最小長度的子份額。文獻[15]的可糾錯秘密共享假設共享秘密的子份額受到了噪聲的干擾，給出了在此情況下可以重構出共享秘密的條件，并設計了相應的可糾錯的秘密共享方案。文獻[16]的社會秘密共享根據參與者的聲譽以及其在秘密共享中表現出的可靠性來為其分配子份額。

在現有秘密共享方案中，共享秘密在重構過程中均會被暴露，使其不能被重復使用，影響了系統(tǒng)的使用效率，而且參與者也不能根據當前環(huán)境動態(tài)改變其提交的子份額或偽子份額，只能基于復雜通信協議基礎上的大量信息交互來更新子份額，提高了系統(tǒng)設計的復雜性。針對該問題，本文提出基于環(huán)境感知的防泄漏多秘密共享方案，與現有方案相比，本文方案的主要優(yōu)點有：

1) 共享秘密在重構過程中不會被泄漏，因此其可以被重復使用；2) 參與者可以根據當前感知的環(huán)境信息來動態(tài)改變其提交的偽子份額，偽子份額具有一定的有效期，過期的偽子份額不能用于重構共享秘密；3) 能夠實現多秘密共享，各個秘密可以具有不同的門限值。

2 雙線性映射

令1是階加法群，2是階乘法群，是大素數，若映射：1×1→2滿足下列條件，則就被稱為雙線性映射[17]。

雙線性映射中的困難性問題是利用雙線性映射來設計密碼系統(tǒng)的基礎，本文方案將用到一個被稱為“計算性Diffie-Hillman問題(CDH)”的困難問題。即：對于給定的參數,,,1，其中,,未知，計算(,)?？梢哉J為不存在能以不可忽略的概率優(yōu)勢解決CDH問題的多項式時間算法。

3 方案描述

在基于環(huán)境感知的防泄漏秘密共享方案中，參與者重構的并不是原始的共享秘密，而只能重構共享秘密有效的驗證信息，該驗證信息需要一個可信的專門驗證機構進行驗證。同樣，驗證機構也不可以獲取原始的共享秘密。

各個參與者以及驗證機構均可以通過傳感器感知當前的環(huán)境信息，包括時間、溫度、濕度、氣壓等。本文方案中，所有節(jié)點感知的環(huán)境信息必須一致。因此，如果參與者以及驗證機構的分布范圍較小，如一個小范圍的多機器人系統(tǒng)，則時間、溫度、濕度、氣壓等環(huán)境信息均可以利用。如果參與者以及驗證機構的分布范圍較大，溫度、濕度、氣壓等環(huán)境信息則無法保證一致性，此時可以利用時間信息，因為在全球范圍內通過GPS感知的時間信息均可以保證高度的一致性。鑒于時間信息在精度、同步性、不重復性等方面具有的優(yōu)勢，本文方案中的環(huán)境信息將以時間為例。

通過GPS可以獲取精度非常高的時間值，系統(tǒng)根據共享秘密重構過程所需要的時間選擇合適的時間單位。為了保證參與者以及驗證機構獲取時間的一致性，由驗證機構在某個時間單位的開始時廣播通知所有參與者獲取當前時間。若秘密重構及驗證在1 min內完成，則驗證機構可以在開始時通知所有參與者獲取時間，且獲取的時間單位定為min。在整個重構及驗證過程中，所有參與者和驗證機構所保存的時間值一致，且所有參與者提交的偽子份額的有效期均為1 min，超出1 min的偽子份額將無效。通過給參與者的偽子份額加上有效期，能極大提高攻擊者的攻擊難度。

3.1 初始化

1) 可信中心PKG選擇一個雙線性映射：1×1→2，1的階為大素數，生成元為。2) PKG選擇一個Hash函數H(×): {0,1}*→1。3) PKG選擇個互不相同的素數，且。4) PKG公開5) PKG隨機選取作為驗證機構的私鑰，計算驗證機構的公鑰并公開。6) PKG隨機選取作為個參與者的私鑰，計算各個參與者的公鑰并公開。7) PKG利用安全通道將秘密發(fā)送給參與者，將秘密發(fā)送給驗證機構。

3.2 子份額分發(fā)

3.3 重構和驗證

1) 參與者給驗證機構發(fā)送一個重構消息，然后驗證機構在合適的時間點廣播通知該個參與者，以一定的時間單位來獲取時間值；2) 參與者利用其子份額計算對應于共享秘密的子份額；3) 設為驗證機構及參與者通過GPS獲取的當前時間，參與者首先計算，然后再計算其偽子份額，并將發(fā)送給驗證機構；4) 驗證機構收到后，先利用Diffie-Hillman密鑰交換技術[18]計算，再計算，最后計算共享秘密的驗證信息，其中，。

4 性能分析

4.1 有效性

4.2 防泄漏性

4.3 基于環(huán)境感知的動態(tài)性

5 性能比較

文獻[3]的可驗證秘密共享和文獻[5]的先應式秘密共享，與本文方案的防泄漏、環(huán)境感知、可驗證等特性較為相似，表1給出了本文方案與文獻[3,5]方案之間的性能比較?？梢钥闯?，在文獻[3,5]的方案中，參與者在秘密重構時提交的是秘密子份額，不能通過提交偽子份額來防止其秘密子份額的泄漏，而本文方案則可以通過提交偽子份額防止秘密子份額的泄漏。

表1 性能比較

文獻[3]的方案不能進行子份額更新，文獻[5]的先應式秘密共享方案可以進行子份額的定期更新，本文方案可以根據當前環(huán)境對偽子份額進行動態(tài)更新。文獻[3]的先應式秘密共享方案通過各個參與者間大量的信息交互，周期性地更新各個參與者的子秘密，增加攻擊者同時獲取或破壞多個子秘密的難度。但先應式秘密共享需要在各個參與者間進行大量的信息交互，為了保證交互信息的同步和一致性，需要采用復雜的通信協議，增加了系統(tǒng)設計的復雜性。此外，如果攻擊者破壞了交互信息中的任何部分，將導致整個門限密碼系統(tǒng)失效，因此文獻[5]的先應式秘密共享方案的魯棒性也難以得到保證。本文方案不需要在參與者間進行大量的信息交互，因而也就不需要在參與者間采用復雜的數據同步和交互協議，可以極大降低系統(tǒng)設計的復雜度。

本文方案中，達到門限要求的參與者只能重構共享秘密的有效驗證信息，不論是各個參與者、秘密生成者還是共享秘密的驗證機構，均不能直接獲取原始的共享秘密，因此共享秘密可以被重復使用，而現有秘密共享方案則不具備這個特性。

文獻[3,5]的方案以及本文方案中的主要計算開銷均是模指數運算，因此它們的計算復雜度相當。此外，本文方案可以實現多秘密共享，而文獻[3,5]的方案只能進行單秘密共享。

6 結束語

秘密共享是保證數據保密性和完整性的一種重要手段，也是密碼學和分布式計算領域中的重要研究內容。本文提出了一種基于環(huán)境感知的防泄漏多秘密共享方案。與現有方案相比，本文方案的顯著特點是共享秘密以及參與者的子份額均具有防泄漏特性，可以被重復使用。此外，其基于環(huán)境感知的動態(tài)性使參與者提交的偽子份額具有一定的有效期，有效提高攻擊者的攻擊難度。本文方案尤其適用于野外的無線傳感器網絡、多機器人等系統(tǒng)中的秘密共享，基于環(huán)境感知的防泄漏特性將可以極大提高這些系統(tǒng)的使用效率和安全性。

[1] SHAMIR A. How to share a secret[J]. Communications of the ACM, 1979, 22(11): 612-613.

[2] ITO M, SAITO A, NISHIZEKI T. Secret sharing schemes realizing general access structure[C]//Proceedings of IEEE Global Telecommunication Conference. New Jersey: IEEE Press, 1987.

[3] FELDMAN P. A practical scheme for non-interactive verifiable secret sharing[C]//Proceedings of the 19th Annual ACM Symposium on Theory of Computing. New York: ACM Press, 1987: 427-437.

[4] PEDERSEN T P. Non-interactive and information-theoretic secure verifiable secret sharing[C]//CRYPTO’91, LNCS 576. Berlin: Springer-Verlag, 1992: 11-15.

[5] HERZBERG A, JARECKI S, KRAWCZYK H, et al. Proactive secret sharing or how to cope with perpetual leakage[C]//Cryptology-Crypto’95. Berlin: Springer-Verlag, 1995: 339-352.

[6] DESMEDT Y, JAJODIA S. Redistributing secret shares to

new access structures and its applications[C]//Technical Report ISSE TR-97-01. Fairfax, USA: [s.n.], 1997.

[7] MORILLO P, PADRO C, SAEZ G, et al. Weighted threshold secret sharing schemes[J]. Information Processing Letters, 1999, 70: 211-216.

[8] SUN H M, CHEN B L. Weighted decomposition construction for perfect secret sharing schemes[J]. Computers and Mathematics with Applications, 2002,43: 877-887.

[9] KARNIN E D, GREENE J W, HELLMAN M E. On secret sharing systems[J]. IEEE Transactions on Information Theory, 1983, 29(1): 35-41.

[10] CHAN C W, CHANG C C. A scheme for threshold multi-secret sharing[J]. Applied Mathematics and Computation, 2005(166): 1-14.

[11] BLAKLEY G R. Safeguarding cryptographic keys [C]//Proceedings of AFIPS National Computer Conference. New York: IEEE Press, 1979: 313-317.

[12] PEDERSEN T P. A threshold cryptosystem without a trusted party[C]//Eurocrypt’91, LNCS 547. Berlin: Springer-Verlag, 1991: 522-526.

[13] TASSA T. Hierarchical threshold secret sharing[J]. Journal of Cryptology, 2007, 20: 237-264.

[14] PARAKH A, KAK S. Space efficient secret sharing for implicit data security[J]. Information Sciences, 2011, 181: 335-341.

[15] KUROSAWA K. General error decodable secret sharing scheme and its application[J]. IEEE Transactions on Information Theory, 2011, 57(9): 6304-6309.

[16] NOJOUMIAN M, STINSON D R, GRAINGER M. Unconditionally secure social secret sharing scheme[J]. IET Information Security, 2010, 4(4): 202-211.

[17] BONEH D, LYNN B, SHACHAM H. Short signatures from the Weil pairing[C]//ASIACRYPT’01, LNCS 2248. Berlin: Springer-Verlag, 2001: 514-532.

[18] DIFFIE W, HELLMAN M E. New directions in cryptography[J]. IEEE Transactions on Information Theory, 1976, 22(6): 644-654.

編 輯 漆 蓉

Leakproof Multi-Secret Sharing Based on Environment Sensing

QIN Hua-wang, ZHU Xiao-hua, and DAI Yue-wei

(School of Automatization, Nanjing University of Science and Technology Nanjing 210094)

A leakproof multi-secret sharing scheme based on environment sensing is proposed, in which the private key generator (PKG) uses the Chinese remainder theorem to combine multi-secret into one secret, and computes the shadows through the Lagrange interpolation polynomial. In the reconstruction, the participants use the bilinear map to compute the counterfeit shadows according to the shadows and the current environment. The verifier computes the authentication information through the Lagrange interpolation and the bilinear map, and checks the validity of the counterfeit shadows. In the scheme, the shadows of participants and the shared secret are leakproof, and can be used repeatedly. The dynamic property based on environment sensing can improve the security against the mobile adversary. The proposed scheme is particularly suitable for the system which needs to run long time in the open, such as the wireless sensor network and the multi-robots, and can improve the efficiency and security of these systems effectively.

cryptography; environment sensing; leakproof; multi-secret sharing; secret sharing

TP393

A

10.3969/j.issn.1001-0548.2015.01.017

2013-12-12；

2014-09-10

國家自然科學基金(61170250, 61103201)

秦華旺(1978-)，男，博士，副教授，主要從事信息安全方面的研究.