基于特征點分類的模糊金庫方案

孫方圓,鄭建德,徐千惠(.廈門大學信息科學與技術學院,.廈門大學信息安全實驗室,福建廈門36005)

?

基于特征點分類的模糊金庫方案

孫方圓1,鄭建德2*,徐千惠2
(1.廈門大學信息科學與技術學院,2.廈門大學信息安全實驗室,福建廈門361005)

摘要:為解決傳統指紋認證方案中指紋模板信息泄露以及指紋和密鑰無法融合等問題,提出一種基于指紋特征點分類的模糊金庫方案(CFM-FV).該方案中,使用指紋奇異點作為輔助數據對指紋圖像進行預對齊,將指紋細節點特征應用于模糊金庫方案進行密鑰綁定.驗證時,提取查詢指紋奇異點作為輔助數據對指紋預對齊,然后提取指紋細節點特征信息進行多項式的重構.本方案將指紋特征點分類方法與模糊金庫方案相結合,一定程度上解決了傳統模糊金庫方案中無法實現指紋盲對齊帶來的影響問題.

關鍵詞:指紋認證;模糊金庫方案;指紋特征點

現代數字身份認證手段存在易復制、被盜取等諸多問題.目前,常用的解決方案是采用基于生物特征的身份認證技術[1-4].而指紋作為目前最常用的生物特征,具有易采集、難偽造的優點,被廣泛應用于現代身份認證中.目前的指紋識別算法過程中都要存儲用戶指紋模板信息,模板信息泄露問題將是指紋識別算法所面臨的最大障礙.指紋和傳統密鑰相結合的間接指紋認證方法越來越受到重視,指紋密碼域技術作為其中一種方法應運而生[5].其中主要的研究代表有Juels 等[6-8]于1999年提出一種模糊承諾方案和在模糊承諾方案的基礎上提出了模糊金庫方案.基于指紋模糊金庫的方案可以實現間接認證的目的,可解決傳統認證系統以及基于生物特征單一認證中的很多局限.

模糊金庫方案的安全性是基于多項式重構難點問題.對于雜亂無序的指紋特征點數據來說,特別適用于這種方案.基于模糊金庫方案的指紋密碼域技術是生物特征認證中的一個新的領域,它的一個最大優點在于不存儲用戶生物特征的模板,而只存儲輔助數據,這種輔助數據即使在被泄露的情況下也不會泄露指紋模板信息,并且在一定程度上解決了指紋和密鑰的有機融合問題.但正是由于這種模糊性(指紋特征集提取的無序性、噪點加入的隨機性等因素造成),導致認證過程中錯誤接受率(FAR)和錯誤拒絕率(FRR)很高,這也是集成指紋密碼域技術面臨的重點難題.

1 基于模糊金庫算法的指紋密碼域技術

1.1指紋密碼域技術

指紋密碼域技術從用戶的指紋特征數據中提取指紋特征數據,并將該指紋特征數據和傳統密鑰有機融合,保存部分數據作為輔助數據,不保存用戶的指紋特征模板信息.在不同的系統中,用戶的注冊信息都是不相同的,這點也保證了用戶注冊身份信息的可更改性.

指紋密碼域技術能夠有效地保護生物特征模板的安全,系統本身不存儲生物模板信息,間接實現指紋特征模板的安全存儲、撤銷和重新發布,有效地解決了生物模板泄露的問題.但指紋密碼域技術中輔助數據是可公開的,所以只包含了很少的模板信息,這也為我們重構用戶注冊信息帶來困難.同時,指紋密碼域技術在指紋識別率和安全度方面很難做到很好的平衡,這也是一個難點問題.

1.2模糊金庫算法

模糊金庫算法的思想是一個用戶可以使用一個集合A將密鑰s上鎖,形成金庫V;另外一個用戶如果想解開這個庫,他必須使用和A相似的集合B,也就是說集合A和集合B在一定程度上必須有足夠多的重復元素,B的用戶才能完全解鎖金庫V,從而獲得密鑰s.算法的突出優勢在于,集合B與集合A可以不相等而只需要在一定程度上相近即可解鎖金庫獲得密鑰值.

1.3基于指紋特征的模糊金庫方案

Uludag等[9]在fuzzy vault基礎之上提出了基于指紋的模糊金庫方案,該方案和模糊金庫的基本思想是一致的,但在密鑰的處理上有所改進,算法中先將密鑰均分為要求的份數,利用循環校驗碼(CRC)進行處理,然后加在密鑰的后面,作為最后一項系數,形成多項式p.比如,算法在運算域GF(216)上進行,將長度為256位的密鑰k順序分割為16=256/16個長度為16 bit的位串R:a1,a2,…,a16,計算R的CRC-16校驗碼,記為a0.構造出多項式p(x)=a0+a1x+a2x2+…+a16x16.

指紋庫加密過程中,選擇t個指紋細節特征點(采用橫坐標和縱坐標表示一個細節點),構成集合A,將集合A投影到在多項式形p(x)上構成點對,再加入隨機產生的噪點集合,這樣就形成了模糊指紋金庫V.具體過程如圖1所示.

圖1　指紋庫加密步驟Fig.1 Vault encoding

指紋庫解密過程中,用戶提供指紋細節點特征集合B(再次提取用戶指紋,從指紋圖像中獲取指紋特征集合).在模糊指紋金庫V中選擇和集合B匹配(兩點的距離小于某個閥值)的點,m為最終匹配點數.如果m小于多項式系數,則指紋庫解密失敗.否則,利用拉格朗日差值法可重構出多項式,并利用CRC糾錯碼進行糾錯,就可恢復密鑰值k.具體過程如圖2所示.

圖2　指紋庫解密步驟Fig.2 Vault decoding

算法通過提取指紋特征點坐標(x,y)作為特征數據.構建指紋金庫之前,先要對模板指紋和驗證指紋進行校準,目的是要消除由于旋轉、扭曲等引起的非線性形變.通過以上分析可得出如下結論:1)該算法是一個可實施的方案,方案簡單易行,有較高的指紋識別效率;2)該算法在構建模糊金庫之前,都是假設指紋圖像是預校準處理后的,這和實際應用不相符.

1.4現有的指紋模糊金庫方案

Clancy等[10]在2003年首次將指紋應用于模糊金庫當中,提出了指紋模糊金庫方案.該方案使用指紋細節點的平面坐標進行加鎖和解鎖,并通過RS糾錯技術來還原特征點位置,最后再還原多項式.Uludag 等[11]在Juels的模糊金庫理論與Clancy的指紋模糊金庫方案的基礎之上提出了一種更加實用化的算法.他們的改進點在于指紋配準算法中,使用指紋細節點代替指紋特征點,算法中計算每兩個指紋細節點之間的距離和連線方向來完成指紋的配準操作.算法中對秘密數據K使用CRC糾錯碼進行編碼之后構造多項式P,再由指紋特征點的位置信息作為輸入,計算點在P上面的投影信息,并添加雜湊點共同構成模糊金庫.Nandakumar等[12]在前人研究的基礎之上,引入了特征點的方向信息θ,使得特征點由原來的(x,y)擴展到(x,y,θ),這使得雜湊點的選取范圍增大.

綜上可看出,以上方案仍存在一些缺點:1)使用鄰域結構描述特征點加大了模糊金庫的存儲空間,領域結構也會暴露指紋的局部結構,一定程度上增大了指紋特征點結構泄露的隱患;2)方案中都是假定指紋特征集合和模板集合是預先精確對齊的,這和實際應用不相符;3)由于算法中指紋特征集合是無序集合,加入過多的噪點,使得多項式重構存在誤差,這將大大提高FRR與FAR.

2 基于指紋特征點分類的模糊金庫方案

本方案對提取的指紋特征進行分類處理,使用指紋奇異點(中心點和三角點)作為輔助數據事先對指紋圖像進行預對齊,將指紋細節點特征(端點和分叉點)應用于模糊金庫方案進行密鑰綁定.驗證時,提取查詢指紋奇異點作為輔助數據對指紋進行預對齊,然后提取指紋細節點特征信息進行多項式的重構.由于該密鑰和指紋特征是相互融合的,為了區分該密鑰和普通口令密鑰等的區別,本文稱該密鑰為身份密鑰.

2.1輔助數據概念

模糊金庫方案中需要對指紋圖像進行指紋預對齊操作,庫中需要存儲一種輔助數據用作指紋的預對齊.該輔助數據需存儲為一種公開信息,這種公開信息不能泄露太多的指紋模板特征點的信息.同時,輔助數據也要包含足夠的信息用來進行指紋預對齊.

指紋的奇異點占指紋特征點的很少一部分(見圖3),它包含了指紋特征的很少信息,基于奇異點的配準匹配方法[13-14]往往具有很高的配準速度和識別率,所以本文將使用指紋的奇異點作為指紋預對齊的輔助數據.

圖3　特征類型分布Fig.3 Type of characteristics

2.2基于指紋奇異點的預對齊算法

針對指紋奇異點的配準算法,本文采用傳統的指紋特征點配準操作,逐步進行局部配準和全局配準.由于篇幅原因,指紋預對齊前的指紋圖像處理工作暫不多做介紹,而指紋奇異點的提取采用傳統的基于POINCARE指數[15]的檢測算法進行過濾得到.通過選擇參考點配準的方法,來完成指紋查詢集合Q和指紋模板集合T的配準操作.

1)選取指紋奇異點對:從集合Q和集合T中各選取一個點作為參考點,若兩點落在可變限界盒中,計算出兩圖的位移量(x,y)和旋轉量r.

2)整體對齊指紋奇異點對:根據以上3個公式中得到的水平和垂直位移量以及旋轉量,將指紋查詢集合Q進行旋轉和平移.計算出落在可變限界盒中的點,落在其中的點認為是匹配的點.最后,統計匹配的點到集合M用作以后的多項式還原操作.

3)匹配分數計算:計算集合M的個數,通過計算匹配分數來決定配準的準確度.根據多次匹配,給出一個閥值作為參考值,當匹配分數超過閥值時就認為該次匹配是成功的,否則是失敗的,返回步驟1)重新開始選擇參考點.當所有的參考點都配準失敗,就認為這兩個指紋不是來自同一個手指,直接返回指紋配準失敗,以后的操作無需進行.

2.3基于指紋特征點分類的模糊金庫方案

基于模糊金庫的實現方案包括兩個步驟:指紋金庫加密(vault encoding)和指紋金庫解密(vault decoding).

在指紋金庫加密階段(如圖4所示):

1)從用戶輸入的指紋圖像中提取奇異點集HD作為輔助數據,以及指紋細節點(端點和分叉點),每個特征點擁有x、y坐標,A代表細節點點集:

n代表特征點的總數目.

2)用戶首先計算密鑰Key的糾錯碼(CRC校驗碼),并將計算得到的CRC校驗值a0與密鑰Key連接,得到S,然后基于S構造一個關于x的多項式p(階數為k),并計算S的散列值hash(S):

3)將特征點集A中的元素映射到GF(p2)上,得到結果集RA:

i=1,2,…,n,bi為隨機數.

4)隨機生成干擾點集C,保證該點集不在p(x)上:

5)由干擾集C和結果集RA生成并集R,這樣指紋金庫V就形成了.

指紋金庫解密階段(如圖5所示):

1)當驗證用戶身份的時候,通過指紋儀提取用戶指紋特征,并將其分類處理.通過指紋奇異點完成指紋圖像的預對齊,平移和旋轉后得到查詢圖像中的指紋細節點集合U:

圖4　指紋金庫加密步驟Fig.4 Vault encoding

m代表特征點的數目.

2)將集合U和在庫加密步驟中生成的指紋金庫V進行比較,用M表示集合U和集合R中,由任意兩點差值落在可變限界盒內形成的點集,r表示配準數:

3)將M和k作為牛頓多項式插值法的參數,解開金庫中的k階多項式p'(x),由多項式p'(x)便可以得到多項式的每位參數項系數a'0,a'1…,a'k,由此可得到每項參數連接后的哈希值K':

4)此時,如果K'和K是一致的,則用戶身份驗證成功,并可還原用戶密鑰,否則失敗.如果集合M包含k+1個真的指紋特征點,那么模糊金庫算法就可重構出同一個多項式.

圖5　指紋庫解密步驟Fig.5 Vault decoding

3 實驗結果分析

為了驗證基本方案的性能,我們使用FVC2002 的DB2指紋庫,并應用VS2008編程工具進行仿真實驗,與前人的研究進行比較.FVC2002的DB2指紋數據庫是由10個手指,每個手指采集8個指紋組成,總共有80個指紋.實驗中,先后使用了本方案與多重控制指紋模糊金庫方案(ASFV)方案[16],基于指紋自動配準的多重控制模糊金庫方案(MFVC)方案[17]及Nagar方案[18]進行指紋對比和解鎖操作.FRR通過一個指紋與相同指紋的其他7個指紋進行比較,總共進行了7×8×10=560次比較,統計得到結果.FAR通過一個指紋與其他不同指紋的70個指紋進行比較,比較次數為80×70=5 600次.

對于每組指紋模板生成的模糊金庫,由真實點和隨機生成的300個噪點共同組成,若成功解鎖金庫就可獲得密鑰,若不成功則得不到密鑰.應用實驗數據庫中的指紋重復上鎖與解鎖實驗,并統計實驗結果得到相應的FAR和FRR.

實驗中指紋金庫加密和解密步驟使用的相關參數如表1所示.

表1　實驗中指紋金庫相關參數Tab.1 The involved parameters of the experiment

本文方案與前人的基于模糊金庫方案的實驗結果對比,如表2所示.

從實驗結果的對比中可以看出,本文方案的FAR小于0.000 1%,是比較低的,在這方面可看出,基于指紋分類的模糊金庫方案的性能優于前人方案.由于每次加入的噪聲點的隨機性以及標準庫中指紋質量問題,這導致了FRR的結果稍微比較高(實驗證明,如果進行同個人的不同指紋的2次查詢,FRR就可降低到0.03%左右),但從指紋金庫解鎖耗時的角度,這種結果是可以接受的.而基于自動配準的方案(ASFV, MFVC)僅僅使用細節點創建模糊金庫,這樣有可能造成細節點泄露,從而泄露指紋模板.而本文采用指紋奇異點作為輔助數據,能夠加強多指紋模板的安全保護.同時,由于奇異點的高配準率的性質,使得配準時間縮短.ASFV采用了多個指紋給秘密信息加鎖,這種方法雖然能更有效地保證安全性,但同時也會提高FRR,增加了驗證時間,造成一些不必要的麻煩.

此外,通過實驗表明,當兩個方案的FAR相同時,本文方案的真實接收率(GAR)(GAR=1-FAR)大于其他糊金庫方案的GAR;當GAR相同時,本文方案的誤識率相對較小.

該方案可有效解決由于單一生物特征認證過程中生物特征模板泄露問題、存儲空間大小限制問題、指紋和傳統密鑰無法有機融合等問題.而模糊金庫的安全性由模糊金庫的模糊性和多項式重構難題保證,如果暴力破解金庫,取每個指紋對應的多項式階次均為10,平均每個模板包含細節點數為40,干擾點個數為300.采用文獻[19]中的安全性分析方法,從所有點(包括干擾點和真實點)中獲取11個點,即可得到總秘密信息.復雜度為C(11,340)/C(11,40),約為85億次.

表2　實驗結果對比Tab.2 Comparison of experimental result

4 結 論

本文通過指紋特征點分類的方法,將指紋奇異點的高配準率的性質應用到指紋的預對齊方案中,利用模糊金庫的特點,通過篩選出的指紋特征點還原出原有密鑰,實現指紋和密鑰的有機融合.但由于庫中隨機加入的噪點(增大了模糊性),這將影響算法性能的穩定性.如何在滿足一定模糊性的情況下,保持高配準率,減少對多項式重構帶來的影響,將是本文以后需要深入研究的地方.

參考文獻:

[1] 鄭智強.指紋匹配算法及集成方案的研究[D].廈門:廈門大學,2013:1-2.

[2] 陳昭智,鄭建德.一種基于身份分層結構加密算法的廣播加密方案[J].廈門大學學報(自然科學版),2006,45(3): 342-346.

[3] 鄭建德,鄭杭杰,楊靜.一種口令,令牌與分物認證技術通用集成框架[J].廈門大學學報(自然科學版),2011,50 (1):42-46.

[4] 賈英濤,鄭建德.J2EE平臺雙因素認證的設計與實現[J].廈門大學學報(自然科學版),2007,46(1):43-46.

[5] SOUTAR C,ROBERGE D,STOIANOV A,et al. Biometric encryption.ICSA guide to cryptography[EB/ OL].[1999-11-13].http:∥www.bioscrypt.com/assets/ BiometricEncryption.pdf.

[6] JUELS A,WATTENBERG M.A fuzzy commitment scheme[C]∥ACM Computer and Comm Security (CCCS).New York:ACM,1999:28-36.

[7] OJHA D B,SHARMA A.A fuzzy commitment scheme with McEliece cipher[J].Surveys in Mathematics &Its Applications,2010,5:73-83.

[8] JUELS A,SUDAN M.A fuzzy vault scheme[J].Designs, Codes and Cryptography,2006,38(2):237-257.

[9] ULUDAG U,PANKANTI S,JAIN A K.Fuzzy vault for fingerprints[M].Heidelberg:Springer,2005:310-319.

[10] CLANCY T C,KIYAVASH N,LIN D J.Secure smartcard-based fingerprint authentication[C]∥ACM Workshop on Biometrics:Methods and Applications.New York:ACM,2003:45-52.

[11] ULUDAG U,JAIN A.Securing fingerprint template: fuzzy vault with helper data[J].Proceedings of Cvpr Workshop on Privacy Research in Vision,2006,163: 17-22.

[12] JEFFERS J,ARAKALA A.Fingerprint alignment for a minutiae-based fuzzy vault[C]∥Biometrics Symposium,2007. Baltimere:IEEE,2007:1-6.

[13] YI C,DASS S C,JAIN A K.Fingerprint quality indices for predicting authentication performance[C]∥Proc of Audioand Uideo-based Biometric Person Authentication.New York:Rye Brook,2005:160-170.

[14] KARU K,JAIN A K.Fingerprint classification[J].Pattern Recognition,1996,29(3):389-404.

[15] 譚臺哲,寧新寶,尹義龍,等.一種指紋圖像奇異點檢測的方法[J].軟件學報,2003,14(6):1082-1088.

[16] FANG E,HAN C,LIU J.Auto-aligned sharing fuzzy fingerprint vault[J].Communications China,2013,10(10): 145-154.

[17] 姚旭,劉嘉勇,韓彩蕓,等.基于指紋自動配準的多重控制模糊金庫方案[J].四川大學學報(自然科學版),2014, 51(6):145-153.

[18] NAGAR A,NANDAKUMAR K,JAIN A K.Securing fingerprint template:fuzzy vault with minutiae descriptors[J].Internat Conf for Pattern Recognition, 2008,26(5):1-4.

[19] HIRSCHBICHLER M,BOYD C,BOLES W.A multiple-control fuzzy vault[C]∥2012 Tenth Annual International Conference on Privacy,Security and Trust. Frederiction:IEEE,2008:36-47.

Fuzzy Vault Scheme Based on Classification of Fingerprint Features Scheme

SUN Fangyuan1,ZHENG Jiande2,XU Qianhui2*
(1.School of Information Science and Engineering,Xiamen University, 2.Information Security Lab,Xiamen University,Xiamen 361005,China)

Abstract:For the purpose of solving fingerprint template leakage problem and the inability of combining fingerprints and traditional keys in the traditional fingerprintidentification,fuzzy vault scheme based on classification of fingerprint features scheme(CFM-FV) is proposed in this paper.In our scheme,singularities will be as helper data for pre-align the fingerprint,while the minutia features will be used to encode the vault in this scheme.In the stage of verification,singularities will be extracted as helper data for fingerprint pre-aligned,then the extracted minutia features will be used to reconstruct the polynomial.In this scheme,the problem that the traditional scheme cannot align the fingerprint blind will be solved to some extent by combining classification method of fingerprint features with fuzzy vault scheme.

Key words:fingerprint authentication;fuzzy vault scheme;fingerprint features

*通信作者:zhengjd@xmu.edu.cn

收稿日期:2015-05-15 錄用日期:2015-07-26

doi:10.6043/j.issn.0438-0479.2016.02.020

中圖分類號:TP 309.7

文獻標志碼:A

文章編號:0438-0479(2016)02-0266-06

引文格式:孫方圓,鄭建德,徐千惠.基于特征點分類的模糊金庫方案[J].廈門大學學報(自然科學版),2016,55(2):266-271.

Citation:SUN F Y,ZHENG J D,XU Q H.Fuzzy vault scheme based on classification of fingerprint features scheme[J].Journal of Xiamen University(Natural Science),2016,55(2):266-271.(in Chinese)