基于Fingercode和同態加密的指紋認證方案

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

1.甘肅農業大學工學院，蘭州 730000

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

基于Fingercode和同態加密的指紋認證方案

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

1.甘肅農業大學工學院，蘭州 730000

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

1 引言

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

2 Fingercode的提取和量化

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

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

（2）在參考點周圍的ROI區域中劃分NS=NR×NA個扇區，其中NR是沿徑向環的劃分數量，NA是角度方向的劃分數量。

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

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

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

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

3 基于Fingercode和同態加密的指紋認證方案

3.1 加掩膜的歐氏距離平方計算與基本認證協議

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

圖1 方案流程圖

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

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

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

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

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

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

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

3.2 改進方案

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

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

在認證時，雙方執行如下協議（為簡單敘述起見，假定雙方已經互換了公鑰，且設服務器公鑰為pkC'，服務器私鑰為skC'；下述協議步驟1亦可在協議準備階段完成）：

協議：算法2

⑤用戶計算：

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

⑥用戶將[BD]pkc′發送給服務器。

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

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

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

3.3 改進方案中“打包（packing）”長度

3.4 安全性分析

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

4 實驗結果

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

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

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

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

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

5 結論

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

[1]馮全.基于指紋的隱私保護型身份認證技術[D].北京：北京郵電大學，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，Franz 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

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

認證；隱私保護；Fingercode；同態加密；數據打包

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.

國家自然科學基金（No.61062012）。

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

2013-07-15

2013-08-30

1002-8331（2013）24-0078-05