賀康，李夢(mèng)醒，趙建，馮全

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

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

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

賀康1，李夢(mèng)醒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ù)計(jì)算技術(shù)（two-party Secure Function Evaluation，SFE），使得互不信任雙方能進(jìn)行生物認(rèn)證。SFE是密碼術(shù)中的一種技術(shù)，它允許不借助可信第三方的幫助，而使互不信任的雙方以各自私有數(shù)據(jù)為輸入，計(jì)算任意函數(shù)而不泄露給對(duì)方各自的私有數(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é)點(diǎn)是指紋認(rèn)證中最常用的特征，但細(xì)節(jié)點(diǎn)的數(shù)量不固定，在利用SFE設(shè)計(jì)認(rèn)證方案時(shí)，基于它的指紋認(rèn)證算法復(fù)雜性高，計(jì)算時(shí)間長(zhǎng)。Fingercode是一種長(zhǎng)度固定的指紋紋理特征，基于該特征的指紋認(rèn)證雖在精度上略遜于細(xì)節(jié)點(diǎn)，但基于其的SFE認(rèn)證方案的計(jì)算復(fù)雜度卻遠(yuǎn)小于細(xì)節(jié)點(diǎn)方案[9-10]，因此在開放網(wǎng)絡(luò)中基于Fingercode的指紋認(rèn)證更具有實(shí)用性。文獻(xiàn)[7]提出了一種基于HE技術(shù)的指紋識(shí)別方案，該方案通過比較兩個(gè)Fingercode之間的歐氏距離的平方值與閾值的大小來確定客戶身份。但該方案在執(zhí)行時(shí)，服務(wù)器上的模板并沒有受到保護(hù)，因此當(dāng)攻擊者入侵服務(wù)器時(shí)，會(huì)輕而易舉地獲得模板庫(kù)內(nèi)用戶指紋信息。為此本文設(shè)計(jì)了新協(xié)議，使模板的隱私得以保護(hù)；在此基礎(chǔ)上實(shí)現(xiàn)了基于Fingercode和HE技術(shù)的指紋認(rèn)證方案，并進(jìn)一步采用了數(shù)據(jù)壓縮技術(shù)，使該方案模板存儲(chǔ)空間、通信量和計(jì)算量進(jìn)一步減少。

2 Fingercode的提取和量化

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

（1）找出指紋參考點(diǎn)（指紋奇異點(diǎn)）。

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

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

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

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

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

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

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

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

圖1 方案流程圖

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

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

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

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

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

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

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

3.2 改進(jìn)方案

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

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

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

協(xié)議：算法2

⑤用戶計(jì)算：

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

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

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

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

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

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

3.4 安全性分析

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

4 實(shí)驗(yàn)結(jié)果

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

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

表1 算法2的運(yùn)行時(shí)間和帶寬

表2 算法1的運(yùn)行時(shí)間和帶寬（t=80）

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

5 結(jié)論

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

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

認(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.

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

賀康（1986—），男，在讀碩士研究生，主要研究領(lǐng)域?yàn)閳D像處理；李夢(mèng)醒（1972—），男，博士，副教授，主要研究領(lǐng)域?yàn)樾盘?hào)處理；趙建（1990—），男，在讀碩士研究生，主要研究領(lǐng)域?yàn)樯镎J(rèn)證；馮全（1969—），男，博士，教授，主要研究領(lǐng)域?yàn)樯镎J(rèn)證、圖像處理。E-mail：fquan@gsau.edu.cn

2013-07-15

2013-08-30

1002-8331（2013）24-0078-05