POPE: Partial Order Preserving Encoding

摘要: Recently there has been much interest in performing search queries over encrypted data to enable functionality while protecting sensitive data. One particularly efficient mechanism for executing such is order-preserving encryption/encoding (OPE) which results ciphertexts that preserve the relative order of underlying plaintexts thus allowing range and comparison be performed directly on ciphertexts. In this paper, we propose an alternative approach optimized support insert-heavy workloads as are common "big data" applications still maintaining achieving stronger security. Specifically, a new primitive called partial preserving encoding (POPE) achieves ideal OPE security with frequency hiding also leaves sizable fraction pairwise incomparable. Using only O(1) persistent $O(n^\epsilon)$ non-persistent client storage $0<\epsilon<1$, our POPE scheme provides extremely fast batch insertion consisting single round, amortized cost up $O(n^{1-\epsilon})$ queries. This improved performance makes better suited today's databases.