SecPack: Secure Data Access for Encrypted Key-Value Stores Using Data-Packing

With the explosive growth of data, many users are outsourcing their local private data to cloud servers for encrypted key-value storage. However, recent research indicates that even if data is encrypted before being outsourced, attackers can still infer sensitive information by analyzing differences in access frequency or value length of key-value pairs. To address this issue, some studies propose sending additional dummy queries to smooth access frequency and padding key-value pairs to the same length to defend against frequency or length analysis attacks, respectively. However, the access frequency and length of key-value pairs generally vary greatly in practice. Those methods can substantially increase the bandwidth overhead of user queries and the storage overhead on the cloud. A new strategy is to combine key-value pairs into data packages, such that the differences in access frequency and length are offset between packages, thereby reducing the overhead caused by frequency smoothing and length padding. Based on this idea, we design a secure encrypted key-value storage scheme using data packing, called SecPack. SecPack combines key-value pairs into data packages and transforms the large differences in access frequency and length between the individual key-value pairs into small differences between data packages, thus achieving secure encrypted key-value storage on the cloud with low overhead. Additionally, we analyze the security of the proposed scheme and implement it on two storage backends, Redis and RocksDB. Experimental results demonstrate that SecPack can prevent attackers' access pattern attacks with lower storage and bandwidth cost.