基于MapReduce框架下的数据隐私保护

姚庚梅，张永棠,2

(1. 广东东软学院 计算机学院，广东 佛山 528225；2. 南昌工程学院 江西省协同感知与先进计算技术研究所，江西 南昌 330003)

0 引言

云计算框架外包数据处理和存储的快速发展，向现代社会发展提供了大量有用的数据。但是，数据隐私保险是云环境下海量数据集管理中的一个主要问题，因为数据集所有者没有按照云安全联盟[1]（CSA）的规定对其数据集进行任何物理控制。因此，MapReduce作为一个处理和创建大量分布式信息的计算框架，必须具有很强的安全性，才能在云中保护数据隐私。通过MapReduce和Cloud发现的安全保证问题已经开始引起认真的考虑。文献[2]提供了一组名为 Silverline的工具，可以将所有实际上可加密的信息与其他云应用程序信息隔离开来，以确保数据保护。同样，文献[3]提出了一种基于隐私泄漏上限限制的解决方案，通过对云上部分可用数据进行加密来解决数据隐私保护问题。文献[4]提出了一个名为Airavat的框架，该框架通过差异隐私技术限制强制访问控制。文献[5]提出了一个名为Prism的数据隐私模型，用于云上的MapReduce结构，对加密数据集进行并行字搜索。文献[6]提出了Hybrex MapReduce模型，该模型通过私有云处理非常敏感和私有的信息，而其他数据可以在公共云中安全地处理。文献[7]提出了一个名为sedic的系统，该系统根据数据的安全标签对Map进行分区，从而减少计算任务。然而，传统的数据加密被认为是解决云安全问题的关键技术，不能直接在MapReduce框架中实现。因此，在文献[8]中首次引入了一种新的可处理加密数据的同态加密体制，以找到解决这一难题的有效方法。这种完全同态加密（Fully homomorphic encryption，FHE）可以在不使用密钥的情况下计算加密数据的任意函数。然而，FHE在实施和计算成本方面提出了两个主要挑战。

为此，文献[9]提出了DGHV方案，使用许多来自Gentry的工具，而不需要理想的格式。此外，Gentry中的某些同态分量可以被一个非常简单的、使用整数的、有些同态的格式所取代。因此，它们的模型在概念上更简单，但是私有密钥应该转移到云服务器，这是非常不安全的。文献[10]提出了一种同态加密 Gen 10方案，适用于云环境，概念简单。在该方案中，加密函数在加、减、乘上是同态的，使用一个随机的私钥参数来代替私有密钥。然而，私钥参数被发送到服务器，需要通过公式计算得出密文，这个过程可能会泄漏密文。所以这个方案也存在安全漏洞。本文的目标是构建一个具有更好密钥大小的有效 FHE方案，提出一种优化的完全同态方案（Op_FHE），该方案首先通过密文的高效操作解决上述数据隐私保护缺点。此外，我们演示了我们提出的解决方案在 Reduce阶段以优化和安全的方式检索密文的速度。

1 准备工作

MapReduce是一种用于处理和生成大型数据集的计算框架。在此编程环境中，用户指定一个映射函数，该函数处理一个键/值对以生成一组中间键/值对，以及一个reduce函数，该函数合并与相同中间键相关的所有中间值。我们有许多可以由 mapreduce表示的问题解决方法，比如计算大型数据集中每个术语的出现次数的问题。

MapReduce框架上的安全保密问题已经开始引起越来越多的关注。安全界从业人员对数据加密保护问题进行了广泛研究，并取得了富有成效的进展。以下是MapReduce框架上已有的几个关于安全保护的模型。

文献[12]中提出了一种利用同态加密的MapReduce数据隐私保险方案。它是一种改进的MapReduce模型，以保证数据的保密性，并以加密的形式对数据进行处理。他们选择两个主要素数A，B，并使P=A· B，然后生成一个随机的正整数A，这是私钥，而B也应该是保密的。

加密：

解密：

但是，为了在该方案中应用同态加密，作者对密文进行了很少的修改，允许约简函数找到相同的密钥，然后对它们进行分组。即，对于密文，其中R为随机正数。然后，通过C*来检索类似的键（而不是C）。因此，很明显，为了得到概率同态密码系统，它们在Reduce阶段需要额外的计算C*，这在计算上是昂贵的。这种同态密码体制的代价非常高，因此它们的模型效率很低。

由于文献[13]需要在Reduce阶段进行额外的计算，并且DGHV 和Gen 10方案分别将它们的私钥和敏感安全参数发送到不可靠的公共云服务器（危及密码系统）。此外，也没有解决密文检索的安全性和效率问题。因此，文献[14]提出了一种完全同态加密（Fully homomorphic encryption，FHE）方案。该方案的主要目标是在还原阶段安全地检索密文，提高检索算法的准确性，而不需要获取有关中间可搜索密文内容的任何信息，以解决DGHV和Gen 10中的安全缺陷。FHE方案是同态加密的有效候选方案，通过强大的混合加密来保护云中的数据隐私，在计算和通信成本方面，这是一种非常昂贵的方案。

因此，我们提出了一种优化的 FHE（Optimized Fully homomorphic encryption，Op_FHE）方案。该方案的创新点是通过逻辑 Merkle哈希树存储库结构，降低时空成本，解决元数据动态和认证路径的输入文件分解（MAP阶段）和密文检索算法（Reduce阶段）的优化问题。

2 Op_FHE 方案描述

同态加密可以有效地在加密数据上进行一些操作，但在计算和通信成本方面，这是一种非常昂贵的方案。因此，我们提出了一种优化的FHE（即 Op_FHE）。Op_FHE解决方案的体系结构如图1所示。

图1 Op_FHE 架构

在主程序的控制下，在用户端引入了一个新的逻辑代理：匿名者（其三个组件：分解表、查询处理和元数据仓库）。这样，用户程序就可以在加密数据之前，有效地将给定输入文件的最优分解（拆分：键/值）发送给主程序。在逻辑Merkle树结构中使用优化的三值搜索尝试（TST）[15]，通过元数据存储库组件最优地解决元数据认证和动态问题。

为了解决元数据身份验证和动态问题，加强数据隐私保护。如图1所示，我们在主控程序中引入了一个逻辑代理：匿名者。匿名者有三个部分组成，即：分解表、查询处理和元数据存储库。它们的功能描述如下：

分解表：它负责为最佳数量的特定输入文件定义精确的属性集A。

查询处理：它过滤主程序生成的候选Map工作线程查询请求，以便对数据位置产生基于查询的匿名请求以进行处理。

元数据存储库：它保存分解表完成的数据分解，并将其转发给查询处理单元，以生成新的匿名查询请求。为了提高该方案的效率，我们使用Merkle哈希树结构[16]来处理元数据认证和动态问题。因此，主程序将特定的输入文件分解表（A）分配给Map工作线程，以便进行逻辑处理，如下所示。

所有输入文件都被转换成一组符号 a1, a2,… ,an，如图2所示。数据匹配和认证以自顶向下的方式从根节点开始，其动态过程可以描述如下。

图2 高效的基于符号的树检索

文件上传：假设数据所有者希望用公共云服务器处理由ai(叶节点)标识的文件F，该文件的属性满足私有云服务器定义的访问策略AP=［ap1, a p2,… ,a pn］。假设文件F由关键字集W组成，那么，所有者从密钥空间中随机选择对称密钥Ske，并用Ske加密文件F以获得密文Ctf。随后，数据所有者运行算法 E ncrypt（ AP , Ske）以获得加密文本Cske，即针对访问策略AP的对称密钥Ske的加密。所有者将（ai, Ctf, Cske）上载到公共云。此外，为了为W中的关键字生成陷门，所有者还向私有云发送 （ai, A P,W ） 。当接收到 （ai, A P,W ） 时，私有云将访问策略AP转换为一组｛Pj｝ AP特权。然后，对于每个wi∈W和 pi∈ ｛ Pj｝AP ，它计算tpi，，其中kpi是每个pi的对称密钥。最后，私有云也向公共云发送

为了提高搜索效率，使用基于符号的树来建立存储在私有云（元数据存储库）中的索引。更准确地说，将单向函数 f的输出划分为l个部分，并预先定义一个属性集 A = ｛a1, a2,… ,ai｝，其中包含每个部分中的所有可能值，图3显示了这种树的一个示例。最初，基于符号树的索引只有一个根节点（表示为node 0），它由∅（一个空集）组成。基于符号的树中的搜索过程是深度优先搜索。可以按以下方式更新和搜索树。

Update：假设数据所有者希望外包一个文件F，该文件由带有关键字集W的ai标识，则公共云将从数据所有者和私有云接收（ai, Ctf, Cske）和（ai, ｛ tpi, wi｝ ） ，其中pi是相应的特权，wi是W中的关键字。然后，对于每个（tpi, wi） ，公有云将按照以下步骤将其添加到trie索引中。

Step.1公有云将 （tpi, wi） 解析为符号 ai1,ai2,… ,ail的序列。

Step.2公有云从树的根节点开始，它扫描根节点的所有子节点，并检查是否存在子节点l，这样节点l中包含的符号等于ail。此操作以自顶向下的方式执行。通常，假设符号 ai1,ai2,… ,ail的子序列已经匹配，当前节点是 n odej-1，公共云将检查nodej-1的所有子节点，并试图找出某个节点，例如nodej中包含的符号等于aij。如果存在这样的节点，则当前节点设置为nodej，并且匹配下一个aij+1对象，否则跳到步骤3。

Step.3假设当前节点nodej没有与符号aij+1匹配的子节点，则公共云将分别为所有其余的符号（i.e. aij+1, aij+2,… ,ail） 构建节点 n odej+1,… ,n odejl，并将它们链接为附加于nodej的节点列表。最后，添加由ai标识为附加 n odejl的叶节点的另一个节点。

Search：假定合法用户希望使用关键字w和权限｛pi｝ 搜索外包文件，则公共云将从私有云接收 （tpi, wi） 。对于每个 （tpi, wi） ，公共云将执行类似于上述三个步骤的操作。一个例外是，如果匹配失败（即当前节点没有可以匹配符号的子节点），则中止对（tpi, wi） 的搜索。否则，通过叶节点中的标识符ai获取相应的（Ctf, Cske）。

因此，为了解决Merkle树遍历问题，我们使用了文献[17]中的高效算法中的一些工具来解决时空问题。此外，为了优化Merkle哈希树遍历过程中的时间空间约束，我们设计了一个优化的三值搜索尝试（ternary search tries，TST），这是一种将快速排序和基排序相结合的排序算法。因此，它与最著名的C-排序码竞争。它比传统的散列和其他常用的搜索方法更快，如表1所示。

表1 不同搜索方法的执行消耗

TST节省空间，但会随着字符串数N的增加而增加。因此，遍历问题是如何有效地计算从第一个叶子到最后一个叶子依次开始的所有叶的身份验证路径，以最小的时空开销。因此，它意味着要分析单件属性ai的最佳分布，以提高所提出的解决方案的效率，即找到填充树的字符串或属性N的最佳数量。在这里，我们使用文献[18]的库恩塔克条件（karush kuhn-tucker，KKT）来解决约束优化问题，以找到最小单件类标识符数目，从而为所提出的遍历算法效率提供最佳的安全级别。

因此，在通用分解表中，任意选择N个选项（条目）中的一个元素，第i个元素成为单个元素的概率为

将变量xi用来表示第i个元素是否为单例的指标，其期望值可计算为：

最后，对于具有最大不同值总数N的分解表，单例拟标识符的最优数目为。利用该最优数填充三值搜索树，通过解决时空代价问题，提高了Merkle树遍历算法的性能。

3 Op_FHE 效率和安全分析

为了优化 Map阶段的外包数据处理，防止Reduce阶段的中间数据泄露，以加强Mapreduce框架上的数据隐私。本文的主要目标是对Map阶段（输入文件分解）和Reduce阶段（密文检索）过程进行安全优化。因此,我们实现一个标量优化基于同态的MapReduce方案（Op_FHE）,它包含注 册KeyGen（ke） 、 加 密KeyGen（ke） 、 解 密Decrypt（c）和检索 R etrieval（c）等四个部分。修改后的输入文件分割算法如算法1所示。

该算法用FS表示的所选特征子集，其初始化为空集，将输入文件分割为子集。通过在选定的特征子集中添加一个特征fd（其中d∈ ［1 ,D］），生成一个候选特征子集FC，并用算法2计算哈希索引IWIFC。然后，该算法删除该特征并添加另一个特征以生成新的候选项。也就是说，所选候选子集中的新特性将被添加到所选的特征子集中。因此，该算法通过迭代添加一个特征（如果使用了浮动策略，则添加固定的特征数）来增加所选的特征子集，直到达到阈值为止。需要指出的是，本文提出的算法与文献[19]中现有算法的主要区别在于：我们的算法基于哈希索引值生成高度相关的数据子集。因此，在压缩阶段的密文检索过程在速度上会更有效。

为了验证Op_FHE的效率，我们使用HElibmaster-2018.3库对Op_FHE系统进行了验证。并将结果与现有的盲全同态Fhe_DFI_LM算法、原Fhe_Schr算法进行了比较，证明了对候选解的有效分析。表2和图3显示了我们提出的解决方案（Op_FHE）与相关工作（FHE_DFI_LM和FHE）的平均性能。

表2 不同算法的平均耗时对比

图3 不同算法的性能比较

可以看出，我们的Op_FHE在Map阶段的数据处理耗时，比 FHE_DFI_LM （13078 ms）少2.5倍（5932 ms），比FHE（11684 ms）少2倍。这个结果是在文件分解过程中，通过使用最优数，对给定的N项分解表进行优化选择得到的。因此，对于给定的数据集，我们的算法预先计算出精确的最优子集数（特征选择）和Map工作进程，以加快Map阶段的分割和数据分配过程。并且子集的每个元素（特征）都由一个有效的特征选择算法（参见算法1）来选择。

基于上述有效的实验结果，提出的优化方案Op_FHE在不影响密码体制的情况下，无疑加快了系统的设置（输入文件分解）和密文检索时间。因此，图3表明，在密文检索和计算成本降低方面，所提出的方案更为有效。由于同态密码系统非常昂贵，因此，我们的解决方案是一个可靠的替代方案，可以最大限度地降低总体计算和通信成本。

我们的安全方案是采用基于属性的加密（Attribute-Based Encryption，ABE），将属性和策略分别嵌入到密钥Ctf和密文Cske中，加密为。因此攻击者应首先解密Cske，但是，由于这种会话密钥受ABE方案的保护。因此，数据的保密性可以归结为ABE的保密安全性。由于策略嵌入密文中，优化方案Op_FHE做到了一个粒度可以细化到属性级别的加密访问控制，实现数据机密性。

为了在数据认证路径和动态方面提高所提解决方案的安全性，我们采用Merkle的哈希树来存储元数据分解 ai∈A= ｛ a1, a2,… ,an｝ ，它完全不受任何数论猜想的限制，从而实现自由安全保护。因此，提出的解决方案（优化的fhe_SHCR）可以加强数据隐私保密性。

4 结论

针对MapReduce框架下的数据隐私问题，提出了在Map阶段优化外包数据处理、防止中间数据泄露。实现了一个安全的前端数据库管理代理：匿名者及其三个组件（分解表、查询处理和元数据仓库），以增强我们提出的解决方案的数据安全机制。密码系统工具是一个标量同态加密，在更安全和优化的设计中对加密的数据执行一些计算。实验结果表明，优化后的密码体制 Op_FHE是降低通信和计算成本的有效选择。在实际应用中，它采用了一个优化的分解表作为输入文件，提高了MapReduce环境下密文检索过程的速度和准确性。在此基础上，应用优化的三值搜索尝试（TST）算法，解决了元数据存储库中Merkle树结构遍历的元数据动态和时空代价约束问题。