Encrypted and Compressed Key-Value Store With Pattern-Analysis Security in Cloud Systems

With the increasing concern about data privacy and data explosion, some encrypted and compressed key-value (KV) stores have been proposed. A remarkable way to combine encryption and compression is to pack KV pairs into packs, and then compress and encrypt each pack separately. Recent research has shown that even if the data is encrypted, adversaries can still use the leaked information about data length and access frequency to launch pattern-analysis attacks. For this problem, some schemes have been proposed to protect the length and frequency distribution of packs. However, existing solutions protect such information at the cost of high storage and bandwidth overhead. In this paper, we propose an encrypted and compressed KV store with pattern-analysis security, which can resist pattern-analysis attacks with minimal overhead. We first devise a secure KV pair packing scheme, which guarantees pack length security with bounded storage overhead. Then we propose a K-indistinguishable pack frequency smoothing scheme. It can protect the distribution of pack frequency with minimal bandwidth overhead. We formally analyze the security of our design and implement our proposed secure KV storage system on Redis and RocksDB. Performance evaluation results demonstrate that our design minimizes the overhead of achieving pattern analysis security.