一种基于同态加密的分布式生物特征认证协议

姚海龙 王彩芬 许钦百 李文婷

1(西北师范大学数学与统计学院 兰州 730070) 2(深圳技术大学大数据与互联网学院 广东深圳 518118) 3(兰州城市学院电子与信息工程学院 兰州 730070) (Hailong.Yao@outlook.com)

随着云计算、大数据和物联网产业的逐渐兴起，可靠身份认证需求的不断增长，基于生物特征的认证系统越来越受到行业和用户的青睐.生物特征认证技术因其认证标识的唯一性和永久性而优于传统认证技术，但也因为同样的原因使其面临严重的隐私威胁.带有隐私保护特性的生物特征认证方案可归为4类[1]：生物特征密码系统类、可撤销生物特征类、混合类和基于同态加密类.生物特征密码系统类方案借助由生物特征导出的“帮助数据”绑定或生成密钥实现认证，可根据“帮助数据”的导出方法分为密钥绑定类和密钥生成类；可撤销生物特征类方案使用可更新的密钥和不可逆函数将原始生物特征转换成模板，一旦模板泄露，更新密钥生成新模板即可；混合类方案综合了密码系统类和可撤销类方案优点，根据应用场景使用相应的特征处理方法；基于同态加密的生物特征认证(生物特征同态认证)方案允许生物特征以密文的形式匹配，可在隐私保护的前提下实现身份认证.

生物特征同态认证技术由Ye等人在文献[2]中首次提出，作者在K匿名分层架构基础上设计了一个匿名生物特征访问控制方案.Erkin等人使用Paillier同态加密系统[3]构造了一个可隐私保护的人脸识别系统[4].Rane等人在文献[5]中提出使用汉明距离匹配指纹向量，Osadchy等人在文献[6]中设计了一个基于安全汉明距离同态匹配的人脸识别系统SCiFi.Barni等人在文献[7]中论述了使用“指纹码”在“半诚信”模型中部署分布式生物特征同态认证系统的可行性.Yasuda使用Lauter同态加密系统[8]设计了一个分布式生物特征同态认证方案[9]，You和Liang也设计了类似的方案[10]，但该类方案不能抵御中间人攻击.Cheon等人在BGV同态加密方案[11]的基础上使用单指令多数据操作、单次消息认证码和密文压缩技术设计了一种可完整性验证的生物特征同态认证方案[12]，但因安全距离计算太过复杂，效率不高.

在生物特征同态认证方案中，通常先计算模板向量密文和请求向量密文之间的距离密文，再以解密明文与系统预设阀值比较结果为依据，选择接受或拒绝.使用汉明距离类近似匹配法一般能够获得理想的拒真率和认假率，但距离计算时涉及同态乘法会导致密文膨胀，而由此产生的降维和减噪开销会大大降低系统效率.

本文提出一种辅助向量近似匹配法，在特征向量封装时线性引入随机辅助向量，模板向量和请求向量匹配时它们之间的误差会线性作用在辅助向量上.由于BioHash值的相似性可以反映其原像的相似性，所以我们可以通过评估注册辅助向量和匹配辅助向量间的汉明相似性间接评估模板向量和请求向量间的相似性.在匹配过程中，模板向量和请求向量均以密文形式参与运算，用所得辅助向量的解密明文的BioHash值评估模板向量和请求向量间的相似性，这是整个过程唯一出现明文的环节.另外，向量相似性评估用的是辅助向量的Hash值，无需在密文域进行距离计算，避免了开销最大的同态乘法操作，在实现安全向量匹配的前提下提高了效率.

基于上述安全向量匹配法，本文设计了一种分布式口令辅助的生物特征同态认证协议，即在同态加密方案的基础上以口令为种子生成的辅助向量BioHash值实现生物特征安全高效匹配.该协议无需令牌等硬件标识物，只需在注册模板向量中线性引入随机辅助向量，将辅助向量和模板向量的密文一起存储在外包计算服务器上即可.认证时用户侧只需输入口令和请求向量，服务器侧就能使用辅助向量近似匹配法完成模板向量和请求向量的相似性评估实现认证.

1 背景知识

本节简要介绍了理解文章所需的密码学知识和工具，包括基本符号的定义与说明、同态加密方案和Biohash函数.

1.1 基本符号与说明

首先，我们介绍本文所使用的符号假设与说明.符号Z表示整数环，多项式环R=Z[x](xd+1)，d=2k，k为正整数.对于环Rq=RqR，[r]q表示其中的元素r的系数在(-q2,q2]上模q约减.小写黑体字母a表示环元素或向量，a[i]表示a的第i个系数或分量，而表示它的欧氏范数.a,b∈Rn的内积记为示输入规定参数运行该函数.

1.2 同态加密方案

我们选择BGV方案[11]作为协议的同态加密方案，参数选择参照文献[15].因为协议所实现的辅助向量匹配法不涉及同态乘法，所以我们的同态加密方案是一个不涉及密文刷新算法的基本BGV(basic BGV，BBGV).

定义1.BBGV公钥加密方案.BBGV由系统参数生成算法BBGV.Setup(·)、密钥生成算法BBGV.SecretKeyGen(·)、公钥生成算法BBGV.PublicKeyGen(·)、加密算法BBGV.Enc(·)、解密算法BBGV.Dec(·)和同态加法BBGV.Add(·)六个多项式算法组成.

BBGV.Setup(1λ)：运行E.Setup(1λ)[11]，输入λ、明文模数p和维数k，输出params：阶数d、密文模数q和噪音分布χ∈Rq.

BBGV.SecretKeyGen(params):s←χ，输出私钥sk=s.

BBGV.PublicKeyGen(params,sk):a←Rq,e←χ,计算b=a·s+p·e，输出公钥pk=(a,b).

BBGV.Enc(params,pk,m)：在运行此算法之前需要将明文向量m映射到环元素m∈Rp，r,f,f′←χ，计算c0=b·r+p·f′+m,c1=a·r+p·f，输出c=(c0,c1).

BBGV.Dec(params,sk,c)：输出解密明文m=[[c0-c1·s]q]p.

BBGV.Add(params,c1,c2)：输出c3=c1+c2.

引理1.BBGV同态加法正确性(文献[11]引理7).

在BBGV中，任意噪音有界密文ci的和密文csum，只要满足‖[csum,s]q‖

引理2.BBGV的安全性(文献[11]定理5).

基于RLWE(learning with error over ring)安全假设的BBGV方案满足选择明文攻击下不可区分性(indistinguishability under chosen plaintext attack， IND-CPA)安全.

1.3 BioHash

1) 假设提取了生物特征向量x∈Rn；

2) 用户在Key的控制下生成由m个线性无关的随机列向量组成的矩阵U=(ui=G(key)∈Rn|i=1,…,m,n>m)[16]；

3) 将U中的m个列向量进行施密特正交化得到矩阵O=(oi∈Rn|i=1,2,…,m)；

依据文献[17]可知，通过判断2个生物特征向量的BioHash值的汉明距离可以判定2个生物特征向量的相似性.依据文献[18]可知，BioHash满足抗冲突性、单向性、高熵性和可撤销性.

2 系统架构、敌手能力和安全威胁

为方便后文的论述，本节给出分布式架构下口令辅助的生物特征同态认证模型，并对该模型所面临的安全威胁和敌手能力做出假定.

2.1 分布式生物特征同态认证模型

Fig. 1 Distributed biometric authentication modelbased on homomorphic encryption图1 分布式的生物特征同态认证模型

系统初始化时AS生成系统参数Params；注册阶段AS和用户向CS提交注册请求，CS生成相应注册信息以备后用；认证阶段用户输入口令和生物特征生成认证信息向AS发起认证请求；收到用户请求后AS向CS提交计算请求，并依据CS的反馈和系统预设阀值权衡接受或拒绝用户的请求.

2.2 敌手能力

分布式架构的生物特征认证系统大多部署在非安全环境中，本节参考Dolev-Yao模型对敌手能力做出假定[21]：

1) 敌手能够获得所有经公共信道传输的消息；

2) 敌手能够冒充其他通信实体向用户发送消息；

3) 敌手能够获得用户口令或有效生物特征，但二者不可兼得；

4) 敌手无私钥不能解密信息且不能破坏密码算法；

5) 在评估服务器侧隐私保护能力时假定敌手可以获得系统私钥.

2.3 安全威胁

相比传统认证系统，生物特征认证系统因其认证标识物生物特征便于携带、不易丢失而具有一定优势，但由于生物特征属于个体的固有属性，它和个体的隐私息息相关，并且一旦泄露就会永久失效.因此生物特征认证系统除了要抵御传统安全威胁外还要抗隐私泄露.

2.3.1 传统安全威胁.

分布式生物特征同态认证系统面临的主要传统安全威胁有：

1) 中间数据攻击.假设CS和AS之间的通信链路安全，主要考虑敌手在用户侧设备和服务器之间进行的侦听、截获、插入、删除或阻断等攻击行为.

2) 重放攻击.假设CS和AS之间的通信链路安全，主要考虑敌手重放之前截获的用户和服务器之间消息，仿冒合法用户欺骗服务器获取权限或仿冒合法服务提供商欺骗用户的情形.

3) 内部特权攻击.依据2.1节定义，用户侧设备不掌握系统私钥且功能简单，同态计算、解密和汉明距离计算均在服务器上进行，所以我们主要考虑诚实又好奇的服务器CS因管理不善导致用户生物特征泄露的情形.

2.3.2 隐私泄露威胁

分布式生物特征同态认证系统面临的主要隐私泄露威胁有：

1) 特征样本恢复.敌手通过社工攻击或暴力攻击方法伪造合法用户的生物特征欺骗服务器通过认证以获取权限，这在一定程度上等效于特征模板恢复攻击.

2) 特征模板恢复.敌手利用密码学技术成功恢复出注册存储在CS上的特征模板的攻击.特征模板恢复攻击使该生物特征面临永久失效的风险，并且严重威胁着用户隐私，如中心搜索攻击[20].

3) 隐私威胁.相比前2种攻击，隐私威胁不以获取用户生物特征为目标，而是收集、分析特定用户的认证足迹，建立特定ID和服务间映射以链接用户的隐私.隐私威胁包括身份隐私威胁和交易匿名性威胁[20].

3 协议构造

本节基于BBGV同态方案设计了一种辅助向量近似匹配法，该方法通过比较BioHash向量间的汉明相似性，间接判断模板向量和请求向量间的匹配关系，并以此为基础提出了一种分布式生物特征同态认证协议.

3.1 向量安全匹配

1) 模板向量x和请求向量x′分别封装为(z为辅助向量)[22]

C(Tref)=BBGV.Enc(x+z)，
C(Tsam)=BBGV.Enc(x′).

2) 向量安全匹配

先计算请求向量和模板向量的和密文:

C(Tref)+C(Tsam)=BBGV.Enc(x+x′+z)=
BBGV.Enc(ξ+z)；

再求其解密明文:

BBGV.Dec(BBGV.Enc(ξ+z))=ξ+z；

最后计算辅助向量ξ+z和z的BioHash之间的汉明距离，如果该值小于系统预设阀值δ，则向量x和x′匹配，反之不匹配.

3.2 协议构造

本节在2.1节模型的基础上使用上述向量匹配法设计了一种分布式口令辅助的生物特征同态认证协议(password-assisted biometric authentication protocol based on homomorphic encryption，HE-PaBAP)，协议流程如图2所示，协议中使用的符号及其描述如表1所示.

1) 初始化阶段

AS先选取BiohashH(·)和安全Hash算法h(·)，再运行BBGV.Setup(·),BBGV.SecretKeyGen(·)和BBGV.PublicKeyGen(·)生成同态加密参数params,sk和pk，最后保密sk并发布其他参数.

2) 注册阶段

① AS安全发送元组{SID}给CS，CS验证SID有效后选取随机数w，计算AS的注册凭证Cr安全返回给AS，并将元组{SID,w}写入服务器注册表以备后用；

② 用户侧CD输入用户ID、口令PW、生物特征向量x和与其等长的辅助向量z；

③ 依据定义2和定义3计算生成：矩阵U、矩阵O和模板特征向量密文C(Tref)，安全发送元组{ID,O,z,C(Tref)}给CS请求注册；

④ CS收到用户请求，验证ID有效后存储{ID,O,z,C(Tref)}为用户注册表项.

Table 1 Notations and Descriptions表1 符号与说明

3) 验证阶段

① 用户侧CD′输入用户ID′、口令PW′、生物特征向量x′ 和辅助向量y；

② 盲化ID为MID，并依据定义2和定义3计算生成：矩阵U′、矩阵O′、请求特征向量密文C(Tsam)；

③ 计算摘要h1并发送元组{MID,H(y),C(Tsam),t1,h1}给AS请求认证；

④ AS收到请求，先验证时钟有效后解密恢复(x′+y)再恢复ID′，验证h1为真后盲化ID′为MID′，最后计算摘要h2并发送元组{SID,MID′,C(Tsam),t2,h2}给CS请求计算；

⑤ CS收到请求，验证时钟有效后以SID搜索服务器注册表，如无记录中止协议，否则计算该服务器的凭证Cr′并恢复ID′，再以ID′搜索用户注册表如无记录中止协议，否则验证h2为真后计算特征向量同态加法密文C(Tsum)和摘要h3，并返回元组{C(Tsum),t3,h3}给AS；

⑥ AS收到请求，验证时钟有效后计算z′=BBGV.Dec(C(Tsum))和摘要h4，并发送元组{z′,t4,h4}给CS请求计算；

⑦ CS收到请求，验证时钟有效后计算辅助向量y′=z′-z，再计算H(y′)和H(y)间的汉明距离d和摘要h5，并返回元组{d⊕h(Cr′‖t5),t5,h5}给AS；

⑧ AS收到请求，验证时钟和h5有效性后提取d，并判断d≤δ是否成立，若成立通过认证，否则中止协议.

4 协议性能

我们从安全性、计算复杂度和通信开销3个方面分析讨论HE-PaBAP协议的性能.一般而言，具有后量子安全性的格基同态加密方案的计算效率和通信效率都远逊于传统方案.以Paillier方案[3]和BGV方案[11]为例，前者的加密效率为后者的3倍多、解密效率为1.5倍、同态计算效率为3 100倍，而前者密文尺寸却不到后者的万分之一[23].因此，我们只给出了HE-PaBAP与另外2个基于RLWE-based同态加密的生物特征认证协议Yasuda2017[9]和Cheon2016[12]的比较结果.

4.1 安全性分析

本节分析讨论HE-PaBAP协议面临主要传统安全攻击时的安全性.

4.1.1 抵御传统安全威胁

1) 抵御中间数据攻击

在分布式环境中，部署在云侧CS和AS之间的通信联络安全性较高，中间数据攻击主要发生在用户侧设备和服务器之间的开放链路上.HE-PaBAP协议的实体间传送的信息只有BBGV密文和Hash值，依据引理1,2和2.2节的敌手能力假设，敌手通过窃听不但无法获取用户口令和请求生物特征向量，而且无法追踪特定ID和生物特征之间的对应关系.即使敌手通过其他途径获取了用户口令成功伪造了O′，但伪造有效Tsam通过系统认证的可能性相当于暴力攻击；如果敌手意外掌握了有效生物特征，就能实施在线字典猜测攻击，所以生物特征泄露会导致生物特征认证系统的安全性降低.但是服务器可以部署其他访问控制策略有效抵御这种威胁.因此，在2.2节中的敌手能力假设下HE-PaBAP协议能够抵御中间数据攻击.

2) 抵御重放攻击

根据敌手能力假设，HE-PaBAP协议在运行时敌手能够截获用户在开放链路上发送给服务器的认证请求{MID,H(y),C(Tsam),t1,h1}.但由于BBGV密文具有不可区分性，敌手仅凭截获的认证信息无法建立特定ID与请求密文的对应关系，而且协议中使用了时间戳认证机制，敌手也无法伪造h1.因此，HE-PaBAP能够抵抗重放攻击.

3) 抵御内部特权攻击

HE-PaBAP协议中，在服务器上存储和运算的敏感信息都是密文形式或者Hash值，依据1.1节和1.2节中安全性假设，敌手在没有系统私钥的情况下无法获取用户生物特征信息.系统中只有AS掌握私钥，但生物特征向量密文的存储和匹配都在CS上进行，而AS只能接触到辅助向量的同态加法密文C(Tsam)和C(Tsum).因此，该协议能够抵御内部特权攻击.

4.1.2 抵御隐私泄露威胁分析

1) 特征样本恢复攻击

HE-PaBAP协议不能抵御通过社工攻击手段实现的特征样本恢复攻击；但由于服务器可以使用入侵检测和防御技术抵御暴力嗅探，因此可以抵御通过暴力攻击手段实现的特征样本恢复攻击.

2) 特征模板恢复攻击

特征模板恢复和特征样本恢复类似，都是以获取生物特征向量为目标的攻击，不同的是样本出现在脆弱的用户侧而特征模板向量存储在安全级别更高的服务器上，针对新鲜样本的社工攻击对安全服务器上存储的特征模板难以奏效.因此，特征模板恢复攻击主要利用密码学技术恢复存储在CS上的特征模板向量，最著名的方法是中心搜索攻击[20].HE-PaBAP在注册信息C(Tref)=BBGV.Enc(x+z)中封装的是生物特征向量x和随机向量z的和向量.因为向量z的选取具有随机性，只要CS和AS不共谋，即使在AS被完全腐化的情况下，针对HE-PaBAP协议的中心搜索攻击仅相当于特征样本恢复攻击，而AS未被腐化时不满足中心搜索攻击的条件.

研究显示，从密码学角度防范这种攻击主要有2种办法：匿名化和审计[24].匿名化使得敌手难以建立用户ID和对应特征向量的映射；审计功能可以帮助AS验证CS提供的认证匹配是否预期以阻止模板嗅探.

3) 隐私威胁

HE-PaBAP协议的认证过程中，用户ID被随机数x′+y盲化，而它被封装在BBGV密文中，根据BBGV的IND-CPA安全性，敌手提取和区分特定用户ID的优势是可忽略的；即使在服务器间传递的索引ID也被h(Cr‖t2)盲化.因此，HE-PaBAP可以抵抗身份隐私威胁和交易匿名性威胁.

4.1.3 安全性对比

结合上述分析，HE-PaBAP协议与Yasuda2017[9]和Cheon2016[12]两个经典协议安全性比较结果如表2所示.其中，“Y”表示该协议能抵御某攻击；“N”表示该协议不能抵御某攻击；“P”表示该协议不能抵御特殊情形的某攻击，如社工攻击.为了获得匿名性，Cheon2016[9]需要提前使用密钥交换协议建立安全信道，即该协议在开放环境下不具备匿名性.

Table 2 Comparison of Security Properties表2 安全特性对比

4.2 效率分析

HE-PaBAP协议与Yasuda2017[9]和Cheon2016[12]计算复杂度比较结果如表3所示.其中，“TEnc”表示加密运算、“TDec”表示解密运算、“TAdd”表示同态加法运算、“TMul”表示同态乘法运算.相比同态加密相关的运算开销，Hash运算、明文异或运算和逻辑运算的开销小到可以忽略；为了方便比较，也忽略了Cheon2016[9]中链路安全协议的实现开销.从表3可以看出，3个协议注册阶段开销持平.但是，HE-PaBAP在认证阶段优势明显，相比其他2个协议，HE-PaBAP的用户侧仅有一次加密操作，服务器侧也只有1次同态加法运算和2次解密运算，没有开销最大的同态乘法运算[25].

Table 3 Comparison of Computational Complexity表3 计算复杂性对比

HE-PaBAP协议与Yasuda2017[9]和Cheon2016[12]通信开销比较结果如表4所示.其中，“LHash”表示Hash值的位长度、“Lring”表示密文域环元素的位长度，为了方便比较，我们假设用户ID、时间戳和距离度量空间的位长度与Hash值等长.由表4可见，HE-PaBAP用户侧的通信开销略大于Yasuda2017[9]，但远小于Cheon2016[12].结合表2分析可知，HE-PaBAP由于引入辅助向量，使协议获得了良好的隐私保护和生物特征模板防护特性；Cheon2016[12]用户侧通信开销过大主要原因是为了获得可信认证和隐私保护，用户侧承担了绝大部分的加密和解密任务.

Table 4 Comparison of Communication Overheads表4 认证阶段通信开销对比

5 总 结

本文在BGV同态加密方案的基础上提出一种安全向量匹配法，并在此基础上设计了个口令辅助的生物特征认证协议.该协议能够应对云计算和大数据环境下分布式生物特征认证系统面临的隐私威胁和安全匹配等问题.和传统的双因子生物特征认证协议相比，该协议构建于RLWE安全假设的同态加密方案之上，具有抗量子攻击特性和良好的隐私保护特性；和其他基于RLWE同态加密方案的生物特征认证协议相比，该协议使用评估辅助向量Biohash值间相似性的方法间接评估模板向量和请求向量的相似性，不但降低了生物特征向量泄露的风险，还避免了密文域的同态乘法运算，提高了协议效率.

生物特征认证协议有其先天的便利性和安全性优势，同时也面临更大的隐私威胁，而且分布式计算的可移动性、开放性、设备异构性等特点给它带来了更多的挑战.虽然现有的生物特征认证方案各自在隐私保护和匹配计算效率方面取得了一定的突破，但大多数都无法抵御模板恢复攻击且未提供可信计算保障.因此，设计能够有效抵御模板恢复攻击的分布式可信生物特征认证协议是本文要进一步研究的问题.