一种云计算环境下基于可变搜索树的保序加密研究方案*

王小骥，杨 竞，汤殿华，王 辉，刘 瑶

（中国电子科技集团公司第三十研究所，四川 成都 610041）

0 引 言

云计算是以互联网为中心的一种技术，采用分布式计算、并行计算、网络存储和虚拟化等技术，将软件、硬件计算和存储等资源通过网络连接，形成一种云状的计算网络，为用户提供快速、便捷、自由的计算与存储服务[1]。其与传统的网络应用模式相比，具有应用/资源虚拟化、动态可扩展、按需部署、灵活性高、可靠性高和性价比高等优势。云计算包括了很多服务[2]，其中最为广泛的为基础设施即服务（Infrastructure as a Service，IaaS）、平台即服务（Platform as a Service，PaaS）和软件即服务（Software as a Service，SaaS）3 种模式。云服务产生大量的个人隐私数据和商业信息等数据资源，由云服务器汇聚存储。

由于云端服务器和用户终端都在开放的网络环境下运行，使得云端数据不可避免地面临着安全风险和威胁。因此，如何在保证云端数据安全性和隐私性的前提下，在云计算环境下为用户提供安全可靠的数据存储和应用服务，成为亟待解决的问题[3]。

目前，在云计算环境下出于对隐私数据的保护，用户终端一般先采用常规密码算法对数据进行加密，再将密态数据存储于云服务器，保证用户的隐私数据的机密性，但同时也杜绝了在云端服务器操作用户数据的可能性，当用户需要对存储在云端服务器或数据库中的密文数据进行操作时，必须先下载至本地终端进行解密，然后才能执行相应的操作。这种方式不仅增加了用户操作成本，还加重了网络和本地的负担，极大地限制了云计算的处理能力。

近些年，结合云计算环境下对密文数据进行操作的使用需求[4]，密码学家研究并提出了保序加密、密文检索、同态加密等密码体制及方案，从而实现密文状态下的密文排序、密文检索、密文计算等功能，通过综合运用这些密码算法，构建密文数据库系统，为用户提供安全的密文保障。其中，密文排序作为云计算安全的主要应用之一，通过保序加密密码技术来实现。本文重点研究云计算环境的保序加密技术，通过对保序加密方案的特点进行分析，得到频率隐藏保序加密方案的构造思路，设计了一种保序加密方案，实现云计算环境下的数据保序加密。此方案在为用户隐私数据提供保护的同时，也能让云服务器进行密文排序等操作。

目前，常见的Popa 方案[5]将二叉树维持在一个B 树的形态，具有较强的安全性，但是只要发生了数据的更新、插入或者删除等操作，就需要对整个树做平衡操作，时间消耗很大。文献[6]提出可以使用非线性的加密算法实现索引加密，在数据库中构造了索引结构，简化数据库检索过程，提出了基于噪声的非线性表达式，但是如果输入的明文重复率很高，则很容易被推算出安全参数，影响算法的安全性。

1 保序加密概述

在云计算环境下，用户终端一般将复杂的计算和存储外包给云服务器。然而，不完全可信的云服务器可能会泄露用户隐私。为保护用户隐私数据，用户采用传统密码算法对数据加密后，再外包存储于云服务器，这些密文数据失去了原有的一些性质，无法对其进行范围查询。因此，在云计算环境下对密文数据实施范围查询提出需求，保序加密是满足密文空间范围查询需求的有效方法。

1.1 系统模型

2004 年，Agrawal 等 人[7]首 次 提 出 保 序加密的概念，给出一种对数值型数据进行保序加密的方案（Order-Preserving Encryption Scheme，OPES）。保序加密系统模型主体一般包括数据拥有者、云服务器、数据使用者，如图1 所示。

（1）数据拥有者。受限于存储和计算能力，数据拥有者一般将外包数据进行加密后，上传至云服务器存储。为了保护数据可用性，数据拥有者将采用可保留明文原有特殊性质的加密方案来加密数据。

（2）数据使用者。对云服务器存储的数据进行查询时，数据使用者需要向数据拥有者索取密钥，再将查询请求发送给云服务器，收到查询结果后，数据使用者对查询结果进行解密。

（3）云服务器。根据数据使用者的查询请求，云服务器在密文数据库中进行检索，将存储结果发送给数据使用者。

1.2 形式化定义

定义1：保序加密方案可描述为多元组，为OPES=(Genk,Enc,Dec)。

其中，包含了密钥生成算法Genk产生的密钥K；加密算法Enc输入密钥K和明文M，输出密文C；解密算法Dec输入密钥K和密文C，输出明文M。对于每个明文M和密钥K，需保证Dec(Enc(K,M))=M。

对于两个随机明文M0和M1及密钥K，当M0≤M1时，Enc(K,M0)≤Enc(K,M1)， 则 称这个方案为保序加密方案。

定义2：（有状态）保序加密方案。

其中，S←KEYGEN(λ)为根据安全性参数λ生成秘密状态S；S',y←ENCRYPT(S,x)为明文x计算密文y并将状态从S更新到S'；x←DECRYPT(S,y)为基于状态S通过密文y计算明文x。

如果对于任何有效状态S和x，都满足DECRYPT(ENCRYPT(S,x))=x，则加密方案是“正确”的。如果保留了顺序（即对于任何i和j有yi≥yj⇒xi≤xj），则加密方案是“保序”的。

定义3：序列随机化。

令n为序列S=x1,x2, … ,xi, …,x n(∀i,xi∈N)中明文的个数。序列X满足随机化顺序Y=y1,y2, … ,y n( ∀i, 1 ≤yi≤n, ∀i,j,i≠j⇒y i≠yj)，则∀i,j:xi＞xj⇒y i＞yj和 ∀i,j:yi＞yj⇒xi＞xj成立。

1.3 方案分类

保序加密方案对明文加密后，密文保留原有明文顺序，用户可直接对密文数据进行排序、比较大小等操作，既可以确保用户数据安全，又可以增加密文数据的可操作性，目前主要应用于云服务器对密文数据库进行范围查询、近似邻检索等[8]。

保序加密方案分类主要有检索结构分类和密文变化情况分类。

（1）检索结构分类。根据保序加密方案中是否含有明文检索结构，将现有的保序加密方案分为无索引结构和基于索引结构的保序加密方案。无索引结构的保序加密方案是指加密密文直接保留原有明文顺序。基于索引结构的保序加密方案是指明文数据采用常规分组体制加密方案进行加密，同时建立保序索引结构来比较明文顺序。

（2）密文变化情况分类。根据密文是否变化，可将现有的保序加密方案大致分为密文不变和密文可变的保序加密方案。密文不变的保序加密方案是指相同的明文数据经保序加密算法加密后，产生的密文相同。密文可变的保序加密方案是指相同的明文数据加密后，产生的密文不相同。

1.4 方案选择

保序加密方案直接对密文进行比较操作，若提高比较操作的效率，就会适当降低其安全性，密文的顺序会向攻击者泄露一些信息。在云计算环境中，攻击者的常用手段是唯密文攻击[9]，其中统计性攻击是最有效的攻击方法。攻击者主要通过分析数据分布规律和数据频率对密文实施统计攻击。

（1）数据分布规律。利用保序加密方案所具有的明文空间映射密文空间的性质，攻击者可通过统计分析密文数据分布规律，推测明文数据分布规律。

（2）数据频率。攻击者通过统计分析高频率出现的密文数据来推导出对应的明文，使得密文数据出现的频率与明文数据一致，从而攻击加密方案成功。

经过安全性及其他性能等综合评估，本文选择了Kerschbaum 等人[9]于2015 年提出的以频率隐藏保序加密方案的思想来构建一种新的方案，该方案通过动态的二叉平衡树结构来随机化密文隐藏明文的频率，每个节点都有个状态t来表示节点最大和最小范围，利用压缩树来节省客户端存储空间。

2 基于搜索树的保序加密方案

2.1 基本思想

频率隐藏保序加密方案的基本思想[10]是随机化密文分布，从而达到隐藏明文频率的目的。该方案需要在客户端（加解密侧）维护一个搜索树（二叉树）状态，以实现对数据的加密和解密，可以将搜索树状态看作私钥。加密时，先检查明文数据是否被存储于客户端的搜索树中，若明文数据未被存储于搜索树中，则对明文数据进行确定性加密产生密文数据；若明文数据被存储于搜索树中，则对明文数据进行随机化加密产生密文数据，并且更新搜索树增加新的节点，该节点含有对应的明文数据和密文数据。总之，频率隐藏保序加密方案对搜索树中首次出现的明文数据进行确定性保序加密，对搜索树中后续出现的明文数据进行随机化保序加密。随机化密文比确定性密文具有更高的熵，与普通保序加密方案相比，频率隐藏保序加密方案需要在客户端存储更多的状态信息，为了节省存储空间，本方案还具备数据压缩技术，既提供了实用性，又增强了密文的安全性。

2.2 基本原理

频率隐藏保序加密方案采用了具有排序性质的二叉树，在每个节点的值为明密文对，其性质如下文所述。

若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左、右子树也分别为二叉排序树。

2.3 方案描述

本文提出的一种基于搜索树的保序加密方案是将明文数据按其被加密的顺序插入到排序二叉树中，具有动态分配的叶子和二叉搜索树。其中，搜索树是动态变化的，存在一定的阈值深度，超过该阈值深度后，搜索树将被重新平衡。因此，本方案包括预处理步骤、加密算法ENCRYPT、解密算法DECRYPT 和重平衡化搜索树算法REBALANCE。

预处理步骤如下文所述。明文数据集合X中的明文数据若非数值形式（如字符串），需要转换成数值，最终以数值形式存在，这些数值与其他数值进行大小比较，其结果有大于、小于和等于3 种情况。当搜索树算法开始执行时，若搜索树为空，则需要创建根节点t0 ，对明文x加密，并且将明文x和其对应的密文y存储在根节点中，创建搜索树根节点过程如图2 所示。

搜索树步骤开始执行时，若已有根节点的搜索树，也就是说，明文集合X中至少有一个明文x已被加密，并且至少有一个节点（如根节点）被包括在该搜索树中。接收输入集合包括明文x、当前考虑的节点t、min 值和max 值，判断明文x是否等于当前考虑的节点t中的明文t.plain，若明文x等于t.plain，则基于RANDOMCOIN 确定判断条件硬币值coin为真；若明文x不等于t.plain，则coin被设置为假，表明明文x是唯一的，对其进行确定性加密。

当判断完成明文x是否大于t.plain或coin是否等于1 时，若条件满足其中之一，则向右遍历搜索树，判断在当前考虑的节点t的右侧是否已经存在子节点，若右子节点t.right不为空（右侧已经存在子节点），则更新该输入集合包括明文x、下一节点t.right作为当前考虑节点t、节点t.right的t.cipher作为min 值和max 值后，返回至起始输入；若t.right为空（右侧没有已经存在的子节点），则判断是否满足搜索树的阈值深度，即当前考虑的节点t的t.cipher与max值的差值是否小于2。若满足阈值深度，则重平衡搜索树，生成更新的搜索树，将明文x及其密文右子节点密文t.right.cipher作为t.right插入到更新的搜索树中；若没有满足阈值深度，则直接将明文x及其密文t.right.cipher作为新节点t.right插入到搜索树中。

当判断明文x是否大于t.plain或coin是否等于1 时，若明文x不大于t.plain，则向左遍历搜索树，判断在当前考虑的节点t的左侧是否已经存在子节点，若左子节点t.left不为空（左侧已经存在子节点），则更新该输入集合包括明文x、下一节点t.left作为当前考虑节点t、min和节点t.left的t.cipher作为max 值，返回至起始输入；若t.left为空（左侧没有已经存在的子节点），则判断是否满足搜索树的阈值深度，即当前考虑的节点t的t.cipher与min 值的差值是否小于2。若满足阈值深度，则重平衡搜索树，生成更新的搜索树，将明文x及其左子节点密文t.left.cipher作为新节点t.left插入到更新的搜索树中；若没有满足阈值深度，则直接将明文x及其密文t.left.cipher作为新节点t.left插入到搜索树中。整个预处理过程如图3 所示。

令λ为方案的安全性参数；N为不同明文数据的个数；k=[log2N]为明文数据的比特长度；l=λk为密文数据的比特长度。

算法1：加密算法FHOPE.Enc(x,t,min,max)→y

输入：明文x，节点t，最小值min，最大值max

输出：密文y

状态：节点{t} 的排序二叉树T

初始化：在初始建立二叉树状态时，可以将T初始化为空

1 若x=t.plain，则随机在{0,1}选择一个RANDOMCOIN()，令coin=RANDOMCOIN()

2 若x≠t.plain，则令coin=⊥

3 若x＞t.plain或者coin= 1，则执行如下操作：

3.1 若max −t.cipher≥ 2，则继续递归调用FHOPE.Enc(x,t.right,t.cipher,max)

3.2 若t.right=Null，则执行以下操作：

3.2a 若max −t.cipher＜ 2，那么调用Rebalance(x, −1,n)

4 若x＜t.plain或者coin=0 ，则执行如下操作：

4.1 若t.left≠Null，则继续递归调用FHOPE.Enc(x,t.left,t.cipher,max)

4.2 若t.right=Null，则执行以下操作：

4.2a 若t.cipher−min ＜ 2，那么调用Rebalance(x, −1,2λlog2n)

加密时，可调用FHOPE.Enc(x,root(T), −1,2 2λlogn)→y。

算法2：解密算法FHOPE.Dec(y,t)输入：密文y，节点t

输出：明文x

状态：节点{t} 的排序二叉树T

1若y＞t.cipher，则递归调用FHOPE.Dec c(y,t.right)

2 若y＜t.cipher，则递归调用FHOPE.Dec

(y,t.left)

3 若y=t.cipher，则返回t.cipher

解密时，可以将T的根节点作为输入来求解密文，即FHOPE.Dec(y,root(T))→x

算法3：重平衡化搜索树算法Rebalance(x,min,max)→y

输入：明文x，最小值min，最大值max

输出：密文y

状态：节点{t} 的排序二叉树T

1 令X={t.plain}∪{x}

2 将X按照升序排列

3 创建一个新节点

4 令y=T.plain

5 令X'={x j|x j＜y}6 令X''={x j|xj＞y}

9 用y'和y''替换y，用X'和X''替换X，进行递归调用

10 在T中找到x，并返回Tx.cipher

2.4 方案安全性分析

对于保序加密的主流研究，可以用不可区分性或香农熵等指标来刻画其安全性，实际上考虑的是从密文中恢复出正确明文的成功率。在使用保序加密的部分场景中，攻击者不需要恢复出精确的明文，只需要恢复出一个足够接近的近似值。为此，可以采用恢复出的明文与实际明文之间的距离，即平均绝对误差来衡量安全性。

假设攻击者知道一定的明密文对，相当于攻击者已知了解密函数FHOPE.Dec(y,t)在一些定点的取值，此时攻击者可以用插值给出解密函数FHOPE.Dec(y,t)的估计。不同的插值方法可以给出解密函数的不同估计。当攻击者对于本方案有一定的了解时，可以根据加密函数的特性针对性地选择插值方案。对于本文方案，假设攻击者采用线性插值方法来恢复明文，对于密文y，若已知的明密文对中小于y的最大密文为y1，大于y的最小密文为y2，且y1和y2对应的明文为x1和x2，则解密函数FHOPE.Dec(y,t)在y的取值为：

对于最小与最大的明文，若已知的明密文对中不包含这两个明文，则认为它们分别被映射到最小密文和最大密文，并以这两对来对其他密文进行插值。则解密函数FHOPE.Dec(y,t)解密出的密文平均绝对误差Dec.error为：

如果攻击者解密出的密文平均绝对误差为定值，则可以估计这两个序列之间的准确映射关系，认为其成功攻击了本文提出的保序加密方案。本文方案在预处理过程中提前判断阈值深度，重平衡搜索树，使得攻击者获得的密文平均绝对误差会一直变化，除非其获得了全部的明密文对才可能得到定值。所以本文方案是安全的。

2.5 实验结果及分析

对本文提出的方案进行实验，设置明文数据比特长度k为12，安全性参数λ为5，则密文数据比特长度l=λ×k= 60。实验操作系统为Windows 10，处理器为Intel Core i5-6200U 2.3 GHz，内存为8 G，编程语言为C 语言。

实验结果表明，虽然随着明文大小的变化，加密时间也随之变化，但是整体的加密速率是一致的，为114.441 Mbit/s，实验结果如图4所示。

本文方案与采用类似构造的Popa 方案在相同实验环境下进行对比，在输入相同明文的情况下，Popa 方案加密速率只有73.934 Mbit/s。相较于Popa 方案，本文的方案在加密速率方面提高了54.7%。

3 结 语

云计算环境下，用户对于安全的进一步需求促使密码技术有了很大的发展。但是传统的密码技术在用户将自身隐私数据传至云端保存的场景下存在困难，如用户端的计算能力有限，传统的加密技术会破坏明文数据的特性，不利于后续的范围检索等。

本文提出的保序加密方案对搜索树中首次出现的明文数据进行确定性保序加密，对搜索树中后续出现的明文数据进行随机化保序加密，可以有效地应用于云环境下的加密数据检索等场景中，同时本方案的加密速率在100 Mbit/s 之上，在一些交互强、延迟低的应用场景下也具有良好的效果。