基于指紋奇異點和Bloom過濾器的指紋加密方案

林波，劉嘉勇，徐鵬，張鵬

（1.四川大學電子信息學院，成都 610065；2.四川大學網絡空間安全學院，成都 610065；3.成都卓越華安信息技術服務有限公司，成都 610000）

0 引言

生物特征保護技術主要分兩類[1]：一是生物特征加密技術，將生物特征與傳統密碼算法結合，生成保護模板。生物特征加密概念最早由文獻[2]提出，其安全性依賴于加密算法或安全密鑰，因此其安全性與基于口令的系統的安全性一樣，一旦密鑰丟失，生物特征數據就會被盜。二是可撤銷模板保護技術，基于生物特征變換后，形成新的特征模板，存儲在信息庫中。文獻[3]率先引入可撤銷生物保護技術的概念，在圖像域中應用不可逆幾何變換，獲得可撤銷的面部圖像和指紋。在進一步的工作中，文獻[4]引入基于Bloom過濾器的模板保護技術，通過將未受保護的二進制模板轉換為不可逆模板。這種方法已應用于多種生物特征，如虹膜[4]、面部[5]和指紋[6]等。由于生物特征中指紋具有唯一性、易采集，算法也最成熟，使得指紋識別的理論研究和實際應用最為廣泛。本文以指紋作為研究對象，研究指紋模板加密技術。

1 相關研究工作

指紋識別系統易受環境影響，當手指磨損嚴重，干濕度發生變化都將對其識別產生影響，同時指紋模板也易被復制、被破解，造成安全隱患。文獻[7]提出了基于指紋細節點比特串的不可逆模板保護方案，采用幾何哈希技術變換指紋原始細節點，用相對特征向量表示細節點在圖像中的相對位置，然后投影到三維空間矩陣中，以可變的順序遍歷它，提取出特征比特串，生成指紋保護模板。該算法不僅具有很好的安全性而且不需要對指紋進行預配準，但是構造三維空間的計算代價較大，且提取的指紋比特串長度很長，在匹配時會花費很多時間，因此實際應用性不強。文獻[8]在此基礎上提出了一種基于指紋奇異點的二進制串提取方法，首先提取二進制串之前先利用復數濾波器檢測和提取指紋奇異點，再以指紋奇異點為基點計算其他指紋細節點相對于基點的距離和角度，以此生成幾何哈希表，再從生成的幾何哈希表中提取指紋二進制串，由于提取的指紋奇異點及與奇異點相關聯的細節點數目遠遠小于指紋細節點總數，減少了比特串的提取數量，因此提高了計算速率，節省了較大的存儲空間。文獻[9]提出了一種基于Bloom過濾器的不可逆指紋模板算法，該算法使用可有效描述細節信息的細節關系代碼（MRC），以及可實現不可逆性的Bloom過濾器，有效提高了指紋模板的安全性。文獻[10]提出基于Bloom過濾器生成受保護的指紋模板，其基本思想是：先對指紋圖像進行預校準，再選取指紋細節點進行特征提取生成二進制模板，然后在對二進制模板計算Bloom過濾器，生成新的保護模板，有效提高了指紋模板認證的準確性。

上述方案在指紋模板保護方面取得了一定的成效，但是也存在一些不足：

一是基于指紋奇異點的二進制串提取[8]，由于提取的指紋細節點數量較少，導致魯棒性不好，使得指紋匹配時的準確性偏低。

二是生成的二進制串中“0”表示無細節點的單元格，“1”表示有細節點的單元格，容易泄露位置信息，安全性不高。

三是基于Bloom過濾器的指紋模板保護方案[9-10]，因為選取指紋細節點領域內的所有細節點，導致細節點數量過多，從而計算代價偏高。

針對以上分析，本文提出一種結合指紋奇異點和Bloom過濾器的指紋加密優化方案。先選取指紋奇異點，再以指紋奇異點為基點計算其他指紋細節點相對于基點的距離和角度，以此生成幾何哈希表，再從生成的幾何哈希表中提取指紋二進制串，生成一個二進制指紋模板，通過對二進制指紋模板進行分塊，并將特征塊結構進行重新排列，最后利用Bloom過濾器映射每個特征塊，生成不可逆指紋模板。通過實驗驗證，這種方案具有很好的魯棒性，提高了驗證的準確率和模板的安全性，又減少了計算代價。

2 基于指紋奇異點的二進制模板提取

指紋奇異點是指紋脊線的凸脊的最大曲率處的指紋特征細節點。主要分為兩類：一類是中心點（core）：指紋脊線上曲率最大的點且周圍的脊線大概是半圓的走向，另一類是三角點（delta）：三條走向不同的指紋紋線的交匯點。

如圖1所示，首先，對采集的指紋圖像進行預處理，然后利用復數濾波器[11]檢測和提取指紋奇異點，再以指紋奇異點為基點計算其他指紋細節點相對于基點的距離和角度，以此生成幾何哈希表，再從生成的幾何哈希表中提取指紋二進制串，最后對每一個指紋細節點進行同樣操作，得到多條指紋特征二進制串，生成指紋特征二進制模板。

2. 1 指紋奇異點的選取

首先定義p(x,y)=(fx+fy)2，用于描述指紋平方復數點方向場。其中 fx是原始指紋圖像x方向上的導數，fy是原始指紋圖像y方向上的導數；其次定義一階復數濾波器模型為exp{iφ}，用于平方復數點方向場對奇異點進行判定，復數濾波器的響應c=μexp{ia(x,y)}，其中 μ是某種對稱模型，a是對稱模型的幾何方向；最后通過調整合適的 μ1和 μ2，使得| μ1|>T1，| μ2|>T2，T1和T2是閾值，則得到的濾波器響應分別近似于中心點和三角點局部方向場，由此選取指紋奇異點。

2. 2 生成幾何哈希表

為了降低比特串的冗余量，減少計算代價，以指紋奇異點為基點進行幾何哈希運算，經過幾何哈希變換后，指紋原始信息隱藏在相對特征向量中，達到了保護指紋隱私的目的。具體步驟如下；

（1）選取奇異點sb=(xb,yb,θb,tb)作為基點。其中xb,yb,θb,tb，分別表示橫坐標、縱坐標、方向場角度及細節點類型（中心點或三角點）。

（3）通過公式（1）計算Sb集合中所有點相對于奇異點sb之間的歐幾里得距離差ED(i)（Euclidean Distance）和方向角度差值θ(i)：

（4）依次遍歷以指紋奇異點為基點的其他指紋細節點，重復以上步驟，產生多個鏈表，組成一個鏈表矩陣，此矩陣表示集合S中細節點與奇異點之間的相對特征向量。

2. 3 提取二進制模板

設原始指紋圖像的大小為 x∈[0,X]，y∈[0,Y]，θ∈[0,2π]，構建由d個單元格的2D平面結構，如圖2所示，其中2D平面結構的長Lx和寬Ly滿足Lx=2，LY=4π。將此2D平面結構劃分為長為Cx，寬為Cy的單元格。2D平面結構所含的單元的個數d可以用公式（2）計算（表示向上取整）。

圖2 2D平面結構圖

將幾何哈希鏈中的相對特征向量對[ED(i),θ(i)]投射到2D平面結構中，若投射后矩陣單元格中有一個或多個特征向量對，則標記此單元格為1，否則標記為0。然后按照一定順序讀取標記后的d個矩陣單元，最后得到由0和1組成的二進制串且長度為d，即指紋奇異點sb對應的比特串ai=(a1a2···ad)。然后對以奇異點為基點的其他指紋細節點進行同樣操作，得到多條指紋二進制串，構成指紋二進制模板。

3 結合Bloom過濾器的優化方案

基于指紋奇異點提取的二進制模板具有自動配準和計算代價小的優點，但提取的指紋細節點數目過少，在交叉匹配的攻擊中，容易暴露二進制矩陣中細節點的位置信息，從而恢復出準確的原始模板，因此安全性不高。所以在原有方案的基礎上引入一種特殊加密技術，即Bloom過濾器[12]方案。

它是一種空間效率極高的隨機數據結構，具有不可逆性[13]，因此不能從基于Bloom過濾器的模板中準確恢復出原始模板，從而解決了安全性不高的問題。首先對基于指紋奇異點提取的二進制模板進行分塊，并將特征塊結構進行重新排列，最后利用Bloom過濾器映射每個特征塊，生成不可逆指紋模板

結合Bloom過濾器的指紋模板優化方案，如圖3所示。

首先將基于指紋奇異點提取的二進制模板分為N個特征塊，每個特征塊的大小為L×W（L是特征塊的垂直大小，W是特征塊的水平大小）。為了實現不可鏈接性，應該消除生物特征向量的信息成分，所以每個特征塊被重新分為n個組合，然后對每個組合中的垂直行進行重新排列，通過這種方式，在每個組合之間交換行，既可以防止信息擴散又提高了防止基于特征塊攻擊的能力。

設定一個初始值為零，長度為2L的Bloom過濾器b，Bloom過濾器b取k個獨立的哈希函數h1,h2···,hk，索引范圍k∈[0,2L-1]。對于每個特征塊，分別將每列轉化為十進制數，并將其在Bloom過濾器b上對應索引下的值設置為1，從而得到經過Bloom過濾器b映射后的向量bk，遍歷所有特征塊，重復上述相同的步驟，得到可撤銷模板C={bk|i=1,2,···N}。Bloom過濾器b的每個特征塊可以被多次設置為1，但只有第一個更改有效，從而隱藏了它的細節點數量及其位置，結果實現不可逆性。

圖3 結合Bloom過濾器的指紋模板優化方案圖

4 實驗測試與性能分析

為了驗證本文方案性能，實驗采用實際采集指紋庫和公開標準指紋庫FVC2002-DB2[14]兩套獨立的數據庫進行測試。

4. 1 實驗參數選取

采用實際采集指紋庫進行實驗參數選取，該指紋庫中共有75個手指，每個手指有5枚指紋樣本，則指紋庫中共有375枚。本文結合Bloom過濾器的優化方案存在的三個參數關系如下：S=N×L×W，其中S表示原始模板的大小，由于模板是固定的，只需要為L和W建立值，那么N的值也被確定。L大小與Bloom過濾器b的長度有關，W值與每個Bloom過濾器中映射的細節點數量有關。因此，L直接影響Bloom過濾器的魯棒性，如果選擇的值太大，準確性就會降低；如果選擇的值較小，根據W選定值，就會有大量的碰撞，也會導致準確性降低。而W值則直接影響模板的不可逆性，W值太大會導致沖突增加，準確性下降；W值太小將導致不可逆性很弱。通過實驗表明，W的適當取值范圍取決于所選的L值。

（1）參數L值的選取

由于二進制模板中相關性越強，相鄰的W就越相似。通過估算模板的自由度df，選取L的最優值：

為了估算模板的自由度df，通過模擬漢明距離HD分布與二項分布均值p和標準差σ[15]：

為了選取最優的L值，df需要考慮模板內垂直的所有關聯。

圖4 實際采集指紋數據庫中指紋特征的漢明距離分布

根據圖4顯示的指紋漢明距離分布圖，結合公式（3-4）計算L的最優值，結果如表2所示。

表2 L的最優值

從表2結果顯示，L的最優值是11。

（2）參數W值的選取

在Bloom過濾器中，W值會影響每一個塊中不同序列的數量，L值越大，被激活的塊中序列數就越多，塊中細節點之間的碰撞可能性就越大。由于指紋特征樣本內存在的相關性，并非所有的細節點都有同等可能性，所以選取原始模板不同細節點的平均值k。對于映射的細節點數量，不同序列被激活的概率p為：

為了設置概率p的邊界，引入細節點分布的重新映射率rmR[16]，對每個塊中的細節點之間的非獨立性進行建模，概率p為：

為了達到模板不可逆性之間的平衡和驗證的準確性，設置rmR在10%-45%之間。

表3 W的最優值

從表3結果顯示，W∈[40,175]，由于原始模板的大小是可變的，所以需要考慮水平方向上模板的細節點的平均數量，即模板的維度U=160。同時為了保持準確性，我們選擇在水平方向上映射的Bloom過濾器數量的最低值。因此，平均

4. 2 實驗測試分析

在實驗測試中采用公開標準指紋庫FVC2002-DB2進行測試，該指紋庫中由100個手指樣本組成，每個手指有8枚指紋樣本，共有800枚指紋樣本。

（1）實驗評價指標

評價指紋算法性能好壞的兩個重要的指標：拒識率（FRR）和誤識率（FAR）。FRR：把應該相互匹配成功的指紋當成不能匹配的指紋的比例，FAR：把不應該匹配的指紋當成匹配的指紋的比例。其計算公式如下：

（2）準確性分析

將最優值L=11和最優值W=40應用于系統中測試準確性，如果測試結果顯示性能參數有所提高，則結合Bloom過濾器的指紋加密優化方案可行。測試結果如圖5和表4所示。

表4 最優結果對比

圖5 ROC曲線

通過對比，拒識率FRR和誤識率FAR都有所降低，識別性能效果更好。說明本文提出的結合Bloom過濾器的指紋加密優化方案具有很好的魯棒性，有效降低了錯誤率，提高了指紋模板識別的準確性。

（3）安全性分析

①暴力破解攻擊

當攻擊者無法獲得指紋密鑰時，只能通過暴力破解的方式獲得可撤銷指紋模板。在模型中暴力攻擊的效率在于密鑰t的大小，攻擊者需要在特征塊中同時猜測正確的細節點分布順序和密鑰才能成功，其成功的概率可以估算2(r-N/n×|t|)-1=2-1279[17（]其中r代表每個塊的序列平均數為240，總塊數N為1024，n為32的二進制組合，密鑰|t|=(5×32)!32≈230,261），在計算上暴力破解難度比較大；如果同時攻擊每個特征塊，由于攻擊是并行化，所以成功率依然很低。

②重建攻擊

在交叉匹配的情況下，這種攻擊目的是模擬保護模板并與原始模板產生相關性，由于暴力攻擊的概率很低，我們只考慮原始模板。冒名攻擊者的漢明距離值低于改進系統的結果，那么重建的模板不被系統所接受。因此，基于Bloom過濾器的方案不接受對接近原始模板的假模板進行有效重建，所以安全性得到保障。

5 結語

本文研究了基于指紋奇異點的二進制串提取技術，在此基礎上結合Bloom過濾器進行了改進，提出結合指紋奇異點和Bloom過濾器的優化指紋加密方案。通過實驗驗證，這種方案具有很好的魯棒性，降低了錯誤率，既提高了驗證的準確率，又增加了模板的不可逆性。