賀康，李夢醒，趙建，馮全

1.甘肅農(nóng)業(yè)大學(xué)工學(xué)院，蘭州 730000

2.湖南城市學(xué)院通信與電子工程學(xué)院，湖南益陽 413000

基于Fingercode和同態(tài)加密的指紋認(rèn)證方案

賀康1，李夢醒2，趙建1，馮全1

1.甘肅農(nóng)業(yè)大學(xué)工學(xué)院，蘭州 730000

2.湖南城市學(xué)院通信與電子工程學(xué)院，湖南益陽 413000

1 引言

近些年來，開放網(wǎng)絡(luò)中的基于生物特征的身份認(rèn)證過程中隱私保護(hù)問題引起了眾多研究者的關(guān)注[1]。一些研究者提出可借助于雙方安全函數(shù)計算技術(shù)（two-party Secure Function Evaluation，SFE），使得互不信任雙方能進(jìn)行生物認(rèn)證。SFE是密碼術(shù)中的一種技術(shù)，它允許不借助可信第三方的幫助，而使互不信任的雙方以各自私有數(shù)據(jù)為輸入，計算任意函數(shù)而不泄露給對方各自的私有數(shù)據(jù)。同態(tài)加密[2]（Homomorphic Encryption，HE）和加密電路[3]（Garbled Circuit）是常用的SFE工具。最近一些基于同態(tài)加密或加密電路的、能保護(hù)交易雙方生物特征數(shù)據(jù)隱私的協(xié)議被陸續(xù)提出[4-8]。指紋認(rèn)證是最常用的一種生物認(rèn)證方式，雖然細(xì)節(jié)點是指紋認(rèn)證中最常用的特征，但細(xì)節(jié)點的數(shù)量不固定，在利用SFE設(shè)計認(rèn)證方案時，基于它的指紋認(rèn)證算法復(fù)雜性高，計算時間長。Fingercode是一種長度固定的指紋紋理特征，基于該特征的指紋認(rèn)證雖在精度上略遜于細(xì)節(jié)點，但基于其的SFE認(rèn)證方案的計算復(fù)雜度卻遠(yuǎn)小于細(xì)節(jié)點方案[9-10]，因此在開放網(wǎng)絡(luò)中基于Fingercode的指紋認(rèn)證更具有實用性。文獻(xiàn)[7]提出了一種基于HE技術(shù)的指紋識別方案，該方案通過比較兩個Fingercode之間的歐氏距離的平方值與閾值的大小來確定客戶身份。但該方案在執(zhí)行時，服務(wù)器上的模板并沒有受到保護(hù)，因此當(dāng)攻擊者入侵服務(wù)器時，會輕而易舉地獲得模板庫內(nèi)用戶指紋信息。為此本文設(shè)計了新協(xié)議，使模板的隱私得以保護(hù)；在此基礎(chǔ)上實現(xiàn)了基于Fingercode和HE技術(shù)的指紋認(rèn)證方案，并進(jìn)一步采用了數(shù)據(jù)壓縮技術(shù)，使該方案模板存儲空間、通信量和計算量進(jìn)一步減少。

2 Fingercode的提取和量化

Jain等[9]提出了指紋的Fingercode特征，它是一種指紋紋理描述，其提取分為四個步驟：

（1）找出指紋參考點（指紋奇異點）。

（2）在參考點周圍的ROI區(qū)域中劃分NS=NR×NA個扇區(qū)，其中NR是沿徑向環(huán)的劃分?jǐn)?shù)量，NA是角度方向的劃分?jǐn)?shù)量。

（3）用一組NG個Gabor濾波器組對指紋圖像ROI濾波，其中Gabor濾波器在空間域的表達(dá)式如下：x，y分別為坐標(biāo)軸坐標(biāo)，f是沿著x軸θ角的正弦頻率，σx′,σy′是沿著x′,y′軸的高斯包絡(luò)常數(shù)。

（4）計算濾波圖像中每個扇形區(qū)內(nèi)灰度值對平均值的平均絕對離差（Average Absolute Deviation），其計算公式為：

其中1≤i≤NS，ni為扇形Si區(qū)域中像素點個數(shù)，F(xiàn)iθ(x,y)為經(jīng)步驟3中Gabor濾波器組處理后的圖像，Piθ是Fiθ(x,y)的像素平均值。

這樣得到的Fingercode是一個k=NS×NG維的向量，由于Fingercode不是旋轉(zhuǎn)不變的，故生成模板時本文選取NR=5，NA=16，NG=8，即一個Fingercode由k=5×16×8=640個數(shù)值組成。為了降低指紋匹配時的復(fù)雜度，本文對Fingercode進(jìn)行了量化：采用l比特表示Fingercode中的每個數(shù)值。由于Fingercode不具備旋轉(zhuǎn)不變性，故生成Fingercode特征模板時，本文對于每枚指紋模板，都生成9個Fingercode，它們合在一起作為特征模板；這些Fingercode是對模板指紋圖像分別旋轉(zhuǎn)i×11.25°而生成的，i=0，±1，±2，±3，±4。這樣可以在一定程度上在匹配時解決模板指紋和現(xiàn)場指紋對齊的問題。本方案中，模板保存在服務(wù)器S。圖1為Fingercode匹配時的流程圖。

3 基于Fingercode和同態(tài)加密的指紋認(rèn)證方案

3.1 加掩膜的歐氏距離平方計算與基本認(rèn)證協(xié)議

指紋信息屬于個人隱私信息，通過第二章得到的Fingercode若以明文保存在服務(wù)器端時會存在巨大的安全隱患。為了解決這個問題，本文對模板進(jìn)行了加密，并設(shè)計了新的歐氏距離計算協(xié)議，為簡單起見協(xié)議中只計算歐氏距離的平方。

圖1 方案流程圖

本文采用的加密方法是Paillier[11]加法同態(tài)加密，它是一種語義安全的公鑰系統(tǒng)，允許在不解密的條件下計算兩明文之和的密文，它具有兩條主要性質(zhì)：

其中A和B均為需加密的明文，C為常數(shù)，[.]pk表示以pk作為公鑰的加密運算。

指紋認(rèn)證時，用戶計算現(xiàn)場指紋與模板Fingercode的歐氏距離的平方，由于用戶擁有解密模板的私鑰skC，為了防止攻擊者非法獲取skC后冒充合法用戶獲取用戶信息，認(rèn)證過程中還必須對模板中的數(shù)據(jù)進(jìn)一步保護(hù)。為此，服務(wù)器可利用同態(tài)加密的性質(zhì)給特征模板加隨機(jī)掩膜后再發(fā)送給用戶，這樣用戶解密后也無法得到特征模板數(shù)據(jù)，只能計算加了掩膜后的歐氏距離的平方，具體協(xié)議如下（為簡單敘述起見，假定雙方已互換了公鑰，且設(shè)服務(wù)器公鑰為，服務(wù)器私鑰為skC'）：

（1）①服務(wù)器選擇隨機(jī)數(shù)r1i和r2i(1≤i≤k)，并以用戶公鑰pkC計算如下結(jié)果：

②服務(wù)器判斷DIS是否小于閾值TD，從而做出接收或拒絕用戶身份的判斷。

上述協(xié)議中通過反復(fù)應(yīng)用公式（3）和公式（4）得到相應(yīng)的結(jié)果，且r1i、r2i都是用戶所不知的，其中r1i和r2i是為了防止模板[yi]pkc和[]pkc的泄漏。而對于步驟3，雖然服務(wù)器知道了最終結(jié)果，但其本身對yi和并不知曉，因此它不會通過結(jié)果反推出用戶的指紋信息。事實上，上述協(xié)議的步驟1完全可以在協(xié)議準(zhǔn)備階段完成。

本方案中由于一個指紋模板包括9個Fingercode，因此若使用上述協(xié)議，可能需要將其執(zhí)行9次（當(dāng)現(xiàn)場提取的Fingercode與模板中9個Fingercode中的任何一個匹配成功時，用戶則停止與剩下的模板Fingercode進(jìn)行認(rèn)證計算）。

3.2 改進(jìn)方案

算法1中服務(wù)器端模板中每個[yi]pkc和[]pkc都是單獨存在于一個密文中，這占用了大量的模板存儲空間；其步驟1中對于模板加掩膜計算，由于每個[yi]pkc和[pkc是單獨存在的，因此不得不將每個掩膜r1i和r2i單獨加密計算，而且每個模板需要單獨計算與現(xiàn)場Fingecode的距離，這無疑是增加了本方案的計算復(fù)雜度。實際上，F(xiàn)ingecode的單個分量長度比起密文要短得多，為此，本文在算法1的基礎(chǔ)上進(jìn)行了改進(jìn)，采用了“打包（packing）”技術(shù)，將多個分量一起裝入一個密文中，且雙方執(zhí)行一次協(xié)議即可計算現(xiàn)場Fingercode與模板中9個Fingercode的匹配認(rèn)證，具有更高的通信與計算效率。

首先本方案改進(jìn)了模板的生成方法，對于9個Fingercode，以用戶公鑰計算：

在認(rèn)證時，雙方執(zhí)行如下協(xié)議（為簡單敘述起見，假定雙方已經(jīng)互換了公鑰，且設(shè)服務(wù)器公鑰為pkC'，服務(wù)器私鑰為skC'；下述協(xié)議步驟1亦可在協(xié)議準(zhǔn)備階段完成）：

協(xié)議：算法2

⑤用戶計算：

為了方便計算，與之相對應(yīng)的[ci]pkc′和[TPj]pkc′中每段數(shù)值前需分別加上(ρ3-ρ1+1)和(ρ3-ρ2+1)個比特0。通過上述數(shù)據(jù)的打包處理，服務(wù)器端模板的存儲空間節(jié)省了(1?(NB+ND)/9k)%，而整個協(xié)議的計算復(fù)雜度也得到了明顯降低，只需要執(zhí)行一次協(xié)議就可完成現(xiàn)場樣本與模板中9個Fingercode的比較。且相較于算法1（設(shè)現(xiàn)場樣本與模板中9個Fingercode均進(jìn)行認(rèn)證計算），本協(xié)議在明文加密

⑥用戶將[BD]pkc′發(fā)送給服務(wù)器。

（3）①服務(wù)器利用自身私鑰skC'解密[BD]pkc′，并分割出：

繼而計算出特征模板和現(xiàn)場Fingercode的歐氏距離的平方：

②服務(wù)器判斷DISj是否小于閾值TD，從而做出接收或拒絕用戶身份的判斷。

3.3 改進(jìn)方案中“打包（packing）”長度

3.4 安全性分析

本文的安全模型為半誠實模型（semi-honest model），即假設(shè)協(xié)議的雙方都能忠實執(zhí)行協(xié)議，但可利用協(xié)議的中間結(jié)果供分析對方的信息。顯然，對于用戶現(xiàn)場數(shù)據(jù)xi，其安全性取決于加密算法本身。在算法2中，服務(wù)器數(shù)據(jù)（即模板）的安全性取決于隨機(jī)掩膜，設(shè)的長度為ρ1比特，就模板的單個分量而言，由于同態(tài)加密的性質(zhì)1的加法不是“模”加，對Fingercode的每個分量來說，其統(tǒng)計安全度為2l-ρ1，而整個模板的統(tǒng)計安全度為2k(l-ρ1)。本文設(shè)掩膜的熵與各分量的熵(2-l)相同，故取ρ1=2l；而對于算法2中的長度ρ2，它是加在是2l+ceil(lbk)，故取ρ2=3l+ceil(lbk)。

4 實驗結(jié)果

為了測試本方案的可實施性，本文在MyEclipse 10環(huán)境中開發(fā)出相應(yīng)的Java程序，并在PC（Intel Core i5-2430M at 2.67 GHz，內(nèi)存2 GB）上對本方案進(jìn)行了仿真。實驗前Fingercode已預(yù)先提取出，且9個Fingercode均需要與現(xiàn)場提取的Fingercode進(jìn)行認(rèn)證。本文取k=640，l=7，則ρ1= 14，ρ2=31，ρ3=32；對于加密算法中安全參數(shù)t和RSA模比特長度T，分別設(shè)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服務(wù)器端節(jié)省了約98.4%～99.4%的模板存儲空間，而明文加密和密文解密的次數(shù)分別減少了約95.7%～96.1%和99.2%～99.7%。

表1給出了基于算法2的本方案在三種條件下需要的帶寬和運行時間的實驗結(jié)果。而限于硬件設(shè)施的不足，基于算法1的本方案，本文只在t=80、T=1 024情況下進(jìn)行了仿真，詳見表2。

表1 算法2的運行時間和帶寬

表2 算法1的運行時間和帶寬（t=80）

由實驗結(jié)果可以看出，在t=80、T=1 024情況下，采用算法2的本方案較直接采用算法1的方案在準(zhǔn)備階段的時間和帶寬上節(jié)省了約95.8%。在運行階段的時間和帶寬上分別節(jié)省了約86.1%和88.5%。由于準(zhǔn)備階段運算是一次性的，服務(wù)器可以在空閑時執(zhí)行后存儲，以后用戶申請認(rèn)證時，服務(wù)器可以直接使用這些數(shù)據(jù)，故這些運算在實際認(rèn)證時不會消耗時間。因此采用算法2的本方案較直接采用算法1的方案更適合在模板加密的情況下進(jìn)行基于Fingercode和同態(tài)加密的雙方隱私保護(hù)的指紋認(rèn)證。

5 結(jié)論

本文提出了一種基于Fingercode特征的指紋認(rèn)證方案，該方案中用戶以其公鑰將模板加密后存儲在服務(wù)器端，服務(wù)器無法獲得用戶指紋信息，用戶隱私得到了保護(hù)。認(rèn)證過程中，利用同態(tài)加密的性質(zhì)，用戶和服務(wù)器可以在不泄露自己私有數(shù)據(jù)的條件下聯(lián)合計算現(xiàn)場指紋和模板對應(yīng)的Fingercode的歐氏距離，服務(wù)器可以利用該距離判斷用戶身份。本方案對開放網(wǎng)絡(luò)中進(jìn)行指紋身份認(rèn)證過程中雙方數(shù)據(jù)的隱私性具有較好的保護(hù)作用。

[1]馮全.基于指紋的隱私保護(hù)型身份認(rèn)證技術(shù)[D].北京：北京郵電大學(xué)，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，F(xiàn)ranz 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

針對開放網(wǎng)絡(luò)中進(jìn)行指紋身份認(rèn)證時的雙方指紋隱私保護(hù)問題，提出了基于Fingercode和同態(tài)加密的指紋認(rèn)證方案。相較傳統(tǒng)方案，該方案中服務(wù)器端模板以加密形式保存，保護(hù)了用戶指紋數(shù)據(jù)的安全性；設(shè)計了安全認(rèn)證協(xié)議，使得服務(wù)器和用戶可以聯(lián)合計算雙方指紋特征的距離而不會泄露各自特征數(shù)據(jù)的隱私。協(xié)議中采用了數(shù)據(jù)打包技術(shù)，能夠明顯減輕服務(wù)器與用戶之間的通訊壓力和計算復(fù)雜度。分析和實驗結(jié)果表明，該方案具有安全性和一定的實用性。

認(rèn)證；隱私保護(hù)；Fingercode；同態(tài)加密；數(shù)據(jù)打包

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.

國家自然科學(xué)基金（No.61062012）。

賀康（1986—），男，在讀碩士研究生，主要研究領(lǐng)域為圖像處理；李夢醒（1972—），男，博士，副教授，主要研究領(lǐng)域為信號處理；趙建（1990—），男，在讀碩士研究生，主要研究領(lǐng)域為生物認(rèn)證；馮全（1969—），男，博士，教授，主要研究領(lǐng)域為生物認(rèn)證、圖像處理。E-mail：fquan@gsau.edu.cn

2013-07-15

2013-08-30

1002-8331（2013）24-0078-05