平均复杂度理想安全的保序加密

摘要

实施例提供了对平均复杂度的数据的理想安全的保序加密(OPE)，从而允许处理加密的数据(例如，在数据库服务器处响应于接收到查询)。具体的实施例通过按照已经可用于数据库的、现有压缩字典所保持的顺序来处理明文，来实现高加密效率。加密是基于对n个节点的二叉搜索树的使用，以构造具有Ω(n)复杂度，甚至在平均情况下具有O(n)复杂度，的保序加密方案。通过利用被证明的二叉搜索树的高度倾向于紧紧围绕O(log n)，计算密集型更新(这使得常规OPE对于理想安全变得不切实际)的概率被大大减少。在包括n个元素的列存储内存数据库架构的上下文中描述利用这样的加密方案的实施例。根据实施例的OPE与可调整的加密方式兼容。