Optimal Average-Complexity Ideal-Security Order-Preserving Encryption
Optimal Average-Complexity Ideal-Security Order-Preserving Encryption
复制标题
DOI：
10.1145/2660267.2660277
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
F. Kerschbaum;Axel Schröpfer
中科院分区：
文献类型：
--
作者：
F. Kerschbaum;Axel Schröpfer
保持顺序的加密允许在加密的数据库上执行多种类型的查询--包括范围查询。Popa等人。最近提出了一种理想安全的保序加密(或编码)方案，但其插入(加密)代价很高。在这篇文章中，我们提出了一个同样理想的安全的，但更有效的保序加密方案。我们的方案是受Reed关于随机二分查找树平均高度的参考工作的启发。我们证明了在均匀分布下，我们的方案将平均通信复杂度从O(Nlogn)提高到O(N)。我们的方案还与CryptDB中使用的可调加密有效地集成在一起。在我们的数据库插入实验中，我们在局域网中实现了高达81%的性能提升，在广域网中实现了95%的性能提升。
Order-preserving encryption enables performing many classes of queries -- including range queries -- on encrypted databases. Popa et al. recently presented an ideal-secure order-preserving encryption (or encoding) scheme, but their cost of insertions (encryption) is very high. In this paper we present an also ideal-secure, but significantly more efficient order-preserving encryption scheme. Our scheme is inspired by Reed's referenced work on the average height of random binary search trees. We show that our scheme improves the average communication complexity from O(n log n) to O(n) under uniform distribution. Our scheme also integrates efficiently with adjustable encryption as used in CryptDB. In our experiments for database inserts we achieve a performance increase of up to 81% in LANs and 95% in WANs.