Transport layer data leaks metadata unintentionally - such as who communicates with whom. While tools for strong transport layer privacy exist, they have adoption obstacles, including performance overheads incompatible with mobile devices. We posit that by changing the objective of metadata privacy for all traffic, we can open up a new design space for pragmatic approaches to transport layer privacy. As a first step in this direction, we propose using techniques from information flow control and present a principled approach to constructing formal models of systems with metadata privacy for some, deniable, traffic. We prove that deniable traffic achieves metadata privacy against strong adversaries- this constitutes the first bridging of information flow control and anonymous communication to our knowledge. Additionally, we show that existing state-of-the-art protocols can be extended to support metadata privacy, by designing a novel protocol for deniable instant messaging (DenIM), which is a variant of the Signal protocol. To show the efficacy of our approach, we implement and evaluate a proof-of-concept instant messaging system running DenIM on top of unmodified Signal. We empirically show that the DenIM on Signal can maintain low-latency for unmodified Signal traffic without breaking existing features, while at the same time supporting deniable Signal traffic.

This work proposes a novel design for secure cloud storage systems using a third party to meet three seemingly opposing demands: reduce storage requirements on the cloud, protect against erasures (data loss), and maintain confidentiality of the data. More specifically, we achieve storage cost reductions using data deduplication without requiring system users to trust that the cloud operates honestly. We analyze the security of our scheme against honest-but-curious and covert adversaries that may collude with multiple parties and show that no novel sensitive information can be inferred, assuming random oracles and a high min-entropy data source. We also provide a mathematical analysis to characterize its potential for compression given the popularity of individual chunks of data and its overall erasure protection capabilities. In fact, we show that the storage cost of our scheme for a chunk with r replicas is O(log(r)/r), while deduplication without security or reliability considerations is O(1/r), i.e., our added cost for providing reliability and security is only O(log(r)). We provide a proof of concept implementation to simulate performance and verify our analytical results.

Proximity testing is at the core of several Location-Based Services (LBS). Despite a series of reported and confirmed abuses, modern LBSs still demand their clients to disclose their locations in plain in order to preform location proximity testing. This works aims at enhancing proximity testing with privacy. We design CatNap a novel protocol that (1) implements precise Euclidean distance matching; (2) allows matching even if the clients are not online at the same time (the "napping party" feature); (3) is secure against active adversaries (malicious actors that corrupt up to one party); (4) makes black-box use of generic Multi-Party Computation techniques (any future improvement of the underlying building blocks will also boost CatNap); and (5) is efficient: servers run with about 0.03 seconds of CPU time and 5.6MB of communication, while clients perform only a small number of Boolean operations and need just 51 bytes of communication.

This paper proposes Yggdrasil, a protocol for privacy-aware dual data deduplication in multi-client settings. Yggdrasil is designed to reduce cloud storage space while safeguarding the privacy of clients’ data. This is achieved by exploiting a ‘dual’ setting, where both the cloud and the clients store a fraction of the data. Yggdrasil combines two innovative techniques to achieve this goal. First, generalized deduplication, an emerging solution to reduce data footprint; second, non- deterministic lightweight transformations that ensure a high level of privacy while improving the degree of cross-user data compression in the cloud. Our client preprocessing guarantees that an honest-but-curious cloud storage provider faces a high degree of uncertainty in determining the original clients’ data. We introduce an uncertainty metric to measure the privacy of the client’s outsourced data and three compression metrics to investigate the performance of Yggdrasil. Our experiments with a dataset of DVI files show that Yggdrasil achieves an overall compression rate of 43%, which means that Yggdrasil can represent the same database using less than half of the original space. Moreover, for the same experiment clients only store 17% of the original data, the cloud hosts the remaining 26%, and the client preprocessing ensures each outsourced fragment has 10293possible original strings. Higher uncertainty is possible, but reduces the cloud’s compression capability.

As messaging applications are becoming increasingly popular, it is of utmost importance to analyze their security and mitigate existing weaknesses. This paper focuses on one of the most acclaimed messaging applications: Signal. Signal is a protocol that provides end-to-end channel security, forward secrecy, and post-compromise security. These features are achieved thanks to a key-ratcheting mechanism that updates the key material at every message. Due to its high security impact, Signal's key-ratcheting has recently been formalized, along with an analysis of its security. In this paper, we revisit Signal, describing some attacks against the original design and proposing SAID: Signal Authenticated and IDentity-based. As the name indicates, our protocol relies on an identity-based setup, which allows us to dispense with Signal's centralized server. We use the identity-based long-term secrets to obtain persistent and explicit authentication, such that SAID achieves higher security guarantees than Signal. We prove the security of SAID not only in the Authenticated Key Exchange (AKE) model (as done by previous work), but also in the Authenticated and Confidential Channel Establishment (ACCE) model, which we adapted and redefined for SAID and asynchronous messaging protocols in general into a model we call identity-based Multistage Asynchronous Messaging (iMAM). We believe our model to be more faithful in particular to the true security of Signal, whose use of the message keys prevents them from achieving the composable guarantee claimed by previous analysis.

Homomorphic authenticators (HAs) enable a client to authenticate a large collection of data elements and outsource them, along with the corresponding authenticators, to an untrusted server. At any later point, the server can generate a short authenticator vouching for the correctness of the output y of a function f computed on the outsourced data, i.e. . The notion of HAs studied so far, however, only supports executions of computations over data authenticated by a single user. Motivated by realistic scenarios in which large datasets include data provided by multiple users, we study the concept of multi‐key homomorphic authenticators. In a nutshell, multi‐key HAs are like HAs with the extra feature of allowing the holder of public evaluation keys to compute on data authenticated under different secret keys. In this paper, we introduce and formally define multi‐key HAs. Secondly, we propose a construction of a multi‐key homomorphic signature based on standard lattices and supporting the evaluation of circuits of bounded polynomial depth. Thirdly, we provide a construction of multi‐key homomorphic MACs based only on pseudorandom functions and supporting the evaluation of low‐degree arithmetic circuits.

Abstract Ridesharing is revolutionizing the transportation industry in many countries. Yet, the state of the art is based on heavily centralized services and platforms, where the service providers have full possession of the users’ location data. Recently, researchers have started addressing the challenge of enabling privacy-preserving ridesharing. The initial proposals, however, have shortcomings, as some rely on a central party, some incur high performance penalties, and most do not consider time preferences for ridesharing. TOPPool encompasses ridesharing based on the proximity of end-points of a ride as well as partial itinerary overlaps. To achieve the latter, we propose a simple yet powerful reduction to a private set intersection on trips represented as sets of consecutive road segments. We show that TOPPool includes time preferences while preserving privacy and without relying on a third party. We evaluate our approach on real-world data from the New York’s Taxi & Limousine Commission. Our experiments demonstrate that TOPPool is superior in performance over the prior work: our intersection-based itinerary matching runs in less than 0.3 seconds for reasonable trip length, in contrast, on the same set of trips prior work takes up to 10 hours.

Authentication in wireless communications often depends on the physical proximity to a location. Distance-bounding (DB) protocols are cross-layer authentication protocols that are based on the round-trip-time of challenge-response exchanges and can be employed to guarantee physical proximity and combat relay attacks. However, traditional DB protocols rely on the assumption that the prover (e.g., user) is in the communication range of the verifier (e.g., access point); something that might not be the case in multiple access control scenarios in ubiquitous computing environments as well as when we need to verify the proximity of our two-hop neighbour in an ad-hoc network. In this paper, we extend traditional DB protocols to a two-hop setting, i.e., when the prover is out of the communication range of the verifier and thus, they both need to rely on an untrusted in-between entity in order to verify proximity. We present a formal framework that captures the most representative classes of existing DB protocols and provide a general method to extend traditional DB protocols to the two-hop case (three participants). We analyze the security of two-hop DB protocols and identify connections with the security issues of the corresponding one-hop case. Finally, we demonstrate the correctness of our security analysis and the efficiency of our model by transforming five existing DB protocols to the two-hop setting and we evaluate their performance with simulated experiments.

An emerging direction for authenticating people is the adoption of biometric authentication systems. Biometric credentials are becoming increasingly popular as a means of authenticating people due to the wide range of advantages that they provide with respect to classical authentication methods (e.g., password-based authentication). The most characteristic feature of this authentication method is the naturally strong bond between a user and her biometric credentials. This very same advantageous property, however, raises serious security and privacy concerns in case the biometric trait gets compromised. In this article, we present the most challenging issues that need to be taken into consideration when designing secure and privacy-preserving biometric authentication protocols. More precisely, we describe the main threats against privacy-preserving biometric authentication systems and give directions on possible countermeasures in order to design secure and privacy-preserving biometric authentication protocols.

Authentication for resource-constrained devices is seen as one of the major challenges in current wireless communication networks. The HB+ protocol performs device authentication based on the learning parity with noise (LPN) problem and simple computational steps, that renders it suitable for resource-constrained devices such as radio frequency identification (RFID) tags. However, it has been shown that the HB+ protocol as well as many of its variants are vulnerable to a simple man-in-the-middle attack. We demonstrate that this attack could be mitigated using physical layer measures from distance-bounding and simple modifications to devices' radio receivers. Our hybrid solution (HB+DB) is shown to provide both effective distance-bounding using a lightweight HB+-based response function, and resistance against the man-in-the-middle attack to HB+. We provide experimental evaluation of our results as well as a brief discussion on practical requirements for secure implementation.