基于Fingercode和同态加密的指纹认证方案

贺康，李梦醒，赵建，冯全

1.甘肃农业大学工学院，兰州 730000

2.湖南城市学院通信与电子工程学院，湖南益阳 413000

基于Fingercode和同态加密的指纹认证方案

贺康1，李梦醒2，赵建1，冯全1

1.甘肃农业大学工学院，兰州 730000

2.湖南城市学院通信与电子工程学院，湖南益阳 413000

1 引言

近些年来，开放网络中的基于生物特征的身份认证过程中隐私保护问题引起了众多研究者的关注[1]。一些研究者提出可借助于双方安全函数计算技术（two-party Secure Function Evaluation，SFE），使得互不信任双方能进行生物认证。SFE是密码术中的一种技术，它允许不借助可信第三方的帮助，而使互不信任的双方以各自私有数据为输入，计算任意函数而不泄露给对方各自的私有数据。同态加密[2]（Homomorphic Encryption，HE）和加密电路[3]（Garbled Circuit）是常用的SFE工具。最近一些基于同态加密或加密电路的、能保护交易双方生物特征数据隐私的协议被陆续提出[4-8]。指纹认证是最常用的一种生物认证方式，虽然细节点是指纹认证中最常用的特征，但细节点的数量不固定，在利用SFE设计认证方案时，基于它的指纹认证算法复杂性高，计算时间长。Fingercode是一种长度固定的指纹纹理特征，基于该特征的指纹认证虽在精度上略逊于细节点，但基于其的SFE认证方案的计算复杂度却远小于细节点方案[9-10]，因此在开放网络中基于Fingercode的指纹认证更具有实用性。文献[7]提出了一种基于HE技术的指纹识别方案，该方案通过比较两个Fingercode之间的欧氏距离的平方值与阈值的大小来确定客户身份。但该方案在执行时，服务器上的模板并没有受到保护，因此当攻击者入侵服务器时，会轻而易举地获得模板库内用户指纹信息。为此本文设计了新协议，使模板的隐私得以保护；在此基础上实现了基于Fingercode和HE技术的指纹认证方案，并进一步采用了数据压缩技术，使该方案模板存储空间、通信量和计算量进一步减少。

2 Fingercode的提取和量化

Jain等[9]提出了指纹的Fingercode特征，它是一种指纹纹理描述，其提取分为四个步骤：

（1）找出指纹参考点（指纹奇异点）。

（2）在参考点周围的ROI区域中划分NS=NR×NA个扇区，其中NR是沿径向环的划分数量，NA是角度方向的划分数量。

（3）用一组NG个Gabor滤波器组对指纹图像ROI滤波，其中Gabor滤波器在空间域的表达式如下：x，y分别为坐标轴坐标，f是沿着x轴θ角的正弦频率，σx′,σy′是沿着x′,y′轴的高斯包络常数。

（4）计算滤波图像中每个扇形区内灰度值对平均值的平均绝对离差（Average Absolute Deviation），其计算公式为：

其中1≤i≤NS，ni为扇形Si区域中像素点个数，Fiθ(x,y)为经步骤3中Gabor滤波器组处理后的图像，Piθ是Fiθ(x,y)的像素平均值。

这样得到的Fingercode是一个k=NS×NG维的向量，由于Fingercode不是旋转不变的，故生成模板时本文选取NR=5，NA=16，NG=8，即一个Fingercode由k=5×16×8=640个数值组成。为了降低指纹匹配时的复杂度，本文对Fingercode进行了量化：采用l比特表示Fingercode中的每个数值。由于Fingercode不具备旋转不变性，故生成Fingercode特征模板时，本文对于每枚指纹模板，都生成9个Fingercode，它们合在一起作为特征模板；这些Fingercode是对模板指纹图像分别旋转i×11.25°而生成的，i=0，±1，±2，±3，±4。这样可以在一定程度上在匹配时解决模板指纹和现场指纹对齐的问题。本方案中，模板保存在服务器S。图1为Fingercode匹配时的流程图。

3 基于Fingercode和同态加密的指纹认证方案

3.1 加掩膜的欧氏距离平方计算与基本认证协议

指纹信息属于个人隐私信息，通过第二章得到的Fingercode若以明文保存在服务器端时会存在巨大的安全隐患。为了解决这个问题，本文对模板进行了加密，并设计了新的欧氏距离计算协议，为简单起见协议中只计算欧氏距离的平方。

图1 方案流程图

本文采用的加密方法是Paillier[11]加法同态加密，它是一种语义安全的公钥系统，允许在不解密的条件下计算两明文之和的密文，它具有两条主要性质：

其中A和B均为需加密的明文，C为常数，[.]pk表示以pk作为公钥的加密运算。

指纹认证时，用户计算现场指纹与模板Fingercode的欧氏距离的平方，由于用户拥有解密模板的私钥skC，为了防止攻击者非法获取skC后冒充合法用户获取用户信息，认证过程中还必须对模板中的数据进一步保护。为此，服务器可利用同态加密的性质给特征模板加随机掩膜后再发送给用户，这样用户解密后也无法得到特征模板数据，只能计算加了掩膜后的欧氏距离的平方，具体协议如下（为简单叙述起见，假定双方已互换了公钥，且设服务器公钥为，服务器私钥为skC'）：

（1）①服务器选择随机数r1i和r2i(1≤i≤k)，并以用户公钥pkC计算如下结果：

②服务器判断DIS是否小于阈值TD，从而做出接收或拒绝用户身份的判断。

上述协议中通过反复应用公式（3）和公式（4）得到相应的结果，且r1i、r2i都是用户所不知的，其中r1i和r2i是为了防止模板[yi]pkc和[]pkc的泄漏。而对于步骤3，虽然服务器知道了最终结果，但其本身对yi和并不知晓，因此它不会通过结果反推出用户的指纹信息。事实上，上述协议的步骤1完全可以在协议准备阶段完成。

本方案中由于一个指纹模板包括9个Fingercode，因此若使用上述协议，可能需要将其执行9次（当现场提取的Fingercode与模板中9个Fingercode中的任何一个匹配成功时，用户则停止与剩下的模板Fingercode进行认证计算）。

3.2 改进方案

算法1中服务器端模板中每个[yi]pkc和[]pkc都是单独存在于一个密文中，这占用了大量的模板存储空间；其步骤1中对于模板加掩膜计算，由于每个[yi]pkc和[pkc是单独存在的，因此不得不将每个掩膜r1i和r2i单独加密计算，而且每个模板需要单独计算与现场Fingecode的距离，这无疑是增加了本方案的计算复杂度。实际上，Fingecode的单个分量长度比起密文要短得多，为此，本文在算法1的基础上进行了改进，采用了“打包（packing）”技术，将多个分量一起装入一个密文中，且双方执行一次协议即可计算现场Fingercode与模板中9个Fingercode的匹配认证，具有更高的通信与计算效率。

首先本方案改进了模板的生成方法，对于9个Fingercode，以用户公钥计算：

在认证时，双方执行如下协议（为简单叙述起见，假定双方已经互换了公钥，且设服务器公钥为pkC'，服务器私钥为skC'；下述协议步骤1亦可在协议准备阶段完成）：

协议：算法2

⑤用户计算：

为了方便计算，与之相对应的[ci]pkc′和[TPj]pkc′中每段数值前需分别加上(ρ3-ρ1+1)和(ρ3-ρ2+1)个比特0。通过上述数据的打包处理，服务器端模板的存储空间节省了(1−(NB+ND)/9k)%，而整个协议的计算复杂度也得到了明显降低，只需要执行一次协议就可完成现场样本与模板中9个Fingercode的比较。且相较于算法1（设现场样本与模板中9个Fingercode均进行认证计算），本协议在明文加密

⑥用户将[BD]pkc′发送给服务器。

（3）①服务器利用自身私钥skC'解密[BD]pkc′，并分割出：

继而计算出特征模板和现场Fingercode的欧氏距离的平方：

②服务器判断DISj是否小于阈值TD，从而做出接收或拒绝用户身份的判断。

3.3 改进方案中“打包（packing）”长度

3.4 安全性分析

本文的安全模型为半诚实模型（semi-honest model），即假设协议的双方都能忠实执行协议，但可利用协议的中间结果供分析对方的信息。显然，对于用户现场数据xi，其安全性取决于加密算法本身。在算法2中，服务器数据（即模板）的安全性取决于随机掩膜，设的长度为ρ1比特，就模板的单个分量而言，由于同态加密的性质1的加法不是“模”加，对Fingercode的每个分量来说，其统计安全度为2l-ρ1，而整个模板的统计安全度为2k(l-ρ1)。本文设掩膜的熵与各分量的熵(2-l)相同，故取ρ1=2l；而对于算法2中的长度ρ2，它是加在是2l+ceil(lbk)，故取ρ2=3l+ceil(lbk)。

4 实验结果

为了测试本方案的可实施性，本文在MyEclipse 10环境中开发出相应的Java程序，并在PC（Intel Core i5-2430M at 2.67 GHz，内存2 GB）上对本方案进行了仿真。实验前Fingercode已预先提取出，且9个Fingercode均需要与现场提取的Fingercode进行认证。本文取k=640，l=7，则ρ1= 14，ρ2=31，ρ3=32；对于加密算法中安全参数t和RSA模比特长度T，分别设t=80、T=1 024；t=112、T=2 048；t=128、T=3 072三种情况，则NB=90、45、36，ND=1、1、1；相较于算法1，算法2服务器端节省了约98.4%～99.4%的模板存储空间，而明文加密和密文解密的次数分别减少了约95.7%～96.1%和99.2%～99.7%。

表1给出了基于算法2的本方案在三种条件下需要的带宽和运行时间的实验结果。而限于硬件设施的不足，基于算法1的本方案，本文只在t=80、T=1 024情况下进行了仿真，详见表2。

表1 算法2的运行时间和带宽

表2 算法1的运行时间和带宽（t=80）

由实验结果可以看出，在t=80、T=1 024情况下，采用算法2的本方案较直接采用算法1的方案在准备阶段的时间和带宽上节省了约95.8%。在运行阶段的时间和带宽上分别节省了约86.1%和88.5%。由于准备阶段运算是一次性的，服务器可以在空闲时执行后存储，以后用户申请认证时，服务器可以直接使用这些数据，故这些运算在实际认证时不会消耗时间。因此采用算法2的本方案较直接采用算法1的方案更适合在模板加密的情况下进行基于Fingercode和同态加密的双方隐私保护的指纹认证。

5 结论

本文提出了一种基于Fingercode特征的指纹认证方案，该方案中用户以其公钥将模板加密后存储在服务器端，服务器无法获得用户指纹信息，用户隐私得到了保护。认证过程中，利用同态加密的性质，用户和服务器可以在不泄露自己私有数据的条件下联合计算现场指纹和模板对应的Fingercode的欧氏距离，服务器可以利用该距离判断用户身份。本方案对开放网络中进行指纹身份认证过程中双方数据的隐私性具有较好的保护作用。

[1]冯全.基于指纹的隐私保护型身份认证技术[D].北京：北京邮电大学，2010.

[2]Rappe D K.Homomorphic cryptosystems and their applications[D].Germany：University of Dortmund，2004.

[3]Yao A C.How to generate and exchange secrets[C]//IEEE Symposium on Foundations of Computer Science（FOCS’86），1986：162-167.

[4]Feng Q，Su F，Cai A N.Secure remote authentication using fingerprint and fuzzy private matching[C]//2009 International Symposium on Intelligent Information Systems and Applications（IISA 2009）.Qingdao：Academy Publisher，2009：290-292.

[5]Erkin Z，Franz M，Guajardo J，et al.Privacy-preserving face recognition[C]//PrivacyEnhancing Technologies Symposium（PETS’09）.Berlin，Heidelberg：Springer-Verlag，2009.

[6]Sadeghi A R，Schneider T，Wehrenberg I.Efficient privacy-preserving face recognition[C]//LNCS 5984：International Conference on Information Security and Cryptology（ICISC），2009.

[7]Barni M，Bianchi T，Catalano D，et al.Privacy-preserving fingercodeauthentication[C]//ACMWorkshoponMultimedia and Security（MM&Sec），2010：231-240.

[8]Huang Y，Malka L，Evans D，et al.Efficient privacy-preserving biometric identification[C]//18th Network and Distributed System Security Conference（NDSS 2011）.San Diego，California：Internet Society，2011.

[9]Jain A，Prabhakar S，Hong L，et al.Filterbank-based fingerprint matching[J].IEEE Transactions on Image Processing，2000，9（5）：846-859.

[10]Sun H W，Lam K Y，Gu M，et al.An efficient algorithm for fingercode-based biometric[C]//OTM Workshops，2006：469-478.

[11]Paillier P.Public-key cryptosystems based on composite degree residuosity classes[C]//LNCS 1592：EUROCRYPT’99. Berlin，Germany：Springer-Verlag，1999：223-238.

[12]Jain A，Prabhakar S，Hong L.A multichannel approach to fingerprint classification[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1999，21（4）：348-359.

[13]Recommendation for key management[S].NIST Special Publication 800-57，2007-03.

HE Kang1,LI Mengxing2,ZHAO Jian1,FENG Quan1

1.College of Engineering,Gansu Agricultural University,Lanzhou 730000,China
2.College of Communications and Electronic Engineering,Hunan City University,Yiyang,Hunan 413000,China

In order to solve the problem in protecting privacy of remote identity authentication using fingerprint,a novel scheme based on Fingercode and homomorphic encryption is presented.In the proposed scheme,the server’s template is stored in the encrypted version while the server’s templates of the past schemes are plain,so its security is ensured.A protocol is designed to allow that the server and the user can jointly compute the Euclidean distance between the template and the query without releasing the private data.In the protocol,“packing”method is employed to effectively reduce the load of the computation and communication between the server and customer.Analysis and experiment results show that the proposed scheme is secure and practical. Key words：authentication;privacy-preserving;Fingercode;homomorphic encryption;packing

针对开放网络中进行指纹身份认证时的双方指纹隐私保护问题，提出了基于Fingercode和同态加密的指纹认证方案。相较传统方案，该方案中服务器端模板以加密形式保存，保护了用户指纹数据的安全性；设计了安全认证协议，使得服务器和用户可以联合计算双方指纹特征的距离而不会泄露各自特征数据的隐私。协议中采用了数据打包技术，能够明显减轻服务器与用户之间的通讯压力和计算复杂度。分析和实验结果表明，该方案具有安全性和一定的实用性。

认证；隐私保护；Fingercode；同态加密；数据打包

A

TP393

10.3778/j.issn.1002-8331.1307-0190

HE Kang,LI Mengxing,ZHAO Jian,et al.Fingercode based remote fingerprint authentication scheme using homomorphic encryption.Computer Engineering and Applications,2013,49（24）：78-82.

国家自然科学基金（No.61062012）。

贺康（1986—），男，在读硕士研究生，主要研究领域为图像处理；李梦醒（1972—），男，博士，副教授，主要研究领域为信号处理；赵建（1990—），男，在读硕士研究生，主要研究领域为生物认证；冯全（1969—），男，博士，教授，主要研究领域为生物认证、图像处理。E-mail：fquan@gsau.edu.cn

2013-07-15

2013-08-30

1002-8331（2013）24-0078-05