基于特征值的可驗證特殊門限秘密共享方案

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

?

基于特征值的可驗證特殊門限秘密共享方案

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

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

秘密共享；特征值；可驗證；黑盒子

1 引言

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

本文在基本Shamir門限方案的基礎上，利用階矩陣的特征方程具有重根的特點，提出了一種基于特征值的安全可驗證的門限秘密共享方案。本文方案從矩陣特征值的角度出發，設計了一種可驗證的秘密共享方案，這是本文方案的主要貢獻。經分析證明，該方案是安全的，可以抵抗惡意欺詐。

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

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

1) 參數選取

設()是有限域（為素數，且>），共享密鑰為。有個參與者，要求重構該共享密鑰至少需要個人。

2) 秘密分割

首先，密鑰分發者獨立隨機地選擇-1個元素1,2,…,a1?()，構造一個-1次多項式為

最后，密鑰分發者將個數對(x,y)，1≤≤，分別秘密傳送給參與者1,2,…,，多項式()則是保密的，可以銷毀。

3）秘密恢復

假設個參與者中的任意個（不妨設為1,2,…,T）準備一起恢復密鑰。

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

其次，個人計算多項式

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

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

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

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

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

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

4 特殊門限秘密共享方案

4.1 預備知識

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

式(3)也可寫成

這是個未知數個方程的齊次線性方程組[15]。

4.1.2 對稱矩陣的性質

4.1.3 黑盒子

1) 黑盒子的定義

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

2) 黑盒子的原理

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

②主密鑰恢復階段，是根據式(3)設計的，即

3) 算例

以下用一個小例子說明黑盒子在本文方案中的用法。

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

①密鑰分發者輸入共享主密鑰、集合的總個數和各集合的人數n：

=input('請輸入要分發的秘密:');

=input('請輸入集合的個數:') ;

for=1:

n=input('所對應的集合的人數:') ;

end for

②生成2階隨機可逆矩陣為

=rand(2,2);

for=1:

x=x(1,)

fprintf('%d',x)

n=input('所對應的集合的人數:') ;

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

黑盒子生成的隨機可逆矩陣為

生成的矩陣為

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

①判斷線性相關性

L=[ ] ;

P=[ ] ;

for=1:2

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

=p'··p

P=[Pp]

=[]

end for

=size(P);

=rank(P);

if(>)

fprintf('線性相關，停止恢復主密鑰 ')

else

fprintf('線性無關，繼續恢復主密鑰 ')

end if

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

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

else

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

當參與者輸入正確的子密鑰為

黑盒子輸出：線性無關，繼續恢復主密鑰；

特征值相同，繼續恢復主密鑰；

λ=6；

當參與者輸入偽造的子密鑰為

黑盒子輸出：線性無關，繼續恢復主密鑰；

特征值不同，停止恢復主密鑰；

當參與者輸入偽造的子密鑰為

黑盒子輸出：線性相關，停止恢復主密鑰；

end if

4.2 方案設計

本節將給出具體方案，該方案可分為4個步驟：系統描述、參數選取、秘密分割以及秘密恢復。

4.2.1 系統描述

4.2.2 參數選取

系統參數的選取是為了給后續工作做準備。

4.2.3 秘密分割

4.2.4 秘密恢復

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

①λ=λ=λ1。

只有同時滿足上述2個條件才可以進行下一步操作，否則，停止密鑰恢復工作。

5 方案分析

從正確性、完善安全性和欺詐檢測這3個方面來分析本文方案。

5.1 正確性證明

命題1 在參與者誠實而正確地執行方案的前提下，任意合法的授權子集都可以恢復密鑰。

實質上，本文方案的正確性是建立在Shamir門限方案正確性的基礎上的。

5.2 完善安全性證明

命題2 當中參與者總數不夠時，無法恢復密鑰。

5.3 欺詐檢測

5.3.1 檢驗密鑰分發者是否可靠

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

5.3.2 檢測參與者是否誠實

命題4 在秘密恢復階段，也可通過式(3)檢驗參與者是否誠實。

6 方案的具體應用

下面用一個例子說明本文方案的可行性。

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

1) 參數選取

2) 秘密分割

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

得到對角矩陣為

3) 秘密恢復

所以，有

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

7 結束語

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

[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] 李濱. 基于特殊訪問權限的差分秘密共享方案[J]. 四川大學學報(自然科學版), 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] 同濟大學數學系編.工程數學線性代數[M]. 北京: 高等教育出版社, 2014. School of Mathematic Sciences, Tongji University . Engineering mathematics, linear algebra[M]. Beijing: Higher Education Press. 2014.

[16] 曹爾強, 張沂, 曹曄, 等. “軟件黑盒子”文件加鎖和加密的一個方法[J]. 長春郵電學院學報,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?），男，陜西寶雞人，博士，北京電子科技學院講師，主要研究方向為密碼理論及其應用。

李文敬（1992?），女，山東濟寧人，北京電子科技學院碩士生，主要研究方向為信息安全。

陳雷（1992?），男，河北邯鄲人，北京電子科技學院碩士生，主要研究方向為信息安全。

畢偉（1980?），男，黑龍江哈爾濱人，博士，中思博安科技（北京）有限公司研究員，主要研究方向為信息安全和區塊鏈技術。

楊濤（1977?），男，安徽蕪湖人，博士，公安部第三研究所副研究員，主要研究方向為信息安全。

2018?01?25；

2018?06?22

信息網絡安全公安部重點實驗室開放基金資助項目（No.C17608）；中國民航信息技術科研基金資助項目（No.CAAC-ITRB-201705）；國家自然科學基金資助項目（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)