格上可追溯的匿名單點(diǎn)登錄方案

湯永利 李 英 趙宗渠 李星宇 王瀚博

（河南理工大學(xué)軟件學(xué)院 河南 焦作 454003）

身份認(rèn)證協(xié)議使用戶能夠高效、方便地訪問(wèn)遠(yuǎn)程資源.但傳統(tǒng)的身份認(rèn)證協(xié)議僅向用戶提供來(lái)自單一身份驗(yàn)證服務(wù)器的訪問(wèn)服務(wù)提供商，如果用戶試圖通過(guò)使用這些認(rèn)證協(xié)議來(lái)訪問(wèn)多個(gè)獨(dú)立的服務(wù)提供商，則需在不同系統(tǒng)中進(jìn)行注冊(cè)，保存大量的賬號(hào)和口令.這種基于用戶名和認(rèn)證信息的獨(dú)立身份管理系統(tǒng)使所有參與的服務(wù)端和用戶端都需要功能類似的認(rèn)證模塊，導(dǎo)致系統(tǒng)資源的浪費(fèi)，同時(shí)增加用戶認(rèn)證信息被泄露的風(fēng)險(xiǎn).

單點(diǎn)登錄（single sign on, SSO ）方案是允許用戶使用一個(gè)主憑證來(lái)訪問(wèn)多個(gè)在線賬戶方案的總稱，它結(jié)合認(rèn)證與授權(quán)，一般應(yīng)用在多個(gè)應(yīng)用的系統(tǒng)中.用戶只需要登錄1 次，在進(jìn)行身份認(rèn)證后就可以訪問(wèn)相互信任的應(yīng)用系統(tǒng)，解決了獨(dú)立身份管理系統(tǒng)的弊端.

2004 年，Wu 等人[1]首次提出多應(yīng)用系統(tǒng)下的單點(diǎn)登錄方案.2006 年，Mangipudi 等人[2]提出匿名單點(diǎn)登錄（anonymous single sign on, ASSO）方案，解決了用戶訪問(wèn)服務(wù)過(guò)程中的拒絕服務(wù)（DoS）攻擊.2012 年，Chang 等人[3]提出可以解決假冒攻擊的ASSO 方案.2013 年，Wang 等人[4]指出Chang 等人[3]的方案不能有效保護(hù)用戶證書(shū)，進(jìn)而基于RSA 簽名構(gòu)造了ASSO方案.2017 年，Wen 等人[5]提出了一個(gè)基于拉格朗日插值多項(xiàng)式的ASSO 方案，它的匿名僅提供給用戶而不提供給服務(wù)器，易受用戶和服務(wù)器假冒攻擊，且用戶的服務(wù)請(qǐng)求由系統(tǒng)的所有驗(yàn)證者來(lái)驗(yàn)證，而不是由指定的驗(yàn)證者來(lái)驗(yàn)證，這可能對(duì)用戶和驗(yàn)證者都造成潛在隱私泄露風(fēng)險(xiǎn).同年，Gope 等人[6]針對(duì)移動(dòng)云計(jì)算服務(wù)，在限制用戶訪問(wèn)服務(wù)次數(shù)的前提下，提出一個(gè)滿足用戶與服務(wù)提供商間雙向匿名認(rèn)證的方案，解決了用戶單點(diǎn)登錄時(shí)的隱私泄露問(wèn)題.

為解決用戶訪問(wèn)服務(wù)時(shí)的限制問(wèn)題，2018 年，Lee[7]構(gòu)造的基于切比雪夫混沌映射的高效ASSO 方案，該方案在多個(gè)服務(wù)提供商串通時(shí)，不能實(shí)現(xiàn)用戶對(duì)服務(wù)提供商的匿名.Jegadeesan 等人[8]基于ECDLP困難問(wèn)題提出新的解決方案，通過(guò)可信第三方為用戶分發(fā)一個(gè)隨機(jī)值來(lái)生成私鑰，實(shí)現(xiàn)分布式移動(dòng)計(jì)算環(huán)境中用戶對(duì)服務(wù)提供商的匿名認(rèn)證.2019 年，Jia等人[9]針對(duì)移動(dòng)邊緣計(jì)算提出基于身份的匿名認(rèn)證方案，利用k-改進(jìn)的雙線性逆Diffie-Hellman（kmodified bilinear inverse Diffie-Hellman,k-mBIDH）困難問(wèn)題，在可信第三方不參與的情況下，通過(guò)服務(wù)器對(duì)用戶登錄消息的解密，實(shí)現(xiàn)用戶的匿名單點(diǎn)登錄.

現(xiàn)存的ASSO 方案[8-13]可以實(shí)現(xiàn)用戶匿名訪問(wèn)服務(wù)，但此時(shí)用戶的完全匿名性，導(dǎo)致用戶可以隨意進(jìn)行惡意操作，從事非法活動(dòng)而不被問(wèn)責(zé).對(duì)于這種情況，應(yīng)該有監(jiān)督機(jī)構(gòu)揭示出用戶的身份，必要時(shí)對(duì)用戶追責(zé)，追溯出用戶所有的服務(wù)請(qǐng)求.2018 年，Han等人[14]引入指定驗(yàn)證者簽名[15-18]技術(shù)，提出一個(gè)只能由指定服務(wù)提供商驗(yàn)證的ASSO 方案，實(shí)現(xiàn)服務(wù)不可鏈接性.并在此基礎(chǔ)上構(gòu)造出新的ASSO 方案[19]，該方案在指定的服務(wù)提供商不可用時(shí)，中央驗(yàn)證者可以授權(quán)新的服務(wù)商代表原始服務(wù)商對(duì)用戶進(jìn)行認(rèn)證，同時(shí)也可以揭示用戶身份并追溯用戶的服務(wù)請(qǐng)求，實(shí)現(xiàn)問(wèn)責(zé)性.2021 年，Zhang 等人[20]構(gòu)造出輕量級(jí)的ASSO 方案，采用PS 簽名[21]構(gòu)造匿名憑證，利用非交互零知識(shí)證明技術(shù)對(duì)用戶信息進(jìn)行選擇性披露，在保護(hù)用戶隱私的情況下實(shí)現(xiàn)用戶的匿名單點(diǎn)登錄；在解密機(jī)構(gòu)的協(xié)助下，對(duì)行為不端的用戶進(jìn)行問(wèn)責(zé).該方案有效降低通信開(kāi)銷，但匿名憑證與非交互零知識(shí)證明的生成，導(dǎo)致其計(jì)算效率較低.

文獻(xiàn)[8-14,19-20]的ASSO 方案都是基于大整數(shù)分解和離散對(duì)數(shù)等數(shù)論難題設(shè)計(jì)的，隨著量子計(jì)算領(lǐng)域的研究不斷取得突破，解決這些數(shù)論難題成為可能[22].目前國(guó)際后量子密碼研究中，格密碼體制因其安全性高、運(yùn)算速度快等特點(diǎn)受到了廣泛關(guān)注，已知格上的最短向量問(wèn)題（shortest vector problem,SVP）和最近向量問(wèn)題（closest vector problem, CVP）等難題在量子計(jì)算機(jī)下還未存在概率多項(xiàng)式時(shí)間高效求解算法[23].

為解決匿名單點(diǎn)登錄過(guò)程中用戶不誠(chéng)信行為的問(wèn)題，本文采用格上基于身份的密碼體制，提出了一個(gè)格上可追溯的匿名單點(diǎn)登錄方案.主要貢獻(xiàn)有4 點(diǎn)：

1）構(gòu)建格上基于身份的可追溯的ASSO 方案.利用格上基于身份的密碼體制緩解現(xiàn)有單點(diǎn)登錄方案中公鑰證書(shū)管理問(wèn)題，采用指定驗(yàn)證者簽名技術(shù)[24]實(shí)現(xiàn)用戶服務(wù)請(qǐng)求的定向驗(yàn)證.方案的不可鏈接性、不可偽造性與可追溯性都可規(guī)約至非齊次小整數(shù)解（inhomogeneous small integer solution，ISIS）問(wèn)題上.在NIST 后量子密碼標(biāo)準(zhǔn)化進(jìn)程的不斷推進(jìn)下，本方案可以有效抵抗量子攻擊[23,25-26].

2）采用授權(quán)認(rèn)證標(biāo)簽和假名技術(shù)[27]實(shí)現(xiàn)用戶匿名性.為保護(hù)用戶隱私，利用假名(pv,qv)進(jìn)行用戶身份認(rèn)證與服務(wù)請(qǐng)求.由于假名是一次性的，因此所提方案可以有效抵抗假冒攻擊與重放攻擊.同時(shí)在假名泄露的情況下，敵手也無(wú)法從多個(gè)已泄露的假名中揭露出任何有關(guān)用戶身份的信息，有效解決跨多個(gè)驗(yàn)證器驗(yàn)證過(guò)程中的用戶信息泄露問(wèn)題.

4）在達(dá)到112 b，230 b，292 b 的量子安全級(jí)別下進(jìn)行方案效率分析.實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的單點(diǎn)登錄方案[4,7,19]相比，本方案生成的密鑰尺寸更小，在降低通信開(kāi)銷的同時(shí)有效提高計(jì)算效率，具有更強(qiáng)的安全性.

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

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

矩陣B=(b1,b2,…,bm)∈Zn×m，b1,b2,…,bm∈Zn為m個(gè)線性無(wú)關(guān)的向量.由B生成的格定義為n和m是整數(shù)，且分別是格 Λ的維數(shù)和秩，B是Λ的基.

設(shè)n為安全參數(shù)，素?cái)?shù)q∈Z為模，大寫(xiě)黑體字母（如A）為矩陣，AT為A的轉(zhuǎn)置，小寫(xiě)黑體字母（如a）為列向量，以及||a||=是向量a=(a1,a2,…,an)∈Rn的歐幾里得范數(shù)，表示a是從集合χ中均勻隨機(jī)選取的.poly(n)為n的多項(xiàng)式函數(shù)，logn是n的對(duì)數(shù)關(guān)系函數(shù).

定義1.ISIS 問(wèn)題.設(shè)A∈，實(shí)數(shù)β ＞0.ISISq,n,m,β問(wèn)題的目標(biāo)是給定任意向量y∈Zn，找到一個(gè)非零向量x∈Zm，使Ax=y(modq)和‖x‖≤β成立.當(dāng)y=(0)n時(shí)，可轉(zhuǎn)化為SISq,n,m,β（small integer solution）問(wèn)題，其目標(biāo)是找到一個(gè)非零向量x∈Zm，使Ax=0(modq)和‖x‖≤β成立.

定義2.最短獨(dú)立向量問(wèn)題（shortest independent vector problem, SIVP）.設(shè)矩陣B∈Zn×m是格Λ ∈Zn的基.格 Λ的最短獨(dú)立向量問(wèn)題是找一個(gè)n個(gè)線性無(wú)關(guān)的格向量集合C={c1,c2,…,cn}?Λ，使得‖ci‖=λi(Λ).SIVPγ的目標(biāo)是獲得一個(gè)集合C={c1,c2,…,cn}?Λ，使得‖C‖≤γ·λn(Λ)，其中λn(Λ)為 Λ的第n個(gè)連續(xù)最小值.

引理1.給定正整數(shù)n，多項(xiàng)式界定的m≈ploy(n)，β ≈ploy(n)，素?cái)?shù)q≥β·w.在平均情況下找到SISq,n,m,β和ISISq,n,m,β問(wèn)題的解，與在任意n維格上，在最糟糕的情況下求解SIVPγ問(wèn)題一樣困難，其中

1.2 離散高斯分布

引理2.高斯分布具有2 個(gè)性質(zhì).給定標(biāo)準(zhǔn)差 σ和正整數(shù)m，則：

2 方案模型

2.1 方案流程

系統(tǒng)初始化時(shí)，各參與方必須從被稱為“私鑰生成器（private key generator，PKG）”的可信第三方獲得基于身份的公私鑰.整個(gè)方案流程如圖1 所示，用戶（user，U）加入系統(tǒng)時(shí)，需要把自己的公鑰和身份發(fā)送給中央驗(yàn)證者（central verifier，CV），以便去匿名化.用戶為獲得1 個(gè)票據(jù)，給票據(jù)發(fā)行者（issuer，I）發(fā)送自己的服務(wù)請(qǐng)求，票據(jù)發(fā)行者為用戶生成相應(yīng)的票據(jù).隨后用戶給指定服務(wù)提供商發(fā)送相應(yīng)的認(rèn)證標(biāo)簽，服務(wù)提供商也稱票據(jù)驗(yàn)證者（verifier，V），當(dāng)票據(jù)驗(yàn)證者認(rèn)證標(biāo)簽通過(guò)后，就可授權(quán)用戶去訪問(wèn)服務(wù).當(dāng)用戶出現(xiàn)不誠(chéng)信行為時(shí)，中央驗(yàn)證者可以通過(guò)票據(jù)對(duì)用戶進(jìn)行去匿名化，追溯出用戶的整個(gè)服務(wù)請(qǐng)求.在具體方案中，用戶、中央驗(yàn)證者、票據(jù)發(fā)行者、票據(jù)驗(yàn)證者分別被實(shí)例化為u，cv，iss，v.

Fig.1 Flow chart of the supervised ASSO scheme on lattice圖1 格上可追溯的ASSO 方案流程圖

2.2 形式化定義

可追溯的匿名單點(diǎn)登錄方案由6 個(gè)多項(xiàng)式時(shí)間算法組成.

1）Keygen(1n)：輸入安全參數(shù)n，輸出系統(tǒng)的公共參數(shù)Param以及系統(tǒng)主密鑰msk.

2）ExtractKey(Param,IDj,msk)：輸入系統(tǒng)的公共參數(shù)Param，身份IDj以及系統(tǒng)的主密鑰msk，輸出私鑰skj和公鑰pkj.

3）User-Registration(Inputu(Param,IDu,pku,pkcv)?Inputcv(Param,skcv))：輸入公共參數(shù)Param，用戶身份IDu以及公鑰pku，中央驗(yàn)證者公私鑰(pkcv,skcv)，最終中央驗(yàn)證者在本地列表里存儲(chǔ)(IDu,pku).“?”表示該算法需要在用戶和中央驗(yàn)證者的交互下才可以有正確輸出.

4）Ticket-Issuing(Inputu(Param,Ju,sku)?Inputiss(skiss,Param,pku))：輸入系統(tǒng)的公共參數(shù)Param，票據(jù)發(fā)行者的私鑰skiss，用戶想要訪問(wèn)的服務(wù)請(qǐng)求Ju以及公私鑰(pku,sku)，輸出用戶服務(wù)請(qǐng)求Ju對(duì)應(yīng)的票據(jù)Tu.

6）Ticket-Trace(Inputu(Tu)?Inputcv(Param,skcv))：輸入系統(tǒng)的公共參數(shù)Param和用戶票據(jù)Tu，中央驗(yàn)證者的私鑰skcv.如果追溯成功，則輸出用戶的身份IDu以及其服務(wù)請(qǐng)求Ju，否則返回 “⊥”.

2.3 安全模型

一個(gè)具有可追溯性的匿名單點(diǎn)登錄方案需要滿足用戶服務(wù)的不可鏈接性、票據(jù)的不可偽造性和服務(wù)票據(jù)的可追溯性[19].

定義3.不可鏈接性.要求即使某些票據(jù)驗(yàn)證者與用戶串通時(shí)也不能對(duì)其他用戶的整個(gè)服務(wù)信息進(jìn)行剖析，有效保護(hù)用戶服務(wù)請(qǐng)求的隱私.如果對(duì)于任意概率多項(xiàng)式時(shí)間（probabilistic polynomial time，PPT）算法敵手 A ，A最多進(jìn)行 σ1次票據(jù)發(fā)行詢問(wèn)、σ2次票據(jù)驗(yàn)證詢問(wèn)、σ3次票據(jù)追溯詢問(wèn)，以可忽略的優(yōu)勢(shì)贏得游戲挑戰(zhàn)時(shí)，則稱格上可追溯的匿名單點(diǎn)登錄方案是(σ1,σ2,σ3,ε(?))用戶服務(wù)請(qǐng)求安全的（具體見(jiàn)4.2 節(jié)）.

定義4.不可偽造性.要求即便指定票據(jù)驗(yàn)證者、中央驗(yàn)證者與用戶串通，它們也不能偽造一個(gè)有效的票據(jù).如果對(duì)于任意PPT 敵手 A ，A最多進(jìn)行p次票據(jù)發(fā)行詢問(wèn)時(shí)，對(duì)于所有IDv∈Ju，以可忽略的優(yōu)勢(shì)AdvA=Pr[Ticket-Validating(Inputu?Inputv)→(⊥,(1,Tagv*))]≤ε(?)贏得游戲挑戰(zhàn)時(shí)，稱格上可追溯的匿名單點(diǎn)登錄方案是(p,ε(?))票據(jù)發(fā)行安全的（具體見(jiàn)4.3 節(jié)）.

定義5.可追溯性要求.即便某些用戶串通，它們也無(wú)法生成屬于串通組某一成員的票據(jù)，使得票據(jù)追溯算法無(wú)法捕捉到該票據(jù).本文假設(shè)票據(jù)發(fā)行者是誠(chéng)實(shí)的.如果任意PPT 敵手 A 在最多進(jìn)行k次票據(jù)發(fā)行詢問(wèn)時(shí)，以可忽略的優(yōu)勢(shì)AdvA=Pr[u*≠∈QKu|Ticket-Trace(Inputu?Inputcv)→(J～u)]≤ε(?)贏得所構(gòu)造的游戲挑戰(zhàn)時(shí)，則稱格上可追溯的匿名單點(diǎn)登錄方案是(k,ε(?))可追溯的（具體見(jiàn)4.4 節(jié)）.

3 格上可追溯的匿名單點(diǎn)登錄方案

本文使用方陣，有助于在矩陣本身與行/列向量間執(zhí)行運(yùn)算，從而保持矩陣乘法的平穩(wěn)運(yùn)行.方案包括6 個(gè)階段.

3.1 系統(tǒng)建立階段

運(yùn)行Keygen(1n)算法，以安全參數(shù)n作為算法輸入，最終輸出PKG 的主密鑰msk和系統(tǒng)的公共參數(shù)Param.PKG 執(zhí)行運(yùn)算1）～4）：

Hook模塊設(shè)計(jì)前期，對(duì)大量惡意軟件的反編譯提取其中敏感API調(diào)用代碼。本文通過(guò)大量的動(dòng)態(tài)監(jiān)測(cè)分析其惡意程度，定義了各敏感API的惡意權(quán)重

3.2 密鑰提取階段

密鑰提取階段用來(lái)產(chǎn)生各參與者基于身份的私鑰，此階段使用安全通道進(jìn)行信息發(fā)送.該階段以PKG 的主密鑰、參與者的身份以及公共參數(shù)作為輸入，輸出參與者基于身份的私鑰.用戶為了獲得基于身份的公私鑰，給PKG 發(fā)送它的身份.為了使用戶注冊(cè)階段和票據(jù)追溯階段能夠順利恢復(fù)出用戶身份，設(shè)IDu∈{0,1}64.PKG選擇，計(jì)算lu=A·ru，Ru=H1(IDu,lu)，du=ru+Ru·xmodq，用安全信道將〈lu,du〉發(fā)送給用戶.基于身份的私鑰du如果滿足A·du=lu+Ru·mpk，則是有效的，此時(shí)用戶的公鑰為pku=A·du.使用相同的方法，計(jì)算中央驗(yàn)證者基于身份的公私鑰(dcv,pkcv)，指定票據(jù)驗(yàn)證者基于身份的公私鑰(dv,pkv).

票據(jù)發(fā)行者基于身份的公私鑰生成方式略有不同，票據(jù)發(fā)行者給PKG 發(fā)送身份IDiss.然后PKG 選擇，計(jì)算liss=·A，Riss=H1(IDiss,liss)，diss=riss+Riss·xmodq，最終給票據(jù)發(fā)行者返回〈liss,diss〉.計(jì)算pkiss=·A，則票據(jù)發(fā)行者基于身份的私鑰為diss，公鑰為pkiss.

3.3 用戶注冊(cè)階段

用戶加入系統(tǒng)時(shí)，需要向中央驗(yàn)證者注冊(cè)，以便中央驗(yàn)證者對(duì)用戶去匿名化，追溯出其服務(wù)請(qǐng)求.每個(gè)用戶加入系統(tǒng)時(shí)，選取，計(jì)算2 個(gè)密文c1=然后發(fā)送((c1,c2),lu)給中央驗(yàn)證者，中央驗(yàn)證者收到信息后，計(jì)算IDu=得到用戶的身份IDu，通過(guò)驗(yàn)證pku=lu+H1(IDu,lu)·mpk是否成立，保證用戶身份的合法性，如果成立，則本地存儲(chǔ)用戶的(IDu,pku).

3.4 票據(jù)發(fā)行階段

為獲得1 張票據(jù)，用戶選擇它的服務(wù)信息Ju，Ju由用戶想要訪問(wèn)的服務(wù)所對(duì)應(yīng)驗(yàn)證者的身份IDv組成，即IDv∈Ju.整個(gè)具體過(guò)程如圖2 所示，對(duì)于每個(gè)IDv∈Ju，用戶使用其私鑰du生成1 個(gè)假名(pv,qv)，并發(fā)送給票據(jù)發(fā)行者.票據(jù)發(fā)行者通過(guò)驗(yàn)證A·qv=?pv·H2(f,pv)+pku來(lái)判斷用戶是否為1 個(gè)合法用戶，若是合法用戶，票據(jù)發(fā)行者為用戶生成認(rèn)證標(biāo)簽Tagv=((f,pv,qv),(t,r,zu),(e1,e2),Text,(sv,cv,zv)).(e1,e2)是用中央驗(yàn)證者公鑰pkcv加密IDv所生產(chǎn)的2 個(gè)密文，在票據(jù)追溯時(shí)，完成用戶服務(wù)請(qǐng)求的恢復(fù).簽名(t,r,zu)是用來(lái)驗(yàn)證Tagv的有效性，只有指定的驗(yàn)證者才可以驗(yàn)證.sv是認(rèn)證標(biāo)簽Tagv的序列號(hào)，(sv,cv,zv)是票據(jù)發(fā)行者對(duì)sv的簽名，Text是時(shí)間戳，用來(lái)防止票據(jù)的重放.最終票據(jù)由這些單獨(dú)的標(biāo)簽組成，即Tu={(Dv,Tagv)|IDv∈Ju}∪{(S,c,z)}.

Fig.2 Ticket-Issuing phase圖2 票據(jù)發(fā)行階段

此階段，票據(jù)發(fā)行者使用它的私鑰對(duì)每個(gè)認(rèn)證標(biāo)簽和整個(gè)票據(jù)進(jìn)行簽名，而認(rèn)證標(biāo)簽和整個(gè)票據(jù)的完整性是使用它們各自內(nèi)容的散列sv=H2(pv||qv||e1||e2||t||r||zu||Text)和S=H2(s1||s2||···||s|Ju|)來(lái)保證的.票據(jù)發(fā)行者將票據(jù)發(fā)送給用戶，用戶通過(guò)驗(yàn)證散列值來(lái)驗(yàn)證每個(gè)認(rèn)證標(biāo)簽和整個(gè)票據(jù)的完整性，以及驗(yàn)證簽名來(lái)證明每個(gè)認(rèn)證標(biāo)簽和整個(gè)票據(jù)來(lái)自票據(jù)發(fā)行者.

3.5 票據(jù)驗(yàn)證階段

當(dāng)驗(yàn)證1 個(gè)票據(jù)時(shí)，指定票據(jù)驗(yàn)證者初始化1 個(gè)空表Tv，將身份IDv發(fā)送給用戶.用戶通過(guò)計(jì)算Dv=H3(qu,IDv)，找到對(duì)應(yīng)的標(biāo)簽Tagv，并將Tagv發(fā)送給指定票據(jù)驗(yàn)證者.如圖3 所示，指定票據(jù)驗(yàn)證者通過(guò)判斷(sv,cv,zv)是否屬于Tv，來(lái)防止票據(jù)2 次驗(yàn)證.如果Tagv是個(gè)新鮮的標(biāo)簽，則將(sv,cv,zv)加入Tv，并通過(guò)檢查A·qvpv·H2(f,pv)+pku來(lái)驗(yàn)證用戶是否為合法用戶，檢查zu-·rT)·tmodq,pkv),cvH(AT·zvmodq,sv)來(lái)驗(yàn)證標(biāo)簽的有效性.若全部成立，則通過(guò)驗(yàn)證.

Fig.3 Ticket-Validating phase圖3 票據(jù)驗(yàn)證階段

3.6 票據(jù)追溯階段

票據(jù)追溯階段用來(lái)揭示用戶的身份，完成用戶的去匿名化，追溯出用戶的整個(gè)服務(wù)請(qǐng)求Ju，實(shí)現(xiàn)監(jiān)管性.如圖4 所示，針對(duì)用戶的服務(wù)票據(jù)Tu，中央驗(yàn)證者初始化一個(gè)集合Pu={}.當(dāng)Tagv∈Tu時(shí)，通過(guò)計(jì)算pku=A·qv-pv·H(f,pv)，再根據(jù)本地存儲(chǔ)的(pku,IDu)去匿名化，最后，計(jì)算獲得指定票據(jù)驗(yàn)證者的身份，通過(guò)判斷IDv∈Ju的所有恒等式來(lái)判斷用戶的服務(wù)請(qǐng)求.此時(shí)，如果已知單個(gè)標(biāo)簽，在用戶不合作的情況下，整個(gè)票證信息Tu也可以直接從票據(jù)發(fā)行者處獲得.

Fig.4 Ticket-Trace phase圖4 票據(jù)追溯階段

4 正確性與安全性證明

本文構(gòu)造的格上可追溯的匿名單點(diǎn)登錄方案具有不可鏈接性、不可偽造性和可追溯性，并給出正確性與安全性證明.

4.1 正確性

所構(gòu)造的格上可追溯的匿名單點(diǎn)登錄方案，在用戶密鑰提取算法ExtractKey中，lu=A·ru，du=ru+Ru·xmodq，由此可得式（1）成立，用戶的公私鑰可以正確生成.

用戶注冊(cè)算法User-Registration中，c1和c2是使用中央驗(yàn)證者公鑰對(duì)用戶身份加密所產(chǎn)生的密文，在式（2）中，通過(guò)使用中央驗(yàn)證者的私鑰dcv，可以正確解密以恢復(fù)用戶身份IDu.

對(duì)于采用假名技術(shù)[27]所生成的正確假名(pv,qv)，根據(jù)pku=A·du可知式（3）一定成立，可順利完成票據(jù)發(fā)行算法Ticket-Issuing中的用戶匿名認(rèn)證.同時(shí)(sv,cv,zv)和(S,c,z)分別是票據(jù)發(fā)行者對(duì)sv和S的簽名，式（4）（5）是對(duì)這2 個(gè)簽名的驗(yàn)證過(guò)程，由zv=uv+diss·sv，z=e+diss·S可得式（4）（5）成立.

票據(jù)驗(yàn)證算法Ticket-Validating 中，通過(guò)對(duì)采用指定驗(yàn)證者簽名方案[24]所生成的票據(jù)信息進(jìn)行式（6）的驗(yàn)證，完成票據(jù)的有效性驗(yàn)證.已知zu=diss·rT+k·t-1，則式（6）恒成立.

通過(guò)式（7）（8），可以分別完成票據(jù)追溯算法Ticket-Trace中的用戶身份去匿名化和訪問(wèn)服務(wù)追溯.由式（3）成立可知式（7）恒成立.式（8）是中央驗(yàn)證者CV利用其私鑰dcv對(duì)密文(e1,e2)進(jìn)行解密.

在PKG 的協(xié)助下，正確生成各參與方的公私鑰，式（1）～（8）成立，用戶服務(wù)票據(jù)能正確生成，并通過(guò)指定票據(jù)驗(yàn)證者驗(yàn)證，最終中央驗(yàn)證者也可以在必要情況下正確追溯出用戶的服務(wù)信息.因此，所提方案滿足正確性.

4.2 不可鏈接性證明

4.3 不可偽造性證明

4.4 可追溯性證明

5 安全性能對(duì)比

本節(jié)對(duì)方案安全性進(jìn)行分析，表1 列出本文方案與文獻(xiàn)[4,7,19]方案在匿名性、可追溯性、不可鏈接性、抗量子性以及各方案中票據(jù)發(fā)行算法的時(shí)間復(fù)雜度對(duì)比.

Table 1 The Safety Performance Comparison of the Proposed Scheme and the Schemes of References [4,7,19]表1 本文方案與文獻(xiàn)[4,7,19]方案的安全性能對(duì)比

文獻(xiàn)[4]引入帶有隨機(jī)數(shù)的單向散列函數(shù)來(lái)解決Hsu 等人[31]方案中的假冒攻擊，文獻(xiàn)[4]方案中票據(jù)驗(yàn)證者可以通過(guò)使用擴(kuò)展歐幾里德算法，以高概率恢復(fù)出用戶的認(rèn)證憑證，并利用RSA 簽名方案和非交互零知識(shí)證明方案，實(shí)現(xiàn)用戶的身份認(rèn)證與票據(jù)的不可偽造性.因此文獻(xiàn)[4]方案不具備可追溯性和用戶服務(wù)的不可鏈接性，不可以抵抗已知的量子算法攻擊.

文獻(xiàn)[7]中的方案利用切比雪夫混沌映射的半群性和交換性來(lái)隱藏用戶的真實(shí)身份，但多個(gè)票據(jù)驗(yàn)證者串通起來(lái)時(shí)可以分析用戶的服務(wù)請(qǐng)求，并且文獻(xiàn)[7]方案在設(shè)計(jì)時(shí)未考慮因?yàn)槠墼p行為的追溯問(wèn)題[32]，其不具備匿名性、可追溯性、不可鏈接性，不可以抵抗已知的量子算法攻擊.

文獻(xiàn)[19]中的方案采用公鑰證書(shū)技術(shù)，使中央驗(yàn)證者在追溯時(shí)獲得用戶公鑰來(lái)揭示用戶身份，并追溯出用戶的所有訪問(wèn)服務(wù)，該方案實(shí)現(xiàn)了可追溯性與不可鏈接性.該方案安全性是基于離散對(duì)數(shù)困難假設(shè)，不能抵抗已知的量子算法攻擊.

本文方案中用戶在請(qǐng)求票據(jù)時(shí)，通過(guò)為指定票據(jù)驗(yàn)證者生成假名來(lái)實(shí)現(xiàn)其匿名性，保證用戶的匿名性與服務(wù)請(qǐng)求的不可鏈接性.利用格上基于身份的密碼體制來(lái)代替文獻(xiàn)[19]中的公鑰證書(shū)技術(shù)，簡(jiǎn)化了用戶身份管理開(kāi)銷.在追溯階段，可信第三方通過(guò)計(jì)算出用戶公鑰來(lái)揭示用戶身份，并追溯出整個(gè)服務(wù)請(qǐng)求.同時(shí)票據(jù)發(fā)行階段作為單點(diǎn)登錄方案的重要一步，票據(jù)發(fā)行算法的時(shí)間復(fù)雜度大小關(guān)乎著方案的實(shí)際運(yùn)行效率.本方案的安全性基于ISIS 困難假設(shè)，在參數(shù)m=512 b，q=783361 ≈220（m，q定義見(jiàn)1.1 節(jié)）下即可達(dá)到與AES-128bit 相當(dāng)?shù)陌踩考?jí).根據(jù)NIST 對(duì)稱加密標(biāo)準(zhǔn)所提供的安全強(qiáng)度范圍分類，在AES-128bit 安全量級(jí)下進(jìn)行對(duì)比方案參數(shù)的實(shí)例化，文獻(xiàn)[4,7,19]中的參數(shù)分別設(shè)置為m=3 200 b（m為文獻(xiàn)[4]中的模數(shù)），κ=8 b、m=3 072 b（κ為文獻(xiàn)[7]中安全Hash 函數(shù)的輸出長(zhǎng)度，m為文獻(xiàn)[7]中的模數(shù)）和m=256 b（m為文獻(xiàn)[19]中群的階數(shù)）[33].由表1 可知，在所設(shè)參數(shù)下，所提方案與對(duì)比方案[4,7,19]的時(shí)間復(fù)雜度分別約為O(212.17),O(234.9),O(239.17),O(216).可見(jiàn)，本方案在提供整體安全性的同時(shí)，具有較低時(shí)間復(fù)雜度.

6 性能分析

6.1 抗量子安全強(qiáng)度分析

本文方案是基于格上困難問(wèn)題構(gòu)造的單點(diǎn)登錄方案，結(jié)合格上ISIS 困難問(wèn)題求解以及未來(lái)數(shù)年中量子計(jì)算機(jī)的發(fā)展，為滿足方案安全強(qiáng)度的要求，在表2中提供3 組參數(shù)，并進(jìn)一步使用格基約化算法BKZ[34]對(duì)本文方案進(jìn)行量子安全強(qiáng)度測(cè)試，在這3 組參數(shù)下，方案可分別達(dá)到112 b，230 b，292 b 的安全度.

Table 2 Security Strength Under Different Parameter Settings表2 不同參數(shù)設(shè)置下的安全強(qiáng)度

6.2 運(yùn)算效率分析

在滿足一定安全等級(jí)的情況下，將本文方案在Windows10 系統(tǒng)、Intel?Core?i5-7200U CPU @2.50 GHz處理器和8.00GB 運(yùn)行內(nèi)存下，利用Sage 數(shù)學(xué)庫(kù)，采用基于SageMath 的Python 進(jìn)行方案實(shí)現(xiàn)與性能評(píng)估.表3 給出了本文方案在PARMS Ⅰ，PARMS Ⅱ，PARMS Ⅲ這3 組參數(shù)下的時(shí)間開(kāi)銷，所顯示的時(shí)間是以1 000 次運(yùn)算的平均值統(tǒng)計(jì).下面主要分析PARMS Ⅱ，PARMS Ⅲ參數(shù)下，即m= 512 和m= 640這2 種情況下各階段的時(shí)間開(kāi)銷.

Table 3 Calculation Cost Analysis of Our Proposed Scheme表3 本文方案的計(jì)算開(kāi)銷分析ms

1）在實(shí)現(xiàn)整個(gè)匿名單點(diǎn)登錄方案過(guò)程中，系統(tǒng)初始化、各參與方公私鑰提取以及每個(gè)用戶注冊(cè)階段只需進(jìn)行1 次操作.在各參與者公私鑰提取階段，對(duì)于PKG 生成的私鑰，用戶要通過(guò)驗(yàn)證等式來(lái)確保私鑰是正確生成的，因此，此階段在m= 512 和m=640 時(shí)，分別需要大概21 ms 和36 ms.

2）當(dāng)m= 512 時(shí)，假如票據(jù)發(fā)行階段用戶一次性請(qǐng)求4 個(gè)服務(wù)，整個(gè)過(guò)程大概需要74.89 ms.其中7.4 ms用來(lái)生成服務(wù)請(qǐng)求，48.55 ms 用來(lái)生成票據(jù)，2.57 ms用來(lái)驗(yàn)證票據(jù)是否有效.即使將m增加到640，整個(gè)發(fā)行階段也只需要108.34 ms.同時(shí)，用戶可以預(yù)先計(jì)算它的票據(jù)請(qǐng)求，而且票據(jù)發(fā)行者可并行驗(yàn)證用戶身份的合法性，從而將與票據(jù)發(fā)行者的交互時(shí)間縮短14.78 ms（m= 512）或22.46 ms（m= 640）.此外，發(fā)行者也可以預(yù)先計(jì)算一些值作為票據(jù)發(fā)行過(guò)程的一部分（例如Dv,e1,e2等部分，參見(jiàn)圖2）.這樣可將票據(jù)生成階段減少5.15 ms（m=512）或6.64 ms（m= 640）.經(jīng)算法優(yōu)化后，整個(gè)過(guò)程大概需要54.96 ms（m= 512）或79.14 ms（m= 640）.

3）在票據(jù)驗(yàn)證階段，用戶需要向指定票據(jù)驗(yàn)證者提交自己的認(rèn)證標(biāo)簽以獲得想要的服務(wù).此時(shí)，指定票據(jù)驗(yàn)證者需要驗(yàn)證指定驗(yàn)證者簽名、單向Hash 函數(shù)以及對(duì)認(rèn)證標(biāo)簽與票據(jù)的簽名，若全部驗(yàn)證通過(guò)，則授權(quán)用戶訪問(wèn)服務(wù)，最終指定票據(jù)驗(yàn)證者驗(yàn)證單個(gè)標(biāo)簽，其過(guò)程只需要大約16.08 ms 或24.11 ms（m= 512或m= 640）.

4）必要時(shí)，中央驗(yàn)證者才執(zhí)行票據(jù)追溯算法.此時(shí)中央驗(yàn)證者在進(jìn)行簡(jiǎn)單的向量運(yùn)算后，揭示用戶的真實(shí)身份并追溯出用戶的整個(gè)服務(wù)請(qǐng)求.由于此階段的主要運(yùn)算過(guò)程與票據(jù)驗(yàn)證階段相似，因此這2 個(gè)階段的計(jì)算開(kāi)銷大體相近.

6.3 存儲(chǔ)與通信開(kāi)銷分析

為進(jìn)一步評(píng)估方案效率，表4 列出方案各階段所產(chǎn)生的存儲(chǔ)開(kāi)銷與通信開(kāi)銷.系統(tǒng)初始化階段與公私鑰提取階段會(huì)產(chǎn)生方案所需的公共參數(shù)與各參與方的公私鑰，各參與方私鑰作為要保密的信息，需要進(jìn)行本地存儲(chǔ).由表4 可知，在給定的3 組參數(shù)下，參與方的本地存儲(chǔ)開(kāi)銷最大為10.53KB.

Table 4 Analysis of Storage Cost and Communication Cost of Scheme表4 方案存儲(chǔ)開(kāi)銷與通信開(kāi)銷分析ms

用戶注冊(cè)階段、票據(jù)驗(yàn)證階段和票據(jù)發(fā)行階段需要2 個(gè)參與方進(jìn)行協(xié)同交互.在用戶注冊(cè)階段，用戶需要傳輸對(duì)身份IDu加密所產(chǎn)生的密文.票據(jù)驗(yàn)證階段，指定票據(jù)驗(yàn)證者和用戶分別需要發(fā)送身份IDv和票據(jù)標(biāo)簽Tagv.在票據(jù)發(fā)行階段，用戶給票據(jù)發(fā)行者發(fā)送一次性假名與服務(wù)請(qǐng)求，票據(jù)發(fā)行者再根據(jù)用戶需求生成服務(wù)票據(jù)，此過(guò)程需要較大的通信開(kāi)銷.在表4 的3 組參數(shù)下，方案各階段的最大通信開(kāi)銷分別是167.31 KB，336.31 KB，420.8 KB，其中所生產(chǎn)的用戶服務(wù)票據(jù)約占票據(jù)發(fā)行者通信開(kāi)銷的97%.

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

本文基于ISIS 困難假設(shè)，結(jié)合格上基于身份的密碼體制與匿名認(rèn)證技術(shù)，構(gòu)造了一個(gè)可追溯的匿名單點(diǎn)登錄方案，解決了同類方案中公鑰證書(shū)管理問(wèn)題以及因用戶匿名訪問(wèn)服務(wù)而無(wú)法追責(zé)的問(wèn)題.根據(jù)方案在不同參數(shù)設(shè)置下的量子安全強(qiáng)度可知，其具備抗量子算法攻擊的特點(diǎn)，同時(shí)在運(yùn)行時(shí)間和通信開(kāi)銷上滿足應(yīng)用實(shí)施的需求.當(dāng)指定票據(jù)驗(yàn)證者發(fā)生單點(diǎn)故障時(shí)，考慮在票據(jù)發(fā)行階段引入代理重加密技術(shù)，在不改變用戶服務(wù)票據(jù)情況下，將用戶重定向到代理票據(jù)驗(yàn)證者并繼續(xù)訪問(wèn)服務(wù)，是未來(lái)的一個(gè)研究方向.

作者貢獻(xiàn)聲明：湯永利負(fù)責(zé)方案構(gòu)造與證明、數(shù)據(jù)整理與實(shí)驗(yàn)分析；李英負(fù)責(zé)方案構(gòu)造與證明，完成論文撰寫(xiě)與修改；趙宗渠負(fù)責(zé)方案構(gòu)造與證明；李星宇負(fù)責(zé)數(shù)據(jù)整理與實(shí)驗(yàn)分析；王瀚博負(fù)責(zé)論文撰寫(xiě)與修改.