Light clients are gaining increasing attention in the literature since they obviate the need for users to set up dedicated blockchain full nodes. While the literature features a number of light client instantiations, most light client protocols optimize for long offline phases and implicitly assume that the block headers to be verified are signed by highly dynamic validators.In this paper, we show that (i) most light clients are rarely offline for more than a week, and (ii) validators are unlikely to drastically change in most permissioned blockchains and in a number of permissionless blockchains, such as Cosmos and Polkadot. Motivated by these findings, we propose a novel practical system that optimizes for such realistic assumptions and achieves minimal communication and computational costs for light clients when compared to existing protocols. By means of a prototype implementation of our solution, we show that our protocol achieves a reduction by up to 90 and 40000× (respectively) in end-to-end latency and up to 1000 and 10000× (respectively) smaller proof size when compared to two state-of-the-art light client instantiations from the literature.

Mix networks are a well-known technique to hide communication metadata, but incur a high overhead especially in group communication settings. This hinders their adoption in real-world usage, as group communication makes up a big part of modern communication patterns. In this paper, we introduce "PolySphinx", a mix format that is a step towards efficient anonymous multicasting and allows a mix node to replicate the message payload to multiple recipients. We prove that PolySphinx does not compromise on the anonymity offered to users, while considerably reducing the latency of group messages: In a group with 25 members, the average latency drops from 6.1s using the state-of-the-art Rollercoaster approach to 4.1s using PolySphinx.

Onion routing and mix networks are a central technology to enable anonymous communication on the Internet. As such, a large number of protocols and model variants have been explored in the field, which offer differing levels of privacy, exhibit vulnerabilities, or even supersede each other. These factors make discovering the appropriate formalization for new developments difficult, and some model variants have not been formalized at all. We address this issue by creating one parametrized framework that encompasses the onion routing and mix network models and functionalities with a global adversary in the related work. In doing so, we create a categorization of the variants of onion routing models in use in the related work and map common OR and mix network protocols to their variants. For each identified variant: Our framework offers i) an ideal functionality in the Universal Composability framework, and ii) game-based properties that imply realization of the ideal functionality when a protocol satisfies them. In effect, our framework both unifies and extends previous formalization efforts in the field.

Onion routing and mix networks are fundamental concepts to provide users with anonymous access to the Internet. Various corresponding solutions rely on the Sphinx packet format. However, flaws in Sphinx's underlying proof strategy were found recently. It is thus currently unclear which guarantees Sphinx actually provides, and, even worse, there is no suitable proof strategy available. In this paper, we restore the security foundation for all these works by building an analytical framework for Sphinx. We discover that the previously-used Decisional Diffie-Hellman (DDH) assumption is insufficient for a security proof and show that the Gap Diffie-Hellman (GDH) assumption is required instead. We apply it to prove that a slightly adapted version of the Sphinx packet format is secure under the GDH assumption. We are thus, to the best of our knowledge, the first to provide a detailed, in-depth security proof for Sphinx that holds. Our adaptations to Sphinx are necessary, as we demonstrate with an attack on sender privacy that would otherwise be possible in Sphinx's adversary model.

A longstanding problem in computer privacy is that of data anonymization. One common approach is to present a query interface to analysts, and anonymize on a query-by-query basis. In practice, this approach often uses a standard database back end, and presents the query semantics of the database to the analyst.

After several years of research on onion routing, Camenisch and Lysyanskaya, in an attempt at rigorous analysis, defined an ideal functionality in the universal composability model, together with properties that protocols have to meet to achieve provable security. A whole family of systems based their security proofs on this work. However, analyzing HORNET and Sphinx, two instances from this family, we show that this proof strategy is broken. We discover a previously unknown vulnerability that breaks anonymity completely, and explain a known one. Both should not exist if privacy is proven correctly.In this work, we analyze and fix the proof strategy used for this family of systems. After proving the efficacy of the ideal functionality, we show how the original properties are flawed and suggest improved, effective properties in their place. Finally, we discover another common mistake in the proofs. We demonstrate how to avoid it by showing our improved properties for one protocol, thus partially fixing the family of provably secure onion routing protocols.

Abstract Many anonymous communication networks (ACNs) with different privacy goals have been developed. Still, there are no accepted formal definitions of privacy goals, and ACNs often define their goals ad hoc. However, the formal definition of privacy goals benefits the understanding and comparison of different flavors of privacy and, as a result, the improvement of ACNs. In this paper, we work towards defining and comparing privacy goals by formalizing them as privacy notions and identifying their building blocks. For any pair of notions we prove whether one is strictly stronger, and, if so, which. Hence, we are able to present a complete hierarchy. Using this rigorous comparison between notions, we revise inconsistencies between the existing works and improve the understanding of privacy goals.

The privacy of users in wireless mesh networks is threatened by attackers that trace the flow of packets through the network or trace users' movements within the network. Untraceable Linear Network Coding, a scheme to provide flow and movement untraceability, suggests to recode messages based on a specified matrix. However, the advantage an attacker gains by knowing this encoding strategy and the routing mechanism is not discussed. Hence, although claimed otherwise packet flows and movement of users might be traceable when the Untraceable Linear Network Coding Scheme is used. In this paper, we investigate this open point and introduce an attack based on the knowledge of the coding scheme and routing. We show the success of our polynomial time attack in a simulation: For most realistic parameters the attacker can trace flows in the network to the receiver's mesh node with a success rate of 80% or more. Additionally, we discuss countermeasures to reinforce the protection of the network coding scheme.