Probabilistic properties of the spatial bloom filters and their relevance to cryptographic protocols
Loading...
Files
Accepted version
Date
2018-07
Authors
Calderoni, Luca
Palmieri, Paolo
Maio, Dario
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE
Published Version
Abstract
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.
Description
Keywords
Spatial Bloom Filters , Data structures , Cryptographic protocols
Citation
Calderoni, L., Palmieri, P. and Maio, D. (2018) 'Probabilistic Properties of the Spatial Bloom Filters and Their Relevance to Cryptographic Protocols', IEEE Transactions on Information Forensics and Security, 13(7), pp. 1710-1721. doi: 10.1109/TIFS.2018.2799486
Link to publisher’s version
Collections
Copyright
© 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.