基于安全多方计算的匿名认证方案

周文钦，张也弛，石润华

1.安徽大学 计算智能与信号处理教育部重点实验室，合肥 230039

2.安徽大学 计算机科学与技术学院，合肥 230039

基于安全多方计算的匿名认证方案

周文钦1，2，张也弛1，2，石润华1，2

1.安徽大学 计算智能与信号处理教育部重点实验室，合肥 230039

2.安徽大学 计算机科学与技术学院，合肥 230039

1 引言

21世纪是信息时代，随着科技的快速发展，信息越来越重要。信息作为一种资源，它的普遍性、共享性、增值性、可处理性和多效用性，使其对于人类具有特别重要的意义。信息安全的实质就是要保护信息系统或信息网络中的信息资源免受各种类型的威胁、干扰和破坏，即保证信息的安全性。信息安全涉及的范围很广，大到国家军事政治等机密安全，小到如防范商业机密泄露、防范青少年对不良信息的浏览、个人信息的泄露等。

身份认证在信息安全领域处于非常重要的地位，是其他安全机制的基础。只有实现了有效的身份认证，才能保证访问控制、安全审计、入侵防范等安全机制的有效实施。另外，它也是密钥分发、密钥交换及其他多方安全协议的必要前提，否则容易遭受中间人攻击（Man-inthe-middle Attacks）。在各种身份认证技术中，匿名认证[1]已成为重要的研究方向。所谓匿名认证，就是在保护用户身份隐私的同时，还能够对用户或终端进行认证。匿名认证在移动通信、电子商务、远程登录，以及其他要求保护用户隐私[2]的场景中有着非常重要的应用。

已有的匿名认证协议主要利用现代密码技术，尤其是公钥密码和零知识证明技术，例如文献[3-5]。但这些协议计算量较大，公钥证书管理和存储开销较高，因此效率不高。尽管后来存在很多改进方案[6-12]，但多数作者只是想尽办法缩短私钥或签名的长度，以此提高方案效率。依然避免不了计算复杂度高、管理和存储开销高的局限性，因而其应用场景受限。特别是在一些智能卡、无线传感器网络或更为一般的普适计算环境下难以推广。

在信息安全领域中，存在很多研究分支，其中现代密码学和安全多方计算是较活跃的两大分支。一般来说，在一个由多个参与方构成的联合计算系统中，如果主要关注的是对系统外部攻击者（例如信道上的窃听者）的防范，则是现代密码学的研究范畴；如果关注的要点是系统内部各参与者可能的作弊方式（例如非法获得其他参与方的隐私输入）与防范，则为安全多方计算的研究范畴。尽管存在很多基于现代密码技术的认证乃至匿名认证协议，但很少有作者从安全多方计算的角度去研究它们。本文中，尝试新的构造方法，引入安全多方计算技术，设计了一个安全高效的匿名认证方案。与已有的方案相比，该方案具有计算量小，存储开销小的优点，特别适宜于智能卡、无线传感器网络或是更为一般的普适计算环境。

本文的主要创新点如下：

（1）把匿名认证抽象为一个具体的多方安全计算问题，继而转向对该具体问题的求解。

（2）基于求解线性方程组的一般理论，建立了一个匿名认证模型。

（3）定义并设计了一个安全有效的两方矩阵与向量乘积协议。

（4）提出了一个新型高效的匿名认证方案。

2 预备知识

安全多方计算[13（]Secure Multiparty Computation，SMC）研究一组互不信任的参与方之间保护隐私的合作计算问题，对解决网络环境下的信息安全具有重要价值。

定义1（安全两方计算[14]）是一种安全的分布式计算协议，在该协议中，两个参与方Alice与Bob分别持有各自的隐私输入x与 y，对某个给定的函数 f，他们希望协作计算函数值 f(x，y)，但Alice与Bob都不愿意向对方暴露自己的输入。

目前安全多方计算已成为信息安全领域热点研究内容。为了解决具体的计算问题，人们构造了很多原子协议，例如秘密比较、比特承诺、茫然传输等基础协议。其中，茫然传输（Oblivious Transfer，OT）的概念最早由Rabin在文献[15]中提出，随后该概念被Even等人在文献[16]中发展为二中选一的OT（简记为OT12），再后来Brassard等[17]又提出了n选一的OT（简记为OT1n）。

定义2（OT1n协议）发送方Alice有n个秘密m1，m2，…，mn，接收方Bob掌握一个整数i∈{1，2，…，n}，协议结果要求：

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

（2）Alice对于Bob的选择i一无所知，即她不知道Bob到底选择了哪一个秘密。

此外，在本文的匿名认证方案中，利用了线性方程组的求解理论。而对于线性方程组的求解存在如下定理1、2[18]。

定理1n元线性方程组Ax=b有解的充分必要条件是系数矩阵A的秩等于增广矩阵ˉ的秩，即R(A)= R(ˉ)。其中 A是m×n维的矩阵，x和b是n维的列向量。

定理2n元线性方程组Ax=b有解时，如果R(A)= n，那么方程组只有唯一解；如果R(A)＜n，那么方程组有无穷多解。

3 基于安全多方计算的匿名认证

首先把匿名认证抽象成一个特定的安全多方计算问题，继而从安全多方计算的角度设计了一个全新的匿名认证方案。该方案既能提供认证功能又能保护用户身份的隐私信息。与已有方案相比，建议的方案有着显著的优点。

3.1 模型及方案

在本文的模型中，共有三类设备：注册服务器，应用服务器，用户（或终端）。它们之间通过有线或无线网络连接。整个网络中可能存在多种应用服务器（例如有满足特定用户对敏感数据库进行查询的服务器，有提供软件和下载功能的服务器等），以及分属于不同角色的用户，不同角色具有不同的访问权限（例如，在医疗卫生网络环境中，医生、护士与病人的权限各不相同）。注册服务器为不同角色及相应的应用服务器生成认证凭证和相应的验证信息。用户或终端访问应用服务器时，先要进行匿名认证，只有合法的用户才能访问或享受应用服务器提供的资源或服务。

为了满足以上模型的匿名认证需求，构造一个用于匿名认证的函数 f：X×Y→Z，要求满足如下属性：存在一个x∈X，使得有多个 yi∈Y对应一个z∈Z，即有f(x，yi)=z(i=1，2，…，t)。继而引入安全多方计算技术，得到具有匿名特性的认证方案，该方案包括两个阶段：注册阶段和认证阶段。在注册阶段，注册服务器给每个合法用户分发一个唯一的子秘密 yi，对于每个 yi均满足 f(x，yi)=z，而把 x和 z秘密发送给验证方（即相应的应用服务器）。在认证阶段，合法用户与应用服务器借助多方安全计算基础协议，在不泄露各自隐私输入 yi和(x，z)的条件下，安全计算 f(x，yi)。接着应用服务器验证是否有 f(x，yi)=z。若相等则完成对用户的验证并对其提供相应的应用服务，否则验证失败。

以上方案的关键是构造匿名认证函数 f，其主要特征为多对一的二元映射。对于一些存在多个解的线性方程组，刚好满足“多对一”的特征。因而，把线性方程组的求解理论引入到协议设计中。在建议的匿名认证协议中，当验证用户凭证时需要两方安全计算矩阵与向量的乘积，所以首先设计了一个安全的两方矩阵与向量乘积基础协议。

3.2 安全两方矩阵与向量乘积协议

定义3（安全两方矩阵与向量乘积协议）Alice有一个私有矩阵A（A不可逆），Bob有一个私有向量x。Alice需要得到的计算结果为 y=Ax（A与x满足相乘的条件，即A的列与x的行数相等），且同时满足：

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

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

下面根据线性方程组的求解理论，设计了一个安全的两方矩阵向量乘积协议。

协议1安全两方矩阵向量乘积协议

输入 Alice秘密输入m×n的矩阵A；Bob秘密输入n维的向量x。

输出 Alice得到 y//在不泄漏各自隐私的前提下，Bob协助Alice计算y=Ax。

（1）Alice和Bob约定两个数值s和t（这里st足够大，使得1/st小到可以忽略）。

（2）Alice产生t个随机矩阵A1，A2，…，At，使A= A1+A2+…+At。

（3）对每一个 j=1，2，…，t，Alice和Bob执行下面的子步骤：

①Alice产生一个秘密的随机数k，1≤k≤s。

②Alice发送(H1，H2，…，Hs)给Bob，这里Hk=Aj，并且其余的Hi是随机矩阵，因为k是一个秘密数据，只有Alice知道，Bob不可能知道哪一个Hi是Aj。

③对所有的i=1，2，…，s，Bob计算Hix+rj，这里rj是一个随机向量。

④用茫然传输OT1s协议，Alice取回结果：Hkx+rj= Ajx+rj。

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

注：以上所有矩阵的维数相同，且其列数与向量 x的维数相同。

3.3 匿名认证协议

简单起见，假定存在一个应用服务器（例如数据库），一个注册服务器（其功能也可以直接由应用服务器承担），另外有一些需要访问服务器的终端或用户（通常为同一个群体或角色，例如医生、护士、病人）。具体协议包括两个阶段：注册阶段和认证阶段。

（1）注册阶段：注册服务器按如下的方法为每个终端或用户生成一个秘密信息，作为以后认证的凭证，并把相应的验证信息秘密送给应用服务器。

①注册服务器随机生成一个m×n矩阵A及m维列向量 y(1＜m≤n)，建立线性方程组 Ax=y，并要求R(A)=R(Aˉ)，且R(A)＜n，即此线性方程组有无穷多个解。

②注册服务器为每个合法用户Ui生成一个唯一的n维向量xi，要求xi满足方程组Axi=y，即xi是线性方程组Ax=y的一个解，且任何一对用户的秘密向量不相等，即 xi≠xj(i≠j)。

③通过面对面的方式或其他安全方式（端到端的加密链路），注册服务器把xi秘密发送给用户Ui作为将来的认证凭证；而把相应的秘密矩阵 A以及秘密向量 y秘密发送给应用服务器。

（2）认证阶段：应用服务器将完成对用户Ui的认证。

①用户向应用服务器提出认证请求。

②应用服务器和用户Ui调用两方矩阵与向量的安全求积协议（协议1）。在具体的两方矩阵与向量安全求积协议中，用户Ui输入xi（n维列向量），应用服务器输入矩阵 A，执行协议后，应用服务器得到m维列向量y′=Axi，且要求两方都不能获取对方的隐私输入信息。

③应用服务器验证是否有 y′=y，若相等则被认证的用户是合法的，从而对其开放相应的资源或服务，否则验证失败。

注：以上计算可以在域GF(2n)上完成，从而用户保存的n维的秘密向量可以看作是一个n位的二进制整数。

3.4 协议分析

以上方案的正确性基于n元线性方程组的求解理论（见定理1、2），因篇幅原因这里就不展开证明。下面主要分析其安全性，由具体协议可看出注册阶段的秘密分发由通信链路的保密性所保证，而认证阶段的安全性主要基于两方矩阵与向量乘积协议的安全性。详细分析参见定理3～5。

定理3在半诚实模型下，协议1在计算上是安全的。

证明 所谓半诚实模型[19]，即所有参与方能够诚实执行协议，但是，同时记录下所有的中间结果，并试图从中推导出额外的信息。

另外，对于Alice来说，尽管她能多次获得包含x的计算结果 Ajx+rj，但均加了一个随机向量rj，而rj并不对她公开，因而Alice得不到任何有关x的秘密信息；再有矩阵 A是不可逆的，且线性方程组Ax=y有无数多解，因而Alice不可能根据Ax的结果计算出x。所以x对于Alice是无条件安全的。

定理4建议的方案保护了认证用户的身份隐私，即认证向量xi，因而是匿名的。

证明 在认证阶段，应用服务器和请求认证的用户协作执行协议1。而定理3已经证明了协议1的安全性。对于应用服务器来说：一方面，尽管她能多次获得包含用户验证向量xi的计算结果Ajxi+rj，但每次交互均加了一个随机向量rj，而rj并不对她公开，因而她得不到任何有关 xi的秘密信息；另一方面，矩阵 A是不可逆的，这由注册服务器所保证。且线性方程组Ax=y有无数多解，因而她不可能根据Ax的结果计算出xi。所以，应用服务器得不到与合法用户的验证向量xi有关的秘密信息（xi的唯一性代表着用户的身份）。因而，本文的认证协议是匿名的。

定理5建议的匿名认证协议能抵抗n个授权用户的共谋攻击。

证明 假定有n个用户串谋，想计算出应用服务器的秘密验证信息A和 y。他们根据各自隐私的验证向量x1，x2，…，xn，可以建立如下方程组：

其中矩阵A是m×n维的，而向量y是m维的。在上式中，对于n个用户来说，总的有m×n+m个未知量，而只有m×n个等式。因而若把A和 y作为未知量进行求解对应着无数多解。所以尽管建立了以上方程组，依旧计算不出正确的A和 y。故本文的方案能防止n个用户的共谋攻击。

下面继续分析方案的效率。纵观整个方案，其主要操作为：t次茫然传输OT1s协议，以及O(ts)次加法和乘法操作。目前对于茫然传输OT1s协议有着较为成熟的研究成果，存在很多高效协议（可参考文献[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。因而这些计算和通信开销对于网络或设备而言均是轻量级的。与方案[3-12]相比，该方案最大的优点在于不需要基于任何公钥密码体系，因而不需要管理或存储大量用户的公钥。对于应用服务器仅仅需要存储秘密矩阵A及向量 y(mnd+md bit)，而对于一般授权用户仅仅需要存储隐私的验证向量 xi(nd bit)。在上面的例子中，n=10，d=8，则xi占用80 bit的空间，因而该方案特别适宜于那些空间受限乃至计算受限的设备或网络，例如智能卡、无线传感器网络或更为一般的普适计算环境。

4 结束语

本文从安全多方计算的角度深入研究了匿名认证，把匿名认证抽象为一个具体的多方安全计算问题，继而构造了一个安全高效的匿名认证方案。在方案详细设计部分，基于线性方程组求解理论，定义并设计了一个两方安全计算矩阵与向量的乘积协议，利用该原子协议，提出了一个完整的匿名认证方案。该方案，安全有效，其计算和通信复杂度低，对存储开销要求小，特别适宜于一些资源受限的设备或终端，例如智能卡、无线传感器网络或更为一般的普适计算环境。今后的工作将继续深入研究安全多方计算理论，以及在其他安全协议中的应用，特别是拟引入安全多方计算基础协议设计高效安全的匿名秘密共享协议。

[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]彭华熹，冯登国.无线匿名认证协议的匿名性缺陷和改进[J].通信学报，2006，27（9）.

[6]曹雪菲，曾兴雯，寇卫东，等.一种新的不安全信道上的匿名认证方案[J].西安电子科技大学学报：自然科学版，2007，34（6）：877-880.

[7]张婕，吴振强，霍成义，等.一种移动互联网络匿名认证协议[J].计算机工程与应用，2008，44（13）：80-83.

[8]冯勇，梁浩.车载自组织网络中一种有效的匿名认证方法[J].计算机工程与应用，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]罗永龙，黄刘生，荆巍巍，等.保护私有信息的叉积协议及其应用[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]辛小龙.线性代数（21世纪高等教育系列规划教材）[M].北京：高等教育出版社，2006：122-125.

[19]罗文俊，李祥.多方安全矩阵乘积协议及其应用[J].计算机学报，2005，28（7）：1230-1235.

[20]赵春明.可保护授权隐私性的不经意传输[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

把匿名认证抽象为一个具体的安全多方计算问题，转而寻求对该具体问题的求解。基于线性方程组的求解理论，构建了一个匿名认证模型。继而设计了一个两方安全计算矩阵与向量乘积协议，并基于该协议提出了一个完整的匿名认证方案。该方案安全、高效，存储开销小，特别适宜于资源受限的设备或网络。

密码编码学；安全多方计算；匿名认证；线性方程组

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）；安徽大学博士科研启动经费项目（No.33190187）；安徽大学“信息安全”新专业项目（No.17110099）。

周文钦（1990—），男，硕士生；张也弛（1987—），男，硕士生；石润华（1974—），男，博士，教授，主要研究方向：现代密码学与安全多方计算。

2013-01-28

2013-05-17

1002-8331（2014）24-0081-05

CNKI网络优先出版：2013-05-27，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130527.1037.002.html