秦華旺，朱曉華，戴躍偉

?

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

秦華旺，朱曉華，戴躍偉

(南京理工大學(xué)自動(dòng)化學(xué)院 南京 210094)

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

1) 共享秘密在重構(gòu)過程中不會(huì)被泄漏，因此其可以被重復(fù)使用；2) 參與者可以根據(jù)當(dāng)前感知的環(huán)境信息來(lái)動(dòng)態(tài)改變其提交的偽子份額，偽子份額具有一定的有效期，過期的偽子份額不能用于重構(gòu)共享秘密；3) 能夠?qū)崿F(xiàn)多秘密共享，各個(gè)秘密可以具有不同的門限值。

2 雙線性映射

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

雙線性映射中的困難性問題是利用雙線性映射來(lái)設(shè)計(jì)密碼系統(tǒng)的基礎(chǔ)，本文方案將用到一個(gè)被稱為“計(jì)算性Diffie-Hillman問題(CDH)”的困難問題。即：對(duì)于給定的參數(shù),,,1，其中,,未知，計(jì)算(,)。可以認(rèn)為不存在能以不可忽略的概率優(yōu)勢(shì)解決CDH問題的多項(xiàng)式時(shí)間算法。

3 方案描述

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

各個(gè)參與者以及驗(yàn)證機(jī)構(gòu)均可以通過傳感器感知當(dāng)前的環(huán)境信息，包括時(shí)間、溫度、濕度、氣壓等。本文方案中，所有節(jié)點(diǎn)感知的環(huán)境信息必須一致。因此，如果參與者以及驗(yàn)證機(jī)構(gòu)的分布范圍較小，如一個(gè)小范圍的多機(jī)器人系統(tǒng)，則時(shí)間、溫度、濕度、氣壓等環(huán)境信息均可以利用。如果參與者以及驗(yàn)證機(jī)構(gòu)的分布范圍較大，溫度、濕度、氣壓等環(huán)境信息則無(wú)法保證一致性，此時(shí)可以利用時(shí)間信息，因?yàn)樵谌蚍秶鷥?nèi)通過GPS感知的時(shí)間信息均可以保證高度的一致性。鑒于時(shí)間信息在精度、同步性、不重復(fù)性等方面具有的優(yōu)勢(shì)，本文方案中的環(huán)境信息將以時(shí)間為例。

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

3.1 初始化

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

3.2 子份額分發(fā)

3.3 重構(gòu)和驗(yàn)證

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

4 性能分析

4.1 有效性

4.2 防泄漏性

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

5 性能比較

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

表1 性能比較

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

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

文獻(xiàn)[3,5]的方案以及本文方案中的主要計(jì)算開銷均是模指數(shù)運(yùn)算，因此它們的計(jì)算復(fù)雜度相當(dāng)。此外，本文方案可以實(shí)現(xiàn)多秘密共享，而文獻(xiàn)[3,5]的方案只能進(jìn)行單秘密共享。

6 結(jié)束語(yǔ)

秘密共享是保證數(shù)據(jù)保密性和完整性的一種重要手段，也是密碼學(xué)和分布式計(jì)算領(lǐng)域中的重要研究?jī)?nèi)容。本文提出了一種基于環(huán)境感知的防泄漏多秘密共享方案。與現(xiàn)有方案相比，本文方案的顯著特點(diǎn)是共享秘密以及參與者的子份額均具有防泄漏特性，可以被重復(fù)使用。此外，其基于環(huán)境感知的動(dòng)態(tài)性使參與者提交的偽子份額具有一定的有效期，有效提高攻擊者的攻擊難度。本文方案尤其適用于野外的無(wú)線傳感器網(wǎng)絡(luò)、多機(jī)器人等系統(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

國(guó)家自然科學(xué)基金(61170250, 61103201)

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