Information and Theory - An improved mOPE coding method

Abstrcat

​ 隐私保护在各个领域都是一个很重要的研究课题，一般而言，隐私的威胁来自于两个方面，一是攻击者利用系统的漏洞或者非法权限访问数据库或云端，窃取隐私数据；二是数据系统内部具有权限的数据管理员对于隐私信息的探查和泄露。在云计算环境中，构建密文对敏感数据加密后存入云端数据库能有效防止以上两种威胁。

​ 目前流行的加密方法称作保序加密(order preserving encryption, OPE)，相比于传统的加密方案，其优点在于：传统的加密方案将会破坏明文数据原有的顺序信息, 使得数据的查询变得十分困难， 保序加密是一种密文保持明文顺序的特殊加密方案。它既能保护用户数据机密性, 也能够实现密文数据高效查询，保序加密可以使得云服务器根据密文的顺序信息来得到明文顺序信息，进而保证涉及顺序信息的查询操作可以在密文空间高效进行。

​ 本文作为信息论与编码的大作业，在阅读了相关论文之后，结合所学过的huffman编码以及信息熵等基本知识，针对OPE方法进行研究学习，以完成本课程的大作业要求。

关键字：云计算；保序加密；完全二叉搜索树编码；

Works

.1 相关工作

​ 2004年Agrawal在文献中提出了一种保序加密方案OPSE，很好解决了密文数据库系统的比较操作实现问题，加密后不影响系统的原有功能，并能直接操作加密数据，但是这种方法需要已知明文预计分布，且不能支持字符串等其他数据类型。其他研究例如复旦大学王正飞等提出的数值型保序加密方法，利用B+树建立索引，提升了效率但是实现难度过大。

基于此，目前已知的mOPE方法基于平衡二叉树编码实现了保序加密，本文在此基础上进行改进，使用完全二叉搜索树，降低了mOPE构建平衡二叉树的开销。

.2 mOPE

mOPE加密方法的主要思想是对待加密数据按二叉搜索树节点位置编码，再结合任意确定加密算法加密数据，举例来说：假设用户想要对5个数值进行加密，(69, 32, 20, 10, 25)，最简单的保序编码方式是为以上5个数编号1-5，分别对应(5, 4, 2, 1, 3)。接着对于5个数用任意的DET确定加密算法加密，然后将密文与对应的编码存储，存储的密文除了大小关系之外，不会再云服务器上暴露任何信息。该简单方法的缺陷在于，如果用户请求新的数值，以70为例，无法找到与其共同编码的明文数据，故无法得知69对应的保序编码，这时候mOPE编码的优势就体现了出来，其主要思想在于，对待加密数据按照二叉搜索树进行编码。

二叉搜索树最早出现于本科学习当中的数据结构课程中，其构造方法是：对于一个二叉树而言，左子树上的所有节点的值小于根节点，右子树的所有的节点的值大于根节点；二叉搜索树的子树也是一个二叉搜索树。如图所示，我们使用mOPE的方法对于上述密文进行编码，构造二叉搜索树T，命名为OPE_Tree-T。
从图中可以看出，该树为BST，每个节点对应表中的一个记录，举例而言，用户当前需要插入值为55的节点，首先请求插入，算法返回x93d12a，用户解密得到32，由于55>32，根据二叉搜索树的性质，用户将请求获取其右孩子节点，得到密文x27716c，解密得到69，69>55，则请求其左孩子，返回空节点，则在此处插入55的密文。在此过程中，除了节点代表的已知密文与待插入密文之间的大小关系之外，并不泄露其他任何的密文信息。

上述过程中涉及到计算密文Enc(55)对应的OPE编码值，其编码算法是：

1. 对于图1中的路径进行二进制编码，0表示左孩子，1表示右孩子，类似于huffman编码，可以得到一个二进制串来表示根到某个节点的路径。例如，节点'69'的路径（path）为[1]，以此类推，将所有的节点进行二进制编码。
2. 将得到的所有二进制编码调整为相同的长度，一般在实际中取32bit或者64bit，本报告例子比较简单，故取3位加以说明。
3. 而后得到节点的OPE编码值：$OPE Encoding = [path]10...0$；也就是说，其构造的方法为，在path后一位补1，其他位全补充0,。举例而言，'69' 编码可以表示为 '[1]10'，'32' 的编码可以表示为 '[]100'，'10' 的编码可以表示为 '[00]1'。
4. 此种编码方式保存了密文的顺序。

算法分析：

对于插入理想顺序的二叉搜索树，其高度期望是树高度，故其操作复杂度为$O(logn)$，对于已构造的二叉搜索树而言，转化其为二叉平衡树。二叉平衡树要求其左右子树的高度差绝对值不超过1，并且其左右子树也是平衡二叉树，对于平衡二叉树而言，其高度一般都接近于期望高度，故查询和插入的效率得到了保证。

在实践中，随着数据规模的大幅度增加，会存在树高增长过快的问题，其导致的结果就是OPE编码变长过快，故需要进行调整节点的步骤，常见的方法是使用AVL算法，其操作过程是对于平衡二叉搜索树插入新节点后，沿着插入路径从下往上回溯节点，检查每个节点为根的子树是否不再是平衡二叉树。如果不再平衡，就需要进行'AVL 旋转'， 旋转后的整棵二叉树又重新处于平衡状态。

但是AVL算法设计的初衷仅仅考虑到了二叉搜索树的平衡，对于节点相对位置的改变并没有进行特殊的优化，这导致了树重新平衡之后，其某个节点可能移动位置，其path的值会改变，进而导致了已存在的OPE 编码的改变，故需要对AVL算法进行改进，以便于让其适应保序编码的要求。具体的代码实现在后面的章节可以查阅。

.3 改进的mOPE方法

在上节对于mOPE算法分析中提到，为了使二叉搜索树保持平衡，需要进行平衡操作，而后还需要根据改进的AVL算法使得其编码的相对位置不发生改变，这两步操作的时间复杂度都是$O(nlogn)$, 空间复杂度是$O(n^2)$，对于数据量很大的编码集来说，其时间复杂度可以接受，但是空间复杂度过于庞大，特别是对于存储在云端服务器数据库上的数据，增加的开销成本是十分庞大的！因此，mOPE的方法需要加以改进，以便于适应具体的需求。

我们对于理想情况下，初始化时存储完全二叉树，用户数据存储的复杂度一直为对数级，但是由于调整步骤的存在，使得二叉搜索树的构造起到了类似于一种 “临时编码” 的作用，故其编码策略可以进行调整。基于所学知识，本报告提出了一种改进的方法，其相比于mOPE方法的不同在于：

1. 采用普通的二叉搜索树，而取消采用平衡的搜索树；

2. 在插入新值后，自定义策略决策是否需要调整；

3. 最终的调整目的是得到一颗完全二叉搜索树。

对于上图中的BST而言，我们根据二叉搜索树策略对其进行构造，但是其并非平衡的二叉搜索树。需要根据调整算法将其调整为完全二叉树：

如图2所示，该二叉平衡树是根据上文普通二叉树调整而成，可以看出，其编码形式和图2差生了巨大的变化，那么是否可以证明其path改变之后依旧符合保序性？我们从构造过程开始说明该问题。

对于n个OPE编码，将它们按照顺序进行标号(1,2...n)，按照该序号构造一颗完全二叉树，而后对该完全二叉树进行OPE编码，这样得到的新的OPE编码就保存了原有的顺序并可以取代后者，操作方法概括如下：

1. 将图2调整前的OPE_Table的编码值按照从小到大的顺序排列，存储于一张表temp中：

   encoding_old	increment	encoding_new
   1	1	2
   2	2	4
   4	3	8
   8	4	12
   16	5	16
   20	6	20
   24	7	24
   28	8	28

2. 其中increment的值可以构成完全二叉树，需要对其进行OPE编码。

3. 对于图4而言，1-8是存在的编码，虚线部分表示未涉及到的但是完全二叉树已构建的节点，其OPE编码的值已表示在图4的完全二叉树上。观察发现，小于"3"的节点序号，其OPE编码与其序号相等；而大于等于"3"的节点序号，其OPE编码对应于其中序遍历的序号。以"4"为例，encoding(4)=[01]10=6，其中序遍历(LRF)的值也是6。应用该结论，可以得到其新的编码值，填于上表中的'encoding_new'中。

   基于此，可以确定对于一个编码集的调整策略：分析两种算法可以发现，影响插入操作的编码策略的复杂度依赖于树的高度，改进的mOPE方法维护了树高与编码长度，但是省略了平衡二叉树的AVL算法步骤，极大降低了计算复杂度，取而代之的是只需要判断哪些节点需要调整。

   而调整的策略取决于例子中类似于"3"的值，其意义在于：对于已插入的不重复的n个条目，二叉树的最小高度：$h_{min} = logn+1$：

   • 对于前$h_{min}$条数据，其OPE编码值与自身相等；
   • 对于第$h_{min} + 1$条数据开始，触发调整算法，构造中序遍历，得到其编码值。

.4 算法效率分析

mOPE算法与改进的mOPE算法其运算过程可分为两个步骤：第一是计算OPE编码并插入，第二是触发调整。

而两种算法由于调整策略的不同，其编码结果不同，编码效率也不同。对于步骤一，其操作的时间复杂度都是对数级别$O(logn)$，而对于步骤二，mOPE算法需要调用平衡二叉树构造函数AVL，其时间复杂度为$O(logn)$，最坏条件下从根节点触发平衡操作，调整需要遍历所有节点，其复杂度为$O(n)$；对于改进的mOPE算法，其触发操作取决于当前插入路径大于完全二叉树的高度，其值越大，触发的概率越低，平均概率远低于AVL。