Optimal packing for encrypted and compressed key-value stores with pattern-analysis security

Rising concerns about data privacy and volume have driven the development of encrypted and compressed key-value (KV) storage systems. To defend against pattern-analysis attacks, the length and access frequency distributions of packs should appear uniform to adversaries. The design of the packing algorithm is crucial because it determines both pack length and frequency distributions, thereby impacting the overhead for hiding pack pattern information. Existing algorithms focus on minimizing length differences, leading to large variations in pack frequency and thus causing large bandwidth overhead. In this paper, we study the optimal packing problem for encrypted and compressed KV stores, aiming to minimize the overheads for protecting both pack length and frequency information. We propose DualPacking, a two-dimensional packing algorithm with an approximation ratio that depends on the length and frequency distributions of KV pairs. We further develop an encrypted and compressed KV storage system that adapts well to dynamic updates of outsourced stores. Finally, we formally analyze the security of our design and implement it on Redis and RocksDB. Experimental results indicate that, compared to existing packing algorithms, our design reduces the bandwidth overhead by up to 25% and the storage overhead for pack length protection by 33%, confirming its superior efficiency. Copyright © 2025 IEEE.