基于線性方程組的門限匿名認(rèn)證方案

殷鳳梅，濮光寧，張 江，侯整風(fēng)

1.合肥師范學(xué)院，合肥 230601

2.安徽財(cái)貿(mào)職業(yè)學(xué)院，合肥 230601

3.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，合肥 230009

1 引言

隨著計(jì)算機(jī)網(wǎng)絡(luò)的飛速發(fā)展，電子商務(wù)、電子政務(wù)和網(wǎng)上銀行得到廣泛應(yīng)用，此類應(yīng)用中，為了增強(qiáng)系統(tǒng)的安全性能，身份認(rèn)證技術(shù)必不可少，在一些特殊的場(chǎng)合下，認(rèn)證的身份還需要匿名保護(hù)。因此，匿名認(rèn)證[1]成為了信息安全領(lǐng)域的研究熱點(diǎn)，很多無(wú)條件匿名認(rèn)證方案[2-7]應(yīng)運(yùn)而生?？蓪?duì)于完備的匿名認(rèn)證，可追蹤的匿名認(rèn)證可以防止“匿名”特性被濫用。

2001年，Shouichi和Susumu[8]基于隨機(jī)自規(guī)約關(guān)系產(chǎn)生了臨時(shí)的公私鑰，實(shí)現(xiàn)了移動(dòng)環(huán)境下的可追蹤匿名認(rèn)證方案，但該方案中存在可信中心權(quán)利過(guò)大的問(wèn)題。2005年，田子健等[9]借鑒環(huán)簽名的思想，提出一種動(dòng)態(tài)可追蹤的匿名認(rèn)證方案，該方案既可以由示證人自由選擇匿名子集，又可以追蹤匿名的身份。2008年，Jung等人[10]提出了A3RP協(xié)議，實(shí)現(xiàn)可追蹤的匿名認(rèn)證方案。但這兩個(gè)方案的匿名追蹤不是門限追蹤，容易導(dǎo)致成員的身份信息被隨意的追蹤，降低了隱私的安全性。2012年，劉方斌等[11]借助民主簽名思想提出了無(wú)可信中心的門限追蹤Ad Hoc網(wǎng)絡(luò)匿名認(rèn)證，有效地解決了Ad Hoc網(wǎng)絡(luò)中的匿名認(rèn)證問(wèn)題，但該方案采用Shamir的Lagrange插值算法計(jì)算成員的秘密份額和群公鑰，計(jì)算和相互通信開銷較大，效率較低。

本文借助石潤(rùn)華等人[12]提出的門限秘密共享的思想，提出了一種基于線性方程組的門限匿名認(rèn)證方案，其安全性依賴于離散對(duì)數(shù)求解的困難性。與文獻(xiàn)[11]相比，秘密份額和群公鑰的計(jì)算代價(jià)較小，匿名認(rèn)證過(guò)程更簡(jiǎn)單。

2 基于線性方程組的門限匿名認(rèn)證方案

2.1 系統(tǒng)初始化

本文方案是基于線性方程組的求解理論，當(dāng)系數(shù)矩陣的秩等于t時(shí)，可以求出t個(gè)未知變量，繼而得到每個(gè)成員的秘密份額。

方案中存在n個(gè)成員Ui(1≤i≤n)，可信中心選取參數(shù)p、g并公開。其中，p是安全的大素?cái)?shù)，q是p-1的素因子，g是GF(p)上的q階生成元。

定義一個(gè)序列如下：

其中，c0是n個(gè)成員共享的秘密，c1，c2，…，ct-1是t-1個(gè)隨機(jī)數(shù)（要求ci(0≤i≤t-1)之間線性無(wú)關(guān)），每個(gè)si(0≤i≤n)由它前面的t項(xiàng)相加modp得來(lái)。即

因此，產(chǎn)生如下線性方程組：

由于s0與共享的秘密c0直接相關(guān)，因此對(duì)s0保密。將式（3）中每個(gè)方程均用ci(0≤i≤t-1)表示，可以得到式（4）：

其中，Bn×t成員可以計(jì)算得到，即相當(dāng)于對(duì)所有成員公開。將si作為秘密份額分發(fā)給用戶Ui，公開C0，計(jì)算成員Ui的公鑰Si并公開。C0、Si可通過(guò)式（7）、（8）計(jì)算得到：

由于C是t維向量，反過(guò)來(lái)，共享的秘密c0與t個(gè)成員si之間的關(guān)系可以用式（9）表示：

而bji′(1≤i≤t)可以由矩陣 B計(jì)算得到。

2.2 匿名認(rèn)證

匿名認(rèn)證包含兩個(gè)方面：一要求示證者可以證明自己的身份；二要求在認(rèn)證中不泄露示證者的身份信息。

示證者Up想證明自己屬于組織U，為了不暴露自己的身份，需要其余任意t-1個(gè)成員協(xié)助，組成認(rèn)證集合UR={U1，…，Ut-1，Up}。

隨機(jī)數(shù)的詳細(xì)獲取過(guò)程可參考文獻(xiàn)[13]。

（4）Up根據(jù)式（10）計(jì)算Kp并公開，根據(jù)式（11）計(jì)算Ep并公開：

（5）Up秘密地選隨機(jī)數(shù)hp，根據(jù)式（12）計(jì)算Hp并公開，根據(jù)式（13）計(jì)算Qp并公開：

（6）認(rèn)證集合UR中每個(gè)成員Ui(i∈UR)，根據(jù)式（14）計(jì)算fi：

（7）根據(jù)式（15）聯(lián)合計(jì)算Fp：

（8）若式（16）成立，則證明Up屬于組織U：

2.3 匿名追蹤

為了防止“匿名”特性被濫用，在某些情況下，需要追蹤并揭示示證者的身份信息，即考慮匿名可控問(wèn)題。如此一來(lái)，匿名認(rèn)證和匿名追蹤似乎有些矛盾，為了兼顧兩者，匿名追蹤不能是隨意的追蹤，必須是達(dá)到門限值t個(gè)成員，聯(lián)合才能追蹤示證者的身份，即實(shí)現(xiàn)匿名的門限追蹤。

（1）t個(gè)成員記為Ui(1≤i≤t)組成追蹤集合UZ={U1，U2，…，Ut}，使用各自的秘密份額根據(jù)式（17）計(jì)算wi，并根據(jù)式（18）聯(lián)合計(jì)算Wp：

（2）根據(jù)式（19）可得到示證者的公鑰，即示證者的身份：

2.4 實(shí)驗(yàn)數(shù)據(jù)

令n=11，t=5，p=47，根據(jù)式（4），si可由ci(0≤i≤4)線性表示，兩者之間的線性關(guān)系可以使用矩陣表示，如式（20）：

假設(shè)共享的秘密c0=13，根據(jù)文獻(xiàn)[14]的證明，取生成元g=5，根據(jù)式（7）計(jì)算C0=513mod47=43并公開。選取隨機(jī)數(shù)c1=3，c2=7，c3=9，c4=11。

（1）根據(jù)式（20）計(jì)算可得si序列：

（2）如果U6想證明自己屬于組織U，需要組織中的4個(gè)成員，假設(shè)是U1，U3，U4，U8協(xié)助認(rèn)證，則認(rèn)證集合UR={U1，U3，U4，U8，U6} 。

以上隨機(jī)數(shù)ci以及p等數(shù)據(jù)的選擇都是一般的整數(shù)，主要用來(lái)模擬驗(yàn)證方案的正確性，在實(shí)際應(yīng)用中，可以從Miracle大數(shù)運(yùn)算庫(kù)選擇位數(shù)較高的大數(shù)，提高方案的安全性。

3 方案分析

3.1 正確性

（1）系統(tǒng)初始化的正確性分析

n個(gè)成員可通過(guò)式（4）獲得各自的秘密份額，且成員數(shù)n可以任意擴(kuò)展。

由于每個(gè)si(0≤i≤n)由它前面的t項(xiàng)相加modp而得，因此所有的si都可以轉(zhuǎn)換成由ci(0≤i≤t-1)線性表示，即通過(guò)式（4）所示的方程組求解。另外，每個(gè)si都由它前t項(xiàng)計(jì)算得來(lái)，因此，式（2）所示的序列可以無(wú)限擴(kuò)展，即n的值不固定。

（2）匿名認(rèn)證的正確性證明

可通過(guò)式（16）認(rèn)證示證者Up屬于組織U。

證明引理[15]gtmodqmodp=gtmodp。由式（11）、（7）、（9）、（14）、（15）可得：

（3）匿名追蹤的正確性證明

可通過(guò)式（19）追蹤示證者Up的身份，即公鑰Sp。

證明由式（18）、（17）、（12）、（7）可得：

3.2 安全性

本文方案的安全性基于對(duì)離散對(duì)數(shù)問(wèn)題的求解，而離散對(duì)數(shù)的求解在現(xiàn)階段是非常困難的。

（1）本文方案具備匿名性

在匿名認(rèn)證過(guò)程中，示證者公開的Ep中并不包含示證者的身份信息，因而，Ep的公開不會(huì)泄露示證者的身份。另外，示證者提供的fp中雖然隱含秘密份額的身份信息，但如果想非法獲得，就必須求解離散對(duì)數(shù)問(wèn)題，而離散對(duì)數(shù)的求解非常困難。因此，在匿名認(rèn)證中，示證者的身份滿足匿名性。

（2）本文方案具備可追蹤性

如果t個(gè)成員各自提供正確的Wi，按照式（18）聯(lián)合計(jì)算出Wp，根據(jù)式（19）便可恢復(fù)出示證者的公鑰Sp即身份信息。

（3）本文方案具備門限性質(zhì)

在系統(tǒng)初始化過(guò)程中，由于Ct中含有t個(gè)未知數(shù)，需要t個(gè)方程才能求解出成員的秘密份額；在匿名認(rèn)證和匿名追蹤過(guò)程中，F(xiàn)p和Wp都需要t個(gè)成員聯(lián)合才能計(jì)算出來(lái)，因而本方案具有門限性質(zhì)。

（4）本文方案具備完備性

所謂的完備性是指外部成員無(wú)法通過(guò)匿名認(rèn)證。在匿名認(rèn)證過(guò)程中，外部成員企圖通過(guò)認(rèn)證，就必須提供正確的fi，fi是根據(jù)成員的秘密份額si計(jì)算得來(lái)的，由于離散對(duì)數(shù)的難解性，外部成員不可能獲得秘密份額，因此，外部成員無(wú)法通過(guò)匿名認(rèn)證。

（5）匿名認(rèn)證過(guò)程抗偽造攻擊

匿名認(rèn)證過(guò)程的偽造攻擊可以從兩個(gè)方面來(lái)分析。

①抗示證者的偽造攻擊

從式（14）可知，認(rèn)證成員提供的fi需要使用認(rèn)證成員的隨機(jī)數(shù)ki'，雖然開始時(shí)認(rèn)證成員的隨機(jī)數(shù)ki是由示證者選擇并提供的，但經(jīng)過(guò)匿名認(rèn)證集合中全體成員的相互協(xié)作，認(rèn)證成員獲得了新的秘密隨機(jī)數(shù)ki'，且對(duì)示證者是保密的，因此，示證者無(wú)法偽造出認(rèn)證成員的fi。

②抗認(rèn)證成員的偽造攻擊

在匿名認(rèn)證過(guò)程中，由于fi的計(jì)算需要使用認(rèn)證成員自身的秘密份額si，而si是安全保密的，因而認(rèn)證成員的fi不可能被其他成員偽造出來(lái)。

（6）匿名認(rèn)證過(guò)程抗一致性攻擊

所謂的一致性攻擊是指兩次認(rèn)證是否認(rèn)證同一個(gè)用戶。由于每次匿名認(rèn)證，示證者選擇的隨機(jī)數(shù)kp和hp是不固定的，認(rèn)證成員獲得的隨機(jī)數(shù)ki'也是不固定的，因而不能判定兩次認(rèn)證是否是認(rèn)證同一個(gè)用戶。

3.3 有效性

（1）協(xié)議性質(zhì)分析

與現(xiàn)有的匿名認(rèn)證方案進(jìn)行比較，本文方案同時(shí)具有匿名性、門限可追蹤性、完備性、抗偽裝攻擊和一致性攻擊，詳見表1。

（2）計(jì)算代價(jià)分析

從表1中可以看出，文獻(xiàn)[11]也能實(shí)現(xiàn)門限匿名追蹤，下面將主要與文獻(xiàn)[11]在計(jì)算代價(jià)上進(jìn)行比較。為了方便比較，用Tmul代表模乘計(jì)算費(fèi)用，Texp代表模指數(shù)計(jì)算費(fèi)用，Th代表哈希函數(shù)計(jì)算費(fèi)用，t是門限值，n是成員數(shù)，模加/異或運(yùn)算的時(shí)間復(fù)雜度相當(dāng)小，計(jì)算費(fèi)用可以忽略。

文獻(xiàn)[11]采用Shamir的Lagrange插值算法計(jì)算成員的秘密份額信息，計(jì)算的開銷是n(t-1)Tmul+n(t-2)Texp，在匿名認(rèn)證中借鑒民主簽名的思想，需要選擇2n-1個(gè)隨機(jī)數(shù)，計(jì)算3n個(gè)中間數(shù)據(jù)xj、yj、zj。本文方案采用線性方程組理論獲得成員的秘密份額，計(jì)算開銷是(t-1)Tmul，在匿名認(rèn)證中，需要選擇t個(gè)隨機(jī)數(shù)，計(jì)算t個(gè)中間數(shù)據(jù)fi，t個(gè)fi進(jìn)行連乘運(yùn)算。兩種方案的計(jì)算代價(jià)詳見表2。

表2中的數(shù)據(jù)表明，實(shí)現(xiàn)同樣功能的情況下，本文方案的計(jì)算代價(jià)相對(duì)較小。

表1 可追蹤匿名認(rèn)證方案性質(zhì)比較

表2 門限可追蹤匿名認(rèn)證方案計(jì)算代價(jià)比較

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

基于線性方程組的求解理論，提出了一種門限匿名認(rèn)證方案，其安全性依賴于離散對(duì)數(shù)求解的困難性。與已有的方案相比，本文方案不僅能實(shí)現(xiàn)匿名認(rèn)證，更能實(shí)現(xiàn)匿名追蹤，且具有門限性質(zhì)。整個(gè)過(guò)程中，計(jì)算代價(jià)相對(duì)較小，匿名認(rèn)證過(guò)程相對(duì)較簡(jiǎn)單。在電子商務(wù)、移動(dòng)通信等眾多領(lǐng)域，本文方案將具有廣闊的應(yīng)用前景。

[1]Ateniese G，Herzberg A，Krawczyk H，et al.Untraceable mobility orhow to travelincognito[J].ComputerNetworks，1999，31（8）：871-884.

[2]Kong J J，Hong X Y，Gerla M.An identity-free and ondemand routing scheme against anonymity threats in mobile Ad Hoc networks[J].IEEE Transactions on Mobile Computing，F(xiàn)requency，2007，6：888-902.

[3]Lee C H，Deng X T，Zhu H F.Design and sccurity analysis of anonymous group identification protocols[C]//Proceedings of Pulic Key Cryptography，F(xiàn)ebruary 2002，Paris，F(xiàn)rance.Berlin Heidelberg：Springer-Verlag，2002：188-198.

[4]Eliane J，Guillaume P.On the security of homage group authentication protocol[C]//Proceedings of Cayman Islands，British West Indies，F(xiàn)eb 19-22，2001，2339：106-116.

[5]Xu Z M，Tian H，Liu D S，et al.A ring-signature anonymous authentication method based on one-way accumulator[C]//Proceedings of Communication Systems，Networks and Applications Conference，2010：56-59.

[6]周彥偉，吳振強(qiáng)，蔣李.分布式網(wǎng)絡(luò)環(huán)境下的跨域匿名認(rèn)證機(jī)制[J].計(jì)算機(jī)應(yīng)用，2010，30（8）：2120-2124.

[7]宋成，孫宇瓊，彭維平，等.改進(jìn)的直接匿名認(rèn)證方案[J].北京郵電大學(xué)學(xué)報(bào)，2011，34（3）：62-65.

[8]Hirose S，Yoshida S.A user authentication scheme with identity and location privacy[C]//Proceedings of the 6th Australasian Conference on Information Security and Privacy，Sydney，Australia，July 11-13，2001，2119：235-246.

[9]田子健，王繼林，伍云霞.一個(gè)動(dòng)態(tài)的可追蹤匿名認(rèn)證方案[J].電子與信息學(xué)報(bào)，2005，27（11）：1737-1740.

[10]Paik J H，Kim B H，Lee D H.A3RP：anonymous and authenticated ad hoc routing protocol[C]//Proceedings of Information Security and Assurance Conference，2008.

[11]劉方斌，張琨，李海，等.無(wú)可信中心的門限追蹤Ad Hoc網(wǎng)絡(luò)匿名認(rèn)證[J].通信學(xué)報(bào)，2012，33（8）：208-213.

[12]石潤(rùn)華，仲紅，黃劉生.公開可驗(yàn)證的門限秘密共享方案[J].微電子學(xué)與計(jì)算機(jī)，2008，25（1）：29-33.

[13]殷鳳梅，濮光寧.允許新成員加入的無(wú)可信中心秘密共享方案分析[J].重慶科技學(xué)院學(xué)報(bào)：自然科學(xué)版，2011，13（6）：173-175.

[14]張清華.基于密鑰交換中離散對(duì)數(shù)生成元的研究[J].重慶郵電學(xué)院學(xué)報(bào)，2002，14（3）：90-92.

[15]Harn L.Efficient sharing（broadcasting）of multiple secrets[J].IEE Proc Comput Digit Tech，1995，142（3）：237-240.