Probabilistic properties of the spatial bloom filters and their relevance to cryptographic protocols

Simple item page
dc.contributor.authorCalderoni, Luca
dc.contributor.authorPalmieri, Paolo
dc.contributor.authorMaio, Dario
dc.date.accessioned2018-04-11T09:02:25Z
dc.date.available2018-04-11T09:02:25Z
dc.date.issued2018-07
dc.date.updated2018-04-10T18:31:07Z
dc.description.abstractThe 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.en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationCalderoni, 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.2799486en
dc.identifier.doi10.1109/TIFS.2018.2799486
dc.identifier.endpage1721en
dc.identifier.issn1556-6013
dc.identifier.issued7en
dc.identifier.journaltitleIEEE Transactions on Information Forensics and Securityen
dc.identifier.startpage1710en
dc.identifier.urihttps://hdl.handle.net/10468/5767
dc.identifier.volume13en
dc.language.isoenen
dc.publisherIEEEen
dc.rights© 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.en
dc.subjectSpatial Bloom Filtersen
dc.subjectData structuresen
dc.subjectCryptographic protocolsen
dc.titleProbabilistic properties of the spatial bloom filters and their relevance to cryptographic protocolsen
dc.typeArticle (peer-reviewed)en
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Calderoni_Palmieri_Maio_IEEETransInfSecFor18.pdf
Size:
446.2 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Journal Articles