密文数据库保序编码方法的研究与改进

不可信云计算环境下的数据隐私保护问题逐渐成为研究重点，而保护隐私的主要方法之一就是对数据库中的记录加密，但对密文进行排序、范围查询等操作较为困难。保序加密能使密文的大小顺序与明文保持一致，支持上述对密文的操作。2013年提出的mOPE(mutable Order-Preserving Encoding)可变保序编码是一种基于二叉搜索树编码的保序加密方法，支持任意的数据类型，且除了明文顺序外不泄露其他任何信息。由于保序编码可能随着插入或删除记录而变更，服务器额外开销较大。本文对此作出改进并提出cmOPE(custom and mutable Order-Preserving Encoding)方法，基于构造完全二叉搜索树来调整保序编码，降低了编码变更带来的额外开销。实验结果显示，修改了编码调整策略的mOPE方法有效地降低了服务器的计算开销，提高了对保序密文增删改的效率。

Investigation and Improvement of Order-Preserving Encoding in Encrypted Database

There is an urgent need to encrypt data in databases to protect sensitive data especially in untrustworthy cloud. But operations on encrypted data cannot be efficiently executed, such as range queries and sort operations. To resolve this problem, Order-Preserving Encryption (OPE) scheme were suggested which preserves the order of plain text. mOPE(mutable Order-Preserving Encoding) is a mutable Order-Preserving encoding scheme based on binary search tree which works on all data types with ideal security. The order-preserving codes may change by insertion or deletion, and the high frequency of codes mutation will bring additional computation overhead to the server in mOPE. This paper demonstrates a new scheme called cmOPE(custom and mutable Order-Preserving Encoding) based on complete binary search tree encoding which reduce the overhead of codes mutation.We implemented it and compared the performance between mOPE and cmOPE to show the latter is more efficient.