加密文档排序中保序加密算法的最优化选取

张久岭，黄道超，沈时军

（国家计算机网络应急技术处理协调中心，北京 100029）

传统的电子邮箱服务、远程数据库服务等需要把包含用户个人隐私的数据存储在服务提供商的服务器上。云计算和云存储的快速发展降低了用户数据信息管理成本及存储资源与计算资源的消耗，而手持移动终端的愈加频繁使用使得更多用户数据存储在云端，这样在客观上造成了数据存储和计算资源的集中化。然而，随着越来越多的用户数据存储在远程服务器，对于服务提供商来说用户的数据是完全可见的。此外，服务提供商还可以对用户数据进行统计分析等操作，如果数据在不同的服务提供商间存在交互流动，则服务商可合并获取用户信息，会进一步侵犯用户隐私。因此，对用户隐私数据的保护越来越受到人们的关注，用户的数据隐私保护是一个迫切需要解决的问题。虽然可以通过签订服务协议或通过多方计算等方式避免服务提供商滥用用户数据，但是无法从根本上保护用户隐私。为有效地保护用户的隐私，对用户信息进行加密处理是一种解决方案。用户数据多以文档形式存储在服务提供商侧，因此对用户以文档形式进行信息加密并存储在远程服务器是一种可行且有效的数据保护方案。

然而，当存储在远程服务器的用户加密数据形成规模之后，用户在进行查询以满足其信息需求时，需把加密文档全部下载回用户终端，这将带来巨大的通信开销，因此难以实现。如何对密文形式的数据进行检索成为亟待解决的问题。Song等［1］在2000年开创性地提出了一种实用的且可以搜索的对称加密算法，在进行加密关键词搜索时，需进行线性遍历，由于加密过程中一次一密，具有较强的抗统计分析能力。Boneh等［2］在2004年提出了一种可搜索公钥加密算法。Park等［3］提出了基于布隆过滤的多关键词安全搜索算法，布隆过滤在小规模数据集情况下可以进行有效检索，但在大规模数据集下，该算法检索时所需的布隆过滤器长度非常大。以上算法可以有效地从加密数据中检索到用户所需的文档。然而，随着数据集规模的增大，检索到可能相关的文档集合的规模也逐渐增大。例如，很多私人信息邮件被存储在某不可靠的邮件提供商服务器上，当进行检索时，即有对较多返回结果进行排序的需求。如果将检索到的文档信息无差别返回给用户，一方面将带来巨大的通信、计算及存储开销，另一方面用户也无力消费大量的原始明文数据。因此，在不泄露用户信息的情况下，对检索到的加密文档进行相关性排序并给出最符合用户信息需求的文档是需要进一步研究和解决的问题。

在一般明文信息检索中，为对结果根据查询的相关性进行排序，一般利用到词频、关键词权重等关键信息。在加密信息检索情况下，为有效依据文档中的词频、关键词权重等加密信息对加密文档进行相关性排序，Swaminathan等［4］提出了基于保序加密算法的加密文档排序算法，该算法中文档的词频被保序加密算法加密，在需要进行排序时，把加密形式的词频相加给出相关度并以此进行排序。Wang等［5］提出了用保序加密算法对关键词权重进行加密，并对加密的权重进行加法运算得到查询与加密文档相似度的算法进行排序。Lu等［6］提出了将其类似的算法推广应用于多媒体检索中并对多媒体信息检索结果进行排序。Phong等［7］提出了基于保序加密算法的隐私保护深度学习系统，可以在不把个人数据透露给远程服务器的基础上，实现基于神经网络的深度学习。因此，有必要研究加密算法在加密文档排序中的应用。

在典型加密信息检索中，当查询中只有1个关键词时，通过基于保序加密算法的加密文档排序算法可以很好地对检索到的加密文档进行排序，这是因为用保序加密算法加密的明文数据加密后其密文顺序保持不变。然而，当查询中有2个及2个以上的关键词时，基于保序加密算法加密得到密文和并不一定保持与其明文和对应的顺序。在这种情况下，并非所有保序加密算法在多关键词查询时，其密文和均能较好保持顺序并取得较好排序结果。因此，可以通过适当地选择加密算法来保证密文和能最大限度保持其明文和的顺序，而研究探索最优化选取满足上述需求的加密算法也至少具有理论上的指导意义。

本文介绍了保序加密算法，拟合了TREC的标准数据集中关键词权重概率分布，比较了2种保序加密算法密文随明文的变化，提出了基于鉴别信息的保序加密算法选取标准。对选择不同保序加密算法的加密文档检索排序结果进行了比较，并在标准数据集上进行了实验，验证了采用开放式保序加密算法进行加密排序取得的结果优于采用封闭式保序加密算法的情况。

1 保序加密算法及其加密文档排序

1.1 保序加密算法

2003年，Ozsoyoglu等［8］开创性提出了保序加密算法，以解决关系型数据库数值数据隐私保护的问题。2004年，Agrawal等［9］提出了一种可以直接加密新数据且无需对已加密密文进行更新的保序加密算法。Boldyreva等［10］提出了基于超几何分布的保序对称加密算法及基于模的保序加密算法［11］。文献［12］中的算法应用于无线传感网，通过加密信号数据并传输到传感节点，传感节点无需解密即可进行大小比较操作，降低了节点的功耗开销。在保序加密算法应用于远程数据库数据保护的相关研究中，有工作针对数据顺序本身也是敏感信息提出了隐藏密文顺序但支持有效比较运算的算法，提高了数据安全性［13］；也有工作提出了一种在数据库中插入假元组并保证数据完整性的算法，在该算法中真元组和假元组都经过保序加密，以允许用户验证保序加密数据库的查询完整性［14］；还有工作提出了具有有序选择重复明文分布攻击下的不可区分性的算法［15］。其他算法包括基于一般近似公约数问题的保序加密算法［16］及使用保序概率编码对明文的变换进行编码并通过2轮交互协议生成密文的公开保序密文生成算法［17］。

由于上述提到的其他算法与开放式及封闭式保序加密算法具有本质上的相似性，为不失一般性，主要针对Ozsoyoglu等［8］提出的2种典型保序加密算法进行分析，其第1种开放形式的保序加密算法实现过程的描述如下：

步骤1 生成一个序列的随机数yi∈［1，M］。

步骤2 定义zi：S1：＝z1：＝y1。

步骤3 对于k≥1，令Ak＝M－Sk。

步骤4 zk＋1＝Int（yk＋1×Ak／M）。

步骤5 Sk＋1＝Sk＋zk＋1。

其中，对于明文k，保序加密算法加密的结果为

第2种为封闭式的保序加密算法，其可以描述为

式中：x为待加密变量；Ci（0≤i≤n）为常量。

在其他算法中，Agrawal等［9］提出的算法把服从某一分布明文映射到服从另一分布的密文空间。而Boldyreva等［10］提出的加密算法的实质是利用超几何分布产生保序的密文数据，与Ozsoyoglu等［8］提出的第1种开放形式保序加密算法本质上类似。

1.2 明文文档检索及排序

典型的信息检索模型包括布尔模型、向量空间模型及概率模型等［18］。布尔模型是基于布尔代数的检索模型，该模型中1个查询即构成了1个布尔表达式。尽管布尔模型在数据库检索中仍有使用价值，但在文档检索中无法对检索到的文档进行排序，在实践中使用较少。在向量空间模型中，文档及查询分别被标记为向量空间中的向量，通过向量之间的相似度来对文档进行相关性排序。概率模型通过计算文档与查询之间相关的概率对文档进行排序。为不失一般性，以概率模型的一种变形，即以Okapi BM25模型为例，实现对文档及查询相关度的计算。

Okapi BM25模型自从20世纪90年代被提出后，由于检索的准确率相对其他模型较高，在文档排序中的应用非常普遍，并被推广应用到文本分类聚类等众多领域［18-19］。

Okapi BM25模型中，文档和查询之间的相似度定义为

式中：wqi为关键词qi在文档D中所占的权重，定义为文档中词频和逆文档频率的函数，有很多个变种。本文中，为不失一般性，采用其中比较常用的一种：

1.3 基于保序加密的文档排序

在加密文档检索中，当检索到所需的文档之后，需要对已经加密的文档进行基于词频或关键词权重对应密文的排序操作。Swaminathan等［4］提出了用保序加密算法对文档中的词频进行加密的方法，在查询单个关键词的情况下，通过保序加密的词频可以得到相关度的排序。尽管词频在一定程度上可以描述文档和查询的相关度，然而权重更为有效地描述了关键词在文档中的出现对文档与查询相关度的影响。

因此，通过对关键词的权重进行加密，可以更为有效地描述一个关键词在文档中出现的作用。这里对文档排序的对象是关键词权重对应的密文。

理论上，当查询中关键词个数｜Q｜为1时，用保序加密算法排序所得到的结果具有很好的性能。而当查询中关键词个数｜Q｜多于1个时，由于涉及到对加密密文的加法操作，而加法后的密文排序并非明文和的顺序。因此，当查询中有多个关键词时，排序的结果与保序加密算法有关。

2 保序加密算法选取

2.1 明文分布

式中：各参数的拟合值如表1所示。

表1 参数拟合值Table 1 Parameter fitting values

由图1可以看出，该分布并非是严格的对数正态分布，这是因为词频和逆文档频率并非是完全独立的，而词频本身是对关键词出现频率进行运算的结果，且权重的分布是选择保序加密算法的决定性因素。

图1 Okapi BM25模型权重出现频率的分布函数Fig.1 Probability distribution function of term weights in Okapi BM25 model

2.2 保序加密算法选取方法

对2种保序加密算法下的密文进行了比较，结果如图2所示。由于加密后的值较大不便于直接展示，为便于比较，对密文取对数。图2的曲线表明，当采用开放形式保序加密算法的密文值增大到一定程度后便保持稳定，而封闭形式保序加密算法的密文值一直明显地增加。

图2 开放式保序加密算法与封闭式保序加密算法密文随明文变化情况Fig.2 Change of cipher text with plaintext for open order preserving encryption scheme and closed order preserving encryption scheme

2种保序加密算法都可以很好地对加密数值保持顺序。然而，本文有以下启发性结论：针对密文的加法运算，采用开放形式保序加密算法加密的密文能更好地保持其顺序。这是因为：用开放式保序算法加密得到的密文值比较接近，然而，用封闭式加密算法加密得到的密文值在数值空间上分布越来越稀疏。因此，封闭式保序加密算法加密得到的密文值加法运算结果的保序效果劣于开放式保序加密算法。反映在加密文档排序效果上，采用开放形式保序加密算法的检索结果在性能上优于封闭形式保序加密算法得到的检索结果。

3 保序加密算法选取标准

理想情况下，设保序加密由连续函数h（x）表示，那么，给定明文X，则其对应密文Y＝h（X）的分布为为使在保序加密的情况下其加法在统计意义上仍然是保序的，通过保序加密算法加密的密文如果服从明文分布f（x）或接近明文的分布，则在理论上同样可以达到明文检索下相差较小的检索结果。经过加密变换Y＝h（X）之后，Y值的变化区间为［h（0），h（3）），为便于进行分布比较，可以将Y通过某线性变换Z＝3（Y－h（0））／（h（3）－h（0））将其值重新映射到区间［0，3）。线性变换不影响2个数加法的结果，因此，可以对Z与X的分布进行比较。Z的分布由Y的分布表示为

衡量2种分布之间差异性的一种比较好的方法是鉴别信息。通过鉴别信息可以对明文与密文概率分布的差异性进行描述。为使二者分布距离最近，需要使鉴别信息最小。为使保序加密后的密文仍然保持原有的分布，需要满足：

然而，对保序加密算法的选择是有其他约束性的。例如，为保证算法的安全性，封闭式保序加密算法系数的选取范围应该足够大；而在开放性的保序加密算法中，为保证明文对应的密文各不相同，需要增加密文值域等。因此，保序加密算法h（x）的优化选择可为

4 实验结果

有工作分析研究了云数据搜索中一到多保序加密算法的安全性，并提出了通过保序密文的差异可以进行差分攻击的问题［20］。本文从另一个角度，即在算法具有同等安全性的前提下对如何最优化选取保序加密算法进行了研究。在TREC的标准数据集ClueWeb09 Cat.B上进行了实验，由于数据集合规模较大，其结果相比Cranfield等小规模数据集更接近真实环境。在该数据集中，有50 000 000个文档、50个标准查询。针对该数据集的任1个文档进行分词、记干化等预处理，可以得到其对应的词频f（ti，D）及文档长度｜D｜。然而，通过对整个文档进行统计，可以得到式（4）中参数的avgdl、C及n（ti）的值。

通过以上参数，可以计算得到关键词ti所对应的Okapi BM25模型下的权重。用户对其通过保序加密算法进行加密，把得到的密文存储在服务器端，而在服务器端，对对应关键词的保序加密形式的权重进行加法运算，通过所得到的结果对文档进行排序。

在实验中所采用的保序加密算法分别为1.1节中文献［8］所提到的开放式保序加密算法与封闭式保序加密算法。

评价检索结果效果的指标为准确率及返回率。准确率定义为返回的且相关的文档占所返回文档的比例，返回率定义为返回的且相关的文档占所有相关文档的比例。

采用不同保序加密算法对加密文档进行排序及明文检索情况下的准确率-返回率曲线的对比结果如图3所示。可以看出，在ClueWeb09 Cat.B数据集上，采用保序加密算法排序的准确率-返回率曲线比明文检索的情况低；采用开放式保序加密的准确率-返回率曲线比封闭式保序加密对应的曲线高。

图3 不同检索排序方式下的准确率-返回率曲线Fig.3 Curves of precision versus recall rate with different retrieval and ranking methods

前N个文档的准确率（P@N）如表2所示，此处N的取值分别为5、10、20、30、50、100。表2中不同返回文档个数下的准确率表明，开放式的保序加密算法可以达到较封闭式保序加密算法更好的检索结果，比较重要的指标，如前10个及前20个的准确率明显高于后者，其中P@10高出3.4%。然而，2种保序加密算法的准确率都低于作为比较基准的明文检索情况下的检索排序准确率。这说明单纯依靠保序加密算法可以开展对加密文档的排序，但距离明文检索下的结果还有差距，后续将研究通过结合使用同态加密算法来进一步提高检索的准确率。通过结合使用保序加密及同态加密算法，可在减少在本地运算量的基础上，为密文空间提供更加精细的相关度计算结果。

表2 前N个返回文档的准确率Table 2 Precision of top N recalled documents

5 结 论

1）通过在ClueWeb09 Cat.B数据集上对权重进行统计分析，拟合了其权重的分布。

2）P@10的加密文档排序中，基于开放式保序加密算法的准确率比封闭式保序加密算法高出3.4%，验证了在加法运算下的开放形式保序加密算法的密文能更好地保持原有顺序的结论。

3）给出了对保序加密算法最优化选取的准则，该准则具有理论上的指导意义。

探索保序加密算法的共性特征及在此基础上提出最优化选取方案有待进一步的深入研究。