基于容错学习的生物特征认证方案研究

柴 虹

(兰州交通大学铁道技术学院 甘肃 兰州 730070)

0 引 言

随着云计算、大数据和物联网产业的逐渐兴起，可靠身份认证需求的不断增长，基于生物特征的认证系统越来越受到行业和用户的青睐。身份认证是指基于“你所知”和“你所有”这两类标识信息鉴别实体是否是其所声称的特定身份的技术。前者主要指“口令”和“密码”类标识信息；而后者包含“实体附着物”和“实体固有物”两类，实体附着物主要指“身份证”和“令牌”类标识物，实体固有物又称生物特征，包括指纹、脸图、虹膜、掌纹、掌型、指静脉、声纹、DNA等生理特征和步态、签名、击键等行为特征[1]。生物特征认证技术就是基于实体独特的生理或行为特征实现自动身份鉴别的技术，它的核心是身份标识信息的识别和标识信息的保护问题[2]。生物特征不像口令类标识那样容易被忘记、泄露或被破解，也不会像“附着物”那样容易被窃取或转移，因此，生物特征认证是一种可靠、便捷、高效的身份认证技术。

通常情况下，部署一个生物特征认证方案主要考虑两个阶段：注册阶段和验证阶段。在注册阶段，将来自传感器等生物特征采集设备的原始特征数据使用一定的技术进行特征提取，再将这些特征以模板的形式存储于数据库中以备后用。

验证阶段，将来自于特征采集设备的请求特征数据使用同样的技术进行处理得到特征值，再和库中的模板进行比对并输出验证结果。

生物特征识别的准确性受识别算法、采集设备及环境等因素的影响，拒真率(False Rejection Rate，FRR)和认假率(False Acceptance Rate，FAR)是直观评价生物特征认证方案性能的两个指标[3]。

近年来，因传统认证标识滥用导致的安全事故屡见报端[4]，原始生物特征泄漏也使得用户隐私受到严重威胁[5]。基于生物特征的认证技术因其认证标识的唯一性和永久性而优于传统认证技术，但也因为同样的原因使其面临严重的安全风险和隐私威胁。因此，可隐私保护的生物特征认证技术研究受到学术界和行业的高度重视。目前，带有生物特征保护特性的认证技术研究可归类为如下四种：生物特征密码系统类、可撤销生物特征类、混合类和基于同态加密类。生物特征密码系统类方案借助由生物特征导出的“帮助数据”绑定或生成密钥实现认证[6]，可根据“帮助数据”的导出方法分为密钥绑定类[7-8]和密钥生成类[9-10]。可撤销生物特征类方案使用可更新的密钥和不可逆函数将原始生物特征转换成模板，一旦模板泄漏，更新密钥生成新模板即可[11-12]。混合类方案综合了密码系统类和可撤销类方案优点，根据应用场景使用相应的特征[13-14]。基于同态加密的生物特征认证方案允许生物特征以密文的形式参与运算，可在保证系统性能的同时实现隐私保护要求[15-16,68]。因此，使用同态加密可以自然地构造可隐私保护的生物特征认证方案。

基于同态加密的生物特征认证方案一般化实现过程如下：注册阶段，通过生物特征采集设备采集用户的原始生物特征信息，使用类似文献[17]设计的特征向量提取技术将原始特征转换成系统所要求长度的模板向量(如2 048比特)，再使用同态加密算法加密该模板向量生成模板密文，并连同用户标识符一同保存在数据库中以备后用；验证阶段，使用和注册过程相同的技术处理请求用户的生物特征得到相应请求密文，计算请求密文和模板密文之间距离密文(如汉明距离)，使用同态解密算法解密距离密文并和预定义的系统阈值比较，根据比较结果做出接受或拒绝的决定。为了获得低的计算复杂度、FRR、FAR和高的可隐私保护性，基于同态加密的生物特征认证方案研究的焦点主要集中在实用同态加密方案和模板安全匹配协议两个方面。实际上，生物特征认证方案还有一个普遍的研究热点，即“安全草图”的提取和对准问题。本文重点论述方案构造问题，对“安全草图”的提取和对准技术不做展开。

同态加密思想最早于1978年由Rivest在文献[18]中提出，它的历史几乎和RSA一样悠久，但远不及后者名气大。历史上出现过许多著名的同态加密方案[19-22]，遗憾的是它们都因为同态性差而没有流行起来。直到2009年，Gentry[23]借助理想格上的困难问题提出了第一个全同态加密方案(Fully Homomorphic Encryption，FHE)，理论上可以同时实现无限次加法和乘法。FHE方案的构造方法依据安全假设可分为数字理论困难问题类[24-27]、解码随机线性码类[27]和格上困难问题类，格基类可根据设计算法及格困难问题分为理想格类[29-31，67]、NTRU类[32-33]和容错学习类[34-47]，其中以容错学习类方案研究最为广泛。

鉴于此，本文对基于LWE类同态加密技术构造的可隐私保护的生物特征认证方案(简称LWE类生物特征同态认证方案)及其相关技术进行了梳理和介绍。由于同态密码受因性能等因素的影响发展缓慢，加之量子攻击因量子计算技术发展缓慢难以对传统密码产生实质性的威胁，因此针对使用格基同态密码构造可隐私保护的生物特征认证方案的研究尚处于初期。本项目研究了“谷歌学术”和“中国知网”从2009年至今以“Homomorphic”“Authentication”“LWE”和“同态”“认证”“LWE”为关键字的检索结果，筛选了代表性成果分为3类从同态方案构造、生物特征认证方案设计及正确性和安全性分析等方面进行梳理，旨在为解决后量子时代隐私保护领域的安全问题提供一些理论参考。

1 预备知识

1.1 符号与说明

1.2 LWE

1.3 全同态加密及关键技术

1.3.1全同态加密

全同态加密有对称和非对称两种构造形式，我们以传统的非对称密码公钥加密(Public Key Encryption，PKE)结构为例介绍其定义。一个典型的公钥全同态加密方案由四个概率多项式(Probabilistic Polynomial-time，PPT)算法组成：公私钥生成算法(Key Generation，KeyGen)、加密算法(Encryption，Enc)、解密算法(Decryption，Dec)和同态计算算法(Evaluation，Eval)[34]。

公私钥生成算法KeyGen(1λ)：输入安全参数，输出公钥pk，私钥sk和密文计算钥evk。

加密算法Enc(μ,pk)：输入明文及公钥，输出明文比特μ∈{0,1}对应的密文c。

解密算法Dec(c,sk)：输入密文及对应的私钥，输出相应的明文比特，如果密文和私钥不匹配或者发生其他错误，输出⊥。

同态计算算法Eval(evk,f,c1,c2，…,ct)：输入同态计算钥evk和密文c1,c2,…,ct，使用函数f，输出满足Dec(cf,sk=f(m1,m2,…,mt)的cf。

函数f通常描述成有限域上的算术电路形式。同态方案的正确性指的是方程Dec(cf,sk=f(m1,m2,…,mt)不成立的概率可忽略；加密方案的安全性指的是方案满足语义安全性。

定义1一个FHE方案的IND-CPA安全性是指：考虑PPT敌手A和挑战者之间的游戏：

(1) 挑战者生成(pk,sk)对和其他安全参数，保密sk并将其他参数发布给敌手A；

必然存在一个可忽略的多项式函数：

1.3.2全同态加密的关键技术

同态加密技术的根本目标是同态计算，即对密文在密文域进行计算，计算结果解密后相当于对应明文执行相同的操作。为了保证密文计算时的安全性，同态加密在构造密文时引入了噪声。所以，同态计算时噪声也参与了运算，而且依据运算规则累积，甚至会变得很大，以至于影响正确解密。因此，构造同态加密方案的关键在于对同态计算中密文的噪声进行有效管理。下面我们介绍全同态加密中噪声管理的关键技术。

c2就是刷新以后的新鲜密文，它的噪声足够小，可继续执行一次同态运算。如果解密电路深度不超过部分同态加密方案所允许计算的深度，就可以在每轮循环使用启动技术获得全同态加密方案[34]。

模交换技术(Modulus Switching)是在维数模约减技术(Dimension-modulus Reduction)基础上提炼而来的密文噪声管理技术。该技术最早由Brakerski等在文献[34]中提出，后经Brakerski和Gentry在文献[36]中提炼命名为模交换技术，使用这一技术可以无须启动技术就能获得层次型全同态方案。该技术可简单描述如下：

[〈c′,s〉]p=[〈c,s〉]q(mod)2

Power2(y)：y∈Zn，输出(y,2y,…,2「logq⎤-1y)(mod)q∈Zn·「logq⎤。

对于所有q∈Z有：

〈x,y〉=〈BitDec(x),Power2(y)〉(mod)q∈Zq。

SwitchKeyGen(s1,s2)：

ai0∈A、i=0,…,(N-1)，τs1→s2=B。

SwitchKey(τs1→s2,s1)：

1.4 基于RLWE的同态假设

自Gentry的第一个全同态方案诞生以来，各种新方案层出不穷，但基于RLWE安全假设的BV11a[34]、BV11b[35]及BGV12[36]三个方案因其良好的性能受到生物特征认证方案研究者广泛关注，其中BV11a是基于标准LWE构造的FHE，BV11b是基于标准RLWE构造的FHE，BGV12是基于标准LWE(over Ring)构造的层次型全同态方案(Leveled Fully Homomorphic Encryption，LHE或Some What Homomorphic Encryption，SHE)。FHE和LHE的主要区别是：前者是依靠启动技术实现的纯的全同态方案，而后者只能获得深度为L层计算电路的全同态方案，L是安全参数λ的函数。对比研究现有方案发现，多数格上的生物特征认证是基于它们构造的，下面我们简要介绍这些方案的基本原理、参数设置等细节在下一章生物特征同态认证方案介绍中给出。

基于LWE假设的BV11a方案的基本思想是：每次密文计算后通过重线性化技术把密文乘积转换成一个维数与原密文相同的新密文以便实现下一层计算，并使用维数模约减技术约减密文噪声获得部分同态，再借助启动技术实现全同态。BV11a方案是一个同态公钥加密方案，主要包含如下四个环节[34]。

BV11a.Enc(μ,pk)：已知公钥pk=(Α,b)，加密一个明文比特μ∈{0,1}，均匀随机抽取向量r∈{0,1}m，令v=ATr，w=bTr+μ，输出包含电路深度的密文向量c=((v,w),l)，其中，l为电路深度标签，l=0表示新鲜密文。

BV11a.Eval(evk,f,c1,…,ct)：f:{0,1}m→{0,1}，是由加法门“+”和乘法门“×”组成的二进制算术电路，乘法电路的深度为L层。

在同态计算过程中，必须保证输入密文c=((v,w),l)具有相同的电路深度标签，并且满足:

w-〈v,sl〉=μ+2·e(modq)

以保证同态计算的正确性。

BV11a.Dec(c,sL)：经同态计算，输出形如c=((v,w),L)的密文，所以解密只需计算：w-〈v,sL]=μ+2·e(modq)(mod2)，只要噪声足够小，就能正确解密。

BV11b.Enc(m,pk)：对于m∈Rt，均匀随机抽取u,f,g∈χ，输出：c=(c0,c1)=(p0·u+t·g+m,p1·u+t·f)。

BV11b.Dec(c,sk)：对于c=(c0,c1,…,cξ)：

m=〈c,s〉(mod)t

只要〈c,s〉的范数小于q/2就能正确解密。

BGV12方案是Brakerski等在文献[36]中提出的一种层次型全同态加密方案，它与前两个方案不同之处在于它使用模交换技术而非启动技术管理噪声。该方案是一种非对称加密方案，它包含了整数向量和整数多项式上的两个版本。下面我们介绍RLWE上方案的基本结构。

BGV12.Setup(1λ,L)：运行E.Setup(1λ,L)，输出模数qj(j=0,1,…,L)，噪声分布χ和维数nj。

BGV12.KeyGen(n,L)：对于j=L…0，计算：

(1)sj←E.SecretKeyGen(·)，

Aj←E.PublicKeyGen(sj)；

BGV12.Enc(m,pk)：(c,L)←E.Enc(m,AL)。

BGV12.Dec(c,sk)：m←E.Dec(c,sj)。

2 RLWE上的生物特征认证方案

2.1 LWE上的生物特征认证方案-BV11a型

2016年，Aono等[53],提出了一种基于LWE上PKE同态的快速安全的生物特征认证方案它的密文尺寸只有文献[54-55]的一半但计算效率提高了1 000倍以上。该系统中，作者设计了一种灵活的向量编码方法，它可以自然地处理二进制串及其密文的同态操作。生物特征的二进制模板密文在“诚实又好奇”的服务器上进行XOR操作完成比对，并返回结果即可。

2.1.1生物特征认证方案设计

将定义2应用于文献[56]提出的协议，构成的新协议由三部分组成：用户CD/CD′、计算服务器CS和认证服务器AS。协议过程如下：

(1) 参数生成：AS运行ParamGen(1λ)和KeyGen(1λ,pp)生成pp、pk和sk，保存sk并公布pp=(q,l,p=2)、pk=(A,P,n,s)。

(3) 验证阶段：CD′发送(id,Enc(A′))给CS，CS计算CT=Enc(A′)+Enc(R+A)，并把(id,H(R),CT)发送给AS；AS计算R′=Decsk(CT)=R+A+A′，并判断H(R)=H(EC(R′))是否成立，若成立返回R，否则返回错误提示，其中EC(·)为纠错函数。

2.1.2正确性和安全性分析

在上述方案中，单个密文c=Enc(·)=(c1,c2)，对应的明文m=Dec(·)=〈c,S〉(modp)，其中：

〈c,S〉=c1S+c2=(e1A+pe2)S+e1P+pe3+m=

e1(AS+P)+pe2S+pe3+m=

因此，只要p(e1R+e2S+e3)足够小，就能正确解密。

对于同态加法密文Add(c,c′=c+c′(mod)p，解密所得明文Dec(·)=[c+c′,S](modp)，其中：

2(e1A+pe2)S+2(e1P+pe3)+(m+m′)=

因此，只要2p(e1R+e2S+e3)足够小，就能正确解密。由于本方案只涉及同态加法，故同态乘法的正确性这里不再赘述，可参见文献[53]。

考虑PPT敌手Α和挑战者之间的游戏：

(1) 挑战者生成(pk,sk)对和其他安全参数，保密sk并将其他参数发布给敌手Α。

2.2 RLWE上的生物特征认证方案-BV11b型

2015年，Yasuda等[57]在BV11b[35]的基础上提出了一种SHE生物特征认证方案，该方案设计了两种密文封装方式用于模板向量和请求生物特征向量的封装。第一种密文封装方式基于Lauter等[58]提出的消息编码技术，它能有效提高密文同态计算的效率和安全性；第二种密文封装方式便于模板密文和请求特征密文之间汉明距离的安全计算。2018年，游林等[68]提出了类似的方案。

2.2.1生物特征认证方案设计

ct(1)(T)=Enc(F1(T),pk)，

ct(2)(Q)=Enc(F2(Q),pk)，

C2(x)=-C1(x)+2

作者在文献[59]的基础上使用定义3设计了一个RLWE上的生物特征认证协议，该协议由三部分组成：用户CD/CD′，计算服务器CS和验证服务器AS，协议过程如下：

(1) 参数生成：AS生成(pk,sk)对，并把pk发布给CD和CS。

(2) 注册阶段：CD(id)提取生物特征模板T并计算ct(1)(T)，发送二元组(id,ct(1)(T))给CS存储。

2.2.2正确性和安全性分析

上述方案完全构建于BV11b，该SHE方案解密的正确性限制条件是||〈c,s〉|∞

对于单个密文c=BV11b.Enc(·)=(c0,c1)，对应的明文m=BV11b.Dec(·)=〈c,s〉(modt)，其中：

〈c,s〉=(p0u+tg+m)+s(p1u+tf)=

m+t(g+sf-ue)∈Rq

对于两个密文c、c′，同态运算后解密所得明文：

m+m′=BV11b.Dec(·)=〈c+c′,s](modt)

m·m′=BV11b.Dec(·)=〈c·c′,s〉(modt)

其中：

〈c·c′,s〉=〈c,s〉+〈c′,s〉∈Rq

〈c·c′,s〉=〈c,s〉·〈c′,s〉∈Rq

而且，RLWE方案在PLWE安全假设下具有IND-CCA1的安全性[65]。

2.3 RLWE上的生物特征认证方案-BGV12型

2016年，Cheon等[60]在BGV12的基础上提出了一种SHE上生物特征认证方案，该方案借助单指令多数据操作(Single Instruction Multiple Data，SIMD)、单次消息认证码[62](one-time MAC，OTM)和密文压缩技术[63]有效提高了密文运算效率、保障了密文的完整性并降低了密文尺寸。2018年，宋新霞等[69]学者也提出了类似的方案。

2.3.1生物特征认证方案设计

[U→S] (u,v,G)←(h,hτ,{H2(hj)|j∈[T]})

[S]h*←(vu-r1)-r0，Check ifH2(h*)∈G

根据上述约定，假设用户U/U′和服务器S之间的通信安全，协议过程描述如下：

(1) 参数生成：

U使用BGV12.Setup(·)和BGV12.KeyGen(·)生成(pk,sk)对和其他参数，并把pk发布给S。

(2) 注册阶段：

(3) 验证阶段：

2.3.2正确性和安全性分析

在上述方案中，注册阶段的安全性由BGV12方案保证；匹配阶段，用户侧的安全性由定理2保证，服务器侧的安全性由定理3保证，证明参见文献[36]的定理1和定理2。

定理2对于元素长度为l(λ)比特的整数集合Rl，假设OTM方案能够抵抗单次存在性伪造攻击，那么对于任意PPT敌手Α，必然存在一个可忽略函数negl(·)满足：

上述定理说明，在OTM方案安全假设下，即使掌握解密密钥的用户侧敌手也无法使用一个错误的输入通过验证。

定理3假设BGV12方案提供IND-CPA安全性，上述生物特征认证方案能够抵抗“半诚实”攻击。

因为BGV12方案提供IND-CPA安全性，在“半诚实”的场景中，必然存在仿真器能够利用SHE密文的统计不可区分性、MAC的密钥和隐藏于离散对数背景中的匹配结果生成与真实协议统计不可区分的观点，使得敌手无法统计区分仿真器和真实协议的输出。

2.4 性能分析

表1 三个方案中安全距离计算时耗及单密文尺寸

(a) Xeon E5- 2660/2.60 GHz,(λ=128,n=921,q=232-1,l=2048,σ=8);

(b) Xeon X3480/3.07 GHz,(λ=80,n=2 048,q=264-1,t=2 048,σ=4);

(c) Xeon E5- 2697/2.60 GHz,(λ=80,n=8 191,q=240-1,t=2 048,σ=8)。

3 挑战和机遇

基于同态加密的生物特征认证方案的可用性和安全性主要依赖于FHE方案的性能，而现有的FHE方案都因其算法复杂度高、密文尺寸过大、方案实现不够简洁而难于部署应用；有些方案缺乏可信计算安全，容易遭受“中心搜索攻击”[64-66]如Yasuda2015[57]；有些依靠“启动技术”约减密文噪声的方案，仍然存在循环安全隐患；加之，标准化工作缓慢，可隐私保护的生物特征认证方案距离产业化实用还有一段很长的路。尽管困难重重，但LWE类同态隐私保护方案的技术优势依然明显且研究意义重大[70]。

(1) 实现可隐私保护的生物特征同态认证方案只需有限次同态计算，因此优秀的格密码技术和SHE方案是该领域永恒的研究热点。

(2) 模板向量和请求向量间的安全匹配及计算方法是本领域的另一个研究热点，正如Anon2015展示的一样，优秀的密码原语和原语的使用方法同样重要。

(3) 随着移动云计算、分布式多方计算和差分隐私服务的兴起，多密钥同态计算及多维特征认证等技术也将成为本领域的研究热点。

生物特征同态认证只是众多有隐私保护需求的相似性评估类应用之一，因此研究LWE类同态隐私保护技术对于满足应用需求和加速同态密码的标准化进程都具有重要的意义。

4 结 语

在信息技术高度发达和发展的今天，云计算和分布式计算等外包计算服务正在使“懒人模式”成为可能并且形成习惯。要使外包服务无后顾之忧，用户隐私保护问题就亟待解决，同态加密技术无疑是理想的候选技术，利用RLWE等格密码技术构造同态加密方案保护生物特征认证中的隐私数据是后量子时代密码工作者的首选技术。文章在介绍生物特征认证和全同态密码关键技术的基础上研究了3类基于RLWE的同态加密方案BV11a、BV11b和BGV12的可隐私保护的生物特征认证方案的构造方法、安全性和效率问题，并指出了该领域可能的机遇和挑战。