2018/01/29 by Luca Calderoni, Paolo Palmieri, Dario Maio · 1 citation
Computer Science · #Caching and Content Delivery #Cryptography and Data Security #Internet Traffic Analysis and Secure E-voting #Bloom filter #Computer science #Probabilistic logic #Hash function #Theoretical computer science #Homomorphic encryption #Cryptography #Cryptographic primitive #Cryptographic protocol #Filter (signal processing) #Data mining #Encryption #Algorithm #Computer security #Artificial intelligence
paper · doi:10.1109/tifs.2018.2799486
openalex publication_date 2018/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
The classical Bloom filter data structure is a crucial component of hundreds of cryptographic protocols. It has been used in privacy preservation and secure computation settings, often in conjunction with the (somewhat) homomorphic properties of ciphers such as Paillier's. In 2014, a new data structure extending and surpassing the capabilities of the classical Bloom filter has been proposed. The new primitive, called spatial Bloom filter (SBF) retains the hash-based membership-query design of the Bloom filter, but applies it to elements from multiple sets. Since its introduction, the SBF has been used in the design of cryptographic protocols for a number of domains, including location privacy and network security. However, due to the complex nature of this probabilistic data structure, its properties had not been fully understood. In this paper, we address this gap in knowledge and we fully explore the probabilistic properties of the SBF. In doing so, we define a number of metrics (such as emersion and safeness) useful in determining the parameters needed to achieve certain characteristics in a filter, including the false positive probability and inter-set error rate. This will in turn enable the design of more efficient cryptographic protocols based on the SBF, opening the way to their practical application in a number of security and privacy settings.