  Among the most challenging traffic-analysis attacks to confound are those
leveraging the sizes of objects downloaded over the network. In this paper we
systematically analyze this problem under realistic constraints regarding the
padding overhead that the object store is willing to incur. We give algorithms
to compute privacy-optimal padding schemes -- specifically that minimize the
network observer's information gain from a downloaded object's padded size --
in several scenarios of interest: per-object padding, in which the object store
responds to each request for an object with the same padded copy; per-request
padding, in which the object store pads an object anew each time it serves that
object; and a scenario unlike the previous ones in that the object store is
unable to leverage a known distribution over the object queries. We provide
constructions for privacy-optimal padding in each case, compare them to recent
contenders in the research literature, and evaluate their performance on
practical datasets.
