基于SEAL 库的同态密文指纹识别系统设计与实现*

杨亚涛, 张奇林, 张艳硕, 左珮良

1. 北京电子科技学院 电子与通信工程系, 北京100070

2. 西安电子科技大学 通信工程学院, 西安710071

1 引言

研究和实际应用表明, 人的指纹具有稳定性和唯一性, 即每个人的指纹都与其他人有着一定的区别,且每个人的指纹终身不会改变. 这使得指纹识别技术成为当今身份识别技术的核心和热点. 指纹识别是一种常见的身份认证方式, 相比于其他认证方式, 具有数据量小、计算量小、获取方便等特点. 1891 年,Galton[1]提出著名的高尔顿分类系统, 之后英国、美国、德国等国家的执法部门先后将指纹鉴别作为身份鉴定的主要方法, 从此指纹识别开始走进人们的生活. 目前, 指纹识别作为一种身份鉴定方法已被广泛应用, 如各种电子消费软件的指纹支付、智能手机的指纹锁, 甚至一些电子门锁也采用了指纹识别技术.

随着信息化以及云计算、云存储的发展, 云服务提供了强大的运算和存储能力, 部分单位已将用户的私人信息存储至云数据库而非用户本地, 这对用户个人信息的隐私保护构成了很大挑战.

1978 年, Rivset 等人[2]首次提出了隐私同态的概念. 2009 年, Gentry[3]提出了一种基于理想格的全同态(fully homomorphic encryption, FHE) 算法. 2010 年, Dijk 等人[4]在Gentry 的思路上提出了整数上的全同态加密方案DGHV, 该方案实现了对整数的全同态加密, 其安全性基于近似最大公约数[5](approximate greatest common divisor, AGCD) 困难问题. 2012 年, Brakerski 等人[6]提出了BGV 方案, 突破了Gentry 提出的构造框架, 不使用Bootstrapping 技术获得层次型FHE 方案. 之后Fan 等人[7]对BGV 方案进行了优化, 并提出了BFV 方案. 近年, Microsoft 发布了同态加密软件库SEAL (simple encrypted arithmetic library), 并且不断地进行更新和完善.

SEAL 是Microsoft 研发的一款开源的同态加密库, 使用C++ 语言进行开发, 可以对密文下的数据进行同态运算操作, 从而可以应用在云端的安全存储与安全计算. 在2016 年, Bajard 等人[8]提出了BFV 方案的一个RNS (residue number systems) 变体, Microsoft 在2017 年发布了SEAL 的2.3.0 版本, 该版本实现了对Bajard 等人方案的支持. 2018 年, Microsoft 发布了SEAL 的3.0 版本, 该版本增添了对Cheon 等人[9]提出的CKKS 方案的支持, 实现了实数上的密文运算. 2019 发布的SEAL3.2.0 版本中, 又实现了对.NET 开发的支持.

2002 年, Hacigumus 等人[10]提出了数据库即服务(database as a service, DaaS) 的概念. 云存储使得用户可以将数据存储到云服务器上, 从而节省本地存储空间. 同时, 云存储也可能泄露用户数据信息.传统加密技术也可以提供对用户数据的安全性保护, 但是加密后的数据会丧失原本数据的数学特性, 导致加密后数据的可操作性大大降低. 若要对密文下的指纹特征进行匹配, 最重要的是解决数据隐私性和数据可操作性之间的矛盾. 同态加密技术对此难题有着良好的契合性, 同态加密不仅能保护数据的隐私性, 还可以对密文进行一定的运算操作. 在云服务飞速发展的今天, 基于同态加密的指纹识别系统有着广阔的应用前景.

本文提出了一种基于SEAL 库的指纹特征密文识别系统, 主要贡献为:

(1) 首次提出了基于SEAL 库的指纹特征识别方案. 本方案可以有效避免用户指纹信息的泄露, 防止内部人员对信息的获取. 将加密后的指纹特征存储于云端数据库中, 将密文下的指纹匹配算法部署于第三方计算平台, 借助云端和第三方计算平台可以实现对数据的快速处理, 有效解决了传统指纹识别仪对数据处理和存储的局限性, 相比于传统的指纹识别方案有着更为广阔的应用前景.

(2) 实现并测试了基于SEAL 库的指纹特征密文识别系统. 本方案基于SEAL 库进行开发, 平均一次识别的时间为1246.33 ms, 相比于Song 等人[11]在2018 年提出的基于SEAL 的虹膜特征密文认证系统耗时减少64.26%. 相比Dakhil 等人[12]在2018 年提出的方案, 本方案识别率提高了1.6%, 本方案认假率降低了45.08%. 相比Ali 等人[13]、Kahyaei 等人[14]和Chen 等人[15]提出的明文指纹识别方案, 系统提供了密文状态下几乎同级别的认假率和拒真率.

2 相关工作

近几年, 研究人员提出了各种方案来提供更优的指纹识别算法. Liu 等人[16]在2015 年提出了基于3D 的指纹识别思路, 相比于2D 的指纹识别可以获得更多有效信息. Jain 等人[17]在2017 年对幼儿的指纹进行了对比研究, 指出对六个月及以上幼儿的指纹进行计算机识别是可行的. Yoon 等人[18]在2015年对指纹的稳定性和唯一性进行了研究. 由于计算机并行计算能力的提升, 神经网络开始应用于指纹识别等身份认证领域, Dakhil 等人[12]在2018 年, 提出了一种基于KNN (K-nearest neighbor) 神经网络的指纹识别方案, 该方案拥有较好的识别率, 认假率与拒真率. Marasco 等人[19]在2015 年对指纹识别的抗欺骗方案进行了研究. Ali 等人[13]在2016 年提出了一种基于细化匹配(minutiae matching) 的指纹识别系统, 并进行了实现和测试. Kahyaei 等人[14]在2016 年提出了一种强鲁棒性的指纹识别系统, 并进行了算法实现和测试.

随着云服务的发展, 数据管理逐渐倾向于采用云储存和云处理模式, 给用户带来便捷的同时, 也会对用户的数据安全与隐私构成一定的威胁. 现有的方案大多数都为明文状态下的指纹识别方案, 这会给恶意攻击者提供实施攻击的可能. 在传统的指纹识别系统中, 首先进行指纹的初次采集, 用户在客户端录入指纹并计算出特征点, 再将特征点和用户ID 上传至云服务器, 云服务器接收到数据后, 以用户ID 作为Key值进行存储. 指纹录入后便可进行指纹的匹配工作, 匹配时需要再次对指纹进行录入和特征点提取, 将此次提取出的特征点和用户ID 上传到服务器. 服务器接收到数据后, 以用户ID 作为Key 值在数据库中进行检索以获取对应的特征点, 然后, 将已存储的特征点与上传的特征点进行匹配操作, 将最终结果发送至客户端.

本文提出了一种基于同态加密的指纹识别方案, 既能保护用户数据的安全, 又能让用户享受云服务带来的强大运算能力. 在基于同态加密的指纹识别系统中, 首先, 用户在客户端得到自己的公私钥对. 在指纹的初次采集中, 用户在客户端录入指纹并计算出特征点, 再用公钥对特征点进行加密, 最后将加密后的特征点与用户ID 上传到服务器进行存储. 指纹录入后便可进行指纹的匹配过程, 匹配时需要再次对指纹进行录入、提取并加密特征点, 加密后的特征点和用户ID 上传至服务器. 服务器接收到数据后, 以用户ID作为Key 值在数据库中进行检索以获取对应的特征点, 将已存储的密文特征点与上传的密文特征点进行密文下的同态匹配操作, 将匹配后得到的数据发送至客户端. 客户端对接收到的数据进行解密操作, 对解密后的明文数据进行少量运算, 得到最终结果.

当前主流的同态加密库为HElib、SEAL 以及FV-NFLlib. 2018 年, Melchor 等人[20]对HElib、SEAL 以及FV-NFLlib 做了性能上的比较, SEAL 库的性能在多个方面均优于HElib 和FV-NFLlib, 所以本方案选取SEAL 库作为开发工具进行开发.

3 BFV 全同态加密方案和SEAL 库

3.1 BFV 全同态加密方案

指纹特征密文识别系统采用BFV 方案. 下面简要介绍BFV 方案的原理[6,21].

BFV 方案建立在环R=Z[x]/(xn+1) 上,λ为安全系数,t为约减明文多项式的系数,χ是R上的错误概率分布,ω是对数的底数, 该方案具体算法如下.

为了证明解密算法是正确的, 将证明下面的辅助定理.

定理1 假设‖χ‖

如果2·δR·B2+B<Δ/2, 解密算法是正确的.

证明:

因为Δ·m+e·u+e1+e2·s已经在Rq具有足够小的误差项,因此可以推断出v=e·u+e1+e2·s. 因为e,e1,e2,u,s随机均匀的选自χ,所以通过恢复给定边界‖v‖≤2·δR·B2+B. 对c0+c1·s=Δ·m+v+q·r除q乘t, 得到m+(t/q)·(v −ε·m)+t·r,·这里ε=q/t −Δ=rt(q)/t<1. 为了四舍五入后的结果正确, 需要让(t/q)·‖v −ε·m‖<1/2.

v被称为噪声, 当噪声过大时, 解密后将得到不正确的明文. 同态加法运算和同态乘法运算都将增加噪声, 当噪声过大时, 需要进行重线性化操作.

3.2 SEAL 库

SEAL 是Microsoft 研发的一款开源的同态加密库, 提供了图1 所示的3 大功能模块.

图1 SEAL 库功能模块图Figure 1 Functional modules in SEAL library

.NET 功能模块提供信息安全应用开发接口. CKKS 方案可以对加密的实数或复数进行同态运算和重线性化, 得到近似精度的结果, 可以用在评估加密数据上的机器学习模型或用来计算加密位置距离等场合. BFV 方案允许在对加密的整数上执行同态运算、重线性化、批处理, 得到精确值结果. 我们选用BFV方案进行开发, 并对SEAL 库中BFV 方案的调用过程进行简单分析, 调用过程中所需要调用的对象如表1 所示.

在表1 中, 第一个设置的参数是多项式模的次数, 其值为2 的正次幂. 较大的poly_modulus_degree会使密文快速膨胀, 运算操作也更慢, 推荐值为1024、2048、4096、8192、16 384、32 768. 第二个设置的参数是密文系数模数, 其值越大, 噪声也会越大, 同时意味着可以进行更复杂的运算. SEAL 库分别提供了128-bit、192-bit、256-bit 的安全级别, coeff_modulus_128() 表示选用128-bit 的安全级别. 第三个设置的参数是明文模数, 其值可以是任何正整数, 我们取值为2 的幂. 明文模数决定了明文数据类型的大小和乘法中噪声的消耗, 为了获得最佳性能, 要尽量保持明文数据类型尽可能小. 新加密密文的噪声预算是log2(coeff_modulus/plain_modulus) bits. 同态乘法运算的噪声消耗为log2(plain_modulus)+(other terms). 所有参数设置完毕后, 就可以生成context 对象. 运用context 对象初始化密钥生成器, 从而获得公钥和私钥. 初始化加密器、解密器、运算器之后, 便可调用相关对象完成同态运算操作.

表1 SEAL 库调用对象Table 1 Objects called in SEAL library

4 系统设计与实现

4.1 传统指纹识别系统与指纹特征密文识别系统对比

在云环境下, 指纹识别系统的匹配操作往往会部署在不可信的第三方平台上, 使用传统指纹识别系统时, 首先对指纹进行录入操作, 再对录入后的指纹进行特征点的提取操作. 客户端为用户生成独有的用户ID, 将用户ID 和特征点上传至数据库服务器, 以用户ID 进行检索并将检索得到的特征点与上传的特征点进行指纹匹配操作. 由于指纹匹配操作是在明文下进行, 这为恶意破坏者提供了窃取甚至篡改匹配结果的可能, 使得识别结果的正确性和数据的机密性难以得到保障. 如图2 所示.

图2 传统指纹识别系统Figure 2 Traditional fingerprint characteristics recognition system

基于同态加密技术的指纹识别系统使得云端可以直接对密文下的特征点进行匹配操作, 从而在指纹匹配阶段保障了指纹特征点数据的机密性、安全性和隐私性, 且设计简单、思路清晰, 如图3 所示. 假设攻击者拥有对云端的操纵权, 如果攻击者想要窃取或者篡改信息, 那就需要知道用户的私钥, 而用户私钥并不会对外公开, 这就有效防止了来自云端内部的恶意攻击. 同时, 基于同态加密的密文指纹识别系统更加适用于云存储和云计算快速发展的今天, 可以在保证安全的前提下将密文指纹匹配操作部署至云端, 从而借助云端强大的计算能力实现高效的指纹识别.

图3 指纹特征密文识别系统Figure 3 Fingerprint characteristics recognition system in ciphertext

4.2 云环境下指纹识别系统的网络架构

分析指纹识别系统的基本数据处理流程, 可以得到云环境下指纹识别系统的网络架构, 如图4 所示.其中, 客户端和云端的功能分别为:

图4 云环境下指纹识别平台网络架构Figure 4 Network architecture for fingerprint recognition platform under cloud environment

客户端: 提供指纹采集、特征点提取、特征点加密、匹配结果解密、计算最终结果的功能, 与云端协同完成指纹识别.

云端: 提供数据特征点密文的存储和匹配功能. 对密文特征点进行匹配操作, 并将结果返回给客户端.云端中的数据除用户ID 外均以密文进行存储, 通过调用部署的函数接口, 实现密文数据的同态运算.

在密文指纹识别系统中, 云端存储的数据为使用SEAL 库进行加密运算后的指纹特征点密文, 并可以直接进行密文下的指纹匹配, 数据库所维持的数据关系也比较简单. 数据库中的实体关系图(entity relationship diagram, ERD) 如图5 所示.

图5 数据库中的实体关系图Figure 5 Entity relationship in database

数据库中主要包含2 个实体: 用户和密文特征点. 其中, 用户实体包含用户ID、姓名属性; 密文特征点包含用户ID、特征点数量、特征点密文、分隔符(一般情况下, 一个指纹会有多个特征点, 而数据库不支持对数组的存储, 所以我们将一个指纹的所有特征点密文存储在一起, 并以分隔符为界).

4.3 指纹特征密文识别系统设计

指纹特征密文识别系统大致分为注册阶段和匹配阶段. 主体步骤如下:

(1) 注册阶段.

客服端执行Init(EnvFHE), 用户使用私有的初始化参数来构建同态加密环境EnvFHE.

根据公/私钥对生成算法KeyGen 和参数λ,生成公钥pk 和私钥sk,并存储在本地,客户端生成UID.

客户端首先对用户指纹进行提取操作, Comp() 函数将提取后的指纹信息fingerinit加载进一个unsigned long 类型的对象re 中. 对re 进行平滑、计算方向场、分割前景背景、二值化等操作后, 进行特征点提取, 特征点featureinit存入FEATURE 类型中, FEATURE 数据结构如图6 所示. FEATURE 类包含一个int 类型的MinutiaNum 对象, 用来记录特征点数目, 特征点具体内容存储在MINUTIA 类型的数组中. MAXMINUTIANUM 限定了最大特征点个数(默认为50). MINUTIA 类包含4 个int 类型的成员.x、y用来记录特征点的位置坐标, Direction 用来记录特征点的方向角度, Triangle 用来记录特征点为中心外接圆半径为定值的正三角形三个顶点的方向, Type 记录特征点的指纹类型. 将明文特征值数据结构中的各成员类型替换为相应的密文类型, 就构成密文特征值的数据结构.

图6 明文特征值的数据结构Figure 6 Data structure of plaintext characteristics

客户端使用 Encrypt() 函数和用户公钥 pk 对特征点 featureinit进行加密, 得到特征点密文featureCtxt.

将UID 与特征点的密文值(UID,featureCtxt) 一起上传至云端. 云端再以UID 为Key 值对其进行存储.

(2) 匹配阶段

与注册阶段相似, 客户端首先对用户指纹进行提取得到 fingermatch, 再用 Comp() 函数提取出特征点 featurematch; 客户端使用用户公钥 pk 对特征点 featurematch进行加密, 得到特征点密文featurematch_Ctxt.

客户端将UID 和密文特征点(UID,featurematch_Ctxt) 上传至服务器数据库.

数据库服务器以 UID 为 Key 值进行检索得到 featureCtxt, 将检索得到的 featureCtxt与featurematch_Ctxt进行匹配Verification.

在明文识别系统中, 执行Verification 操作需要比较特征点类型、计算特征点之间的距离和夹角, 将各计算值与各阈值进行对比, 从而得出识别结果. 由于目前主流的同态加密算法还不能支持同态比较操作,所以这种方案并不能够直接应用于同态密文识别系统中. 本方案对明文识别模式进行修改,将Verification操作分为两个功能模块. 第一个功能模块部署于云端, 第二个功能模块部署于客户端, Verification 操作需要云端与客户端一起协作完成. 图7 和图8 分别是云端和客户端的Verification 流程图.

图7 云端Verification 流程图Figure 7 Verification flow in cloud

图8 客户端Verification 流程图Figure 8 Verification flow in client

假设要比对的一对指纹图片为X、Y (假定X 为注册指纹图片, Y 为待比对指纹图片), X 中特征点xi对应的特征值为CVxi= (Typexi,pxxi,pyxi,Dirxi), Typexi表示特征点xi的类型值、pxxi和pyxi表示特征点xi的坐标、Anlxi表示特征点xi的方向角度. Y 中特征点对应的特征值定义与此类似. 分别计算特征点xi与特征点y1,y2,··· ,yn的类型差值、特征点之间的距离和夹角.

指纹类型值Typexi表示特征点xi的类型值, 指纹类型分为斗型、弓型和箕型, 分别为1、2、3. 取定一个特征点xi, 分别计算xi与y1,y2,··· ,yn的类型差值, 记为Diffxi,yj. 重复此过程, 分别计算出所有x1,x2,··· ,xn与y1,y2,··· ,yn的类型差值, 每一个特征点需要进行n次减法运算, 所有特征点总共需要n2次减法运算.

根据特征点x的坐标px 和y的坐标py, 分别计算出xi与y1,y2,··· ,yn欧氏距离的平方, 记为Disxi,yj. 重复此过程, 分别计算出所有有x1,x2,··· ,xn与y1,y2,··· ,yn欧氏距离的平方, 每个特征点x、y坐标分别需要进行n次减法运算、n次乘法运算, 所有特征点总共需要进行2n2次减法运算、n2次加法运算、2n2次乘法运算.

根据特征点的方向角度Dir, 分别计算xi与y1,y2,··· ,yn的夹角, 记为Anlxi,yj. 重复此过程, 分别计算出所有x1,x2,··· ,xn与y1,y2,··· ,yn的夹角, 每一个特征点需要进行n次减法运算, 所有特征点总共需要n2次减法运算.

云端完成计算后, 将所有计算结果发至客户端.

客户端首先用私钥对收到的数据进行解密, 得到对应的明文.

首先判断所得明文类型差值diffxi,yj是否为0, 若不为0 则代表指纹类型不同, 从而不可能匹配, 直接得出结果为不匹配.

如果类型差值为0, 根据所得明文分别计算xi与y1,y2,··· ,yn的得分scorexi,yj. 根据得分scorexi,yj求xi的最高得分score_maxxi. 重复上述过程, 直到计算出所有x1,x2,··· ,xn的最高得分. 对所有最高得分进行求和, 得出最终得分score_final, 将最终得分与阈值进行比较, 大于阈值则结果为匹配, 否则结果为不匹配.

在上述方案中, 客户端如果直接对MAXMINUTIANUM (默认为50 个) 特征点进行加解密, 计算量将难以承受. 为了减少客户端的工作量, 进一步采用批处理技术(batching), 将客户端的加解密次数降为只有4 次. 批处理技术[22]利用中国剩余定理(Chinese remainder theorem, CRT) 和单指令多数据流(single instruction multiple data, SIMD)[23], 执行批处理时, 将n个明文数据打包为一个中间明文p1,p2,··· ,pn, 对中间明文p的运算相当于采用并行方式对p1,p2,··· ,pn进行运算.

以指纹类型值为例, 注册时客户端采集每个特征点的指纹类型值Typexi得到如下矩阵Mtype, 采用批处理技术将矩阵Mtype打包成为一个中间明文ptype, 对其执行同态加密得到所对应的密文ctype.

本方案将匹配时的数值大小比较运算转化为同态加减法运算, 客户端收到结果并解密后便可根据结果的正负来判断数值的大小. 把尽可能多的运算部署于云端, 少量的运算过程部署于客户端, 同时利用批处理技术进一步降低客户端的加解密运算量. 从而高效实现同态密文指纹识别方案.

5 测试与分析

测试环境配置为Intel i5 1.6 GHz 处理器, 8 GB 内存, Win10 操作系统, 下面给出认假率和拒真率的相关定义.

定义1 (认假率) 又称错误接收率、false accept rate、FAR、flse match rate、FMR, 指在来自不同类别的样本比对过程中, 比对结果误为同类的比对次数占不同类别的样本比对总次数的比例.

定义2 (拒真率) 又称错误拒绝率、false reject rate、FRR、false non-match rate、FNMR, 在来自同类样本的比对过程中, 比对结果误为不同类的比对次数占同类样本的总比对次数的比例.

5.1 数据集分析

本方案的测试考虑了多种情况带来的影响, 例如指头的脱皮、指纹的断裂、不同大小的指纹录取面积.如图9 所示, (a) 为带有脱皮的指纹, (b) 为带有断裂的指纹, (c) 为同一指纹不同的采集面积, 测试样本包含上述所有情况, 并且每种情况均进行了多次测量并取平均值.

图9 不同类型的指纹图片Figure 9 Different fingerprint images

5.2 与其他明文指纹识别系统对比与分析

本方案与近5 年新提出的明文指纹识别方案进行对比, 给出了在识别率、认假率、拒真率上的对比结果, 如表2 所示. 文献[12] 提出了一种基于KNN 神经网络的指纹识别方案, 文献[13] 提出了一种基于细化匹配(minutiae matching) 的指纹识别方案, 文献[14] 提出了一种使用pseudo-Zernike moments 的鲁棒指纹匹配方案, 文献[15] 提出了一种超短二进制描述符(USB-POC) 指纹快速匹配方案. 上述4 种方案在识别率上仅高出本方案1% 到2%. 本方案的认假率相对于文献[12] 降低了45.08%, 相对于文献[15]降低了85.06%. 本方案的拒真率优于文献[13] 和文献[15], 最为关键的是, 本方案提供了用户指纹特征数据的安全性与隐私性的保障.

表2 与其他明文方案性能对比Table 2 Performance comparison with other plaintext schemes

5.3 本方案的明文实现与密文实现对比与分析

为了说明同态加密的引入对原有明文指纹识别方案在时间效率上的影响程度, 与本方案对应的明文识别方案进行了实现和对比, 结果如表3 所示.

表3 本方案的密文实现与明文实现的性能对比Table 3 Performance comparison between ciphertext and plaintext in proposed scheme

从表3 中可以看出, 同态运算在噪声不超出上限的情况下, 不会对识别结果产生影响. 也就是说, 明文实现与密文实现的识别率、认假率、拒真率之间只存在微小的差异, 可能的原因在于, 两次录入的指纹图片不能保证完全一致. 但密文实现的用时比明文实现多出1046.33 ms, 随着云计算能力的不断加强, 此差异会不断减小.

5.4 与其他同态身份识别系统的对比与分析

为了进一步说明本全同态加密指纹识别方案的优势, 与采用其他生物特征的同态识别方案也进行了时间效率上的对比, 结果如表4 所示.

表4 与其他同态身份识别系统的性能对比Table 4 Performance comparison with other homomorphic identification recognition schemes

文献[11] 给出了一种基于SEAL 库的虹膜特征密文认证系统. 由于指纹识别过程中的数据量和计算量远小于虹膜识别, 所以在都基于SEAL 库进行开发的同时, 本方案的耗时相比于文献[11] 减少了64.23%.

6 小结

本文通过将同态加密与指纹识别相结合, 首次提出了一种基于SEAL 库的指纹特征密文识别方案与系统. 在指纹识别系统中引入全同态加密运算, 把密文状态的指纹特征信息存储于云端数据库, 通过云计算克服了密文识别中加解密运算开销过大的难题, 高效完成了密文识别. 测试结果表明, 与当前的明文指纹识别方案相比, 本文提供了密文状态下与之几乎同级别的识别率、认假率和拒真率. 本方案和系统在密文人脸识别、隐私保护、身份认证领域具有一定的参考价值和应用前景. 下一步研究方向是结合神经网络进一步提高识别率并且降低认假率和拒真率.