基于格的分層無證書代理簽名方案

農(nóng) 強(qiáng)，張棒棒，歐陽玉豪

（1.閩南師范大學(xué) 計(jì)算機(jī)學(xué)院，福建 漳州 363000；2.數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室（閩南師范大學(xué)），福建 漳州 363000）

0 引言

代理簽名是一種特殊的數(shù)字簽名，廣泛應(yīng)用于需要簽名權(quán)力委托的應(yīng)用場合。近年來，為解決基于身份密碼系統(tǒng)中固有的密鑰托管問題，一些無證書代理簽名［1-5］被相繼提出，然而這些代理簽名的安全性主要基于橢圓曲線上的離散對數(shù)或者雙線性對困難問題假設(shè)。隨著量子計(jì)算機(jī)技術(shù)的不斷突破，傳統(tǒng)方案的安全性將受到威脅，而基于格的密碼體制被普遍認(rèn)為是抗量子攻擊的。Gentry 等［6］利用原像采樣構(gòu)造了一類單向陷門函數(shù)，并提出在隨機(jī)預(yù)言機(jī)模型下可證安全的數(shù)字簽名方案，隨后格密碼體制進(jìn)入快速發(fā)展階段。然而原像采樣需要在擁有陷門的情況下獲取原像，導(dǎo)致簽名方案的計(jì)算復(fù)雜度較高。Lyubashevsky［7］在2012 年歐洲密碼年會上摒棄原像采樣函數(shù)，提出拒絕采樣的概念，它構(gòu)造的無陷門格簽名所采用的密鑰是一個小范數(shù)矩陣，而不是陷門基，遵循Fiat-Shamir 模式，顯著地提高了簽名效率。Ducas等［8］在Lyubashevsky 工作的基礎(chǔ)上提出雙峰高斯分布以減小標(biāo)準(zhǔn)差的方式提高了效率，卻被證明存在側(cè)信道攻擊［9］，缺乏安全性。

其次，已有的無證書代理簽名方案在大規(guī)模分布式異構(gòu)網(wǎng)絡(luò)環(huán)境中往往會面臨單點(diǎn)失效問題。Horwitz 等［10］首次提出了基于身份的分層簽名方案，一定程度上解決了單點(diǎn)失效問題并支持負(fù)載均衡；Zhang 等［11］首次提出基于無證書的分層簽名方案，該方案不存在密鑰托管問題且簽名尺寸與層次結(jié)構(gòu)的深度無關(guān)。在現(xiàn)實(shí)世界中，代理簽名已被廣泛應(yīng)用于電子商務(wù)、分布式系統(tǒng)、物聯(lián)網(wǎng)和無線自組網(wǎng)等場景，如Verma 等［12］將代理簽名技術(shù)應(yīng)用于醫(yī)療無線傳感器網(wǎng)絡(luò)，以對遠(yuǎn)程無線體域網(wǎng)用戶進(jìn)行基于電子醫(yī)療監(jiān)測的大數(shù)據(jù)采集，在傳輸、存儲和計(jì)算開銷方面都取得了較好的效果；He等［13］將代理簽名技術(shù)應(yīng)用于無人機(jī)網(wǎng)絡(luò)，顯著減少了地面控制中心與無人機(jī)之間的傳播時(shí)延，從而提高了無人機(jī)的工作效率。這些應(yīng)用系統(tǒng)具有網(wǎng)絡(luò)規(guī)模大、節(jié)點(diǎn)數(shù)量多及地理分布廣泛等特點(diǎn)。為了解決單一密鑰生成中心（Key Generation Center，KGC）的瓶頸問題，可通過在代理簽名方案中引入分層機(jī)制，由根KGC 按照層次結(jié)構(gòu)的順序?qū)⒚荑€管理任務(wù)及用戶認(rèn)證權(quán)限分散到其子域KGC，以實(shí)現(xiàn)高效的密鑰管理和負(fù)載均衡。然而，在已提出的分層結(jié)構(gòu)中，根KGC 把密鑰分發(fā)及用戶認(rèn)證的權(quán)限委托給其子域KGC，子域KGC 進(jìn)而向下迭代，用戶作為最底層的葉子節(jié)點(diǎn)，其密鑰僅由其父節(jié)點(diǎn)即最底層的KGC 來分發(fā)，這就造成了系統(tǒng)資源的極大浪費(fèi)。如同在操作系統(tǒng)的多級目錄結(jié)構(gòu)中，只有最底層的目錄才具有存儲普通文件的權(quán)限，而其上層目錄僅能存儲目錄文件，顯然是不合理的。

針對上述問題，在Lyubashevsky［7］提出的拒絕采樣技術(shù)和無陷門格簽名的基礎(chǔ)上，本文構(gòu)造了一類基于格的分層無證書代理簽名方案。該方案是首個允許簽名人來自不同層級隸屬于不同KGC 的代理簽名方案，優(yōu)點(diǎn)是將密鑰分發(fā)及用戶認(rèn)證功能分布到更多的KGC，能夠?qū)崿F(xiàn)更好的負(fù)載均衡且更具靈活性。所提方案在隨機(jī)預(yù)言機(jī)模型下基于格上標(biāo)準(zhǔn)的小整數(shù)解（Short Integer Solution，SIS）困難問題假設(shè)是可證安全的。與已有的基于格的代理簽名方案比較，所提方案具有較低的通信延遲和計(jì)算開銷。相較于傳統(tǒng)的無證書代理簽名方案，所提方案在計(jì)算開銷方面具備優(yōu)勢。

1 基礎(chǔ)知識

1.1 符號說明

令R 表示實(shí)數(shù)集，Z 表示整數(shù)集。用粗體大寫字母表示矩陣，如A；粗體小寫字母表示向量，如a。AT表示矩陣A的轉(zhuǎn)置，‖a‖表示向量a的歐幾里得范數(shù)。令OS（Original Signer）表示原始簽名人，PS（Proxy Signer）表示代理簽名人。OSj表示第j層原始簽名人，PSi表示第i層代理簽名人，表示第j層原始簽名人的身份信息表示第i層代理簽名人的身份信息。

1.2 格的定義

1.3 拒絕采樣

根據(jù)文獻(xiàn)［7］的定義，設(shè)V∈Zm，σ∈R 且V中所有元素的范數(shù)都小于T，滿足σ=，且h：V→R 是一個概率分布。那么存在一個常數(shù)E=O(1)滿足算法alg-A 的分布和算法alg-B 的分布之間的統(tǒng)計(jì)距離為2-w(logm)/E，且算法alg-A 有輸出的概率至少為(1-2-w(logm))/E。

1.4 困難問題

SISq，m，β問題：給定素?cái)?shù)q，矩陣和實(shí)數(shù)β，找到一個非零向量e∈Zm使得Ae≡0 mo dq且‖e‖≤β。

2 安全模型

Boldyreva 等［14］首次給出了代理簽名的安全定義，并建立了形式化的安全模型。在該模型中，代理簽名的安全性要求在適應(yīng)性選擇授權(quán)文件和消息攻擊下，任意一個OS 或PS 均無法偽造一個有效授權(quán)，也無法偽造一個有效代理簽名。結(jié)合Al-Riyami 等［15］所定義的無證書簽名體制下兩類敵手，即用戶攻擊和KGC 攻擊，分別考慮OS 和PS 的安全性，把分層無證書代理簽名的敵手定義為Ai（i∈[1，4]），具體分類如下：

1）A1：敵手不知道PS 的完整密鑰但可以替換任意用戶的公鑰，其試圖偽造一個有效代理簽名。

2）A2：敵手不知道OS 的完整密鑰但可以替換任意用戶的公鑰，其試圖偽造一個有效授權(quán)。

3）A3：敵手不知道PS 的完整密鑰但擁有系統(tǒng)主密鑰，其試圖偽造一個有效代理簽名。

4）A4：敵手不知道OS 的完整密鑰但擁有系統(tǒng)主密鑰，其試圖偽造一個有效授權(quán)。

綜上所述，分層無證書代理簽名的不可偽造性通過敵手Ai和挑戰(zhàn)者C之間模擬的4 個游戲來定義，游戲采用與文獻(xiàn)［1-5］類似的隨機(jī)預(yù)言機(jī)模型。Ai在每個游戲中經(jīng)過自適應(yīng)詢問后，最終輸出授權(quán)文件ω*上的有效授權(quán)cert*或消息μ*上的有效代理簽名Sig*。如果滿足以下條件，認(rèn)為Ai贏得了游戲。

3 分層無證書代理簽名方案

本章以Lyubashevsky［7］的工作為基礎(chǔ)，構(gòu)建了一種格上的分層無證書代理簽名方案，所提方案既不使用原像采樣技術(shù)也不使用陷門技術(shù)，由如下算法構(gòu)成：

4 安全分析

定理1在隨機(jī)預(yù)言機(jī)模型下，若存在多項(xiàng)式時(shí)間敵手A1能夠以不可忽略的概率成功偽造代理簽名，那么存在一個挑戰(zhàn)者C也能夠以不可忽略的概率解決SIS 困難問題。

證明 在SIS 困難問題假設(shè)下，利用A1和挑戰(zhàn)者C之間的游戲來證明在沒有PS 完整密鑰的情況下代理簽名是不可偽造的，過程如下：

定理3在隨機(jī)預(yù)言機(jī)模型下，若存在多項(xiàng)式時(shí)間敵手A3能夠以不可忽略的概率成功偽造代理簽名，那么存在一個挑戰(zhàn)者C也能夠以不可忽略概率解決SIS 困難問題。

證明 在SIS 困難問題假設(shè)下，利用A3和挑戰(zhàn)者C之間的游戲來證明在沒有PS 完整密鑰的情況下代理簽名是不可偽造。過程如下：

定理4在隨機(jī)預(yù)言機(jī)模型下，若存在多項(xiàng)式時(shí)間敵手A4能夠以不可忽略的概率成功偽造授權(quán)，那么存在一個挑戰(zhàn)者C也能夠以不可忽略的概率解決SIS 困難問題。

證明 在SIS 困難問題假設(shè)下，利用A4和挑戰(zhàn)者C之間的游戲來證明在沒有OS 完整密鑰的情況下無法偽造代理授權(quán)。

C模擬的詢問預(yù)言機(jī)與定理3 類似，區(qū)別在于A4無需詢問H4，H5和簽名預(yù)言機(jī)。當(dāng)A4結(jié)束詢問階段后，輸出身份和授權(quán)文件上有效的偽造代理授權(quán)。由定理2 的證明過程很容易證明其簽名不可偽造，這里不再贅述。

5 性能評價(jià)

將所提方案與傳統(tǒng)的較為高效的無雙線性對的無證書代理簽名方案［3］和現(xiàn)有基于格的代理簽名方案［17-19］相比較。Shor［20］已經(jīng)證明傳統(tǒng)方案所依賴的經(jīng)典數(shù)論難題，如RSA 問題和離散對數(shù)問題，都可以用量子計(jì)算機(jī)以多項(xiàng)式時(shí)間求解，即使取任意長度的密鑰。而格中的很多難題，如SIS，已被證明是NP 困難的，因此基于格的密碼體制被普遍認(rèn)為是抗量子攻擊的。

實(shí)驗(yàn)采用的硬件環(huán)境為Intel Core i7-8550u CPU 和DDR3 8 GB RAM，操作系統(tǒng)為Windows 10，使用JAVA JDK 9.0.4 在IDEA 2020 上通過JBLAS 矩陣運(yùn)算庫和JPBC 2.0.0密碼庫模擬相關(guān)的密碼運(yùn)算。為了保證方案在實(shí)施過程中的安全性，對于所提方案和現(xiàn)有基于格的代理簽名方案，參考文獻(xiàn)［7］的系統(tǒng)參數(shù)設(shè)置，取n=512，q=227，d=1，k=80，m=64+nlogq/log(2d+1) ≈8 786，κ=28 和σ=≈31 945，每種運(yùn)算運(yùn)行一百萬次取其耗時(shí)均值，得出矩陣向量乘法耗時(shí)TM≈0.514 ms，向量模加法耗時(shí)TA≈0.024 ms。對于傳統(tǒng)方案，在不失一般性的前提下，設(shè)G是一個階為q的循環(huán)加法群，生成元P∈G為非奇異橢圓曲線y2=x3+ax+bmodp上的點(diǎn)，其中a，b∈，p和q為160 比特素?cái)?shù)，得出標(biāo)量乘耗時(shí)Tm≈4.749 ms，標(biāo)量加耗時(shí)Ta≈0.019 ms。

表1 比較了各方案的簽名和驗(yàn)證開銷。從表1 可以看出，所提方案的代理簽名和驗(yàn)證開銷與層級無關(guān)，驗(yàn)證效率要優(yōu)于其他方案。

表1 簽名和驗(yàn)證開銷比較 單位：msTab.1 Signature and verification overhead comparison unit：ms

表2 給出了所提方案的層級對通信開銷的影響。由于層級l通常是一個小整數(shù)，從表2 可以看出，所提方案的代理公鑰尺寸是一個常數(shù)，與層級無關(guān)，授權(quán)證書、代理密鑰和簽名尺寸也非層級的線性量。

表2 層級對通信開銷的影響 單位：bitTab.2 Impact of hierarchy on communication overhead unit：bit

表3 比較了各方案的代理密鑰和簽名尺寸。由于所比較的方案均為無分層結(jié)構(gòu)，表3 中只給出所提方案的參數(shù)i和j取值均為1 的情形。文獻(xiàn)［17］方案中的參數(shù)l′為哈希函數(shù)的輸出長度，取l′=80。文獻(xiàn)［18］方案中的參數(shù)λ′為系統(tǒng)安全參數(shù)，取λ′=512。從表3 可以看出，與其他基于格的代理簽名方案相比較，所提方案的代理密鑰和簽名尺寸較小，而傳統(tǒng)的基于離散對數(shù)問題的無證書代理簽名方案在存儲和通信開銷上更具優(yōu)勢。

表3 代理密鑰和簽名尺寸比較 單位：bitTab.3 Proxy key and signature size comparison unit：bit

6 結(jié)語

隨著量子計(jì)算機(jī)技術(shù)的不斷成熟，已有基于經(jīng)典數(shù)論難題的無證書代理簽名將不再安全，設(shè)計(jì)后量子時(shí)代安全的替代方案已迫在眉睫。基于SIS 難題假設(shè)，結(jié)合拒絕采樣技術(shù)和無陷門格簽名，本文構(gòu)造一種分層無證書代理簽名方案，其密碼操作時(shí)間復(fù)雜度與層次的深度無關(guān)。該方案首次實(shí)現(xiàn)了不同層級隸屬不同KGC 的兩個用戶之間的代理簽名權(quán)限委托，非常適合大規(guī)模用戶的使用，對提高已有層次密碼系統(tǒng)的均衡負(fù)載能力也具有指導(dǎo)意義。本文方案的性能明顯優(yōu)于已有的基于格的代理簽名方案，相較于傳統(tǒng)方案，其計(jì)算開銷較小，而密鑰和簽名尺寸較大，這也是當(dāng)前格密碼體制的固有弊端。為進(jìn)一步提升方案的空間效率，下一步的研究將逐步關(guān)注能結(jié)合傳統(tǒng)橢圓曲線密碼與格密碼的混合公鑰密碼算法，構(gòu)造更為高效的分層無證書代理簽名方案。