Shanshan Han: Veil: Storage and Communication Efficient Volume Hiding Algorithms

Volume leakage is a major threat to searchable encryption and data outsourcing, where an adversary can obtain the number of values in response to a query and deduce additional information about the data, such as the query key. This work deals with the problem of volume leakage in the context of key-value datasets, and develops solutions, entitled Veil, that partition the dataset into buckets and achieve a tradeoff between the storage and communication overheads. We design bucketing approaches that consider two types adversaries, weak adversaries (i.e., passive adversaries) that passively observes the query processing, and strong adversaries (i.e., active adversaries) that knows some keys in the dataset can actively query the encrypted database to gain information about other keys in the dataset. We then propose two strategies to add fake values to buckets, including a straightforward disjoint strategy, and an advanced overlapping strategy that further reduces the storage overhead.