張艷碩，李文敬，陳雷，畢偉，楊濤

?

基于特征值的可驗(yàn)證特殊門限秘密共享方案

張艷碩1,2，李文敬1,2，陳雷1，畢偉3，楊濤2

（1. 北京電子科技學(xué)院密碼科學(xué)與技術(shù)，北京 100070；2.公安部第三研究所，上海 201204； 3. 中思博安科技（北京）有限公司科學(xué)研究院，北京 100195）

秘密共享；特征值；可驗(yàn)證；黑盒子

1 引言

秘密共享技術(shù)已成為應(yīng)用密碼學(xué)中的一項(xiàng)重要技術(shù)，它在信息安全存儲(chǔ)、傳輸以及安全計(jì)算等環(huán)節(jié)起著非常關(guān)鍵的作用。在秘密共享技術(shù)中最常見(jiàn)的是門限方案，已提出的門限方案有很多種，主要代表為Shamir[1]的Lagrange插值多項(xiàng)式方案、Blakley[2]的矢量方案、Asmuth等[3]的同余類方案及Karnin等[4]的矩陣法方案，這些方案已經(jīng)得到了廣泛的研究，但大多沒(méi)有解決參與者行騙和密鑰分發(fā)者欺騙的問(wèn)題。為了解決上述問(wèn)題，文獻(xiàn)[5]提出了可驗(yàn)證秘密共享的思想，并給出了完整的實(shí)現(xiàn)方案。文獻(xiàn)[6-8]提出了可抵抗惡意欺騙的秘密共享方案。文獻(xiàn)[9-13]提出了可抵抗惡意欺騙的多秘密共享方案。

本文在基本Shamir門限方案的基礎(chǔ)上，利用階矩陣的特征方程具有重根的特點(diǎn)，提出了一種基于特征值的安全可驗(yàn)證的門限秘密共享方案。本文方案從矩陣特征值的角度出發(fā)，設(shè)計(jì)了一種可驗(yàn)證的秘密共享方案，這是本文方案的主要貢獻(xiàn)。經(jīng)分析證明，該方案是安全的，可以抵抗惡意欺詐。

2 基本Shamir門限秘密共享方案

1979年，Shamir[1]基于多項(xiàng)式的Lagrange插值公式提出了一個(gè)(,)門限方案，稱為Shamir門限方案或Lagrange插值法。Shamir門限方案的詳細(xì)介紹如下。

1) 參數(shù)選取

設(shè)()是有限域（為素?cái)?shù)，且>），共享密鑰為。有個(gè)參與者，要求重構(gòu)該共享密鑰至少需要個(gè)人。

2) 秘密分割

首先，密鑰分發(fā)者獨(dú)立隨機(jī)地選擇-1個(gè)元素1,2,…,a1?()，構(gòu)造一個(gè)-1次多項(xiàng)式為

最后，密鑰分發(fā)者將個(gè)數(shù)對(duì)(x,y)，1≤≤，分別秘密傳送給參與者1,2,…,，多項(xiàng)式()則是保密的，可以銷毀。

3）秘密恢復(fù)

假設(shè)個(gè)參與者中的任意個(gè)（不妨設(shè)為1,2,…,T）準(zhǔn)備一起恢復(fù)密鑰。

首先，參與者出示他們的子密鑰后，得到個(gè)點(diǎn)對(duì)(1,1)，(2,2)，…，(x,y)。

其次，個(gè)人計(jì)算多項(xiàng)式

最后，取多項(xiàng)式()的常數(shù)項(xiàng)(0)，即為所求的密鑰。

3 （n1+n2+…+nt , 1+1+…+1）特殊門限秘密共享方案

在給出本文方案之前，我們先看（,+1）門限方案。文獻(xiàn)[14]以某銀行3位出納和2位主任（正、副）開(kāi)啟保險(xiǎn)庫(kù)為例，為防止出現(xiàn)職員監(jiān)守自盜、遺忘密鑰或因職員缺席而打不開(kāi)保險(xiǎn)庫(kù)等各種問(wèn)題，銀行規(guī)定至少有2位出納和1位主任在場(chǎng)才能開(kāi)啟保險(xiǎn)庫(kù)，這樣共有3×2=6種開(kāi)啟方式。本例中，由于出納與主任的訪問(wèn)權(quán)限不同，定義了(,+1)門限方案。

定義1[14]設(shè)、為2個(gè)參與者的集合，∩（為空集），|，|，為門限值且<。假設(shè)共享密鑰為，集合中的參與者A的子秘密為k(=1,2,…,)，集合中的參與者B的子秘密為k(=1,2,…,)。集合中不少于個(gè)參與者和中的一個(gè)參與者在一起可以恢復(fù)密鑰，而其他任意組合方式都不能恢復(fù)密鑰，稱該方案為(,+ 1)門限共享方案。

在上述方案的基礎(chǔ)上，本文提出一種特例。3家銀行1、2和3共同管理一項(xiàng)基金，基金的使用需要征求3家銀行執(zhí)行董事的意見(jiàn)。其中，銀行1有3個(gè)執(zhí)行董事，銀行2有4個(gè)執(zhí)行董事，銀行3有3個(gè)執(zhí)行董事，每個(gè)執(zhí)行董事都有一把鑰匙。在這個(gè)例子中，3家銀行均只需派出任意一位執(zhí)行董事，即可決定該基金的使用狀況，此時(shí)一共有3×4×3=36種決定方式。由此，本文定義了一種新的(1+2+…+n,1+1+…+1)門限秘密共享方案。

定義2 設(shè)1,2,…,B是個(gè)參與者的集合，任意2個(gè)集合的交集是空集，即B∩B=(1≤≤, 1≤≤,), |1|=1, |2|=2, …, |B|=n(1+2+…+n=)。每個(gè)集合的參與者均分得一個(gè)子密鑰。主密鑰恢復(fù)階段，每個(gè)集合至少都出一個(gè)人，才可以計(jì)算出密鑰，缺少任何一個(gè)集合的參與者都不能計(jì)算出密鑰，則稱這種方案為(1+2+…+n,1+1+…+1)特殊門限秘密共享方案。

4 特殊門限秘密共享方案

4.1 預(yù)備知識(shí)

4.1.1 方陣的特征值和特征向量

式(3)也可寫成

這是個(gè)未知數(shù)個(gè)方程的齊次線性方程組[15]。

4.1.2 對(duì)稱矩陣的性質(zhì)

4.1.3 黑盒子

1) 黑盒子的定義

基于“黑盒子”[16]的含義給出其在本文方案中的定義。

2) 黑盒子的原理

①子密鑰生成階段是根據(jù)式(5)設(shè)計(jì)的，即

②主密鑰恢復(fù)階段，是根據(jù)式(3)設(shè)計(jì)的，即

3) 算例

以下用一個(gè)小例子說(shuō)明黑盒子在本文方案中的用法。

子密鑰生成階段，主要功能程序如下。

①密鑰分發(fā)者輸入共享主密鑰、集合的總個(gè)數(shù)和各集合的人數(shù)n：

=input('請(qǐng)輸入要分發(fā)的秘密:');

=input('請(qǐng)輸入集合的個(gè)數(shù):') ;

for=1:

n=input('所對(duì)應(yīng)的集合的人數(shù):') ;

end for

②生成2階隨機(jī)可逆矩陣為

=rand(2,2);

for=1:

x=x(1,)

fprintf('%d',x)

n=input('所對(duì)應(yīng)的集合的人數(shù):') ;

for=1:?1

()=()=+(1,)(^());

(x)=(x)+(1,)(x^());

end for

for=1:n

for=1:2

E=[Emod((x),)];

end for

end for

end for

黑盒子生成的隨機(jī)可逆矩陣為

生成的矩陣為

主密鑰恢復(fù)階段，主要功能程序如下。

①判斷線性相關(guān)性

L=[ ] ;

P=[ ] ;

for=1:2

p=input('輸入子秘鑰:') ;

=p'··p

P=[Pp]

=[]

end for

=size(P);

=rank(P);

if(>)

fprintf('線性相關(guān)，停止恢復(fù)主密鑰 ')

else

fprintf('線性無(wú)關(guān)，繼續(xù)恢復(fù)主密鑰 ')

end if

if((1,1)==(1,2))

fprintf('特征值相同，繼續(xù)恢復(fù)主密鑰 ')

else

fprintf('特征值不同，停止恢復(fù)主密鑰 ')

當(dāng)參與者輸入正確的子密鑰為

黑盒子輸出：線性無(wú)關(guān)，繼續(xù)恢復(fù)主密鑰；

特征值相同，繼續(xù)恢復(fù)主密鑰；

λ=6；

當(dāng)參與者輸入偽造的子密鑰為

黑盒子輸出：線性無(wú)關(guān)，繼續(xù)恢復(fù)主密鑰；

特征值不同，停止恢復(fù)主密鑰；

當(dāng)參與者輸入偽造的子密鑰為

黑盒子輸出：線性相關(guān)，停止恢復(fù)主密鑰；

end if

4.2 方案設(shè)計(jì)

本節(jié)將給出具體方案，該方案可分為4個(gè)步驟：系統(tǒng)描述、參數(shù)選取、秘密分割以及秘密恢復(fù)。

4.2.1 系統(tǒng)描述

4.2.2 參數(shù)選取

系統(tǒng)參數(shù)的選取是為了給后續(xù)工作做準(zhǔn)備。

4.2.3 秘密分割

4.2.4 秘密恢復(fù)

本文方案要求恢復(fù)秘密參與者的人數(shù)不少于門限值，即每個(gè)參與者集合必須至少出一個(gè)人。

①λ=λ=λ1。

只有同時(shí)滿足上述2個(gè)條件才可以進(jìn)行下一步操作，否則，停止密鑰恢復(fù)工作。

5 方案分析

從正確性、完善安全性和欺詐檢測(cè)這3個(gè)方面來(lái)分析本文方案。

5.1 正確性證明

命題1 在參與者誠(chéng)實(shí)而正確地執(zhí)行方案的前提下，任意合法的授權(quán)子集都可以恢復(fù)密鑰。

實(shí)質(zhì)上，本文方案的正確性是建立在Shamir門限方案正確性的基礎(chǔ)上的。

5.2 完善安全性證明

命題2 當(dāng)中參與者總數(shù)不夠時(shí)，無(wú)法恢復(fù)密鑰。

5.3 欺詐檢測(cè)

5.3.1 檢驗(yàn)密鑰分發(fā)者是否可靠

命題3 各參與者在收到子秘密之后，可通過(guò)式(3)檢驗(yàn)密鑰分發(fā)者是否可靠。

5.3.2 檢測(cè)參與者是否誠(chéng)實(shí)

命題4 在秘密恢復(fù)階段，也可通過(guò)式(3)檢驗(yàn)參與者是否誠(chéng)實(shí)。

6 方案的具體應(yīng)用

下面用一個(gè)例子說(shuō)明本文方案的可行性。

例 設(shè)有1、2這2個(gè)集合，集合1中有一個(gè)參與者11，集合2中有一個(gè)參與者21。為這2個(gè)用戶分配密鑰，并分析重構(gòu)密鑰的過(guò)程。

1) 參數(shù)選取

2) 秘密分割

密鑰分發(fā)者取1=(1)=(3)=2，2=(2)=(6)=1。

得到對(duì)角矩陣為

3) 秘密恢復(fù)

所以，有

所以=3，從而獲得共享密鑰。

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

本文提出了一種基于特征值的可驗(yàn)證的特殊門限秘密共享方案。方案中的每個(gè)參與者需持有2種子密鑰，其優(yōu)點(diǎn)是可以有效地保證密鑰分發(fā)者分發(fā)子密鑰的真實(shí)性和參與者提供子密鑰的真實(shí)性。同時(shí)，本文方案利用黑盒子的設(shè)計(jì)理念，使方案的密鑰分發(fā)者和參與者可以進(jìn)行互相認(rèn)證，實(shí)現(xiàn)了防欺詐功能。本文方案的貢獻(xiàn)還在于，從特征值的角度出發(fā)設(shè)計(jì)了一種可驗(yàn)證的秘密共享方案。

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

[2] BLAKLEY G R. Safeguarding cryptographic keys[C]//IEEE Computer Society. 1979: 313.

[3] ASMUTH C, BLOOM J. A modular approach to key safeguarding[J]. IEEE Transactions on Information Theory, 1983, 29(2):208-210.

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

[5] CHOR B, GOLDWASSER S, MICALI S, et al. Verifiable secret sharing and achieving simultaneity in the presence of faults[C]// Symposium on Foundations of Computer Science.2008:383-395.

[6] LIU C J, LI Z H, BAI C M, et al. Quantum-secret-sharing scheme based on local distinguishability of orthogonal seven-qudit entangled states[J]. International Journal of Theoretical Physics, 2018, 57(3):1-15.

[7] XU T T, LI Z H, BAI C M, et al. A new improving quantum secret sharing scheme[J]. International Journal of Theoretical Physics, 2017, 56:1-10.

[8] SINGH N, TENTU A N, BASIT A, et al. Sequential secret sharing scheme based on Chinese remainder theorem[C]// IEEE International Conference on Computational Intelligence and Computing Research. 2017:1-6.

[9] SONG Y, LI Y, WANG W. Multiparty quantum direct secret sharing of classical information with bell states and bell measurements[J]. International Journal of Theoretical Physics, 2018, 57(5):1559-1571.

[10] PILARAM H, EGHLIDOS T, PILARAM H, et al. A lattice-based changeable threshold multi-secret sharing scheme and its application to threshold cryptography[J]. Scientia Iranica, 2017, 24(3):1448-1457.

[11] BASIT A, KUMAR N C, VENKAIAH V C, et al. Multi-stage multi-secret sharing scheme for hierarchical access structure[C]//International Conference on Computing, Communication and Automation. 2017:556-563.

[12] ZHANG T, KE X, LIU Y. (,) multi-secret sharing scheme extended from Harn-Hsu’s scheme[J]. Eurasip Journal on Wireless Communications & Networking, 2018, 2018(1):71.

[13] YUAN D, HE M, ZENG S, et al. (,)-threshold point function secret sharing scheme based on polynomial interpolation and its application[C]//IEEE/ACM International Conference on Utility and Cloud Computing. 2017:269-275.

[14] 李濱. 基于特殊訪問(wèn)權(quán)限的差分秘密共享方案[J]. 四川大學(xué)學(xué)報(bào)(自然科學(xué)版), 2006(1): 78-83.

LI B. Differential secret sharing scheme based on special access permissions[J]. Journal of Sichuan University (Natural Science Edition), 2006(1): 78-83.

[15] 同濟(jì)大學(xué)數(shù)學(xué)系編.工程數(shù)學(xué)線性代數(shù)[M]. 北京: 高等教育出版社, 2014. School of Mathematic Sciences, Tongji University . Engineering mathematics, linear algebra[M]. Beijing: Higher Education Press. 2014.

[16] 曹爾強(qiáng), 張沂, 曹曄, 等. “軟件黑盒子”文件加鎖和加密的一個(gè)方法[J]. 長(zhǎng)春郵電學(xué)院學(xué)報(bào),1991(3):11-14. CAO E Q, ZHANG Y, CAO Y ,et al. A technique of locking a disk and secreting a whole disk[J]. Journal of Changchun Post & Telecommunication Institute, 1991(3):11-14.

Verifiable special threshold secret sharing scheme based on eigenvalue

ZHANG Yanshuo1,2, LI Wenjing1,2, CHEN Lei1, BI Wei3, YANG Tao2

1. Department of Cryptography Science and Technology, Beijing Electronic Science and Technology Institute, Beijing 100070, China 2. The Third Research Institute of Ministry of Public Security, Shanghai 201204, China 3. Institute of Science, Zsbatech Corporation, Beijing 100195, China

secret sharing, eigenvalue, verifiable, black box

TP309

A

10.11959/j.issn.1000?436x.2018143

張艷碩（1979?），男，陜西寶雞人，博士，北京電子科技學(xué)院講師，主要研究方向?yàn)槊艽a理論及其應(yīng)用。

李文敬（1992?），女，山東濟(jì)寧人，北京電子科技學(xué)院碩士生，主要研究方向?yàn)樾畔踩?/p>

陳雷（1992?），男，河北邯鄲人，北京電子科技學(xué)院碩士生，主要研究方向?yàn)樾畔踩?/p>

畢偉（1980?），男，黑龍江哈爾濱人，博士，中思博安科技（北京）有限公司研究員，主要研究方向?yàn)樾畔踩蛥^(qū)塊鏈技術(shù)。

楊濤（1977?），男，安徽蕪湖人，博士，公安部第三研究所副研究員，主要研究方向?yàn)樾畔踩?/p>

2018?01?25；

2018?06?22

信息網(wǎng)絡(luò)安全公安部重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金資助項(xiàng)目（No.C17608）；中國(guó)民航信息技術(shù)科研基金資助項(xiàng)目（No.CAAC-ITRB-201705）；國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61772047）

The Opening Project of Key Lab of Information Network Security of Ministry of Public Security (No.C17608) , The Information Technology Research Base of Civil Aviation Administration of China (No.CAAC-ITRB-201705), The National Natural Science Foundation of China (No. 61772047)