基于線性方程組的門限匿名認證方案

殷鳳梅，濮光寧，張 江，侯整風

1.合肥師范學院，合肥 230601

2.安徽財貿職業學院，合肥 230601

3.合肥工業大學 計算機與信息學院，合肥 230009

1 引言

隨著計算機網絡的飛速發展，電子商務、電子政務和網上銀行得到廣泛應用，此類應用中，為了增強系統的安全性能，身份認證技術必不可少，在一些特殊的場合下，認證的身份還需要匿名保護。因此，匿名認證[1]成為了信息安全領域的研究熱點，很多無條件匿名認證方案[2-7]應運而生?？蓪τ谕陚涞哪涿J證，可追蹤的匿名認證可以防止“匿名”特性被濫用。

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

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

2 基于線性方程組的門限匿名認證方案

2.1 系統初始化

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

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

定義一個序列如下：

其中，c0是n個成員共享的秘密，c1，c2，…，ct-1是t-1個隨機數（要求ci(0≤i≤t-1)之間線性無關），每個si(0≤i≤n)由它前面的t項相加modp得來。即

因此，產生如下線性方程組：

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

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

由于C是t維向量，反過來，共享的秘密c0與t個成員si之間的關系可以用式（9）表示：

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

2.2 匿名認證

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

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

隨機數的詳細獲取過程可參考文獻[13]。

（4）Up根據式（10）計算Kp并公開，根據式（11）計算Ep并公開：

（5）Up秘密地選隨機數hp，根據式（12）計算Hp并公開，根據式（13）計算Qp并公開：

（6）認證集合UR中每個成員Ui(i∈UR)，根據式（14）計算fi：

（7）根據式（15）聯合計算Fp：

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

2.3 匿名追蹤

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

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

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

2.4 實驗數據

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

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

（1）根據式（20）計算可得si序列：

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

以上隨機數ci以及p等數據的選擇都是一般的整數，主要用來模擬驗證方案的正確性，在實際應用中，可以從Miracle大數運算庫選擇位數較高的大數，提高方案的安全性。

3 方案分析

3.1 正確性

（1）系統初始化的正確性分析

n個成員可通過式（4）獲得各自的秘密份額，且成員數n可以任意擴展。

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

（2）匿名認證的正確性證明

可通過式（16）認證示證者Up屬于組織U。

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

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

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

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

3.2 安全性

本文方案的安全性基于對離散對數問題的求解，而離散對數的求解在現階段是非常困難的。

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

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

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

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

（3）本文方案具備門限性質

在系統初始化過程中，由于Ct中含有t個未知數，需要t個方程才能求解出成員的秘密份額；在匿名認證和匿名追蹤過程中，Fp和Wp都需要t個成員聯合才能計算出來，因而本方案具有門限性質。

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

所謂的完備性是指外部成員無法通過匿名認證。在匿名認證過程中，外部成員企圖通過認證，就必須提供正確的fi，fi是根據成員的秘密份額si計算得來的，由于離散對數的難解性，外部成員不可能獲得秘密份額，因此，外部成員無法通過匿名認證。

（5）匿名認證過程抗偽造攻擊

匿名認證過程的偽造攻擊可以從兩個方面來分析。

①抗示證者的偽造攻擊

從式（14）可知，認證成員提供的fi需要使用認證成員的隨機數ki'，雖然開始時認證成員的隨機數ki是由示證者選擇并提供的，但經過匿名認證集合中全體成員的相互協作，認證成員獲得了新的秘密隨機數ki'，且對示證者是保密的，因此，示證者無法偽造出認證成員的fi。

②抗認證成員的偽造攻擊

在匿名認證過程中，由于fi的計算需要使用認證成員自身的秘密份額si，而si是安全保密的，因而認證成員的fi不可能被其他成員偽造出來。

（6）匿名認證過程抗一致性攻擊

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

3.3 有效性

（1）協議性質分析

與現有的匿名認證方案進行比較，本文方案同時具有匿名性、門限可追蹤性、完備性、抗偽裝攻擊和一致性攻擊，詳見表1。

（2）計算代價分析

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

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

表2中的數據表明，實現同樣功能的情況下，本文方案的計算代價相對較小。

表1 可追蹤匿名認證方案性質比較

表2 門限可追蹤匿名認證方案計算代價比較

4 結束語

基于線性方程組的求解理論，提出了一種門限匿名認證方案，其安全性依賴于離散對數求解的困難性。與已有的方案相比，本文方案不僅能實現匿名認證，更能實現匿名追蹤，且具有門限性質。整個過程中，計算代價相對較小，匿名認證過程相對較簡單。在電子商務、移動通信等眾多領域，本文方案將具有廣闊的應用前景。

[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，Frequency，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，February 2002，Paris，France.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，Feb 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]周彥偉，吳振強，蔣李.分布式網絡環境下的跨域匿名認證機制[J].計算機應用，2010，30（8）：2120-2124.

[7]宋成，孫宇瓊，彭維平，等.改進的直接匿名認證方案[J].北京郵電大學學報，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]田子健，王繼林，伍云霞.一個動態的可追蹤匿名認證方案[J].電子與信息學報，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]劉方斌，張琨，李海，等.無可信中心的門限追蹤Ad Hoc網絡匿名認證[J].通信學報，2012，33（8）：208-213.

[12]石潤華，仲紅，黃劉生.公開可驗證的門限秘密共享方案[J].微電子學與計算機，2008，25（1）：29-33.

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

[14]張清華.基于密鑰交換中離散對數生成元的研究[J].重慶郵電學院學報，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.