周文欽，張也弛，石潤華

1.安徽大學 計算智能與信號處理教育部重點實驗室，合肥 230039

2.安徽大學 計算機科學與技術(shù)學院，合肥 230039

基于安全多方計算的匿名認證方案

周文欽1，2，張也弛1，2，石潤華1，2

1.安徽大學 計算智能與信號處理教育部重點實驗室，合肥 230039

2.安徽大學 計算機科學與技術(shù)學院，合肥 230039

1 引言

21世紀是信息時代，隨著科技的快速發(fā)展，信息越來越重要。信息作為一種資源，它的普遍性、共享性、增值性、可處理性和多效用性，使其對于人類具有特別重要的意義。信息安全的實質(zhì)就是要保護信息系統(tǒng)或信息網(wǎng)絡(luò)中的信息資源免受各種類型的威脅、干擾和破壞，即保證信息的安全性。信息安全涉及的范圍很廣，大到國家軍事政治等機密安全，小到如防范商業(yè)機密泄露、防范青少年對不良信息的瀏覽、個人信息的泄露等。

身份認證在信息安全領(lǐng)域處于非常重要的地位，是其他安全機制的基礎(chǔ)。只有實現(xiàn)了有效的身份認證，才能保證訪問控制、安全審計、入侵防范等安全機制的有效實施。另外，它也是密鑰分發(fā)、密鑰交換及其他多方安全協(xié)議的必要前提，否則容易遭受中間人攻擊（Man-inthe-middle Attacks）。在各種身份認證技術(shù)中，匿名認證[1]已成為重要的研究方向。所謂匿名認證，就是在保護用戶身份隱私的同時，還能夠?qū)τ脩艋蚪K端進行認證。匿名認證在移動通信、電子商務(wù)、遠程登錄，以及其他要求保護用戶隱私[2]的場景中有著非常重要的應(yīng)用。

已有的匿名認證協(xié)議主要利用現(xiàn)代密碼技術(shù)，尤其是公鑰密碼和零知識證明技術(shù)，例如文獻[3-5]。但這些協(xié)議計算量較大，公鑰證書管理和存儲開銷較高，因此效率不高。盡管后來存在很多改進方案[6-12]，但多數(shù)作者只是想盡辦法縮短私鑰或簽名的長度，以此提高方案效率。依然避免不了計算復(fù)雜度高、管理和存儲開銷高的局限性，因而其應(yīng)用場景受限。特別是在一些智能卡、無線傳感器網(wǎng)絡(luò)或更為一般的普適計算環(huán)境下難以推廣。

在信息安全領(lǐng)域中，存在很多研究分支，其中現(xiàn)代密碼學和安全多方計算是較活躍的兩大分支。一般來說，在一個由多個參與方構(gòu)成的聯(lián)合計算系統(tǒng)中，如果主要關(guān)注的是對系統(tǒng)外部攻擊者（例如信道上的竊聽者）的防范，則是現(xiàn)代密碼學的研究范疇；如果關(guān)注的要點是系統(tǒng)內(nèi)部各參與者可能的作弊方式（例如非法獲得其他參與方的隱私輸入）與防范，則為安全多方計算的研究范疇。盡管存在很多基于現(xiàn)代密碼技術(shù)的認證乃至匿名認證協(xié)議，但很少有作者從安全多方計算的角度去研究它們。本文中，嘗試新的構(gòu)造方法，引入安全多方計算技術(shù)，設(shè)計了一個安全高效的匿名認證方案。與已有的方案相比，該方案具有計算量小，存儲開銷小的優(yōu)點，特別適宜于智能卡、無線傳感器網(wǎng)絡(luò)或是更為一般的普適計算環(huán)境。

本文的主要創(chuàng)新點如下：

（1）把匿名認證抽象為一個具體的多方安全計算問題，繼而轉(zhuǎn)向?qū)υ摼唧w問題的求解。

（2）基于求解線性方程組的一般理論，建立了一個匿名認證模型。

（3）定義并設(shè)計了一個安全有效的兩方矩陣與向量乘積協(xié)議。

（4）提出了一個新型高效的匿名認證方案。

2 預(yù)備知識

安全多方計算[13（]Secure Multiparty Computation，SMC）研究一組互不信任的參與方之間保護隱私的合作計算問題，對解決網(wǎng)絡(luò)環(huán)境下的信息安全具有重要價值。

定義1（安全兩方計算[14]）是一種安全的分布式計算協(xié)議，在該協(xié)議中，兩個參與方Alice與Bob分別持有各自的隱私輸入x與 y，對某個給定的函數(shù) f，他們希望協(xié)作計算函數(shù)值 f(x，y)，但Alice與Bob都不愿意向?qū)Ψ奖┞蹲约旱妮斎搿?/p>

目前安全多方計算已成為信息安全領(lǐng)域熱點研究內(nèi)容。為了解決具體的計算問題，人們構(gòu)造了很多原子協(xié)議，例如秘密比較、比特承諾、茫然傳輸?shù)然A(chǔ)協(xié)議。其中，茫然傳輸（Oblivious Transfer，OT）的概念最早由Rabin在文獻[15]中提出，隨后該概念被Even等人在文獻[16]中發(fā)展為二中選一的OT（簡記為OT12），再后來Brassard等[17]又提出了n選一的OT（簡記為OT1n）。

定義2（OT1n協(xié)議）發(fā)送方Alice有n個秘密m1，m2，…，mn，接收方Bob掌握一個整數(shù)i∈{1，2，…，n}，協(xié)議結(jié)果要求：

（1）Bob得到秘密mi，除此以外，對于其他的秘密m1，m2，…，mi-1，mi+1，…，mn一無所知。

（2）Alice對于Bob的選擇i一無所知，即她不知道Bob到底選擇了哪一個秘密。

此外，在本文的匿名認證方案中，利用了線性方程組的求解理論。而對于線性方程組的求解存在如下定理1、2[18]。

定理1n元線性方程組Ax=b有解的充分必要條件是系數(shù)矩陣A的秩等于增廣矩陣ˉ的秩，即R(A)= R(ˉ)。其中 A是m×n維的矩陣，x和b是n維的列向量。

定理2n元線性方程組Ax=b有解時，如果R(A)= n，那么方程組只有唯一解；如果R(A)＜n，那么方程組有無窮多解。

3 基于安全多方計算的匿名認證

首先把匿名認證抽象成一個特定的安全多方計算問題，繼而從安全多方計算的角度設(shè)計了一個全新的匿名認證方案。該方案既能提供認證功能又能保護用戶身份的隱私信息。與已有方案相比，建議的方案有著顯著的優(yōu)點。

3.1 模型及方案

在本文的模型中，共有三類設(shè)備：注冊服務(wù)器，應(yīng)用服務(wù)器，用戶（或終端）。它們之間通過有線或無線網(wǎng)絡(luò)連接。整個網(wǎng)絡(luò)中可能存在多種應(yīng)用服務(wù)器（例如有滿足特定用戶對敏感數(shù)據(jù)庫進行查詢的服務(wù)器，有提供軟件和下載功能的服務(wù)器等），以及分屬于不同角色的用戶，不同角色具有不同的訪問權(quán)限（例如，在醫(yī)療衛(wèi)生網(wǎng)絡(luò)環(huán)境中，醫(yī)生、護士與病人的權(quán)限各不相同）。注冊服務(wù)器為不同角色及相應(yīng)的應(yīng)用服務(wù)器生成認證憑證和相應(yīng)的驗證信息。用戶或終端訪問應(yīng)用服務(wù)器時，先要進行匿名認證，只有合法的用戶才能訪問或享受應(yīng)用服務(wù)器提供的資源或服務(wù)。

為了滿足以上模型的匿名認證需求，構(gòu)造一個用于匿名認證的函數(shù) f：X×Y→Z，要求滿足如下屬性：存在一個x∈X，使得有多個 yi∈Y對應(yīng)一個z∈Z，即有f(x，yi)=z(i=1，2，…，t)。繼而引入安全多方計算技術(shù)，得到具有匿名特性的認證方案，該方案包括兩個階段：注冊階段和認證階段。在注冊階段，注冊服務(wù)器給每個合法用戶分發(fā)一個唯一的子秘密 yi，對于每個 yi均滿足 f(x，yi)=z，而把 x和 z秘密發(fā)送給驗證方（即相應(yīng)的應(yīng)用服務(wù)器）。在認證階段，合法用戶與應(yīng)用服務(wù)器借助多方安全計算基礎(chǔ)協(xié)議，在不泄露各自隱私輸入 yi和(x，z)的條件下，安全計算 f(x，yi)。接著應(yīng)用服務(wù)器驗證是否有 f(x，yi)=z。若相等則完成對用戶的驗證并對其提供相應(yīng)的應(yīng)用服務(wù)，否則驗證失敗。

以上方案的關(guān)鍵是構(gòu)造匿名認證函數(shù) f，其主要特征為多對一的二元映射。對于一些存在多個解的線性方程組，剛好滿足“多對一”的特征。因而，把線性方程組的求解理論引入到協(xié)議設(shè)計中。在建議的匿名認證協(xié)議中，當驗證用戶憑證時需要兩方安全計算矩陣與向量的乘積，所以首先設(shè)計了一個安全的兩方矩陣與向量乘積基礎(chǔ)協(xié)議。

3.2 安全兩方矩陣與向量乘積協(xié)議

定義3（安全兩方矩陣與向量乘積協(xié)議）Alice有一個私有矩陣A（A不可逆），Bob有一個私有向量x。Alice需要得到的計算結(jié)果為 y=Ax（A與x滿足相乘的條件，即A的列與x的行數(shù)相等），且同時滿足：

（1）Alice不能由 y計算得到x；

（2）Bob不能計算得到A及y的值。

下面根據(jù)線性方程組的求解理論，設(shè)計了一個安全的兩方矩陣向量乘積協(xié)議。

協(xié)議1安全兩方矩陣向量乘積協(xié)議

輸入 Alice秘密輸入m×n的矩陣A；Bob秘密輸入n維的向量x。

輸出 Alice得到 y//在不泄漏各自隱私的前提下，Bob協(xié)助Alice計算y=Ax。

（1）Alice和Bob約定兩個數(shù)值s和t（這里st足夠大，使得1/st小到可以忽略）。

（2）Alice產(chǎn)生t個隨機矩陣A1，A2，…，At，使A= A1+A2+…+At。

（3）對每一個 j=1，2，…，t，Alice和Bob執(zhí)行下面的子步驟：

①Alice產(chǎn)生一個秘密的隨機數(shù)k，1≤k≤s。

②Alice發(fā)送(H1，H2，…，Hs)給Bob，這里Hk=Aj，并且其余的Hi是隨機矩陣，因為k是一個秘密數(shù)據(jù)，只有Alice知道，Bob不可能知道哪一個Hi是Aj。

③對所有的i=1，2，…，s，Bob計算Hix+rj，這里rj是一個隨機向量。

④用茫然傳輸OT1s協(xié)議，Alice取回結(jié)果：Hkx+rj= Ajx+rj。

（6）Alice計算y=w-r=Ax。

注：以上所有矩陣的維數(shù)相同，且其列數(shù)與向量 x的維數(shù)相同。

3.3 匿名認證協(xié)議

簡單起見，假定存在一個應(yīng)用服務(wù)器（例如數(shù)據(jù)庫），一個注冊服務(wù)器（其功能也可以直接由應(yīng)用服務(wù)器承擔），另外有一些需要訪問服務(wù)器的終端或用戶（通常為同一個群體或角色，例如醫(yī)生、護士、病人）。具體協(xié)議包括兩個階段：注冊階段和認證階段。

（1）注冊階段：注冊服務(wù)器按如下的方法為每個終端或用戶生成一個秘密信息，作為以后認證的憑證，并把相應(yīng)的驗證信息秘密送給應(yīng)用服務(wù)器。

①注冊服務(wù)器隨機生成一個m×n矩陣A及m維列向量 y(1＜m≤n)，建立線性方程組 Ax=y，并要求R(A)=R(Aˉ)，且R(A)＜n，即此線性方程組有無窮多個解。

②注冊服務(wù)器為每個合法用戶Ui生成一個唯一的n維向量xi，要求xi滿足方程組Axi=y，即xi是線性方程組Ax=y的一個解，且任何一對用戶的秘密向量不相等，即 xi≠xj(i≠j)。

③通過面對面的方式或其他安全方式（端到端的加密鏈路），注冊服務(wù)器把xi秘密發(fā)送給用戶Ui作為將來的認證憑證；而把相應(yīng)的秘密矩陣 A以及秘密向量 y秘密發(fā)送給應(yīng)用服務(wù)器。

（2）認證階段：應(yīng)用服務(wù)器將完成對用戶Ui的認證。

①用戶向應(yīng)用服務(wù)器提出認證請求。

②應(yīng)用服務(wù)器和用戶Ui調(diào)用兩方矩陣與向量的安全求積協(xié)議（協(xié)議1）。在具體的兩方矩陣與向量安全求積協(xié)議中，用戶Ui輸入xi（n維列向量），應(yīng)用服務(wù)器輸入矩陣 A，執(zhí)行協(xié)議后，應(yīng)用服務(wù)器得到m維列向量y′=Axi，且要求兩方都不能獲取對方的隱私輸入信息。

③應(yīng)用服務(wù)器驗證是否有 y′=y，若相等則被認證的用戶是合法的，從而對其開放相應(yīng)的資源或服務(wù)，否則驗證失敗。

注：以上計算可以在域GF(2n)上完成，從而用戶保存的n維的秘密向量可以看作是一個n位的二進制整數(shù)。

3.4 協(xié)議分析

以上方案的正確性基于n元線性方程組的求解理論（見定理1、2），因篇幅原因這里就不展開證明。下面主要分析其安全性，由具體協(xié)議可看出注冊階段的秘密分發(fā)由通信鏈路的保密性所保證，而認證階段的安全性主要基于兩方矩陣與向量乘積協(xié)議的安全性。詳細分析參見定理3～5。

定理3在半誠實模型下，協(xié)議1在計算上是安全的。

證明 所謂半誠實模型[19]，即所有參與方能夠誠實執(zhí)行協(xié)議，但是，同時記錄下所有的中間結(jié)果，并試圖從中推導(dǎo)出額外的信息。

另外，對于Alice來說，盡管她能多次獲得包含x的計算結(jié)果 Ajx+rj，但均加了一個隨機向量rj，而rj并不對她公開，因而Alice得不到任何有關(guān)x的秘密信息；再有矩陣 A是不可逆的，且線性方程組Ax=y有無數(shù)多解，因而Alice不可能根據(jù)Ax的結(jié)果計算出x。所以x對于Alice是無條件安全的。

定理4建議的方案保護了認證用戶的身份隱私，即認證向量xi，因而是匿名的。

證明 在認證階段，應(yīng)用服務(wù)器和請求認證的用戶協(xié)作執(zhí)行協(xié)議1。而定理3已經(jīng)證明了協(xié)議1的安全性。對于應(yīng)用服務(wù)器來說：一方面，盡管她能多次獲得包含用戶驗證向量xi的計算結(jié)果Ajxi+rj，但每次交互均加了一個隨機向量rj，而rj并不對她公開，因而她得不到任何有關(guān) xi的秘密信息；另一方面，矩陣 A是不可逆的，這由注冊服務(wù)器所保證。且線性方程組Ax=y有無數(shù)多解，因而她不可能根據(jù)Ax的結(jié)果計算出xi。所以，應(yīng)用服務(wù)器得不到與合法用戶的驗證向量xi有關(guān)的秘密信息（xi的唯一性代表著用戶的身份）。因而，本文的認證協(xié)議是匿名的。

定理5建議的匿名認證協(xié)議能抵抗n個授權(quán)用戶的共謀攻擊。

證明 假定有n個用戶串謀，想計算出應(yīng)用服務(wù)器的秘密驗證信息A和 y。他們根據(jù)各自隱私的驗證向量x1，x2，…，xn，可以建立如下方程組：

其中矩陣A是m×n維的，而向量y是m維的。在上式中，對于n個用戶來說，總的有m×n+m個未知量，而只有m×n個等式。因而若把A和 y作為未知量進行求解對應(yīng)著無數(shù)多解。所以盡管建立了以上方程組，依舊計算不出正確的A和 y。故本文的方案能防止n個用戶的共謀攻擊。

下面繼續(xù)分析方案的效率?？v觀整個方案，其主要操作為：t次茫然傳輸OT1s協(xié)議，以及O(ts)次加法和乘法操作。目前對于茫然傳輸OT1s協(xié)議有著較為成熟的研究成果，存在很多高效協(xié)議（可參考文獻[20]）。本方案的通信開銷為O(s×t×m×n×d)比特，其中d為矩陣（或向量）每個元素（或分量）的比特位長（若在GF(2n)上，則d=1），每個矩陣的比特位長為m×n×d。這里，可以令s=4，t=5，則1/st=1/1 024，滿足1/st足夠小。另外可以取m=8，n=10，d=8（此時xi位長為80比特，其安全級別為O(280)），則總通信開銷約為12.8 kb。因而這些計算和通信開銷對于網(wǎng)絡(luò)或設(shè)備而言均是輕量級的。與方案[3-12]相比，該方案最大的優(yōu)點在于不需要基于任何公鑰密碼體系，因而不需要管理或存儲大量用戶的公鑰。對于應(yīng)用服務(wù)器僅僅需要存儲秘密矩陣A及向量 y(mnd+md bit)，而對于一般授權(quán)用戶僅僅需要存儲隱私的驗證向量 xi(nd bit)。在上面的例子中，n=10，d=8，則xi占用80 bit的空間，因而該方案特別適宜于那些空間受限乃至計算受限的設(shè)備或網(wǎng)絡(luò)，例如智能卡、無線傳感器網(wǎng)絡(luò)或更為一般的普適計算環(huán)境。

4 結(jié)束語

本文從安全多方計算的角度深入研究了匿名認證，把匿名認證抽象為一個具體的多方安全計算問題，繼而構(gòu)造了一個安全高效的匿名認證方案。在方案詳細設(shè)計部分，基于線性方程組求解理論，定義并設(shè)計了一個兩方安全計算矩陣與向量的乘積協(xié)議，利用該原子協(xié)議，提出了一個完整的匿名認證方案。該方案，安全有效，其計算和通信復(fù)雜度低，對存儲開銷要求小，特別適宜于一些資源受限的設(shè)備或終端，例如智能卡、無線傳感器網(wǎng)絡(luò)或更為一般的普適計算環(huán)境。今后的工作將繼續(xù)深入研究安全多方計算理論，以及在其他安全協(xié)議中的應(yīng)用，特別是擬引入安全多方計算基礎(chǔ)協(xié)議設(shè)計高效安全的匿名秘密共享協(xié)議。

[1]Zhu Jianming，Ma Jianfeng.A new authentication scheme with anonymity for wireless environments[J].IEEE Transactions on Consumer Electronics，2004，50（1）：230-234.

[2]Ren K，Lou W J，Kim K，et al.A novel privacy preserving authentication and access control scheme for pervasive computing environments[J].IEEE Transactions on Vehicular Technology，2006，55（4）：1373-1384.

[3]Wang S J.Anonymous wireless authentication on a portable cellular mobile system[J].IEEE Trans on Computer，2004，53（10）：1317-1329.

[4]Brickell E，Camenisch J，Chen L.Direct anonymous attestation[C]//The Proceedings of the 11th ACM Conference on Computer and Communications Security.[S.l.]：ACM Press，2004：132-145.

[5]彭華熹，馮登國.無線匿名認證協(xié)議的匿名性缺陷和改進[J].通信學報，2006，27（9）.

[6]曹雪菲，曾興雯，寇衛(wèi)東，等.一種新的不安全信道上的匿名認證方案[J].西安電子科技大學學報：自然科學版，2007，34（6）：877-880.

[7]張婕，吳振強，霍成義，等.一種移動互聯(lián)網(wǎng)絡(luò)匿名認證協(xié)議[J].計算機工程與應(yīng)用，2008，44（13）：80-83.

[8]馮勇，梁浩.車載自組織網(wǎng)絡(luò)中一種有效的匿名認證方法[J].計算機工程與應(yīng)用，2010，46（23）：126-128.

[9]Lu R X，Lin X D，Zhu H J，et al.A novel anonymous mutual authentication protocol with provable link-layer location privacy[J].IEEE Transactions on Vehicular Technology，2009，58（3）：1454-1466.

[10]Brickell E，Chen Liqun，Li Jiangtao.Simplified security notions of direct anonymous attestation and a concrete scheme from pairings[J].International Journal of Information Security，2009，8（5）：315-330.

[11]Su R W，Cao Z F.An efficient anonymous authentication mechanism for delay tolerant networks[J].Computers and Electrical Engineering，2010，36（3）：435-441.

[12]Chen T H，Chen Y C，Shih W K，et al.An efficient anonymous authentication protocol for mobile pay-TV[J]. Journal of Network and Computer Applications，2011，34（4）：1131-1137.

[13]Yao A C.Protocols for secure computation[C]//Proc 23rd IEEE Symposium on the Foundation of Computer Science（FOCS）.New York：IEEE，1982：160-164.

[14]羅永龍，黃劉生，荊巍巍，等.保護私有信息的叉積協(xié)議及其應(yīng)用[J].計算機學報，2007，30（2）：248-254.

[15]Rabin M O.How to exchange secrets with oblivious transfer，Technical Report 81[R/OL].Harvard University, 1981.http：//eprint.iacr.org/2005/187.

[16]Even S，Goldreich O，Lempel A.A randomized protocol for signing contracts[C]//Proc CRYPTO’82.New York：Plenum Press，1983：205-210.

[17]Brassard G，Crépeau C，Robert J.All-or-nothing disclosure of secrets[C]//Lecture Notes in Computer Science：Advances in Cryptology-Crypto86，1987，263：234-238.

[18]辛小龍.線性代數(shù)（21世紀高等教育系列規(guī)劃教材）[M].北京：高等教育出版社，2006：122-125.

[19]羅文俊，李祥.多方安全矩陣乘積協(xié)議及其應(yīng)用[J].計算機學報，2005，28（7）：1230-1235.

[20]趙春明.可保護授權(quán)隱私性的不經(jīng)意傳輸[D].西安：西安電子科技大學，2006：9-11.

ZHOU Wenqin1，2,ZHANG Yechi1，2,SHI Runhua1，2

1.Key Laboratory of Intelligent Computing&Signal Processing,Ministry of Education,Anhui University,Hefei 230039,China
2.School of Computer Science and Technology,Anhui University,Hefei 230039,China

This paper takes anonymous authentication as a special secure multi-party computation problem and turns to the solution of this problem.This paper constructs an anonymous authentication model based on the basic theory of solving linear equations.A secure two-party multiplication protocol of matrix and vector is presented,and further the whole anonymous authentication scheme is proposed based on this multiplication protocol.The proposed scheme is secure and efficient,and it is very adaptable for resource-constrained devices or networks since its storage cost is low.

cryptography;secure multiparty computation;anonymous authentication;linear equations

把匿名認證抽象為一個具體的安全多方計算問題，轉(zhuǎn)而尋求對該具體問題的求解?；诰€性方程組的求解理論，構(gòu)建了一個匿名認證模型。繼而設(shè)計了一個兩方安全計算矩陣與向量乘積協(xié)議，并基于該協(xié)議提出了一個完整的匿名認證方案。該方案安全、高效，存儲開銷小，特別適宜于資源受限的設(shè)備或網(wǎng)絡(luò)。

密碼編碼學；安全多方計算；匿名認證；線性方程組

A

TP309

10.3778/j.issn.1002-8331.1301-0299

ZHOU Wenqin,ZHANG Yechi,SHI Runhua.Anonymous authentication scheme based on secure multiparty computation.Computer Engineering and Applications,2014,50（24）：81-85.

國家自然科學基金（No.61173187，No.61173188）；安徽省自然科學基金（No.11040606M141）；安徽大學博士科研啟動經(jīng)費項目（No.33190187）；安徽大學“信息安全”新專業(yè)項目（No.17110099）。

周文欽（1990—），男，碩士生；張也弛（1987—），男，碩士生；石潤華（1974—），男，博士，教授，主要研究方向：現(xiàn)代密碼學與安全多方計算。

2013-01-28

2013-05-17

1002-8331（2014）24-0081-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-05-27，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130527.1037.002.html