基于Bloom过滤和分块的组合指纹模板保护算法

郭蕊，张雪锋

西安邮电大学通信与信息工程学院，西安710061

基于Bloom过滤和分块的组合指纹模板保护算法

郭蕊，张雪锋

西安邮电大学通信与信息工程学院，西安710061

CNKI网络出版：2017-06-12,http://kns.cnki.net/kcms/detail/11.2127.TP.20170612.1652.002.html

1 引言

随着信息技术的快速发展，信息技术与人们的日常工作、学习和生活联系日益紧密，相应的隐私安全问题也越来越受到人们的重视，使得信息安全已成为当前的一个研究热点。在信息安全保护技术中，身份识别技术作为实现访问控制和保障信息系统安全的基础，越来越受到人们关注。信息系统常用的身份认证方式主要有：基于用户名/密码的身份认证；基于IC卡的身份认证；基于动态口令的身份认证；基于生物特征的身份认证和基于USB Key的身份认证等。其中生物特征由于具有的唯一性、不易改变和伪造等良好的安全特性[1]，已经被广泛应用于身份认证的多个领域。由于生物特征模板在众多的生物特征识别技术中都有着广泛的应用，而现实中的生物特征模板存在着泄露的风险，这将导致用户的生物特征隐私性的泄露，而鉴于生物特征的唯一性，一经泄露，其造成的损害将是永久性的，因此，需要有效解决生物特征模板的保护问题。目前针对生物特征模板的保护方法一般分为两类[2]：一是通过寻找某种特征变换，将原始的生物特征数据转换成新的特征模板，以新的模板代替原始模板存储在模板信息库中。另一种生物特征模板保护方法称为生物特征加密技术，它将生物特征与密码学知识相结合，通过将生物特征与密钥绑定，实现对生物特征模板和密钥的安全性的保护。

由于指纹具有唯一性、不变性、易采集等特性，使得指纹模板保护成为生物特征模板保护领域中发展最为成熟、应用最为广泛的技术之一。在传统算法中[3-7]，指纹模板保护均由密钥或转化方式所决定，易受到攻击者的干扰，攻击者一旦获得密钥或转换方式，指纹模板就会被盗取。针对传统算法存在的问题，2011年，Ross等人[8-9]提出将两种不同的指纹图像进行组合构成混合指纹，该算法有效地保护了指纹的隐私性，降低了指纹模板被攻击的可能性。2013年，Li等人[10]提出一种新的指纹模板保护系统，构造出新的指纹，再对其以细节点基础的二阶匹配方式进行匹配，实现了对指纹模板私密性的提高。但是由于在模板匹配时，使用细节点为基础的二阶匹配方法，测试的组合指纹需要以注册的组合指纹模板为基础，这就前期形成组合指纹模板的要求较高，一旦注册的指纹模板出现问题，对于测试组合指纹影响很大，在一定程度上降低了指纹的认证性。2015年Abe等人[11]提出了一种基于Bloom过滤的不可逆指纹的细节点关系编码算法，此算法可以降低指纹被攻击的几率，提高指纹模板的安全性。Li等人[12]提出基于Bloom过滤器的指纹模板保护算法，通过使用Bloom过滤器对于预校准前的二进制指纹模板进行过滤，以提高指纹模板认证的准确性。

针对以上问题，本文提出一种基于组合指纹和Bloom过滤器的指纹特征模板保护算法，该算法基于最小指纹表征[13]，在组合指纹模板存入模板信息库之前，通过Bloom过滤器，将组合指纹模板通过Bloom过滤器所生成的二进制矩阵存入信息库，再对其进行检索与恢复，降低了测试组合指纹对于组合指纹模板的依赖性，提高了指纹模板的认证性。实验仿真结果表明，本文算法有效地提高了指纹模板的认证性，降低了指纹检索恢复时的错误率，提高了匹配的准确率。

2 组合指纹模板

通过指纹识别系统采集同一个人的两个指纹数据，分别记为指纹A和B。从指纹A中提取细节位置集PA和参考点，指纹B提取其方向场OB和参考点。然后，基于细节点的位置、方向和参考点生成组合指纹模板。具体过程如下。

2.1 参考点的选取

在创建组合指纹时，指纹的参考点根据奇异点提取方法进行选取[14]，具体步骤如下：

（1）根据快速指纹增强算法[15]，提取指纹的方向场O，并获得其复数域方向Z：

（2）根据基于复杂过滤器的指纹细节点定位方法[14]及公式（1），计算出细节点映射Cref：

（3）根据公式（4）对于细节点映射Cref进行提高：

其中，arg(z)返回z的角度（其取值范围为(-π,π)）。

（5）将指纹中的所有细节点不断地重复步骤（4）直到参考点被定位。

（6）若通过步骤（4）与（5）仍未定位到参考点，则取指纹图像中细节点中的振幅最大的点作为该指纹的参考点。

2.2 组合指纹细节点模板生成

给定指纹A的细节点坐标集PA={pia=(xia,yia),1≤i≤N}，指纹B的方向场OB，指纹A和指纹B的参考点。如图1所示，组合指纹模板生成过程共分为两个部分：一是细节点位置的校准；二是细节点方向场的分配[10]。

图1 组合指纹模板生成过程

2.2.1 细节点位置的校准

根据上述的指纹参考点选取方法，分别从指纹A和指纹B中提取出两个参考点Ra和Rb，其中参考点Ra的位置坐标为ra=(rxa,rya)，方向角为βa，参考点Rb的位置坐标为rb=(rxb,ryb)，方向角为βb。通过公式（5）进行转化并进行旋转变换，将细节点pia的位置坐标校准为pic=(xic,yic)。

其中(⋅)T为转置，旋转矩阵H为公式（6）：

两个指纹图像经过细节点校准后，其两个参考点Ra和Rb的位置和方向角重叠，组合指纹的细节点位置坐标也随之确定。

2.2.2细节点方向的分配

对于每一个校准后的细节点坐标pic进行方向角分配，具体过程如公式（7）所示：

其中ρi取随机数0或1。由于OB(xic,yic)的范围为(0,π)，因此方向角θic与原始的指纹方向角的取值范围相同，均为(0,2π)，这与原先的指纹图像的方向场取值范围相同。

将所有进行了位置校准的细节点坐标pic平均分配到方向场，则生成了组合指纹模板MC={mic=(pic,θic),1≤i≤N}。该算法通过两个不同的指纹进行组合，创建出新的指纹作为指纹模板，提高了指纹自身的私密性。但是该算法在保证指纹的私密性的同时，会导致指纹的认证性的下降，在一定程度上降低了指纹匹配的准确性。针对这一问题，本文将给出一种能有效提高组合指纹模板认证性的组合指纹模板保护算法。

3 Bloom过滤器保护算法

文献[10]中的组合指纹模板虽然能提高指纹的私密性，但会导致指纹的认证性能下降，使得进行指纹匹配时的错误率提高。为了改进指纹的认证性，本文提出一种基于组合指纹和Bloom过滤的指纹模板保护算法。

Bloom过滤器b是一个初始为全零，长度为n的向量。为了表示一组向量S={x1,x2,…,xn}，Bloom取k个独立的哈希函数h1,h2,…,hk(k∈[0,n-1])，使得每一个x(x∈S)，在Bloom过滤器b的索引hi(x)为1（其中1≤i≤k），且索引值可以多次设置为1，但只有第一次的变化对其有影响[16]。如果要测试元素y是否是S中的元素，就必须判断Bloom过滤器b中的所有索引hi(y)是否全为1。如果全为1的话，说明y极有可能在集合S中；如果没有的话，说明y不是S的成员，传统的Bloom过滤器适用于任何应用程序[17]。

本文基于Bloom过滤器，结合文献[10]中的组合指纹算法所创建出的组合指纹，设计一种组合指纹模板保护和认证算法。

具体的组合指纹模板通过Bloom过滤器的转化过程如图2所示，首先，将组合指纹所生成的模板MC通过细节点柱形编码（MCC）[18]，将其转化为二进制模板J，矩阵J大小为N×M（其中N为一固定值，M根据指纹模板中的细节点个数而定）。再将二进制模板矩阵J进行分块，其水平方向分为l块，垂直方向分为N/w块（每块的垂直大小w），可以得出其模板共分为l×N/w块。初始Bloom过滤器bk为一长度为2w-1的全零向量。对于矩阵J所分的每一块矩阵，分别将其每一列转化为一个十进制数，并将这个十进制在向量bk所对应索引上的0变为1，最终形成Bloom的二进制向量bk(k=1,2,…,l×N/w)。

图2 Bloom过滤器转化过程

4 指纹模板注册检索过程

为了检验本文所提出算法的性能，对于指纹模板进行注册与检索，具体过程如图3所示。

图3 组合指纹模板注册检索流程

假设给定两个组合指纹模板R和P，b_R和b_P是其分别经过Bloom过滤器形成的K维的二进制矢量。由于改进算法的特性，所以R和P的相似分数如下：

在注册时，选取同一个人的两个不同手指指纹，形成组合指纹模板R。将组合指纹模板R通过MCC编码形成二进制指纹模板，再使其进入Bloom过滤器进行转化，形成多对一的Bloom的模板二进制向量b_Ri。在检索时，选取这两个不同手指的另外的两个不同指纹进行组合，构成测试组合指纹P，通过MCC编码形成测试二进制矩阵，再将其进入Bloom过滤器进行转化，形成多对一的Bloom的测试二进制向量b_Pj。最后与组合指纹模板进行匹配，通过公式（8）计算出其相似分数，并将其输出。

5 实验仿真与分析

为了评价本文所给算法的性能，采用指纹库FVC2000-DB1进行测试，该指纹库由100个手指样本组成，每个手指样本取8张指纹，共800张指纹图像。文中选取每个手指样本的两张指纹，选取的指纹图像实例如图4所示。首先将两个紧邻不同手指的两张指纹图像组合后构成100张组合指纹图像，进行柱形编码，然后进入Bloom过滤器进行过滤，形成的二进制向量作为指纹模板信息库。再将这两个不同手指的另外的两个不同指纹图像进行组合，构成100张指纹图像作行柱形编码，进入Bloom过滤器进行过滤，将形成的二进制向量作为测试指纹，所生成的组合指纹模板图像的细节点位置与测试组合指纹图像的细节点位置示例如图5所示。

图4 实验选用的指纹图像示例

图5 组合指纹细节点位置分布

5.1 认证性能分析

首先对文献[10]与本文给出的算法真假匹配的相似分数分布情况进行对比。实验结果如图6所示。

由图6的实验结果可知，组合指纹模板匹配的相似分数分布在0.41～0.89，假匹配的相似分数分布在0.06～0.63，而本文算法中的真匹配的相似分数分布在0.64～0.95，假匹配的相似分数分布在0～0.42之间，相对于文献[10]组合指纹模板保护算法，本文通过Bloom过滤器的组合指纹模板的其真假匹配的相似分数可以更明显地区分，具有更好的指纹认证性能。

对文献[10]与本文所提出的算法进行匹配准确率上的对比，其中错误率为未找到搜索指纹的百分比，普及率是信息库系统中部分搜索到的平均值，实验结果如图7所示。

图6 指纹模板真假匹配的相似分数分布

图7 指纹检索结果

图7的实验结果表明，随着普及率的升高，指纹匹配时的错误率随之降低。在相同的指纹检索时，本文所提出算法在指纹匹配时的错误率相对较低，也更趋于稳定，且在相同的组合指纹图像，不同的Bloom过滤器时，指纹匹配错误率随着指纹模板矩阵分块总数的增多而降低，性能也趋于稳定。

通过在指纹匹配性能上对文献[10]与本文算法进行对比。指纹匹配性能评价参数主要有错误拒绝率（False Non-Match Rate，FNMR）、错误接受率（False Match Rate，FMR）和等错误率（Equal Error Rate，EER）。ROC曲线（Receiver Operating Characteristic），即FMR-FNMR相关性曲线。指纹匹配性能会随着等错误率的降低而提高，因此等错误率是评价指纹性能的主要指标。

接下来，基于FVC2000-DB1数据库，分别对文献[10]所给出的算法与本文提出的改进算法的相关性能进行对比测试，测试结果如图8～10和表1所示。

图8 组合指纹模板通过Bloom过滤器ROC曲线(l=3)

图9 组合指纹模板通过Bloom过滤器ROC曲线(l=5)

图10 组合指纹模板通过Bloom过滤器ROC曲线(l=6)

表1 FVC2000-DB1性能对比

图8～10和表1实验结果表示文献[10]所提出的算法及本文算法的系统性能指标和ROC曲线，从图8～10中可以得出通过不同的Bloom过滤器过滤的指纹模板，其指纹的错误拒绝率和等错误率均有效地降低。由表1可知，在相同的组合指纹图像下，本文所提出的算法相较于文献[10]所提出的算法，等错误率均有所下降，并且随着水平分块数l的增大，模板分块总数的增多，这样的优势越来越明显。通过以上分析说明本文所提出的算法在一定程度上对于指纹模板的认证性能上有所提高，可以有效地降低指纹匹配时的错误率，提高指纹匹配的准确率，具有更好的匹配性能。

5.2 安全性分析

本文所提出的改进算法中存储在指纹数据库的信息为组合指纹通过Bloom过滤器后所形成的二进制向量，在匹配时并未引入任何其他密钥，所以整个系统需要保护的是用户的原始指纹图像。

首先，考虑系统遭受到暴力攻击的情形，在攻击者必须要得知原先组合前的指纹图像以及组合编码方式，鉴于到指纹图像的唯一性等良好的保密性能，这在计算上是不可行；其次，本算法相较于文献[10]算法组合指纹图像在进入Bloom过滤器之前需要进行MCC编码，在未知指纹图像和转换方式的情况下，若攻击者想要获得1 536长度的指纹模板，需要进行21536次尝试，这就需要大量的计算尝试，在计算上是不可行的；同时，组合指纹进入Bloom过滤器时，只是对于组合指纹进行MCC编码后的二进制矩阵进行分块再转化，并没有引入其他因素，具有较好的私密性，因此本文的指纹模板保护算法具有较好的安全性。

通过对于指纹模板进行认证性，匹配性能和安全性的分析，结果表明，本文所提出的算法的各项性能均优于文献[10]所提出的算法。

6 结论

本文设计了一种基于组合指纹的Bloom过滤模板保护算法，通过将组合指纹模板进行MCC编码再进入Bloom过滤器过滤后，形成二进制指纹矩阵，构成指纹模板，进行后续匹配。通过实验表明，该算法在保证了组合指纹模板的私密性的同时，可以有效地提高指纹进行组合构成模板时所下降的认证性，使其在指纹匹配过程中的匹配错误率降低，提高了指纹匹配的准确性。

[1] Maltoni D，Maio D，Jain A K，et al.Handbook of fingerprint recognition[M].2nd ed.London：Springer-Verlag，2009：8-11.

[2] Jain A K，Nandakumar K，Nagar A.Biometric template security[J].Eurasip Journal on Advances in Signal Processing，2008（1）：1-17.

[3] Jin A T B，Ling D N C，Goh A.Biohashing：Two factor authentication featuring fingerprint data and tokenized random number[J].Pattern Recognition，2004，37（11）：2245-2255.

[4] Ratha N K，Chikkerur S，Connell J H，et al.Generating cancelable fingerprint templates[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2007，29（4）：561-572.

[5] Nandakumar K，Nagar A，Jain A K.Hardening fingerprint fuzzy vault using password[C]//Advances in Biometrics，International Conference（ICB 2007），Seoul，Korea，Aug 27-29，2007：927-937.

[6] Nandakumar K，Jain A K，Pankanti S.Fingerprint-based fuzzyvault：Implementationandperformance[J].IEEE Transactions on Information Forensics&Security，2007，2（4）：744-757.

[7] Li J，Yang X，Tian J，et al.Topological structure-based alignment for fingerprint fuzzy vault[C]//19th International Conference on Pattern Recognition（ICPR 2008），Tampa，FL，Dec 8-11，2008：1-4.

[8] Ross A，Othman A.Mixing fingerprints for template security and privacy[C]//2011 19th European Signal Processing Conference，Barcelona，Aug 29-Sept 2，2011：554-558.

[9] Othman A，Ross A.Mixing fingerprints for generating virtual identities[C]//2011 IEEE International Workshop on Information Forensics and Security，Iguacu Falls，Nov 29-Dec 2，2011：1-6.

[10] Li S，Kot A C.Fingerprint combination for privacy protection[J].IEEE Transactions on Information Forensics&Security，2013，8（2）：350-360.

[11] Abe N，Yamada S，Shinzaki T.Irreversible fingerprint template using minutiae relation code with bloom filter[C]//IEEE International Conference on Biometrics Theory，Applications and Systems，2015：1-7.

[12] Li G，Yang B，Rathgeb C，et al.Towards generating protected fingerprint templates based on bloom filters[C]//International Workshop on Biometrics and Forensics，2015：1-6.

[13] ISO/IEC 19794-2：2005，Information technology-biometric data interchange formats-Part 2：Finger minutiae data[S].2005.

[14] Nilsson K，Bigun J.Localization of corresponding points in fingerprints by complex filtering[J].Pattern Recognition Letters，2003，24（13）：2135-2144.

[15] Hong L，Wan Y，Jain A.Fingerprint image enhancement：Algorithm and performance evaluation[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，1998，20（8）：777-789.

[16] Gomez-Barrero M，Rathgeb C，Galbally J，et al.Protected facial biometric templates based on local gabor patterns and adaptive bloom filters[C]//International Conference on Pattern Recognition，2014：4483-4488.

[17] Li G，Yang B，Rathgeb C，et al.Towards generating protected fingerprint templates based on bloom filters[C]//2015 International Workshop on Biometrics and Forensics（IWBF），Gjovik，March 3-4，2015：1-6.

[18] Cappelli R，Ferrara M，Maltoni D.Minutia cylinder-code：A new representation and matching technique for fingerprint recognition[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2010，32（12）：2128-2141.

GUO Rui,ZHANG Xuefeng.Combination fingerprint template protection algorithm based on Bloom filter and block.Computer Engineering andApplications,2018,54（6）：75-80.

GUO Rui,ZHANG Xuefeng

School of Telecommunication and Information Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710061,China

Aiming at the problem that fingerprint combination template protection method is poor in fingerprint authentication,which leads to the high error rate of retrieval,a new algorithm based on Bloom filter and block of fingerprint combination template protection is proposed.The proposed method divides Minutia Cylinder Code（MCC）of the original fingerprint combination template into Bloom filters to form new fingerprint template.This algorithm can effectively improve the authentication of the fingerprint template,reduce the error rate of the fingerprint retrieval,and improve the matching accuracy.The simulation results show that the algorithm can effectively improve the authentication when the fingerprint is combined to form the template,while ensuring the privacy of fingerprints,in the fingerprint matching process,the error rate is reduced,improves the accuracy of fingerprint matching.

fingerprint combination;template protection;Bloom filters;block

针对现有的组合指纹模板保护方法存在的认证性较差，导致检索错误率较高的问题，提出了一种基于组合指纹的Bloom过滤和分块的模板保护算法。该算法通过对原有的组合指纹模板进行MCC编码，再分块应用Bloom过滤器进行过滤，形成新的指纹模板。有效地提高了指纹模板的认证性，降低了指纹检索恢复时的错误率，提高了匹配的准确率。通过实验仿真与结果对比表明，该算法在保证了指纹模板私密性的同时，可以有效地提高指纹进行组合构成模板时所下降的认证性，使其在指纹匹配过程中的匹配时错误率降低，提高了指纹匹配的准确性。

组合指纹；模板保护；Bloom过滤器；分块

2016-11-01

2017-03-07

1002-8331（2018）06-0075-06

A

TP391

10.3778/j.issn.1002-8331.1611-0004

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

郭蕊（1991—），女，硕士研究生，主要研究方向为信息安全，E-mail：guoruiwallace@163.com；张雪锋（1975—），男，博士，教授，主要研究方向为信息安全。