基于格的無證書盲簽名方案

張小萍

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院,廣西南寧530004）

基于身份的簽名體制[1]是利用用戶的身份信息作為公鑰,不需要證書去認(rèn)證,由私鑰生成中心（KGC）來生成用戶私鑰,這樣就大大簡化了PKI對證書的管理,降低了密鑰管理的開銷.但是,由于KGC掌握了所有用戶的私鑰,所以存在著密鑰托管問題,一旦KGC不可信或者系統(tǒng)主密鑰泄露,所有用戶的私鑰都將變得不安全.無證書的公鑰密碼體制[2]的提出解決了密鑰托管問題,在無證書的密碼體制中,用戶身份信息作為用戶的部分公鑰,KGC只生成用戶的部分私鑰,無法掌握用戶的完整私鑰,所以基于無證書的簽名比基于身份的簽名安全性更強(qiáng),比傳統(tǒng)基于證書的簽名效率更高.

盲簽名[3]是一種特殊簽名,在簽名人和消息擁有者的交互協(xié)議中,簽名人在不知道具體消息內(nèi)容的情況下對消息進(jìn)行簽名,簽名人也無法將簽名的中間過程和最終簽名聯(lián)系起來.由于盲簽名具有保護(hù)消息擁有者隱私的性質(zhì),因此盲簽名在電子選舉、電子投票、電子現(xiàn)金中有許多重要的應(yīng)用.

無證書的盲簽名是將無證書的密碼體制和盲簽名相結(jié)合的簽名方案,目前已有的無證書的盲簽名方案[4-6]是基于整數(shù)分解和離散對數(shù)等數(shù)論假設(shè)難題提出的,在量子計(jì)算機(jī)下,基于數(shù)論假設(shè)難題被證明是可以在多項(xiàng)式時(shí)間內(nèi)求解的[7],尋找能夠抵抗量子攻擊的公鑰密碼體制成為急需解決的問題.基于格構(gòu)建的公鑰密碼體制具有抵抗量子攻擊的優(yōu)點(diǎn),目前為止發(fā)現(xiàn)最快攻擊格困難問題算法的時(shí)間復(fù)雜度還不存在亞指數(shù)級,達(dá)到了指數(shù)級,這為格密碼體制在量子攻擊的安全性提供了保障.在格基上構(gòu)建無證書的簽名已經(jīng)獲得了一些研究成果,以格困難問題構(gòu)建了無證書的加密方案[8],無證書簽名[9]和前向安全的簽名方案[10]以及無證書代理重簽名方案[11],但是還沒有出現(xiàn)格上無證書的盲簽名方案.

2012年,Lyubashevsky利用拒絕采樣技術(shù)提出一個(gè)無陷門的格簽名方案[12],拒絕采樣算法的核心思想是使輸出簽名的分布與所使用的密鑰分布相互獨(dú)立,無法從簽名分析出密鑰的分布特征.相對于已有的抽樣技術(shù)的簽名方案,這個(gè)簽名方案的效率比較高.本文在格上提出一個(gè)無證書的盲簽名方案,方案使用文獻(xiàn)[9]提出的矩陣采樣算法來生成用戶的部分私鑰,以拒絕采樣算法來生成簽名.在格上最小整數(shù)解困難問題的假設(shè)下,提出方案滿足隨機(jī)語言模型下選擇消息和選擇身份攻擊的不可偽造性.

1 預(yù)備知識

1.1 格上的相關(guān)定義

定義1格：令B=[b1,b2,...,bm]∈Rn×m是一組基,其中向量b1,b2,...,bm∈Rn并且線性無關(guān),定義由一組基B生成的格Λ=L（B）={Bv|v∈Zn}.

定義2 q模格：對于q∈Z,u∈Z nq和A∈Z n×m,定義2種整數(shù)格Λ⊥（A）={e∈Zm：Ae=0 modq}和=Λ⊥u（A）{e∈Zm：Ae=umodq}.

定義3格上離散高斯分布：令s＞0,c∈Rn,Λ是一個(gè)格,則Λ上的高斯分布是其中ρs,c（x）=exp（-π‖x-c‖2/s2）.

定義4小整數(shù)解問題（SISq,n,m,β）：給定q∈Z和A∈Zn×m,β（n）是一個(gè)有界多項(xiàng)式函數(shù),求解非零向量滿足Ae=0 modq.

1.2 格上的相關(guān)技術(shù)

定理1格陷門生成技術(shù)[13]：給定n,q≥2,m≥（5+3θ）nlogq,θ是一個(gè)固定常數(shù),存在一個(gè)概率多項(xiàng)式算法TrapGen（q,m,n）輸出且滿足：A在統(tǒng)計(jì)上接近于上的均勻分布,TA是Λ⊥（A）上的基,

定理3拒絕采樣算法：若V是Zm的一個(gè)子集并且V中所有元素的范數(shù)都小于h：V→R是一個(gè)概率分布.若s←S表示從集合S中均勻隨機(jī)選擇一個(gè)元素s.

那么存在一個(gè)常數(shù)M=O（1）使算法A和算法F兩者分布的統(tǒng)計(jì)距離不超過2-w(logm）/M.

2 無證書盲簽名方案（CLBS）的定義與安全性要求

2.1 形式化定義

一個(gè)CLBS方案由下面4個(gè)多項(xiàng)式時(shí)間算法組成：

（1）系統(tǒng)初始化：輸入安全參數(shù)n,輸出系統(tǒng)主密鑰makey和系統(tǒng)公開參數(shù)para.

（2）密鑰提?。狠斎胂到y(tǒng)主密鑰makey,系統(tǒng)公開參數(shù)para和簽名人身份信息ID,生成簽名人的部分私鑰DID并發(fā)送給簽名人,簽名人選擇一個(gè)秘密值SID,根據(jù)SID和DID,獲得簽名人的私鑰skID和公鑰pkID.

（3）盲簽名生成：輸入系統(tǒng)公開參數(shù)para,欲簽名消息msg,簽名人身份信息ID和私鑰skID,簽名人和用戶之間進(jìn)行一系列交互協(xié)議后輸出簽名sig.

（4）簽名驗(yàn)證：輸入系統(tǒng)公開參數(shù)para,簽名人ID和公鑰pkID以及消息簽名對（msg,sig）,對簽名進(jìn)行驗(yàn)證,若簽名驗(yàn)證成功則輸出是,否則輸出否.

2.2 安全性要求

（1）盲性：簽名者在簽名時(shí)無法獲得簽名的內(nèi)容,事后也無法將最終簽名和某個(gè)簽名過程聯(lián)系起來.

（2）不可偽造性：無證書盲簽名方案定義了2種敵手AI和A∏,其中AI不知道系統(tǒng)主密鑰,但能對簽名人秘密值對應(yīng)的部分公鑰進(jìn)行替換,用于模擬外部攻擊者;A∏可以獲得系統(tǒng)主密鑰,但不能替換簽名人公鑰,用于模擬內(nèi)部攻擊者.如果方案能夠抵抗這2種敵手的存在性偽造攻擊,那么方案就具有不可偽造性.

3 格上CLBS簽名方案

3.1 系統(tǒng)初始化

選擇安全的參數(shù)n,q＞2是一個(gè)素?cái)?shù),b,λ是正整數(shù),m1＞2nlogq,m2＞64+nlogq（/2b+1）,m=m1+m2,運(yùn)行TrapGen（n,m,q）,輸出一個(gè)校驗(yàn)矩陣和Λ⊥（A）的一組基.然后,KGC選擇2個(gè)安全的哈希函數(shù)再選擇一個(gè)隨機(jī)矩陣公開參數(shù)para={A,B,H1,H2）,KGC的主私鑰是TA.

3.2 密鑰生成

用戶（身份為ID）密鑰的生成具體步驟如下：

①KGC運(yùn)行采樣算法SampleMa（tA,TA,s,H（1ID））,輸出一個(gè)矩陣并發(fā)送給用戶就是用戶的部分私鑰.

③用戶計(jì)算PID=BSID,用戶的完整私鑰就是skID=（DID,SID）,完整公鑰是pkID=（H1（ID）,PID）.

3.3 盲簽名生成

假設(shè)要簽名的消息是msg,簽名人（身份為ID）和消息擁有者U之間的交互過程由以下步驟組成：

②盲化：U收到c′ 后隨機(jī)選擇3個(gè)向量計(jì)算發(fā)送給簽名人.

④去盲：消息擁有者U計(jì)算,輸出簽名sig=（msg,ε,z,c）.

3.4 簽名驗(yàn)證

任何驗(yàn)證人都可以通過下面的計(jì)算進(jìn)行驗(yàn)證簽名的正確性.

4 安全性分析

4.1 正確性

定理4提出的CLBS方案滿足正確性.

證明

4.2 盲性

定理5提出的無證書盲簽名滿足盲性.

證明：假設(shè)（msg,ε,z,c）是任意一個(gè)有效的盲簽名,是某次盲簽名過程中簽名人獲得的視圖,考查下面3個(gè)關(guān)系式

需要證明滿足（1）（2）式的盲因子也滿足（3）式.因?yàn)椋╩sg,ε,z,c）是一個(gè)有效的盲簽名,所以

所以由（1）、（2）式求解出（α1,α2,β）滿足（3）式,任意一個(gè)有效簽名（msg,ε,z,c）和中間視圖之間都可以確定唯一的一組盲因子而不產(chǎn)生矛盾,簽名者無法將簽名的中間視圖和最終的某個(gè)有效簽名對應(yīng)起來.所以,提出的方案滿足盲性.

4.3 不可偽造性

定理7在隨機(jī)預(yù)言模型下,如果存在敵手AI能在多項(xiàng)式時(shí)間內(nèi),最多經(jīng)過q1次H1詢問,q2次H2詢問,qb次部分密鑰詢問,qm次秘密值詢問,qp次公鑰詢問,qt次公鑰替換詢問,qs次簽名詢問以不可忽略的概率θ偽造簽名,那么就存在挑戰(zhàn)者CH利用敵手AI可以在多項(xiàng)式時(shí)間內(nèi)以概率θ2/（2qp（q2+qs））解決SISq,n,m,β問題.

證明：挑戰(zhàn)者CH和敵手AI以下面的步驟進(jìn)行游戲

（1）系統(tǒng)初始化：選擇安全的參數(shù)n,q＞2是一個(gè)素?cái)?shù),b,λ是正整數(shù),m1＞2nlogq,m2＞64+nlogq/（2b+1）,.隨機(jī)選擇2個(gè)矩陣,初始化3個(gè)表L1,L2和LS.

（2）AI可以對CH發(fā)起以下的詢問：

H1詢問：敵手AI發(fā)送IDi給挑戰(zhàn)者CH,希望獲得H1（IDi）,CH先查詢表L1,若表L1中已有身份IDi,則將其對應(yīng)的FID?發(fā)給AI;CH選擇隨機(jī)的,計(jì)算,將存入表L1,將FID?發(fā)送給AI.H2詢問：敵手AI發(fā)送（c,msg）給挑戰(zhàn)者CH,CH先查詢表L2,若表L2中已有（c,msg）對應(yīng)的哈希值,就直接發(fā)送給AI,否則,隨機(jī)選擇,將（c,msg,ε）存入表L2,將CH發(fā)送給AI.

部分私鑰詢問：敵手AI向挑戰(zhàn)者CH發(fā)送IDi希望獲得IDi的部分私鑰,否則挑戰(zhàn)者CH查詢表L1,若已有身份IDi,則將其對應(yīng)的發(fā)給AI,否則先進(jìn)行H1詢問,再返回給AI.

秘密值詢問：敵手AI向挑戰(zhàn)者CH發(fā)送IDi,希望獲得IDi的秘密值,挑戰(zhàn)者CH查詢表L1,若L1中已有身份IDi,則將其對應(yīng)的發(fā)給AI,否則先進(jìn)行H1詢問,再返回給AI.

公鑰詢問：敵手AI向挑戰(zhàn)者CH發(fā)送IDi希望獲得IDi的公鑰,挑戰(zhàn)者CH查詢表L1,若L1已有身份IDi,則將其對應(yīng)的公鑰發(fā)給AI,否則先進(jìn)行H1詢問.

公鑰替換詢問：敵手AI向挑戰(zhàn)者CH發(fā)送,若L1中已有身份IDi,則用替換掉原來的對應(yīng)值將更新后的存回表L1.否則先進(jìn)行H1詢問,再進(jìn)行更新.

簽名詢問：CH用表LS維護(hù)簽名詢問.當(dāng)AI想獲得（IDi,msg）的盲簽名時(shí),若在表LS中找到相應(yīng)信息就返回給AI,如果找不到,就由CH按照第3章盲簽名的生成過程生成簽名（IDi,msg,ε,z,c）并保存到表LS并發(fā)給AI.

（3）偽造簽名：敵手AI成功偽造出一個(gè)身份ID*的有效簽名（msg*,ε*,z*,c*）.其中ID*沒有進(jìn)行過部分私鑰詢問,（ID*,msg*）沒有進(jìn)行過簽名詢問,敵手AI選擇身份ID*偽造簽名的概率是1/qp.在沒有進(jìn)行H2詢問的情況下,敵手AI猜對ε*的概率是（1/3）k.

根據(jù)分叉引理[14],可以至少以概率生成身份ID*關(guān)于消息msg*的另一個(gè)有效簽名（msg*,ε*,z*,c*）,那么滿足

可以將z*和z′表示成以下形式

那么可以得到

所以挑戰(zhàn)者CH在多項(xiàng)式時(shí)間內(nèi)至少以概率（2q（pq2+q）s）解決SISq,n,m,β困難問題,其中

定理8在隨機(jī)預(yù)言模型下,如果存在敵手A∏能在多項(xiàng)式時(shí)間內(nèi),最多經(jīng)過q1次H1詢問,q2次H2詢問,qb次部分密鑰詢問,qm次秘密值詢問,qp次公鑰詢問,qs次簽名詢問以不可忽略的概率θ偽造簽名,那么就存在挑戰(zhàn)者CH利用敵手A∏可以在多項(xiàng)式時(shí)間內(nèi)以概率θ2/（2qp（q2+qs））解決SISq,n,m,β問題.

證明：和定理7的證明類似,敵手A∏和挑戰(zhàn)者CH進(jìn)行一些步驟的游戲,初始化階段和定理7證明相同,在詢問階段敵手不能進(jìn)行公鑰替換詢問,其他詢問也和定理5證明相同.在偽造簽名階段敵手A∏成功偽造出一個(gè)身份ID*的有效簽名（msg*,ε*,z*,c*）.其中ID*沒有進(jìn)行過秘密值詢問（ID*,msg*）沒有進(jìn)行過簽名詢問,敵手選擇身份ID*偽造簽名的概率至少是1/qp.

可以將z*和z′表示成以下形式

那么可以得到

綜合定理5和定理6的證明,提出的CLBS方案可以抵抗兩種敵手AI和A∏的偽造攻擊,所有具有不可偽造性.

5 結(jié)束語

量子計(jì)算機(jī)的發(fā)展使得傳統(tǒng)的無證書盲簽名方案變得不安全,基于格困難問題構(gòu)建的簽名體制具有抵抗量子攻擊的優(yōu)勢,本文提出的格上無證書的盲簽名方案利用格上SIS困難問題并使用了矩陣采樣技術(shù)和無陷門的拒絕采樣技術(shù)來構(gòu)建簽名,經(jīng)證明提出的方案在隨機(jī)預(yù)言模型下具有不可偽造性,并且可以抵抗量子算法攻擊,具有更高的安全性,也豐富了格上關(guān)于無證書密碼簽名方案種類的具體構(gòu)建.在本文提出方案的基礎(chǔ)上,為了滿足一些比較特殊的應(yīng)用需求,構(gòu)建格上無證書的部分盲簽名方案和限制性部分盲簽名方案將是下一步要研究的內(nèi)容.