Spatial Bloom Filters

In this paper we compare two probabilistic data structures for association queries derived from the well-known Bloom filter: the shifting Bloom filter (ShBF), and the spatial Bloom filter (SBF). With respect to the original data structure, both variants add the ability to store multiple subsets in the same filter, using different strategies. We analyse the performance of the two data structures with respect to false positive probability, and the inter-set error probability (the probability for an element in the set of being recognised as belonging to the wrong subset). As part of our analysis, we extended the functionality of the shifting Bloom filter, optimising the filter for any non-trivial number of subsets. We propose a new generalised ShBF definition with applications outside of our specific domain, and present new probability formulas. Results of the comparison show that the ShBF provides better space efficiency, but at a significantly higher computational cost than the SBF.

Indoor localization is widely used as enabling technology for location-based services, such as advertising, indoor routing, and behavioral analysis. To keep these features available, service providers passively collect a large amount of data that may reveal strictly personal information about an individual. As an example, a timestamped mobility trace acquired in a mall may help the business owner to rearrange the user surroundings relying on a punctual analysis of the user behavior. In this paper we discuss some information processing techniques relying on probabilistic data structures designed to mitigate the user’s privacy leakage. The work is also accompanied by a case study. Our experiments were carried out using well-known networking equipment, Cisco Meraki, which is provided in combination with several primitives designed to passively infer and collect the user position in an indoor environment.

Among the possible future Internet architectures, Information Centric Networking (ICN) is the most promising one and researchers working on the Named Data Networking (NDN) project are putting efforts towards its deployment in a real scenario. To properly handle content names, the different components of an NDN network need efficient and scalable data structures. In this paper, we propose a new data structure to support the NDN forwarding procedure by replacing the current Forwarding Information Base (FIB): the Spatial Bloom Filter (SBF), a probabilistic data structure that guarantees fast lookup and efficient memory consumption. Through a set of simulations run to compare the performance of FIB and SBF, we found that the latter uses less than 5 KB of data to handle 106 queried interests, with a (negligible) probability 10^-4 of false positive events. Conversely, the FIB requires up to 2.5 GB of data in disadvantageous cases, e.g. when interests are composed of a considerable number of components.

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.

With the diffusion of the Internet of Things (IoT), computing is becoming increasingly pervasive, and different heterogeneous networks are integrated into larger systems. However, as different networks managed by different parties and with different security requirements are interconnected, security becomes a primary concern. IoT nodes, in particular, are often deployed “in the open”, where an attacker can gain physical access to the device. As nodes can be deployed in unsurveilled or even hostile settings, it is crucial to avoid escalation from successful attacks on a single node to the whole network, and from there to other connected networks. It is therefore necessary to secure the communication within IoT networks, and in particular, maintain context information private, including the network topology and the location and identity of the nodes. In this paper, we propose a protocol achieving anonymous routing between different interconnected networks, designed for the Internet of Things and based on the spatial Bloom filter (SBF) data structure. The protocol enables private communication between the nodes through the use of anonymous identifiers, which hide their location and identity within the network. As routing information is encrypted using a homomorphic encryption scheme, and computed only in the encrypted domain, the proposed routing strategy preserves context privacy, preventing adversaries from learning the network structure and topology. This, in turn, significantly reduces their ability to gain valuable network information from a successful attacks on a single node of the network, and reduces the potential for attack escalation.

As computing becomes increasingly pervasive, different heterogeneous networks are connected and integrated. This is especially true in the Internet of Things (IoT) and Wireless Sensor Networks (WSN) settings. However, as different networks managed by different parties and with different security requirements are integrated, security becomes a primary concern. WSN nodes, in particular, are often deployed "in the open", where a potential attacker can gain physical access to the device. As nodes can be deployed in hostile or difficult scenarios, such as military battlefields or disaster recovery settings, it is crucial to avoid escalation from successful attacks on a single node to the whole network, and from there to other connected networks. It is therefore crucial to secure the communication within the WSN, and in particular, maintain context information, such as the network topology and the location and identity of base stations (which collect data gathered by the sensors) private. In this paper, we propose a protocol achieving anonymous routing between different interconnected IoT or WSN networks, based on the Spatial Bloom Filter (SBF) data structure. The protocol enables communications between the nodes through the use of anonymous identifiers, thus hiding the location and identity of the nodes within the network. The proposed routing strategy preserves context privacy, and prevents adversaries from learning the network structure and topology, as routing information is encrypted using a homomorphic encryption scheme, and computed only in the encrypted domain. Preserving context privacy is crucial in preventing adversaries from gaining valuable network information from a successful attacks on a single node of the network, and reduces the potential for attack escalation.

Location aware applications that provide smart city building blocks are growing in popularity as mobile devices approach ubiquity. While the specific definition of "smart city" is still evolving, most agree that the term implies integrating communication and information technology to advance quality of life. Location-aware mobiles apps can provide many services tailored to a user's current location. Several current apps provide routing and proximity alerts for hazards, but require users to disclose locations and data owners/providers (DO) to advertise areas of interest locations. We analyze three encryption based approaches that provide granular proximity detection without openly divulging any location information. These approaches use different techniques to assure the user and DO mutual privacy while still providing proximity detection of users to defined areas of interest. We implemented the approaches, and as part of our implementation effort, extended the functionality of one of the approaches, originally designed as a generic Secure k-Nearest Neighbor approach, to align it to our specific problem domain. We compare the security and privacy guarantees, and the efficiency and accuracy of each approach. Our results can be used to choose the most applicable mutually private proximity detection (MPPD) approach for a smart city environment.

Location-aware applications are one of the biggest innovations brought by the smartphone era, and are effectively changing our everyday lives. But we are only starting to grasp the privacy risks associated with constant tracking of our whereabouts. In order to continue using location-based services in the future without compromising our privacy and security, we need new, privacy-friendly applications and protocols. In this paper, we propose a new compact data structure based on Bloom filters, designed to store location information. The spatial Bloom filter (SBF), as we call it, is designed with privacy in mind, and we prove it by presenting two private positioning protocols based on the new primitive. The protocols keep the user’s exact position private, but allow the provider of the service to learn when the user is close to specific points of interest, or inside predefined areas. At the same time, the points and areas of interest remain oblivious to the user. The two proposed protocols are aimed at different scenarios: a two-party setting, in which communication happens directly between the user and the service provider, and a three-party setting, in which the service provider outsources to a third party the communication with the user. A detailed evaluation of the efficiency and security of our solution shows that privacy can be achieved with minimal computational and communication overhead. The potential of spatial Bloom filters in terms of generality, security and compactness makes them ready for deployment, and may open the way for privacy preserving location-aware applications.

The wide availability of inexpensive positioning systems made it possible to embed them into smartphones and other personal devices. This marked the beginning of location-aware applications, where users request personalized services based on their geographic position. The location of a user is, however, highly sensitive information: the user’s privacy can be preserved if only the minimum amount of information needed to provide the service is disclosed at any time. While some applications, such as navigation systems, are based on the users’ movements and therefore require constant tracking, others only require knowledge of the user’s position in relation to a set of points or areas of interest. In this paper we focus on the latter kind of services, where location information is essentially used to determine membership in one or more geographic sets. We address this problem using Bloom Filters (BF), a compact data structure for representing sets. In particular, we present an extension of the original Bloom filter idea: the Spatial Bloom Filter (SBF). SBF’s are designed to manage spatial and geographical information in a space efficient way, and are well-suited for enabling privacy in location-aware applications. We show this by providing two multi-party protocols for privacy-preserving computation of location information, based on the known homomorphic properties of public key encryption schemes. The protocols keep the user’s exact position private, but allow the provider of the service to learn when the user is close to specific points of interest, or inside predefined areas. At the same time, the points and areas of interest remain oblivious to the user.