Light-weight and secure aggregation protocols based on Bloom filters

摘要

In this paper we present a light-weight data aggregation protocol based on probabilistic data structure used for representing a subset of elements called Bloom filter. Our construction is optimal (up to a small multiplicative constant) in terms of the size of the aggregated data representation. Moreover, all necessary operations have minimal computational and memory requirements (no asymmetric cryptography is used) and provides data confidentiality in a model with an adversary with moderate capabilities. This protocol is adequate for systems of very constrained devices (like sensors) and is based solely on Bloom filters. Finally, we present two modifications of the basic protocol that can provide immunity against substantially stronger models of adversaries for the price of slightly more complex computations and increased size of the transmitted data. The security results of our protocol are mainly based on analysis of some properties of Bloom filters. We first investigate how much information about the number of represented elements can be learned by an external observer given a Bloom filter (or a part of it). The information leakage is expressed in terms of (α,β)-indistinguishability notion. We believe that this algorithm is quite general and can be applied for security analysis of other communication protocols based on Bloom filters.