  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.
