Journal ArticleVeil: A Storage and Communication Efficient Volume-Hiding AlgorithmHan, Shanshan; Chakraborty, Vishal; Goodrich, Michael T; Mehrotra, Sharad; Sharma, Shantanu<p>This paper addresses volume leakage (i.e., leakage of the number of records in the answer set) when processing keyword queries in encrypted key-value (KV) datasets. Volume leakage, coupled with prior knowledge about data distribution and/or previously executed queries, can reveal both ciphertexts and current user queries. We develop a solution to prevent volume leakage, entitled Veil, that partitions the dataset by randomly mapping keys to a set of equi-sized buckets. Veil provides a tunable mechanism for data owners to explore a trade-off between storage and communication overheads. To make buckets indistinguishable to the adversary, Veil uses a novel padding strategy that allow buckets to overlap, reducing the need to add fake records. Both theoretical and experimental results show Veil to significantly outperform existing state-of-the-art.</p>ACM2023-12-0810523002Proceedings of the ACM on Management of Data141 to 272836-6573https://doi.org/10.1145/36267592245372; 2212129National Science Foundation