Print

发布时间: 2018-09-16
摘要点击次数:
全文下载次数:
DOI: 10.11834/jig.170647
2018 | Volume 23 | Number 9




    图像处理和编码    




  <<上一篇 




  下一篇>> 





面向人脸图像发布的差分隐私保护
expand article info 张啸剑1, 付聪聪1, 孟小峰2
1. 河南财经政法大学计算机与信息工程学院, 郑州 450046;
2. 中国人民大学信息学院, 北京 100872

摘要

目的 由于人脸图像蕴含着丰富的个人敏感信息,直接发布出来可能会造成个人的隐私泄露。为了保护人脸图像中的隐私信息,本文提出了一种基于傅里叶变换与差分隐私技术相结合的人脸图像发布方法FIP(facial image publication)。方法 将人脸图像作为实数域2维矩阵,充分利用离散傅里叶变换技术压缩图像。为了有效均衡由拉普拉斯机制引起的噪音误差以及由傅里叶变换导致的重构误差,引入一种基于指数机制的傅里叶系数选择方法EMK(exponential mechanism-based $k$ coefficients sampling),它能够在不同的系数空间中挑选出合理的傅里叶系数来压缩人脸图像,然后利用拉普拉斯机制对所挑选出的系数添加噪音,进而使整个处理过程满足$\varepsilon $-差分隐私。此外,为了避免较大的傅里叶系数空间导致指数机制挑选系数不准确问题,基于离散实数傅里叶变换的共轭对称特性,提出了一种增强的指数机制挑选傅里叶系数方法BEMK(boosted exponential mechanism-based $k$ coefficients sampling),该方法不仅进一步压缩离散傅里叶系数空间,而且还能够提高人脸图像发布的精度。结果 基于4种真实人脸图像数据集采用支持向量机分类与采用主成分分析技术验证方法的正确性。从算法的准确率、召回率,以及F1-Score度量结果显示,提出的基于离散傅里叶变换技术的人脸图像发布方法均优于直接采用拉普拉斯机制的发布方法LAP(Laplace mechanism-based publication)。结论 实验结果表明,本文方法能够实现满足$\varepsilon $-差分隐私的敏感人脸图像发布,图像分类验证其具有较高的可用性。特别是BEMK方法具有较好的鲁棒性,是一种有效的隐私人脸图像发布方法。

关键词

人脸图像处理; 隐私保护; 差分隐私; 傅里叶变换

Facial image publication with differential privacy
expand article info Zhang Xiaojian1, Fu Congcong1, Meng Xiaofeng2
1. School of Computer & Information Engineering, Henan University of Economics and Law, Zhengzhou 450046, China;
2. School of Informatica, Renmin University of China, Beijing 100872, China
Supported by: National Natural Science Foundation of China (61502146, 91646203, 91746115, 61572420); National Natural Science Foundation of Henan Province, China (162300410006); The Key Technologies R&D Program of Henan Province, China (172102310713)

Abstract

Objective Facial image publication (FIP) in a direct way may lead to privacy leakage of individuals because facial images are inherently sensitive. To protect the private information in facial images, this paper proposes an efficient publishing algorithm called FIP that is based on Fourier transform combined with differential privacy, which is the state-of-the-art model to address privacy concerns. Method First, this algorithm uses the real-valued matrix to model the facial image, in which each cell corresponds to each pixel point of the image. Then, on the basis of the matrix, this algorithm relies on the Fourier transform technique to extract the Fourier coefficients (e.g., a pre-defined limit $k$ on the coefficients sampled) and then uses the Laplace mechanism to inject noise into each coefficient to ensure differential privacy. Finally, this algorithm uses Fourier inverse transform to reconstruct the noisy facial image. However, in the FIP algorithm, we encounter two sources of errors:1) the Laplace error (LE) due to the Laplace noise injected and 2) the reconstruction error (RE) caused by the lossy compression of Fourier transform. The selection of $k$ is a serious dilemma:for the FIP algorithm to produce the low LE, $k$ cannot be large, whereas a small $ causes the RE to be extremely large. However, increasing $k$ would cause RE to be small but LE to be extremely large. Furthermore, $ cannot be directly tuned on the basis of facial images; otherwise, the selection of $k$ itself reveals private information in facial images and violates differential privacy. Therefore, a differentially private $k$ value is vital in balancing the LE and RE in sanitized facial images. To remedy the deficiency of FIP, we present exponential mechanism-based $k$ coefficient sampling (EMK), a $k$ coefficient sampling algorithm that adopts exponential mechanism to select the suitable coefficients but eliminates the dependency on a pre-defined $k$. The core of EMK is to sample $k$ coefficients first by using a portion of the privacy budget in different candidate coefficients set via exponential mechanism and uses the Laplace noise to perturb the $k$ samples by utilizing the remaining budget. On the basis of the sequential composition of differential privacy, the two phases meet $\varepsilon $-differential privacy. The EMK algorithm, however, does not exploit the correlation over all coefficients, which may generate a large candidate sampling set and an inaccurate $k$ selection. We notice that the discrete real-valued Fourier coefficients are correlated as they are half-redundant. On the basis of this observation, a boosted EMK (BEMK) is proposed to address the problem in EMK. The main idea of BEMK is to use the conjugate symmetry of discrete real Fourier transform to compress the candidate set and adopt the exponential mechanism to select the $k$ coefficients in the compressed candidate set. Result On the basis of the SVM classification and principal component analysis technique, comprehensive experiments were conducted over four real facial image datasets ((CMU), (ORL), Yale, and YaleB) to evaluate the quality of the facial images generated from the BEMK, EMK, FIP, and LAP algorithms using a variety of metrics, including precision, recall, and F1 score. Our experiments show that the proposed BEMK, EMK, and FIP algorithms outperform LAP in terms of the abovementioned four metrics. BEMK applies to the four datasets and achieves better accuracy than EMK and FIP. For example, on the CMU dataset, we fix the matrix=128×128 and vary the privacy budget $\varepsilon $ (i.e., 0.1, 0.5, 0.9, and 1.4) to study the accuracy of each algorithm. Tables 1-12 show the results. As expected, the accuracy measures of all algorithms increase when $\varepsilon $ increases. When $\varepsilon $ varies from 0.1 to 1.4, BEMK still achieves a better precision, recall, and F1 score than the other algorithms. Their values are 88%, 90%, and 89%, respectively. Conclusion We provide both in-depth theoretical analysis and extensive experiments to compare BEMK with EMK, FIP, and LAP. Results show that the proposed algorithms can overcome the privacy leakage of FIP. BEMK significantly improves compared with the other three algorithms. Moreover, BEMK also maintains good robustness and generates high-quality synthetic facial images while still satisfying differential privacy.

Key words

facial image processing; privacy protection; differential privacy; Fourier transform

0 引言

信息技术的迅速发展,使得数字图像的获取与共享变得尤为容易。用户可以通过社交媒体(例如,Facebook, Instagram)发布自己手机或者相机中的照片。图像收集方对所获得的照片进行集成分析,能够为企业与个人提供更具有个性化的服务。然而,数字图像通常蕴含着丰富的个人隐私信息,如果直接发布这些隐私图像,会直接泄露个人的敏感信息。例如,苹果6S或苹果7中的“Live Photo”功能根据用户上传的自己照片能够准确定位用户所在的位置。因此,隐私保护的图像发布得到研究者广泛关注。文献[1-2]利用匿名化机制提出了k-same方法,该方法对所发布的灰度人脸图像进行匿名化操作,使攻击者通过发布的人脸图像重新甄别出用户身份的概率不超过1/k。然而,传统的匿名化机制主要缺陷是对攻击者的背景知识和攻击模型给出了相当多的假设,但是那些假设在现实中并不完全成立。例如,文献[3]揭示匿名化后的人脸图像放到Facebook社交平台,攻击者通过该平台额外的Friendster特征可以推理出匿名人脸图像中的个人社会安全号(SSN),通过SSN号码攻击者可以甄别出个人的疾病、住址等敏感信息。文献[4]利用同态加密技术对灰度人脸图像进行加密处理,防止通信过程被重新甄别。然而,数据加密技术同样会对攻击做出相应的假设,基于这些假设再设计相应的加密算法,而这类加密方法会陷入“新加密方法不断被提出但又不断被打破”的循环怪圈中。

目前,差分隐私已经成为一种新型隐私保护技术,该技术不关心攻击者拥有多少背景知识,通过向查询或者分析结果中添加适当噪音来达到隐私保护的效果。基于差分隐私的发布技术已涉及多种数据类型,例如关系数据、空间数据、流数据等,然而针对人脸图像数据,却存在很少的工作。其主要挑战在于:1)对人脸图像进行噪音处理时,如何计算其噪音敏感度;2)对噪音处理后的人脸图像进行分析(例如,SVM分类)时,如何保持其精度。

总而言之,目前还没有一个行之有效的隐私人脸图像发布方法来同时克服上述两种挑战带来的不足。为此,本文基于差分隐私提出高效的灰度人脸图像发布方法。

本文主要贡献如下:

1) 为了降低人脸图像中噪音的影响,提出一种基于离散傅里叶变换的图像压缩方法FIP(facial image publication),针对所压缩的图像添加相应的拉普拉斯噪音;

2) 为了减少傅里叶变换带来的重构误差,提出了两种基于指数机制的傅里叶系数选择方法EMK(exponential mechanism-based k coefficients sampling)与BEMK(boosted exponential mechanism-based k coefficients sampling)。这两种算法利用指数机制在系数空间中挑选合适的k值进行图像压缩,并且使挑选k值的过程满足差分隐私。

3) 理论证明所提出的人脸图像发布方法满足$\varepsilon $-差分隐私。在4种真实的人脸库上验证了所提出方法的有效性与可用性。

1 相关工作

基于差分隐私的数据发布已得到研究者的广泛关注。目前,直方图发布[5]、空间数据发布[6]、图数据发布[7]、流数据发布[8]、时序数据发布[9]、高维数据发布[10]等均已存在相应的研究工作。而鉴于人脸图像数据的复杂性,目前研究者还未涉及采用差分隐私技术保护人脸图像中的隐私信息。然而人脸图像数据却比较容易泄露用户的个人隐私,造成用户的隐私安全威胁,所以迫切需要一种基于差分隐私的人脸图像数据发布方法。

傅里叶变换与小波变换是人脸图像处理的常用压缩技术。目前已有研究者采用这两种技术来处理1维的隐私数据。文献[9]借助傅里叶变换与差分隐私技术发布1维的时序数据,其主要思想是对1维时序数据进行傅里叶变换,然后对傅里叶系数添加拉普拉斯噪音;文献[11]利用小波变换与差分隐私技术发布1维序列数据,其主要思想与傅里叶变换类似,主要是对小波系数进行噪音处理。然而,这两种方法不能直接应用于灰度人脸图像,其原因是无法直接采用文献[10-11]中的方法度量人脸图像发布的全局敏感性。

实数域矩阵也是人脸图像常用的表示形式。目前已有工作利用矩阵技术来处理批处理查询[12-13]。文献[12]利用矩阵机制响应批处理查询,其主要思想是把批处理查询视为查询矩阵,根据查询矩阵本身的敏感性添加噪音;文献[13]利用低秩机制将批量性数据看做一种矩阵模型,该机制是线性相关的处理方式,而人脸图像数据中的数值有时并不具备相关性,所以该方法并不适用于人脸图像数据发布。因此,本文基于离散傅里叶变换提出了一种满足差分隐私的人脸图像发布方法。该方法不但满足差分隐私,同时所发布的图像具有较高的正确性。

2 定义与问题

2.1 差分隐私

差分隐私保护模型[14-15]的精髓是确保在数据集中插入或者删除一条记录的操作不会影响任何计算的输出。相比于传统的隐私保护模型,差分隐私保护模型具有两个显著的特点:1)不依赖于攻击者的背景知识;2)具有严谨的统计学模型,能够提供可量化的隐私保证。因此,本文利用差分隐私对人脸图像发布时进行隐私保护。给定一幅人脸图像,将每一个像素点作为一个单元,则人脸图像可以表示成一个2维数据矩阵${\mathit{\boldsymbol{A}}_{m \times n}}$,其中 $m$表示矩阵$\mathit{\boldsymbol{A}}$的行数,$n$表示$\mathit{\boldsymbol{A}}$的列数。在给出差分隐私形式化定义之前,首先结合$\mathit{\boldsymbol{A}}$给出近邻关系的定义。

定义1 给定一矩阵${\mathit{\boldsymbol{A}}_{m \times n}} = \left[{\begin{array}{*{20}{c}} {{a_{11}}, }&{{a_{12}}, }&{ \cdots, }&{{a_{1n}}}\\ {{a_{21}}, }&{{a_{22}}, }&{ \cdots, }&{{a_{2n}}}\\ \vdots & \vdots &{}& \vdots \\ {{a_{m1}}, }&{{a_{m2}}, }&{ \cdots, }&{{a_{mn}}} \end{array}} \right]$,其中${a_{ij}}$表示人脸图像中的某个像素点。用向量把$\mathit{\boldsymbol{A}}$表示为$\mathit{\boldsymbol{W = }}\left[{{a_1}, {a_2}, \cdots, {a_n}} \right]$,其中${\mathit{\boldsymbol{a}}_i} = {\left[{{a_{1i}}, {a_{2i}}, \cdots, {\mathit{a}_{ni}}} \right]^{\rm{T}}}$。如果$\mathit{\boldsymbol{W}}$${\mathit{\boldsymbol{W'}}}$相差一个向量,即$\left| {\mathit{\boldsymbol{W}}-\mathit{\boldsymbol{W'}}} \right| = {\mathit{\boldsymbol{a}}_i}$,则$\mathit{\boldsymbol{W}}$${\mathit{\boldsymbol{W'}}}$互为近邻关系。

结合$\mathit{\boldsymbol{W}}$${\mathit{\boldsymbol{W'}}}$上的近邻关系给出$\varepsilon $-差分隐私的形式化定义,如下所示:

定义2[16] 给定一个人脸图像数据发布算法$M$$Range\left( M \right)$$M$的输出范围,若算法$M$$\mathit{\boldsymbol{W}}$${\mathit{\boldsymbol{W'}}}$上的任意输出结果$O\left( {O \in Range\left( M \right)} \right)$满足下列不等式,则$M$满足$\varepsilon $-差分隐私,即

$ \begin{array}{*{20}{c}} {\mathit{Pr}\left( {M\left( \mathit{\boldsymbol{W}} \right) = O} \right) \le \exp \left( \varepsilon \right) \times }\\ {\mathit{Pr}\left( {M\left( {\mathit{\boldsymbol{W'}}} \right) = O} \right)} \end{array} $ (1)

式中,$\varepsilon $表示隐私预算,其值越小则表示算法$M$的隐私保护程度越高,$P\mathit{r}\left( {M\left( \mathit{\boldsymbol{W}} \right) = O} \right)$表示$M$基于$\mathit{\boldsymbol{W}}$输出$O$的概率。

从定义2可以看出,$\varepsilon $-差分隐私限定了$\mathit{\boldsymbol{W}}$中任一向量的改变对算法$M$输出结果的影响。实现差分隐私需要噪声机制的介入,拉普拉斯机制[17]是实现差分隐私的主要技术。而所需要的噪声大小与其相应查询函数$f$的全局敏感性密切有关。

定义3 设$f$为某一个查询函数,且$f:D \to {{\bf{R}}^d}$$f$的全局敏感性为

$ \Delta f = \mathop {\max }\limits_{\mathit{\boldsymbol{W}},\mathit{\boldsymbol{W'}}} {\left\| {f\left( \mathit{\boldsymbol{W}} \right) - f\left( {\mathit{\boldsymbol{W'}}} \right)} \right\|_p} $ (2)

式中,$p$可以取值1或者2,${\bf{R}}$表示所映射的实数空间,$d$表示$f$的查询维度。

文献[17]提出的拉普拉斯机制可以取得差分隐私保护效果,该机制采用拉普拉斯分布产生的噪音(噪音分布满足拉普拉斯概率密度函数$pdf\left( {x\left| \lambda \right.} \right) = \frac{1}{{2\lambda }}{{\rm{e}}^{-\left| x \right|/\lambda }}, \left. {\lambda = \Delta f/\varepsilon } \right)$使发布算法满足$\varepsilon $-差分隐私,如定理1所示。

定理1 设$f$为某一个查询函数,且$f:D \to {{\bf{R}}^d}$,若发布算法$M$符合下列等式,则$M$满足$\varepsilon $-差异隐私。

$ \begin{array}{*{20}{c}} {M\left( D \right)}=\\ {f\left( D \right) + \left\langle {la{p_1}\left( {\Delta f/\varepsilon } \right), \cdots ,la{p_d}\left( {\Delta f/\varepsilon } \right)} \right\rangle } \end{array} $ (3)

式中,$lap\left( {\Delta f/\varepsilon } \right)\left( {1 \le i \le d} \right)$为相互独立的拉普拉斯噪音变量,噪音量大小与$\Delta f$成正比,与$\varepsilon $成反比。因此,查询$f$的全局敏感性越大,所需的噪音越多。

文献[18]提出的指数机制主要处理抽样算法的输出为非数值型的结果。该机制的关键技术是如何设计打分函数$u\left( {\mathit{\boldsymbol{W}}, k} \right)$。设$M$为指数机制下的某个抽样方法,则$M$在打分函数作用下的输出结果为

$ \begin{array}{*{20}{c}} {M\left( {\mathit{\boldsymbol{W}},k} \right) = }\\ {\left\{ {k\left| {\mathit{Pr}\left[ {k \in O} \right] \propto \exp \left( {\frac{{\varepsilon \times u\left( {\mathit{\boldsymbol{W}},k} \right)}}{{2\Delta u}}} \right)} \right.} \right\}} \end{array} $ (4)

式中,$\Delta u$为打分函数$u\left( {\mathit{\boldsymbol{W}}, k} \right)$的全局敏感性,$O$$M$算法的输出域。由式(4)可知,$k$的打分函数越高,被选择输出的概率越大。

2.2 离散傅里叶变换

离散傅里叶变换是一种可逆的、线性的变换,将时域信息转换为频域信息。以一个尺寸为$m$×$n$的人脸图像为例,$f\left( {x, y} \right)$为其图像函数,该图像函数的离散傅里叶变换$F\left( {u, v} \right)$

$ F\left( {u,v} \right) = \frac{1}{{mn}}\sum\limits_{x = 0}^{m - 1} {\sum\limits_{y = 0}^{n - 1} {f\left( {x,y} \right){{\rm{e}}^{ - j2{\rm{ \mathsf{ π} }}\left( {ux/m + vy/n} \right)}}} } $ (5)

$f\left( {x,y} \right)$经过离散傅里叶变换后,可以采用傅里叶反变换得到无损恢复,即

$ f\left( {x,y} \right) = \sum\limits_{u = 0}^{m - 1} {\sum\limits_{v = 0}^{n - 1} {F\left( {u,v} \right){{\rm{e}}^{j2{\rm{ \mathsf{ π} }}\left( {ux/m + vy/n} \right)}}} } $ (6)

给定$\mathit{\boldsymbol{W}} = \left( {{a_1}, {a_2}, \cdots, {a_n}} \right)$,根据式(5)可知,若$\mathit{\boldsymbol{F}} = DFT\left( \mathit{\boldsymbol{W}} \right)$成立,其中$DFT$()表示离散傅里叶变换函数,则根据傅里叶变换的共轭对称性可推理出${F_i} = F_{n-i}^*$成立,即$F_{n-i}^*$${F_{n-i}}$的共轭复数。因此,离散傅里叶变换的输出是半冗余的,则傅里叶变换的表达公式为

$ DF{T^{{\rm{real}}}}\left( \mathit{\boldsymbol{W}} \right) = \left( {{F_0}, \cdots ,{F_q}} \right) $ (7)

式中,$q = \left\{ \begin{array}{l} \left( {n + 1} \right)/2\;\;\;\;\;n为偶数\\ n/2 + 1\;\;\;\;\;\;\;\;\;n为奇数 \end{array} \right.$

此外,根据式(6)可知,$DFT\left( \mathit{\boldsymbol{W}} \right)$$DF{T^{{\rm{real}}}}\left( \mathit{\boldsymbol{W}} \right)$分别满足可逆性,即$\mathit{\boldsymbol{W = }}\mathit{IDFT}\left( {DFT\left( \mathit{\boldsymbol{W}} \right)} \right)$$\mathit{\boldsymbol{W = }}\mathit{I}DF{T^{{\rm{real}}}}\left( {DF{T^{{\rm{real}}}}\left( \mathit{\boldsymbol{W}} \right)} \right)$

2.3 问题描述

给定一张人脸图像以及其相应的表示矩阵$\mathit{\boldsymbol{A}}$与向量$\mathit{\boldsymbol{W}}$。结合$\mathit{\boldsymbol{A}}$$\mathit{\boldsymbol{W}}$,利用离散傅里叶技术对$\mathit{\boldsymbol{W}}$进行$DFT$变换,采用拉普拉斯机制对$DFT$变换过程进行扰动。然后利用$IDFT$操作重新恢复W,进而得到$\mathit{\boldsymbol{\widetilde W}}$。然而在获得$\mathit{\boldsymbol{\widetilde W}}$的过程中却存在两种误差,一种是拉普拉斯机制导致的噪音误差$LE$($\mathit{\boldsymbol{\widetilde W}}$),另外一种是重构过程中的重构误差$RE$($\mathit{\boldsymbol{\widetilde W}}$)。因此,发布人脸图像$\mathit{\boldsymbol{\widetilde W}}$的总体误差$Error$($\mathit{\boldsymbol{\widetilde W}}$)可以表示为

$ Error\left( {\mathit{\boldsymbol{\tilde W}}} \right) = RE\left( {\mathit{\boldsymbol{\tilde W}}} \right) + LE\left( {\mathit{\boldsymbol{\tilde W}}} \right) $ (8)

因此,本文的问题为如何发布总体误差较小的灰度人脸图像。

3 基于差分隐私的人脸图像处理方法

在设计人脸图像发布方法时,需要考虑以下两种原则:

原则1,由于人脸图像数据是2维数据类型,若对人脸图像进行整体性加噪,所发布图像的可用性比较差。因此,所设计的发布方法要考虑到如何减少$LE$ ($\mathit{\boldsymbol{\widetilde W}}$);

原则2,在采用离散傅里叶变换对人脸图像进行压缩变换时,要考虑到人脸图像的信息是否存在过度失真问题,即傅里叶系数的选择问题,很小的系数会导致图像过度损失,即导致$RE$($\mathit{\boldsymbol{\widetilde W}}$)比较大。因此,所设计的发布方法应考虑如何减少$RE$($\mathit{\boldsymbol{\widetilde W}}$)。

针对原则1,本文采用傅里叶变换的方法,先对人脸图像进行压缩变换,再对压缩之后的数据加拉普拉斯噪声,这样不仅可以满足$\varepsilon $-差分隐私,还可以降低整体噪声误差$LE$($\mathit{\boldsymbol{\widetilde W}}$)。

针对原则2,本文在保证人脸图像数据的特征信息方面,利用基于指数机制的采样方法选择合适的傅里叶系数,进而减少重构误差$RE$($\mathit{\boldsymbol{\widetilde W}}$)。

3.1 LAP发布方法

本文基于拉普拉斯机制提出LAP发布方法,该方法直接利用拉普拉斯噪音对人脸图像进行扰动,扰动后发布。给定一幅尺寸为$m$×$n$的人脸图像${\mathit{\boldsymbol{A}}_{m \times n}}$,其向量表示形式为$\mathit{\boldsymbol{W}}{\rm{ = }}\left[{{a_1}, {a_2}, \cdots, {a_n}} \right]$。利用LAP方法对向量$\mathit{\boldsymbol{W}}$添加相应的拉普拉斯噪音后获得噪音向量$\mathit{\boldsymbol{\widetilde W}}= \left( {{{\tilde a}_1}, {{\tilde a}_2}, \cdots, {{\tilde a}_n}} \right)$,其中,${{\tilde a}_i} = {a_i} + \sum\limits_{j = 1}^m {lap\left( {{\Delta _1}\mathit{\boldsymbol{W}}{\rm{/}}\varepsilon } \right)} $。根据定理1可知,LAP发布方法满足$\varepsilon $-差分隐私。

接下来阐述LAP方法产生的噪音误差。本文采用误差平方和的期望来度量$LE$($\mathit{\boldsymbol{\widetilde W}}$),即

$ \begin{array}{*{20}{c}} {LE\left( {\mathit{\boldsymbol{\tilde W}}} \right) = {\rm{E}}\left( {\sum\limits_{i = 1}^n {Error\left( {{{\tilde a}_i}} \right)} } \right) = {\rm{E}}\left( {\sum\limits_{i = 1}^n {{{\left( {{{\tilde a}_i} - {a_i}} \right)}^2}} } \right) = }\\ {{\rm{E}}\left( {\sum\limits_{i = 1}^n {{{\left( {{a_i} - {a_i} + \sum\limits_{j = 1}^m {lap\left( {\frac{{{\Delta _1}\mathit{\boldsymbol{W}}}}{\varepsilon }} \right)} } \right)}^2}} } \right) = }\\ {\sum\limits_{i = 1}^n {\frac{{2m{{\left( {{\Delta _1}\mathit{\boldsymbol{W}}} \right)}^2}}}{{{\varepsilon ^2}}}} = 2mn\frac{{{\Delta _1}\mathit{\boldsymbol{W}}}}{\varepsilon }} \end{array} $

式中,${\Delta _1}\mathit{\boldsymbol{W = }}{\left\| \mathit{\boldsymbol{W}} \right\|_1} = \mathop {{\rm{max}}}\limits_j \;\sum\limits_{i = 1}^n {\left| {{a_{ij}}} \right|} $,即为最大的列范数。

由上述公式可知,当图像矩阵尺寸比较大时,所产生的总误差就越大。直接利用LAP发布人脸图像,会导致发布结果的可用性比较低。为了提高可用性,本文基于离散傅里叶技术提出几种发布方法。

3.2 基于离散傅里叶变换的发布方法

为了满足原则1,本文利用离散傅里叶技术对原始人脸图像进行压缩变换。给定向量矩阵$\mathit{\boldsymbol{W}}{\rm{ = }}\left[{{a_1}, {a_2}, \cdots, {a_n}} \right]$,利用式(5)对$\mathit{\boldsymbol{W}}$进行变换,提取前$k$×$k$个傅里叶系数,进而形成系数向量${\mathit{\boldsymbol{F}}^k} = \left( {{F_1}, {F_2}, \cdots, {F_k}} \right)$。获得系数向量${\mathit{\boldsymbol{F}}^k}$之后,采用拉普拉斯机制对${\mathit{\boldsymbol{F}}^k}$中的系数添加拉普拉斯噪音,形成噪音系数向量,即${{\mathit{\boldsymbol{\tilde F}}}^k} = \left( {{{\tilde F}_1}, {{\tilde F}_2}, \cdots, {{\tilde F}_k}} \right)$,其中,${{\tilde F}_i} = {F_i} + lap\left( {{\Delta _1}{\mathit{\boldsymbol{F}}^k}/\varepsilon } \right)\left( {1 \le i \le k} \right)$。基于上述分析思想,本文提出了一种基于傅里叶变换的人脸图像发布方法FIP,该方法的具体实现步骤如下所示:

输入:人脸图像$\mathit{\boldsymbol{W}}$,参数$k$,隐私预算$\varepsilon $

输出:满足$\varepsilon $-差分隐私的人脸图像$\mathit{\boldsymbol{\widetilde W}}$

1) ${\mathit{\boldsymbol{F}}^n}$$DFT$($\mathit{\boldsymbol{W}}$) //对$\mathit{\boldsymbol{W}}$进行离散傅里叶变换

2) ${\mathit{\boldsymbol{F}}^k}$${\mathit{\boldsymbol{F}}^n}$ //取${\mathit{\boldsymbol{F}}^n}$的前$k$×$k$个傅里叶系数

3) for $r$ from 1 to $k$//$r$是矩阵的行

4) for $c$ from 1 to $k$//$c$是矩阵的列

5) ${{\mathit{\boldsymbol{\tilde F}}}^k}$($r$, $c$)←${{\mathit{\boldsymbol{\tilde F}}}^k}$($r$, $c$)+2×$lap$(${{\Delta _1}{\mathit{\boldsymbol{F}}^k}/\varepsilon }$)

6) ${{\mathit{\boldsymbol{\tilde F}}}^k}$${{\mathit{\boldsymbol{\tilde F}}}^k}$${{\mathit{\boldsymbol{\tilde F}}}^k}$($r$, $c$)

7) ${{\mathit{\boldsymbol{\tilde F}}}^n}$←ZeroFilln(${{\mathit{\boldsymbol{\tilde F}}}^k}$) //对${{\mathit{\boldsymbol{\tilde F}}}^k}$进行补0操作

8) return $\mathit{\boldsymbol{\widetilde W}}$$IDFT$ (${{\mathit{\boldsymbol{\tilde F}}}^n}$)

根据FIP算法的步骤7)可知,利用ZeroFill方法对${{\mathit{\boldsymbol{\tilde F}}}_k}$填补(n-k)2个0,再利用IDFT函数来重构$\mathit{\boldsymbol{W}}$。然而该过程却由于忽略了(n-k)2个傅里叶系数向量产生了重构误差$RE$($\mathit{\boldsymbol{\widetilde W}}$),本文采用平方根误差度量$RE$($\mathit{\boldsymbol{\widetilde W}}$),即

$ RE\left( {\mathit{\boldsymbol{\tilde W}}} \right) = \sqrt {\sum\limits_{i = k + 1}^n {{{\left| {{F_{i - 1}}} \right|}^2}} } $ (9)

根据FIP算法的步骤3)—5)可知,前$k$×$k$个傅里叶系数是由实数部和虚数部构成的,相当于对每个系数添加两倍的拉普拉斯噪音(如步骤5)所示)。因此,FIP产生的噪音误差为

$ LE\left( {\mathit{\boldsymbol{\tilde W}}} \right) = {\rm{E}}\left( {\sqrt {\sum\limits_{i = 1}^k {\sum\limits_{i = 1}^k {4{{\left( {{\Delta _1}{\mathit{\boldsymbol{F}}^k}/\varepsilon } \right)}^2}} } } } \right) $

定理2 FIP发布方法产生的总体误差满足下列不等式$Erro{r_{{\rm{FIP}}}}\left( {\mathit{\boldsymbol{\widetilde W}}} \right) \le \sqrt {\sum\limits_{i = k + 1}^n {{{\left| {{F_{i-1}}} \right|}^2}} } + \frac{{2k{\Delta _1}{\mathit{\boldsymbol{F}}^k}}}{\varepsilon }$

证明:给定FIP方法,$\mathit{\boldsymbol{\widetilde W}}$=$FIP$($\mathit{\boldsymbol{W}}$),则

$ \begin{array}{*{20}{c}} {Error\left( {\mathit{\boldsymbol{\tilde W}}} \right) = {\rm{E}}{{\left\| {\mathit{\boldsymbol{\tilde W}} - \mathit{\boldsymbol{W}}} \right\|}_2} = {\rm{E}}\left( {\sqrt {\left\| {\mathit{\boldsymbol{\tilde W}} - \mathit{\boldsymbol{W}}} \right\|_2^2} } \right) \le }\\ {\sqrt {{\rm{E}}\left( {\left\| {\mathit{\boldsymbol{\tilde W}} - \mathit{\boldsymbol{W}}} \right\|_2^2} \right)} = \sqrt {{{\left( {RE\left( {\mathit{\boldsymbol{\tilde W}}} \right)} \right)}^2} + {{\left( {LE\left( {\mathit{\boldsymbol{\tilde W}}} \right)} \right)}^2}} \le }\\ {RE\left( {\mathit{\boldsymbol{\tilde W}}} \right) + LE\left( {\mathit{\boldsymbol{\tilde W}}} \right) = }\\ {\sqrt {\sum\limits_{i = k + 1}^n {{{\left| {{F_{i - 1}}} \right|}^2}} } + \sqrt {\sum\limits_{i = 1}^k {\sum\limits_{i = 1}^k {4{{\left( {{\Delta _1}{\mathit{\boldsymbol{F}}^k}/\varepsilon } \right)}^2}} } } = }\\ {\sqrt {\sum\limits_{i = k + 1}^n {{{\left| {{F_{i - 1}}} \right|}^2}} } + \frac{{2k{\Delta _1}{\mathit{\boldsymbol{F}}^k}}}{\varepsilon }} \end{array} $ (10)

根据定理2可知,为了度量FIP方法的总体误差,需要提前计算出${{\Delta _1}{\mathit{\boldsymbol{F}}^k}}$$k$值。对于FIP方法中的$k$值计算,本文采用启发式方法挑选合适的值。然而,由于傅里叶向量${\mathit{\boldsymbol{F}}^k} = \left( {{F_1}, {F_2}, \cdots, {F_k}} \right)$的频域数值通常包含实部和虚部两部分,致使无法利用式(2)估算出${{\Delta _1}{\mathit{\boldsymbol{F}}^k}}$,因此,根据${\Delta _2}\mathit{\boldsymbol{W}}$计算出${{\Delta _1}{\mathit{\boldsymbol{F}}^k}}$的上界值,如定理3所示。

定理3 给定人脸图像$\mathit{\boldsymbol{W}}{\rm{ = }}\left[{{a_1}, {a_2}, \cdots, {a_n}} \right]$及其相应的傅里叶系数所形成的向量${\mathit{\boldsymbol{F}}^k} = \left( {{F_1}, {F_2}, \cdots, {F_k}} \right)$,则${\Delta _1}{\mathit{\boldsymbol{F}}^k} \le \sqrt K {\Delta _2}\mathit{\boldsymbol{W}}$成立。

证明:已知${\Delta _2}\mathit{\boldsymbol{W = }}\;\mathop {{\rm{max}}}\limits_{W, W'} {\left\| {\mathit{\boldsymbol{W}}{\rm{-}}\mathit{\boldsymbol{W'}}} \right\|_2} = \mathop {{\rm{max}}}\limits_{{a_i} \in cols\left( \mathit{\boldsymbol{W}} \right)} \left\| {{a_i}} \right\|$$\mathit{\boldsymbol{W}}$${\mathit{\boldsymbol{W'}}}$互为近邻,$clos$($\mathit{\boldsymbol{W}}$)表示$\mathit{\boldsymbol{W}}$的列向量集合。此时${\Delta _2}\mathit{\boldsymbol{W}}$表示$\mathit{\boldsymbol{W}}$列的最大L2范数。

已知${\mathit{\boldsymbol{F}}^k} = \left( {{F_1}, {F_2}, \cdots, {F_k}} \right)$,设${\left\| {{\mathit{\boldsymbol{F}}^k}} \right\|_p} = {\left( {\sum\limits_{i = 1}^k {{{\left| {{F_i}} \right|}^p}} } \right)^{\frac{1}{p}}}$。任意给定两个参数$p$, $q$ ($q$>1),且满足$\frac{1}{p} + \frac{1}{q} = 1$。给定$\mathit{\boldsymbol{\alpha }} = {\left( {{\mathit{\boldsymbol{\alpha }}_1}, {\mathit{\boldsymbol{\alpha }}_2}, \cdots, {\mathit{\boldsymbol{\alpha }}_n}} \right)^{\rm{T}}}, \;\mathit{\boldsymbol{\beta = }}{\left( {{\mathit{\boldsymbol{\beta }}_1}, {\mathit{\boldsymbol{\beta }}_2}, \cdots {\mathit{\boldsymbol{\beta }}_n}} \right)^{\rm{T}}}$任意两个向量矩阵,根据赫尔德不等式可知$\mathit{\boldsymbol{\alpha }}$$\mathit{\boldsymbol{\beta }}$满足不等式

$ \sum\limits_{i = 1}^n {\left| {{\mathit{\boldsymbol{\alpha }}_i}} \right|\left| {{\mathit{\boldsymbol{\beta }}_i}} \right|} \le {\left( {\sum\limits_{i = 1}^n {{{\left| {{\mathit{\boldsymbol{\alpha }}_i}} \right|}^p}} } \right)^{\frac{1}{p}}}{\left( {\sum\limits_{i = 1}^n {{{\left| {{\mathit{\boldsymbol{\beta }}_i}} \right|}^q}} } \right)^{\frac{1}{q}}} $ (11)

根据上述不等式(11)可知,当分别取$p$=$q$=2,设${\mathit{\boldsymbol{\alpha }}_1} = \; \cdots = {\mathit{\boldsymbol{\alpha }}_k} = {\left[{1, 1, \cdots, 1} \right]^{\rm{T}}}$$\mathit{\boldsymbol{\beta }} = {\mathit{\boldsymbol{F}}^k} = {\left[{{F_1}, {F_2}, \cdots {F_k}} \right]^{\rm{T}}}$由赫尔德不等式可得$\sum\limits_{i = 1}^k {\left| {{F_i}} \right| \le \sqrt k {{\left( {\sum\limits_{i = 1}^k {{{\left| {{F_i}} \right|}^2}} } \right)}^{\frac{1}{2}}}} $,即${\Delta _1}{\mathit{\boldsymbol{F}}^k} \le \sqrt k {\Delta _2}{\mathit{\boldsymbol{F}}^k}$。而${\mathit{\boldsymbol{F}}^k}$忽略了最后$n$$k$个向量矩阵的傅里叶系数,所以${\Delta _2}{\mathit{\boldsymbol{F}}^k} \le {\Delta _2}\mathit{\boldsymbol{W}}$,即得出${\Delta _1}{\mathit{\boldsymbol{F}}^k} \le \sqrt k {\Delta _2}\mathit{\boldsymbol{W}}$

由式(10)可知,当${{\Delta _1}{\mathit{\boldsymbol{F}}^k}}$$k$值确定后,即可计算出$\mathit{\boldsymbol{\widetilde W}}$的发布误差。然而,$k$值的选择至关重要。$k$值越大,$RE$($\mathit{\boldsymbol{\widetilde W}}$)越小,而$LE$($\mathit{\boldsymbol{\widetilde W}}$)却很大;相反,$k$值越小,$LE$($\mathit{\boldsymbol{\widetilde W}}$)越小,而$RE$($\mathit{\boldsymbol{\widetilde W}}$)却很大。这两种情况均使所发布人脸图像的可用性较差。因此,如何选择合适的$k$值来均衡这两种误差是接下来要解决的问题。然而,直接基于傅里叶系数空间选择$k$值是数据相关的,该操作需要满足$\varepsilon $-差分隐私。因此,本文基于指数机制提出一种$k$值选择方法EMK,具体步骤如下:

输入:人脸图像$\mathit{\boldsymbol{W}}$,隐私预算$\varepsilon $

输出:满足差分隐私的人脸图像$\mathit{\boldsymbol{\widetilde W}}$

1) ${\mathit{\boldsymbol{F}}^n} = DFT\left( \mathit{\boldsymbol{W}} \right)$

2) $\forall 1 \le k \le n$,计算每个打分函数$-U\left( {\mathit{\boldsymbol{W}}, \mathit{k}} \right)$,其中$U\left( {\mathit{\boldsymbol{W}}, \mathit{k}} \right) = \sqrt {\sum\limits_{i = k + 1}^n {{{\left| {{F_{i-1}}} \right|}^2}} } + \frac{{2k{\Delta _1}{\mathit{\boldsymbol{F}}^k}}}{\varepsilon }$

3) 以概率$\mathit{Pr}\left( k \right)$${\rm{exp}}\left( {-\frac{{\varepsilon U\left( {\mathit{\boldsymbol{W}}{\rm{, }}\mathit{k}} \right)}}{{2{\Delta _1}U}}} \right)$选择一个合适的$k$

4) for $r$ from 1 to $k$//$r$是矩阵的行

5) for $c$ from 1 to $k$//$c$是矩阵的列

6) ${{\mathit{\boldsymbol{\tilde F}}}^k}\left({r, c} \right)$${\mathit{\boldsymbol{F}}^k}\left( {r, c} \right) = 2lap\left( {{\Delta _1}{\mathit{\boldsymbol{F}}^k}/\varepsilon } \right)$

7) ${\mathit{\boldsymbol{\tilde F}}}$${{\mathit{\boldsymbol{\tilde F}}}^k} \cup {{\mathit{\boldsymbol{\tilde F}}}^k}\left( {r, c} \right)$

8) ${{\mathit{\boldsymbol{\tilde F}}}^n}$←ZeroFilln(${{\mathit{\boldsymbol{\tilde F}}}^k}$)//对${{\mathit{\boldsymbol{\tilde F}}}^k}$进行补0操作

9) return $\mathit{\boldsymbol{\widetilde W}}$$IDFT$ (${{\mathit{\boldsymbol{\tilde F}}}^n}$)

EMK方法首先在${\mathit{\boldsymbol{F}}^n}$向量中计算每个打分函数值(如步骤2)),然后采用指数机制以概率Pr($k$)挑选合适的$k$值(如步骤3)),针对所挑选的$k$值,采用拉普拉斯机制对每个傅里叶系数进行噪音扰动(如步骤4)—7)),最后是ZeroFill补零与IDFT操作,进而获得$\mathit{\boldsymbol{\widetilde W}}$

EMK方法利用指数机制实现$k$值的挑选。然而指数机制的关键之处是设计高效的打分函数。打分函数的优劣直接决定着所挑选$k$值的合理性。合理的$k$值能够均衡$RE$($\mathit{\boldsymbol{\widetilde W}}$)与$LE$($\mathit{\boldsymbol{\widetilde W}}$)。本文利用定理2中的总体误差来设计打分函数${U\left( {\mathit{\boldsymbol{W}}{\rm{, }}\mathit{k}} \right)}$${U\left( {\mathit{\boldsymbol{W}}{\rm{, }}\mathit{k}} \right)}$越大说明总体误差越小。具体公式为

$ U\left( {\mathit{\boldsymbol{W}},k} \right) = \sqrt {\sum\limits_{i = k + 1}^n {{{\left| {{F_{i - 1}}} \right|}^2}} } + \frac{{2k{\Delta _1}{\mathit{\boldsymbol{F}}^k}}}{\varepsilon } $ (12)

把式(12)代入式(4),可以计算出选择$k$值的概率,如式(13)所示。

由式(13)与式(4)可知,若要计算出每个$k$值的抽样概率,还必须知道打分函数${U\left( {\mathit{\boldsymbol{W}}{\rm{, }}\mathit{k}} \right)}$的全局敏感度是多少,即${\Delta _1}U$

$ \begin{array}{*{20}{c}} {\mathit{Pr}\left( k \right) \propto \exp }\\ {\left( { - \varepsilon \left( {\sqrt {\sum\limits_{i = k + 1}^n {{{\left| {{F_{i - 1}}} \right|}^2}} } + \frac{{2k{\Delta _1}{\mathit{\boldsymbol{F}}^k}}}{\varepsilon }} \right)/2{\Delta _1}U} \right)} \end{array} $ (13)

为了度量${\Delta _1}U$,本文结合定理2给出定理4。

定理4 ${\Delta _1}U = \left( {1 + \sqrt k } \right){\Delta _1}\mathit{\boldsymbol{W}}$

证明:由$U\left( {\mathit{\boldsymbol{W}}{\rm{, }}\mathit{k}} \right) = \sqrt {\sum\limits_{i = k + 1}^n {{{\left| {{F_{i-1}}} \right|}^2}} } + \frac{{2k{\Delta _1}{\mathit{\boldsymbol{F}}^k}}}{\varepsilon }$可知,${\Delta_1}U$由两部分组成:$\sqrt {\sum\limits_{i = k + 1}^n {{{\left| {{F_{i - 1}}} \right|}^2}} } $的敏感度${\Delta _1}U$$\frac{{2k{\Delta _1}{\mathit{\boldsymbol{F}}^k}}}{\varepsilon }$的敏感度${\Delta _1}{U_2} = {\Delta _1}U = {\Delta _1}{U_1} + {\Delta _1}{U_2}$

${\Delta _1}{U_1} = {\Delta _1}\left( {\sqrt {\sum\limits_{i = k + 1}^n {{{\left| {{F_{i-1}}} \right|}^2}} } } \right) \le {\Delta _1}\left( {{{\left\| {{\mathit{\boldsymbol{F}}^n}} \right\|}_2}} \right)$成立。

给定$\mathit{\boldsymbol{W}}$及其近邻${\mathit{\boldsymbol{W'}}}$,由傅里叶变换$DFT$可知,${\mathit{\boldsymbol{F}}^n} = DFT\left( \mathit{\boldsymbol{W}} \right)$${{\mathit{\boldsymbol{F'}}}^n} = DFT\left( {\mathit{\boldsymbol{W'}}} \right)$。根据L2范式在DFT变换下具有不变性,则${\left\| {{\mathit{\boldsymbol{F}}^n}} \right\|_2} = {\left\| \mathit{\boldsymbol{W}} \right\|_2}$${\left\| {{{\mathit{\boldsymbol{F'}}}^n}} \right\|_2} = {\left\| {\mathit{\boldsymbol{W'}}} \right\|_2}$成立。

$ \begin{array}{*{20}{c}} {{\Delta _1}\left( {{{\left\| {{\mathit{\boldsymbol{F}}^n}} \right\|}_2}} \right) = \max \left( {\left| {{{\left\| {{\mathit{\boldsymbol{F}}^n}} \right\|}_2} - {{\left\| {{{\mathit{\boldsymbol{F'}}}^n}} \right\|}_2}} \right|} \right) = }\\ {\max \left( {\left| {{{\left\| {{\mathit{\boldsymbol{W}}^n}} \right\|}_2} - {{\left\| {{{\mathit{\boldsymbol{W'}}}^n}} \right\|}_2}} \right|} \right) \le }\\ {\max \left( {{{\left\| {\mathit{\boldsymbol{W}} - \mathit{\boldsymbol{W'}}} \right\|}_2}} \right) \le }\\ {\max \left( {{{\left\| {\mathit{\boldsymbol{W}} - \mathit{\boldsymbol{W'}}} \right\|}_1}} \right) \le {\Delta _1}\mathit{\boldsymbol{W}}} \end{array} $ (14)

进而可以推理出${\Delta _1}{U_1} \le {\Delta _1}\mathit{\boldsymbol{W}}$成立。

根据定理3与不等式(14)可以推理出下列不等式成立

$ {\Delta _1}{U_2} = {\Delta _1}{\mathit{\boldsymbol{F}}^k} \le \sqrt k {\Delta _2}\mathit{\boldsymbol{W}} \le \sqrt k {\Delta _1}\mathit{\boldsymbol{W}} $ (15)

由式(14)与式(15)可以推理出不等式${\Delta _1}U = {\Delta _1}{U_1} + {\Delta _1}{U_2} \le \left( {1 + \sqrt k } \right){\Delta _1}\mathit{\boldsymbol{W}}$成立。

则定理4成立。

因此,当打分函数U(W, k)全局敏感性确定之后,即可以采用指数机制在整个傅里叶系数空间中挑选使整体误差最小的$k$值。

根据EMK算法可知,该算法是在整个傅里叶系数空间中挑选合适$k$值。由EMK算法的步骤2)与步骤3)所示,当傅里叶系数空间非常大时,需要不断地分割隐私预算$\varepsilon $来挑选合适的${U\left( {\mathit{\boldsymbol{W}}{\rm{, }}\mathit{k}} \right)}$。大的系数空间直接造成$\varepsilon $不断被划分,进而使得指数机制挑选$k$值越来越不准确。据观察可知,EMK算法忽略了真实人脸图像的傅里叶系数之间的关联性,以及傅里叶变换的共轭对称性。

根据离散实数傅里叶变换满足共轭对称性,则可以推理出该变换的输出同时满足半冗余性。即$DF{T^{{\rm{real}}}}\left( \mathit{\boldsymbol{W}} \right) = \left( {{F_0}, \cdots, {F_q}} \right)$,其中,$n$为偶数时,$q$=($n$+1)/2;$n$为奇数时,或者$q$=$n$/2 + 1。基于此,本文提出了一种增强的EMK算法BEMK算法,具体步骤为:

输入:人脸图像$\mathit{\boldsymbol{W}}$,隐私预算$\varepsilon $

输出:满足差分隐私的人脸图像$\mathit{\boldsymbol{\widetilde W}}$

1) ${\mathit{\boldsymbol{F}}^q} = DF{T^{{\rm{real}}}}\left( \mathit{\boldsymbol{W}} \right)$//对原始图像进行傅里叶变换后去掉一半冗余

2) $q = \frac{n}{2} + 1$//$q$$\mathit{\boldsymbol{F}}$的行列数值

3) ${\mathit{\boldsymbol{F}}^k}$${\mathit{\boldsymbol{F}}^q}$$\forall 1 \le k \le q$//取前$k$×$k$个系数

4) for $k$ from 1 to $q$

5) 计算$U\left( {\mathit{\boldsymbol{W}}{\rm{, }}\mathit{k}} \right) = \sqrt {\sum\limits_{i = k + 1}^q {2{{\left| {{F_{i-1}}} \right|}^2}} } + \frac{{2k{\Delta _1}{F^k}}}{\varepsilon }$

6) 以概率$\mathit{Pr}\left( k \right)$${\rm{exp}}\left( {-\frac{{\varepsilon U\left( {\mathit{\boldsymbol{W}}{\rm{, }}\mathit{k}} \right)}}{{2{\mathit{\Delta }_1}U}}} \right)$选择一个合适的$k$

7) for $r$ from 1 to $k$//$r$是矩阵的行

8) for $c$ from 1 to $k$ //c是矩阵的列

9) ${{\mathit{\boldsymbol{\tilde F}}}^k}\left( {r, c} \right)$${\mathit{\boldsymbol{F}}^k}\left( {r, c} \right) + 2lap\left( {{\Delta _1}{\mathit{\boldsymbol{F}}^k}/\varepsilon } \right)$

10) ${{\mathit{\boldsymbol{\tilde F}}}^k}$${{\mathit{\boldsymbol{\tilde F}}}^k}$${{\mathit{\boldsymbol{\tilde F}}}^k}\left( {r, c} \right)$

11) ${{\mathit{\boldsymbol{\tilde F}}}^n}$←ZeroFilln(${{\mathit{\boldsymbol{\tilde F}}}^k}$) //对${{\mathit{\boldsymbol{\tilde F}}}^k}$进行补0操作

12) return $\mathit{\boldsymbol{\widetilde W}}$$IDFT$ (${{\mathit{\boldsymbol{\tilde F}}}^n}$)

BEMK算法首先利用${DF{T^{{\rm{real}}}}}$操作对原始图像W进行变换(如步骤1)2)所示)。步骤3)—6),与EMK算法一致,也是挑选合适的$k$值,只是挑选$k$值的空间变成了[1, $q$]。步骤7)—10)是对所挑选的傅里叶系数添加拉普拉斯噪音。步骤11)与步骤12)分别利用ZeroFill补零与IDFT操作获得$\mathit{\boldsymbol{\widetilde W}}$

定理5 LAP算法、FIP算法、EMK以及BEMK算法满足$\varepsilon $-差分隐私。

证明:根据定理1可知,LAP算法与FIP算法满足$\varepsilon $-差分隐私。接下来证明EMK与BEMK算法满足$\varepsilon $-差分隐私。

假设EMK算法步骤3)所需要的隐私预算为$\varepsilon $1,则根据指数机制(如式(4)所示)可知每个$k$值被选择的概率为

$ \mathit{Pr}\left( k \right) = \frac{{\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W}},k} \right)}}{{2{\Delta _1}U}}} \right)}}{{\sum\limits_{k' \in O} {\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W}},k'} \right)}}{{2{\Delta _1}U}}} \right)} }} $ (16)

给定$\mathit{\boldsymbol{W}}$及其近邻${\mathit{\boldsymbol{W'}}}$,对于任意$k$值($k$$O$),根据式(16)可得

$ \begin{array}{*{20}{c}} {\frac{{\mathit{Pr}\left( {{E^{{\rm{EMK}}}}\left( {\mathit{\boldsymbol{W}},k} \right)} \right)}}{{\mathit{Pr}\left( {{E^{{\rm{EMK}}}}\left( {\mathit{\boldsymbol{W'}},k} \right)} \right)}} = \frac{{\frac{{\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W}},k} \right)}}{{2{\Delta _1}U}}} \right)}}{{\sum\limits_{k' \in O} {\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W}},k'} \right)}}{{2{\Delta _1}U}}} \right)} }}}}{{\frac{{\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W'}},k} \right)}}{{2{\Delta _1}U}}} \right)}}{{\sum\limits_{k' \in O} {\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W'}},k'} \right)}}{{2{\Delta _1}U}}} \right)} }}}} = }\\ {\left( {\frac{{\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W}},k} \right)}}{{2{\Delta _1}U}}} \right)}}{{\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W'}},k} \right)}}{{2{\Delta _1}U}}} \right)}}} \right) \times \left( {\frac{{\sum\limits_{k' \in O} {\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W'}},k'} \right)}}{{2{\Delta _1}U}}} \right)} }}{{\sum\limits_{k' \in O} {\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W}},k'} \right)}}{{2{\Delta _1}U}}} \right)} }}} \right) \le }\\ {\exp \left( {\frac{{{\varepsilon _1}}}{2}} \right) \times \left( {\frac{{\sum\limits_{k' \in O} {\exp \left( {\frac{{{\varepsilon _1}}}{2}} \right)} \times \exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W}},k'} \right)}}{{2{\Delta _1}U}}} \right)}}{{\sum\limits_{k' \in O} {\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W}},k'} \right)}}{{2{\Delta _1}U}}} \right)} }}} \right) \le }\\ {\exp \left( {\frac{{{\varepsilon _1}}}{2}} \right) \times \exp \left( {\frac{{{\varepsilon _1}}}{2}} \right) \times \left( {\frac{{\sum\limits_{k' \in O} {\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W}},k'} \right)}}{{2{\Delta _1}U}}} \right)} }}{{\sum\limits_{k' \in O} {\exp \left( { - \frac{{{\varepsilon _1}U\left( {\mathit{\boldsymbol{W}},k'} \right)}}{{2{\Delta _1}U}}} \right)} }}} \right) = }\\ {\exp \left( {{\varepsilon _1}} \right)} \end{array} $

式中,${E^{{\rm{EML}}}}\left( {} \right)$表示EMK算法,假设EMK算法步骤7)—10)所需要的隐私预算为$\varepsilon $2,根据定理1可知,步骤7)—10)满足$\varepsilon $2-差分隐私。

因此,根据定理6可知,EMK满足$\varepsilon $-差分隐私,其中$\varepsilon $ =$\varepsilon $1 + $\varepsilon $2

同理,根据上述证明过程也可以推理出BEMK算法满足$\varepsilon $-差分隐私。

定理6[18] 设$\mathit{\boldsymbol{D}}$为隐含个人隐私的数据集,${A_1}$, ${A_2}$, …, ${A_n}$$n$个随机算法,且${A_i}$满足${\varepsilon _i}$-差分隐私。{${A_1}$, ${A_2}$, …, ${A_n}$}在$\mathit{\boldsymbol{D}}$上操作的顺序组合满足$\varepsilon $-差分隐私,且$\varepsilon = \sum\limits_{i = 1}^n {{\varepsilon _i}} $

4 实验与结果分析

为了研究算法的可用性,在Lena的灰度人脸图像(如图 1所示)上进行实验。

图 1 Lena原始图像
Fig. 1 The original image of Lena

以Lena的原始图像作为人脸图像分别对其进行4种算法进行比较,4种算法的发布结果如图 2所示。图 2(a) LAP图像是直接利用拉普拉斯噪音处理的结果;图 2 (b)FIP图像在直接添加噪声的基础上对其进行傅里叶变换的处理结果;图 2 (c)EMK图像是在傅里叶干扰算法的基础上采用指数机制选取所添加噪声数值的处理结果;图 2 (d)BEMK考虑到傅里叶变换的共轭对称性,在添加噪声前,对其减少一半的图像冗余,之后再采用指数机制添加拉普拉斯噪声。由图像所显示的效果可以看出,其中EMK与BEMK两种算法的效果更好,为了验证算法的有效性与可用性,本文基于真实的人脸库,采用SVM+PCA方法来检验这4种方法。

图 2 加噪图像
Fig. 2 Adding noise images of Lena
((a) LAP; (b) FIP; (c) EMK; (d) BEMK)

4.1 人脸数据库

人脸库主要包括CMU人脸库(http://www.cs.cmu.edu/afs/cs.cmu.edu/user/mitchell/ftp/faces.html)、ORL人脸库(http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html)、Yale人脸库(http://cvc.cs.yale.edu/cvc/projects/yalefaces/yalefaces.html)和Yale人脸库B(http://cvc.cs.yale.edu/cvc/projects/yalefacesB/yalefacesB.html)。其中,CMU人脸图像数据集有20人,每人包括32幅图像,在本文所使用的图像大小为128×128像素。将前15幅图像作为训练集,后15幅图像作为测试集;ORL人脸库中一共有40个人,每个人包括10幅表情细微变换的图像,图像尺寸大小为92×112像素。将每个人前5幅图像作为训练集,后5幅图像作为测试集;Yale人脸库中共有15人,每人包括10幅图像,其中含有微小姿势变化的图像,大小为320×243像素。将每人前5幅图像作为训练集,其余图像作为测试集;Yale人脸库B中共有30个人,每人包含30幅具有拍照光线强度不一的图像,尺寸为192×168像素。将每个人前15幅图像作为训练集,后15幅图像作为测试集进行实验。

4.2 实验分析

实验采用人脸识别的方法是SVM+PCA,主要有以下几个步骤,首先读取训练数据集,采用主成分分析法(PCA)降维并去除数据之间的相关性,其次采用SVM训练器对数据集进行训练,接着读取测试数据并对其降维,最后采用SVM所产生的分类函数对测试数据集进行分类,并从准确率、召回率、F1-Score来验证分类的正确率。隐私预算$\varepsilon $分别取0.1、0.5、0.9、1.4。具体结果如表 1表 3所示。

表 1 准确率
Table 1 Precision

下载CSV
$\varepsilon $ 方法 CMU ORL Yale YaleB
LAP 0.07 0.02 0.08 0.04
FIP 0.07 0.03 0.08 0.04
0.1 EMK 0.23 0.34 0.37 0.25
BEMK 0.58 0.47 0.43 0.32
Non-Privacy 0.97 0.88 0.96 0.83
LAP 0.06 0.03 0.07 0.03
FIP 0.26 0.11 0.23 0.16
0.5 EMK 0.48 0.41 0.33 0.28
BEMK 0.68 0.73 0.45 0.56
Non-Privacy 0.97 0.88 0.96 0.83
LAP 0.03 0.04 0.07 0.04
FIP 0.64 0.12 0.60 0.44
0.9 EMK 0.33 0.58 0.65 0.38
BEMK 0.81 0.73 0.56 0.64
Non-Privacy 0.97 0.88 0.96 0.83
LAP 0.05 0.05 0.05 0.03
FIP 0.85 0.33 0.84 0.66
1.4 EMK 0.60 0.64 0.64 0.54
BEMK 0.88 0.80 0.70 0.71
Non-Privacy 0.97 0.88 0.96 0.83
注:加粗字体表示BEMK方法相对其他3种方法比较接近Non-Privacy方法。

表 2 召回率
Table 2 Recall

下载CSV
$\varepsilon $ 方法 CMU ORL Yale YaleB
LAP 0.34 0.75 0.90 0.87
FIP 0.71 0.80 0.49 0.68
0.1 EMK 0.65 0.84 0.58 0.57
BEMK 0.77 0.71 0.72 0.51
Non-Privacy 0.97 0.91 0.97 0.91
LAP 0.51 0.77 0.74 0.64
FIP 0.64 0.85 0.57 0.42
0.5 EMK 0.75 0.71 0.76 0.50
BEMK 0.79 0.80 0.84 0.70
Non-Privacy 0.97 0.91 0.97 0.91
LAP 0.51 0.77 0.61 0.90
FIP 0.72 0.72 0.71 0.58
0.9 EMK 0.60 0.80 0.83 0.50
BEMK 0.85 0.87 0.86 0.72
Non-Privacy 0.97 0.91 0.97 0.91
FIP 0.90 0.76 0.92 0.77
1.4 EMK 0.78 0.79 0.76 0.70
BEMK 0.90 0.88 0.80 0.84
Non-Privacy 0.97 0.91 0.97 0.91
注:加粗字体表示BEMK方法相对其他3种方法比较接近Non-Privacy方法。

表 3 F1-分数($\varepsilon $ = 0.1)
Table 3 F1-Score ($\varepsilon $= 0.1)

下载CSV
$\varepsilon $ 方法 CMU ORL Yale YaleB
LAP 0.12 0.04 0.15 0.08
FIP 0.13 0.06 0.14 0.08
0.1 EMK 0.34 0.48 0.45 0.35
BEMK 0.66 0.57 0.54 0.39
Non-Privacy 0.97 0.90 0.96 0.87
LAP 0.11 0.06 0.13 0.06
FIP 0.37 0.19 0.33 0.23
0.5 EMK 0.59 0.52 0.46 0.36
BEMK 0.72 0.76 0.59 0.62
Non-Privacy 0.97 0.90 0.96 0.87
LAP 0.06 0.08 0.13 0.08
FIP 0.68 0.21 0.65 0.50
0.9 EMK 0.43 0.67 0.73 0.43
BEMK 0.83 0.79 0.68 0.68
Non-Privacy 0.97 0.90 0.96 0.87
LAP 0.09 0.09 0.09 0.06
FIP 0.89 0.46 0.88 0.68
1.4 EMK 0.68 0.71 0.70 0.61
BEMK 0.89 0.84 0.75 0.77
Non-Privacy 0.97 0.90 0.96 0.87
注:加粗字体表示BEMK方法相对其他3种方法比较接近Non-Privacy方法。

表 1表 3可以看出,随着$\varepsilon $从0.1变化到1.4,准确率、召回率以及F1-Score的值均在增加,其原因是拉普拉斯噪音误差的大小与隐私预算$\varepsilon $成反比。当$\varepsilon $=0.1时,BEMK算法在CMU数据集的准确率是LAP的8倍多,是FIP的8倍多,是EMK的2倍多,在ORL数据集上是LAP的23倍多;BEMK算法在CMU上的召回率是LAP的2倍多,在ORL数据集上是LAP的1倍多;BEMK算法在CMU数据集上的F1-Score是LAP的5倍多,在ORL上是LAP的14倍多。此外,当$\varepsilon $分别为0.5、0.9、1.4时BEMK与EMK同样优于LAP和FIP算法。

从整体上来看,CMU数据集的识别率最高,ORL数据集的识别率相对比较低。但是,对比4种算法,其中增强傅里叶干扰算法BEMK和先傅里叶再矩阵分解算法EMK两种算法所产生的正确率相对其他两种算法的正确率较高。在比较不同的隐私预算,4种方法所得到的正确率中,同样是BEMK和EMK所产生的实验结果相对稳定,而BEMK算法在4种算法中正确性最好。

5 结论

在提出的人脸图像发布算法中,采用离散傅里叶技术对人脸图像进行变换,利用拉普拉斯机制与指数机制对变换过程进行扰动,较好地保持了图像的可用性;相对于直接在人脸图像矩阵中添加拉普拉斯噪音,FIP、EMK、BEMK算法较好地对图像进行压缩,相对减少了噪音的影响。相对于LAP与FIP算法,EMK与BEMK算法利用指数机制比较合理地挑选出傅里叶系数的个数$k$,进而来均衡重构误差与拉普拉斯误差。特别是BEMK算法,利用离散实数傅里叶变换的共轭性对$k$值的候选空间进行充分压缩,进而使得最终的图像发布精度比较高,并获得较好的实验结果。

由于人脸图像与其图像特征密切关联,接下来将研究如何在满足差分隐私的情况下获取人脸特征。并根据这些隐私人脸特征重构人脸图像,并具有较好的分类特性。

参考文献

  • [1] Newton E M, Sweeney L, Malin B. Preserving privacy by de-identifying face images[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(2): 232–243. [DOI:10.1109/TKDE.2005.32]
  • [2] Gross R, Sweeney L, Cohn J F, et al. Model-based de-identification of facial images[C]//2008 American Medical Informatics Association Annual Symposium. Washington, DC, USA: AMIA, 2008: 38-47.
  • [3] Gross R, Acquisti A. Information revelation and privacy in online social networks[C]//Proceedings of 2005 ACM Workshop on Privacy in the Electronic Society. Alexandria, VA, USA: ACM, 2005: 71-80. [DOI:10.1145/1102199.1102214]
  • [4] Sadeghi A R, Schneider T, Wehrenberg I. Efficient privacy-preserving face recognition[C]//Proceedings of the 12th International Conference on Information, Security and Cryptology. Seoul, Korea: Springer, 2009: 507. [DOI:10.1007/978-3-642-14423-3_16]
  • [5] Xu J, Zhang Z J, Xiao X K, et al. Differentially private histogram publication[J]. The VLDB Journal, 2013, 22(6): 797–822. [DOI:10.1007/s00778-013-0309-y]
  • [6] Qardaji W, Yang W N, Li N H. Differentially private grids for geospatial data[C]//Proceedings of the 29th International Conference on Data Engineering. Brisbane, Australia: IEEE, 2013: 32-33. [DOI:10.1109/ICDE.2013.6544872]
  • [7] Zhang J, Cormode G, Procopiuc C M, et al. Private release of graph statistics using ladder functions[C]//Proceedings of 2015 ACM SIGMOD International Conference on Management of Data. Melbourne, Victoria, Australia: ACM, 2015: 731-745. [DOI:10.1145/2723372.2737785]
  • [8] Chen Y, Machanavajjhala A, Hay M, et al. PeGaSus: data-adaptive differentially private stream processing[C]//Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas, TX, USA: ACM, 2017: 1375-1388. [DOI:10.1145/3133956.3134102]
  • [9] Rastogi V, Nath S. Differentially private aggregation of distributed time-series with transformation and encryption[C]//Proceedings of 2010 ACM SIGMOD International Conference on Management of Data. Indianapolis, Indiana, USA: ACM, 2010: 735-746. [DOI:10.1145/1807167.1807247]
  • [10] Su S, Tang P, Cheng X, et al. Differentially private multi-party high-dimensional data publishing[C]//Proceedings of the 32nd International Conference on Data Engineering. Helsinki, Finland: IEEE, 2016: 205-216. [DOI:10.1109/ICDE.2016.7498241]
  • [11] Xiao X K, Wang G Z, Gehrke J. Differential privacy via wavelet transforms[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(8): 1200–1214. [DOI:10.1109/TKDE.2010.247]
  • [12] Li C, Miklau G, Hay M, et al. The matrix mechanism:optimizing linear counting queries under differential privacy[J]. The VLDB Journal, 2015, 24(6): 757–781. [DOI:10.1007/s00778-015-0398-x]
  • [13] Yuan G Z, Zhang Z J, Winslett M, et al. Optimizing batch linear queries under exact and approximate differential privacy[J]. ACM Transactions on Database Systems, 2015, 40(2): #11. [DOI:10.1145/2699501]
  • [14] Dwork C, McSherry F, Nissim K, et al. Calibrating noise to sensitivity in private data analysis[C]//Proceedings of the 3rd Theory of Cryptography Conference. New York, USA: Springer, 2006: 363-385. [DOI:10.1007/11681878_14]
  • [15] Dwork C. Differential privacy[C]//Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Venice, Italy: Springer, 2006: 1-12. [DOI:10.1007/11787006_1]
  • [16] Zhang X J, Shao C, Meng X F. Accurate histogram release under differential privacy[J]. Journal of Computer Research and Development, 2016, 53(5): 1106–1117. [张啸剑, 邵超, 孟小峰. 差分隐私下一种精确直方图发布方法[J]. 计算机研究与发展, 2016, 53(5): 1106–1117. ] [DOI:10.7544/issn1000-1239.2016.20150304]
  • [17] Dwork C, McSherry F, Nissim K, et al. Calibrating noise to sensitivity in private data analysis[C]//Proceedings of the 3rd Theory of Cryptography Conference. New York, NY, USA: Springer, 2006: 268-284. [DOI:10.1007/11681878_14]
  • [18] McSherry F, Talwar K. Mechanism design via differential privacy[C]//The 48th Annual IEEE Symposium on Foundations of Computer Science. Providence, RI, USA: IEEE, 2007: 94-103. [DOI:10.1109/FOCS.2007.41]