Systems and methods for hiding response volume with encrypted multi-maps

Abstract

A volume hiding structured encryption system and method is provided. According to some embodiments, the system leverages the principle that a STE scheme can leak cumulative information about the query volumes of the data stored in multi-map format, while still hiding the volumes of client queries at query time. According to various examples, the system implements encryption schemes that have smaller storage and better query complexity than the current state-of-the-art, for some input distributions. According to one example, the STE schemes are adapted to the input data structure in order to improve efficiency over known approaches. Further examples includes schemes that are configured to partition a multi-map into smaller multi-maps, and use different allocation functions for different efficiency trade-offs: (i) random allocation, (ii) cuckoo-hashing allocation, and (iii) Garbled Bloom Filter allocation. In one example, the GBF construct enables a stash-less encryption scheme that hides query volumes.