張 劍， 林昌露，5， 黃可可， 劉亞麗

1. 福建師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院， 福州 350117

2. 福建師范大學(xué) 福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點實驗室， 福州 350007

3. 福建師范大學(xué) 計算機與網(wǎng)絡(luò)空間安全學(xué)院， 福州 350117

4. 江蘇師范大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 徐州 221116

5. 桂林電子科技大學(xué) 廣西可信軟件重點實驗室， 桂林 541004

6. 桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點實驗室， 桂林 541004

1 引言

秘密共享能夠?qū)⒚孛苄畔⒐蚕斫o多個參與者， 使其中的授權(quán)集合可得到秘密信息， 而非授權(quán)集合得不到秘密信息， 是一種有效的秘鑰管理方法. 1979 年， Shamir[1]和Blakley[2]分別基于不同的方法提出了門限秘密共享方案， 當(dāng)達(dá)到一定數(shù)量的參與者提供子秘密時可以重構(gòu)得到秘密的信息， 否則得不到秘密的任何信息. 但由于門限結(jié)構(gòu)存在的局限性， 因此對秘密共享的研究推廣到一般性存取結(jié)構(gòu)中， 如文獻(xiàn)[3-7]構(gòu)造的秘密共享方案實現(xiàn)了具有一般性的存取結(jié)構(gòu). 為了提高秘密共享的效率， 提出了多秘密共享的概念，目前已有大量關(guān)于多秘密共享的研究， 如文獻(xiàn)[8-11]. 多秘密共享可一次共享多個秘密信息， 所消耗的計算資源遠(yuǎn)小于重復(fù)多次的使用單秘密共享， 在密鑰管理中可通過少量的計算操作實現(xiàn)多個密鑰的管理. 同時， 秘密共享也是區(qū)塊鏈、安全多方計算和隱私計算等新技術(shù)的重要組成部分， 在大量數(shù)據(jù)的計算中， 多秘密方案的使用也能夠提高其使用和計算的效率.

現(xiàn)實當(dāng)中對于某些機構(gòu)而言， 機構(gòu)中的人員身份存在等級關(guān)系， 等級高則具有更多的權(quán)限. 為了實現(xiàn)這種多等級場景中的秘密共享， Simmons 于1988 年提出了第一個多等級秘密共享方案(HSS)[12]， 將參與者集合P分為m個不相交的集合P=∪m i=1Li，Li ∩Lj=?(1≤i，j ≤m，i/=j)， 其中L1為最高等級，Lm為最低等級， 每一個集合中的參與者為同一個等級， 不同等級的門限值不同， 參與者個數(shù)達(dá)到門限時可恢復(fù)秘密. 當(dāng)某一等級中的參與者在重構(gòu)時， 參與者個數(shù)小于門限值， 此時更高等級的參與者可參與到該等級的秘密重構(gòu)當(dāng)中， 完成秘密重構(gòu). 如L1門限為2、L2門限為3， 則L1中2 個參與者、L2中3個參與者均可恢復(fù)秘密， 同時L1中1 個參與者和L2中2 個參與者合作也可以恢復(fù)秘密.

1989 年， Brickell[13]提出一個理想的多等級秘密共享方案， 該方案不同的等級選擇不同的多項式生成子秘密， 并且該方案利用向量的線性無關(guān)性構(gòu)造， 需要通過指數(shù)級的計算來確保矩陣的非奇異性， 從而保證方案的安全性， 因此實現(xiàn)該方案的效率過低. 1998 年， Ghodosi 等人[14]基于Shamir (t，n) 門限方案構(gòu)造了一個理想的多等級秘密共享方案， 并且不產(chǎn)生額外的公開值. 其構(gòu)造為逐級生成子秘密， 首先構(gòu)造L1層的秘密分發(fā)多項式， 再根據(jù)L1中全部參與者的子秘密結(jié)合第二級門限求解方程組， 來構(gòu)造第二級的秘密分發(fā)多項式， 依次下去直至生成Lm級的子秘密. 但該構(gòu)造在門限的選擇有一定的限制， 因此只適合門限值較小、同時參與者個數(shù)較少時使用.

2007 年， Tassa[15]利用Birkhoff插值的方法， 構(gòu)造了一個理想的多等級秘密共享方案， 方案的主要思想是構(gòu)造秘密分發(fā)多項式， 在不同等級中計算多項式的導(dǎo)數(shù)， 再根據(jù)其導(dǎo)函數(shù)計算和分發(fā)子秘密.Tassa 和Dyn[16]基于二元插值的思想構(gòu)造了一個新的多等級秘密共享方案. 2009 年， Lin 等人[17]根據(jù)Shamir(t，n) 門限方案， 利用多項式方法構(gòu)造了多等級門限秘密共享方案. 該方案從L1開始構(gòu)造秘密分發(fā)多項式， 計算L1中n1個參與者的子秘密， 再根據(jù)n1與t2的大小確定L2的秘密分發(fā)多項式次數(shù)和對應(yīng)公開點的個數(shù)， 使得L2中滿足(t2，n2) 門限方案的條件， 同時L1中參與者可充當(dāng)L2中的成員參與重構(gòu). 按照這種方式依次執(zhí)行相同的操作， 直至生成所有參與者的子秘密為止. 與前面幾種方案相比，該方案中參與者Pij保存的子秘密信息中包含自身的身份信息xij與多項式的函數(shù)值yij， 對xij沒有進(jìn)行公開， 只有當(dāng)重構(gòu)秘密時， 參與者Pij提供(xij，yij) 進(jìn)行重構(gòu)運算， 可用于一些需要對參與者身份信息保護(hù)的情景.

2014 年， Harn 和Miao[18]提出了第一個基于中國剩余定理的多等級門限秘密共享方案. 該方案中為實現(xiàn)高等級參與者參與低等級秘密重構(gòu)， 每一級都需對更高等級的全部參與者產(chǎn)生對應(yīng)公開值， 因此需要大量公開信息. 針對上述方案[18]存在的問題， Erosy 等人[19]在Harn 和Miao 方案[18]的基礎(chǔ)上， 基于中國剩余定理構(gòu)造了新的多等級門限方案， 通過引入hash 函數(shù)實現(xiàn)對信息進(jìn)一步隱藏， 使得公開值中不會泄露秘密的任何信息. Shima 和Doi[20]基于生成矩陣的方法提出了新的構(gòu)造多等級秘密共享的方法.

近期多位研究者給出了關(guān)于多等級多秘密共享的研究工作， 2020 年， Meriem 和Sadek 在文獻(xiàn)[21]中基于以樹結(jié)構(gòu)表示的企業(yè)層次概念， 提出了一個理想的多等級單秘密共享方案， 采用多項式的構(gòu)造方式實現(xiàn)了特殊的門限結(jié)構(gòu)， 高等級的參與者所擁有的的子秘密更多， 可以充當(dāng)多個低等級參與者. 2020 年， Wu等人在文獻(xiàn)[22] 中基于多項式的門限方案提出一種多等級的圖像秘密共享方案， 該方案中參與者個數(shù)需達(dá)到門限值， 且每個等級中有一個子門限， 每個等級中均也需達(dá)到對應(yīng)門限值的參與者個數(shù)才能夠重構(gòu)出共享的圖像信息. 2020 年， Zhang 等人在文獻(xiàn)[23] 中基于區(qū)塊鏈提出了一種分散公平的多等級門限秘密共享方案， 利用智能合約的方式實現(xiàn)多等級結(jié)構(gòu).

為提高多等級結(jié)構(gòu)秘密共享方案的通信和存儲效率， Basit 等人提出了基于多等級結(jié)構(gòu)的多階段多秘密共享方案[24]， 但該方案僅僅是將多秘密共享與文獻(xiàn)[25] 所提出的多等級秘密共享方案進(jìn)行結(jié)合， 實現(xiàn)了具有順序性的多等級多秘密共享. 當(dāng)某一等級的參與者恢復(fù)任一秘密時， 為實現(xiàn)更高等級參與者可參與重構(gòu)， 需要為所有更高等級參與者生成公開值， 因此公開值個數(shù)與秘密個數(shù)成比例. Singh 等人[26，27]基于Harn 和Miao 方案[18]與多秘密共享方案[25]構(gòu)造了基于CRT 的多等級多秘密共享方案. Tentu 等人[27]基于二次剩余和離散對數(shù)等方法構(gòu)造了新的多等級多秘密方案.

在多等級門限秘密共享方案中， 為實現(xiàn)高等級參與者可參與低等級參與者集的秘密重構(gòu)， 現(xiàn)有實現(xiàn)該功能的方法包括:

(1) 秘密分發(fā)時， 為高等級參與者生成對應(yīng)公開值， 參與者根據(jù)子秘密與指定公開值的運算結(jié)果可參與低等級的秘密重構(gòu);

(2) 秘密分發(fā)過程由高等級開始， 低等級對應(yīng)生成多項式的構(gòu)造與更高等級全部參與者子秘密信息相關(guān);

(3) 如Tassa 方案[15]中的構(gòu)造， 不同等級參與者的子秘密由同一多項式不同階的導(dǎo)函數(shù)計算得到.

本文提出一種新的實現(xiàn)多等級門限秘密共享方案， 運算量小并且方案每一等級只有一個公開的素數(shù)，參與者保存一份子秘密， 當(dāng)高等級參與者參與低等級的秘密重構(gòu)時， 參與者提供子秘密模對應(yīng)素數(shù)后的值即可. 由于現(xiàn)有多等級結(jié)構(gòu)中所構(gòu)造的多秘密方案在秘密分發(fā)階段需要產(chǎn)生大量公開值來確保實現(xiàn)多秘密的多等級秘密共享， 因此本文在構(gòu)造單秘密的方法基礎(chǔ)上提出了兩種多秘密的多等級秘密共享方案， 通過不同的構(gòu)造， 使得更少的公開值即可實現(xiàn)多秘密共享.

文章剩余部分結(jié)構(gòu)為: 第2 節(jié)介紹相關(guān)基礎(chǔ)內(nèi)容， 第3 節(jié)提出新的多等級門限秘密共享方案的構(gòu)造以及方案的分析， 第4-5 節(jié)提出兩類多秘密方案的構(gòu)造， 第6 節(jié)是與相關(guān)工作進(jìn)行對比分析， 第7 節(jié)對文章工作進(jìn)行總結(jié).

2 預(yù)備知識

本節(jié)首先介紹了存取結(jié)構(gòu)的概念和中國剩余定理的具體內(nèi)容， 然后簡要介紹了Shamir 門限秘密共享方案的內(nèi)容以及多等級秘密共享方案的定義.

2.1 存取結(jié)構(gòu)

2.2 中國剩余定理

定義2 中國剩余定理(Chinese remainder theorem， CRT)[28]是求解同余方程組的方法. 隨機選擇兩兩互素的整數(shù)m1，m2，···，mn， 對于任意的整數(shù)r1，r2，···，rn， 滿足ri ∈Zmi(i=1，2，···，n)， Zmi為整數(shù)模mi的剩余類環(huán)， 則下列同余方程組

2.3 Shamir (t，n)-門限秘密共享方案

Shamir[1]用多項式的方法構(gòu)造了一個(t，n)-門限秘密共享方案， 將秘密S ∈Fp(p為大素數(shù)，p ＞n)作為多項式f(x) 的常數(shù)項， 計算f(x) 在n個不同點處的函數(shù)值作為對應(yīng)參與者的子秘密. 從而將秘密拆分為n份發(fā)送給n個參與者P1，P2，···，Pn， 使得任意大于等于t個參與者可以重構(gòu)出秘密S， 任意少于t個參與者不能得到秘密S的任何信息. 具體過程分為下面兩個階段進(jìn)行:

2.4 多等級秘密共享方案

一般的門限結(jié)構(gòu)中， 所有參與者扮演地位相同的角色， 不存在等級的高低. 但是在很多機構(gòu)或商業(yè)公司存在普通職員和管理人員， 職位具有上下級關(guān)系， 因此本文研究一種存在等級關(guān)系的門限結(jié)構(gòu)秘密共享，即多等級秘密共享(hierarchical secret sharing， HSS)[15].

3 方案設(shè)計

本節(jié)將介紹一種新的多等級門限秘密共享方案， 其中第3.1 節(jié)介紹了多等級門限結(jié)構(gòu)秘密共享方案的構(gòu)造方法， 第3.2 節(jié)分析了方案的正確性和安全性.

3.1 多等級門限秘密共享方案

根據(jù)中國剩余定理的多項式形式， 結(jié)合Shamir (t，n)-門限方法構(gòu)造了一種新的多等級門限共享方案.根據(jù)參與者的等級， 分發(fā)給不同等級參與者子秘密時， 通過選擇不同的模數(shù)來實現(xiàn)多等級結(jié)構(gòu)， 同時滿足高等級的參與者可參與低等級的秘密重構(gòu)， 而低等級參與者無法正確參與高等級的秘密重構(gòu). 方案的公開值為m個模數(shù)和每個參與者的身份信息， 減少了大量的公開值個數(shù). 下面介紹方案的具體構(gòu)造方法:

3.2 方案分析

定理2 設(shè)秘密S ∈Zq1，利用3.1 節(jié)中秘密共享方案進(jìn)行秘密共享時，任意至少ti個參與者Plj(l ≤i)可重構(gòu)出秘密S.

證明: 由于多項式f(x)=a0+a1x+···+at-1xt-1， 其系數(shù)構(gòu)造為

因此，ri(＜ti) 個Li中的參與者和(ti-ri) 個高等級的參與者可恢復(fù)秘密S.

定理3 設(shè)秘密S ∈Zq1， 利用3.1 節(jié)中秘密共享方案進(jìn)行秘密共享時， 少于ti個級別不低于i的參與者無法恢復(fù)秘密S.

證明: 由定理2 可知， 更高等級參與者可充當(dāng)?shù)趇級參與者的角色， 因此這里考慮兩種情況: (1) 只存在第i級參與者進(jìn)行重構(gòu); (2) 存在低等級參與者參與重構(gòu)的情況.

4 多秘密方案

本節(jié)對第3 節(jié)提出的單秘密HSS 方案進(jìn)行擴展， 構(gòu)造了兩種多秘密方案. 方案一通過公開部分信息實現(xiàn)多秘密共享， 方案二的構(gòu)造是將多個秘密通過中國剩余定理(CRT) 進(jìn)行聚合， 在模不同素數(shù)時可得到不同的秘密信息.

4.1 擴展方案一

擴展方案一在構(gòu)造多秘密共享時， 采用轉(zhuǎn)換值和單向函數(shù)的方法計算公開值， 同時結(jié)合上述基礎(chǔ)方案的構(gòu)造方法， 以較少的公開值個數(shù)實現(xiàn)了多秘密共享. 每一個秘密都會為所有參與者對應(yīng)生成一個公開值用于秘密重構(gòu)， 同時采用單向函數(shù)來保證子秘密的安全性， 并且秘密恢復(fù)必須按照順序Si(i=k →1) 逐個恢復(fù). 參數(shù)選取和秘密分發(fā)、重構(gòu)過程如下:

· 秘密重構(gòu)階段:

4.2 擴展方案二

本方案是將所有k個秘密通過中國剩余定理的同余方程組進(jìn)行聚合， 產(chǎn)生一個聚合后新的秘密值， 將這個新生成的秘密值通過基礎(chǔ)方案的方法進(jìn)行共享， 再選擇不同的模數(shù)進(jìn)行秘密重構(gòu)， 得到的計算結(jié)果可參與恢復(fù)對應(yīng)的秘密， 減少了大量公開值的產(chǎn)生. 方案的具體構(gòu)造如下:

5 多秘密方案分析

5.1 方案一分析

本節(jié)通過定理4 對方案的正確性和安全性進(jìn)行說明， 定理5 分析了秘密重構(gòu)過程中子秘密的安全性，定理6 說明了在秘密重構(gòu)階段， 已恢復(fù)的秘密不會泄露任何未恢復(fù)秘密的信息， 確保了多秘密的安全性.

定理4 根據(jù)擴展方案一進(jìn)行秘密共享時， 任意大于等于ti個參與者Pi′j(i′≤i) 能夠正確恢復(fù)秘密Sl， 少于ti個則不能得到秘密的任何信息.

5.2 方案二分析

本節(jié)對擴展方案二進(jìn)行分析， 定理7 證明了方案的正確性和安全性， 定理8 分析了方案多秘密的安全性.

定理7 根據(jù)擴展方案二進(jìn)行秘密共享時， 任意大于等于ti個參與者Pi′j(i′≤i) 能夠正確恢復(fù)秘密Sl， 少于ti個則得不到秘密的任何信息.

證明: 根據(jù)定理2， 僅考慮第i級參與者參與重構(gòu)的情況. 關(guān)于秘密Sl的分發(fā)多項式fil(x)≡fi(x)(modpl)≡f(x) (modqi) (modpl)，fil(x) 為ti-1 次多項式， 且yi′j ≡fil(xi′j) (modpl). 因此根據(jù)Shamir (t，n)-門限方案， 當(dāng)至少ti個參與者Pij參與重構(gòu)可恢復(fù)秘密Sl， 而少于ti個參與者不能得到秘密Sl的任何信息.

定理8 根據(jù)擴展方案二進(jìn)行秘密共享， 第i級參與者恢復(fù)秘密Sα?xí)r， 不能根據(jù)秘密Sα得到未恢復(fù)的秘密Sβ(β/=α) 的任何信息.

6 方案對比

6.1 單秘密方案

文獻(xiàn)[17] 將參與者的xij信息作為子秘密的一部分， 將秘密S進(jìn)行分割S=S1||S2， 分別將S1，S2作為多項式的常數(shù)項和一次項系數(shù)進(jìn)行分發(fā). 該方案同樣首先構(gòu)造最高等級的t1-1 次分發(fā)多項式， 根據(jù)該級全部參與者子秘密以及秘密值通過Lagrange 插值的方式構(gòu)造下一級的分發(fā)多項式， 但根據(jù)每一級的門限值和多項式次數(shù)大小進(jìn)行比較， 會產(chǎn)生部分公開的點用于秘密重構(gòu).

文獻(xiàn)[18] 根據(jù)中國剩余定理構(gòu)造多等級門限方案， 為實現(xiàn)不同等級之間的關(guān)系， 在秘密分發(fā)時為高等級參與者生成大量對應(yīng)的公開值， 同時該方案需要選擇大量的互素整數(shù)， 使得高等級能夠正確參與到低等級的秘密重構(gòu)中， 但運算過程較為簡單， 生成子秘密與公開值均為整數(shù)上的模運算.

本文所提出的方案， 首先構(gòu)造t次多項式f(x)， 使得在模不同素數(shù)qi情況下可得到次數(shù)為ti-1 的多項式fi(x)，fi(x) 作為第i級的分發(fā)多項式， 實現(xiàn)了不同等級的門限結(jié)構(gòu). 方案在公開值以及計算復(fù)雜度等方面均實現(xiàn)了較好的性質(zhì). 表1 中對幾個單秘密的多等級門限方案進(jìn)行了比較， 因為秘密重構(gòu)時幾種方案的計算量基本持平， 表中僅考慮方案在秘密分發(fā)時的計算復(fù)雜度.

表1 多等級單秘密方案對比Table 1 Comparison with hierarchical secret sharing schemes

6.2 多秘密方案

文獻(xiàn)[24] 中Basit 等人根據(jù)He 和Dawson[25]的多階段多秘密方案， 結(jié)合多等級秘密共享構(gòu)造了一個多等級結(jié)構(gòu)中的多階段多秘密共享方案. 該方案在構(gòu)造時， 對應(yīng)每個秘密在每個等級都構(gòu)造一個子秘密生成多項式， 為實現(xiàn)等級結(jié)構(gòu)之間的關(guān)系， 所有低等級都需為高等級參與者生成對應(yīng)公開值， 使得高等級參與者可參與到低等級的秘密重構(gòu)中. 因此該方案需要產(chǎn)生大量的公開信息. 文獻(xiàn)[26] 中Singh 等人基于中國剩余定理以及文獻(xiàn)[25] 的多秘密方法構(gòu)造多秘密的多等級共享方案， 每一個秘密均應(yīng)用Harn 和Miao[18]的方法進(jìn)行構(gòu)造， 并根據(jù)多秘密方法產(chǎn)生公開值， 因此具有和文獻(xiàn)[24] 相同的公開值個數(shù). 多等級多秘密共享方案對比如表2 中所示， 其中k為共享秘密的個數(shù).

表2 多等級多秘密方案對比Table 2 Comparison of hierarchical multi-secret sharing schemes

本文所構(gòu)造的多秘密方案一利用多秘密方案的構(gòu)造方式， 每個參與者對應(yīng)不同的秘密有一個公開值作為參與該秘密重構(gòu)的子秘密， 同時利用單向函數(shù)的構(gòu)造， 確定秘密恢復(fù)時的順序性， 當(dāng)按照這個順序進(jìn)行重構(gòu)時， 可以確保還未恢復(fù)秘密的安全性. 多秘密方案二根據(jù)中國剩余定理的思想， 將多個秘密的信息隱藏在同一個多項式中， 從而只公開模數(shù)以及參與者的身份信息即可.

7 結(jié)論

本文提出了一種新的構(gòu)造多等級門限結(jié)構(gòu)上的秘密共享方案， 方案基于多項式構(gòu)造， 計算簡單并且公開值個數(shù)較少. 分發(fā)子秘密時根據(jù)參與者等級選擇不同的模數(shù)， 同時參與者在重構(gòu)秘密時根據(jù)對應(yīng)等級進(jìn)行模運算， 并發(fā)送參與重構(gòu)以此可實現(xiàn)多等級結(jié)構(gòu)并且高等級參與者可參與到低等級的秘密重構(gòu)當(dāng)中. 在此基礎(chǔ)上構(gòu)造了兩種新的多秘密方案， 相比其他相關(guān)方案而言， 本文構(gòu)造的多秘密方案運算簡單， 同時所產(chǎn)生的公開值個數(shù)少， 具有更好的性質(zhì).