An Efficient Update Algorithm for Mutable Order-Preserving Encryption

Order-preserving encryption (OPE) produces ciphertexts that preserve the numerical order of plaintexts. Many researchers have focused on designing ideally-secure OPE schemes. This security notion, known as IND-OCPA, has been shown to be achievable by the mutability of ciphertexts and interaction between a database server and a client. This implies that the ciphertexts stored on the server can be updated. Unfortunately, existing update algorithms of mutable OPE schemes are designed to generate ciphertexts uniformly regardless of the distribution of the plaintexts. This leads to inefficiency that requires frequent ciphertext updates for a certain input data pattern (e.g., sequential data). In this paper, we propose a more efficient ciphertext update algorithm that is suitable for mutable OPE schemes. This algorithm makes it possible to reduce the number of updates by considering the input pattern of encrypted data without loss of security. Our experimental results show that, when applied to existing mutable OPE schemes, our update algorithm delivers significantly improved performance on a variety of datasets.