Martin Beck

Christiane Kuhn, Martin Beck, Thorsten Strufe

The recent SARS-CoV-2 pandemic gave rise to management approaches using mobile apps for contact tracing. The corresponding apps track individuals and their interactions, to facilitate alerting users of potential infections well before they become infectious themselves. Naive implementation obviously jeopardizes the privacy of health conditions, location, activities, and social interaction of its users. A number of protocol designs for colocation tracking have already been developed, most of which claim to function in a privacy preserving manner. However, despite claims such as "GDPR compliance", "anonymity", "pseudonymity" or other forms of "privacy", the authors of these designs usually neglect to precisely define what they (aim to) protect. We make a first step towards formally defining the privacy notions of proximity tracing services, especially with regards to the health, (co-)location, and social interaction of their users. We also give a high-level intuition of which protection the most prominent proposals can and cannot achieve. This initial overview indicates that all proposals include some centralized services, and none protects identity and (co-)locations of infected users perfectly from both other users and the service provider.

Christiane Kuhn, Martin Beck, Thorsten Strufe

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.

Christiane Kuhn, Martin Beck, Stefan Schiffner et al.

Many anonymous communication networks (ACNs) with different privacy goals have been developed. However, there are no accepted formal definitions of privacy and ACNs often define their goals and adversary models ad hoc. However, for the understanding and comparison of different flavors of privacy, a common foundation is needed. In this paper, we introduce an analysis framework for ACNs that captures the notions and assumptions known from different analysis frameworks. Therefore, we formalize privacy goals as notions and identify 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. Further, we show how to add practical assumptions, e.g. regarding the protocol model or user corruption as options to our notions. This way, we capture the notions and assumptions of, to the best of our knowledge, all existing analytical frameworks for ACNs and are able to revise inconsistencies between them. Thus, our new framework builds a common ground and allows for sharper analysis, since new combinations of assumptions are possible and the relations between the notions are known.

Martin Beck, Florian Dumpert, Joerg Feuerhake

In the first half of 2018, the Federal Statistical Office of Germany (Destatis) carried out a "Proof of Concept Machine Learning" as part of its Digital Agenda. A major component of this was surveys on the use of machine learning methods in official statistics, which were conducted at selected national and international statistical institutions and among the divisions of Destatis. It was of particular interest to find out in which statistical areas and for which tasks machine learning is used and which methods are applied. This paper is intended to make the results of the surveys publicly accessible.

Kilian Becher, Martin Beck, Thorsten Strufe

Benchmarking is an important measure for companies to investigate their performance and to increase efficiency. As companies usually are reluctant to provide their key performance indicators (KPIs) for public benchmarks, privacy-preserving benchmarking systems are required. In this paper, we present an enhanced privacy-preserving benchmarking protocol that is based on homomorphic encryption. It enables cloud-based KPI comparison including the statistical measures mean, variance, median, maximum, best-in-class, bottom quartile, and top quartile. The theoretical and empirical evaluation of our benchmarking system underlines its practicability. Even under worst-case assumptions regarding connection quality and asymmetric encryption key-security, it fulfils the performance requirements of typical KPI benchmarking systems.

Alexander Senier, Martin Beck, Thorsten Strufe

One single error can result in a total compromise of all security in today's large, monolithic software. Partitioning of software can help simplify code-review and verification, whereas isolated execution of software-components limits the impact of incorrect implementations. However, existing application partitioning techniques are too expensive, too imprecise, or involve unsafe manual steps. An automatic, yet safe, approach to dissect security protocols into component-based systems is not available. We present a method and toolset to automatically segregate security related software into an indefinite number of partitions, based on the security guarantees required by the deployed cryptographic building blocks. As partitioning imposes communication overhead, we offer a range of sound performance optimizations. Furthermore, by applying our approach to the secure messaging protocol OTR, we demonstrate its applicability and achieve a significant reduction of the trusted computing base. Compared to a monolithic implementation, only 29% of the partitioned protocol requires confidentiality guarantees with a process overhead comparable to common sandboxing techniques.

Do Le Quoc, Martin Beck, Pramod Bhatotia et al.

How to preserve users' privacy while supporting high-utility analytics for low-latency stream processing? To answer this question: we describe the design, implementation, and evaluation of PRIVAPPROX, a data analytics system for privacy-preserving stream processing. PRIVAPPROX provides three properties: (i) Privacy: zero-knowledge privacy guarantees for users, a privacy bound tighter than the state-of-the-art differential privacy; (ii) Utility: an interface for data analysts to systematically explore the trade-offs between the output accuracy (with error-estimation) and query execution budget; (iii) Latency: near real-time stream processing based on a scalable "synchronization-free" distributed architecture. The key idea behind our approach is to marry two existing techniques together: namely, sampling (used in the context of approximate computing) and randomized response (used in the context of privacy-preserving analytics). The resulting marriage is complementary - it achieves stronger privacy guarantees and also improves performance, a necessary ingredient for achieving low-latency stream analytics.

Stefanie Roos, Martin Beck, Thorsten Strufe

Friend-to-friend (F2F) overlays, which restrict direct communication to mutually trusted parties, are a promising substrate for privacy-preserving communication due to their inherent membership-concealment and Sybil-resistance. Yet, existing F2F overlays suffer from a low performance, are vulnerable to denial-of-service attacks, or fail to provide anonymity. In particular, greedy embeddings allow highly efficient communication in arbitrary connectivity-restricted overlays but require communicating parties to reveal their identity. In this paper, we present a privacy-preserving routing scheme for greedy embeddings based on anonymous return addresses rather than identifying node coordinates. We prove that the presented algorithm are highly scalalbe, with regard to the complexity of both the routing and the stabilization protocols. Furthermore, we show that the return addresses provide plausible deniability for both sender and receiver. We further enhance the routing's resilience by using multiple embeddings and propose a method for efficient content addressing. Our simulation study on real-world data indicates that our approach is highly efficient and effectively mitigates failures as well as powerful denial-of-service attacks.

Martin Beck

This paper presents new attacks against TKIP within IEEE 802.11 based networks. Using the known Beck-Tews attack, we define schemas to con- tinuously generate new keystreams, which allow more and longer arbitrary packets to be injected into the network. We further describe an attack against the Michael message integrity code, that allows an attacker to concatenate a known with an unknown valid TKIP packet such that the unknown MIC at the end is still valid for the new entire packet. Based on this, a schema to decrypt all traffic that flows towards the client is described.

Florian Kerschbaum, Martin Beck, Dagmar Schönfeld

Privacy is of the utmost importance in genomic matching. Therefore a number of privacy-preserving protocols have been presented using secure computation. Nevertheless, none of these protocols prevents inferences from the result. Goodrich has shown that this resulting information is sufficient for an effective attack on genome databases. In this paper we present an approach that can detect and mitigate such an attack on encrypted messages while still preserving the privacy of both parties. Note that randomization, e.g.~using differential privacy, will almost certainly destroy the utility of the matching result. We combine two known cryptographic primitives -- secure computation of the edit distance and fuzzy commitments -- in order to prevent submission of similar genome sequences. Particularly, we contribute an efficient zero-knowledge proof that the same input has been used in both primitives. We show that using our approach it is feasible to preserve privacy in genome matching and also detect and mitigate Goodrich's attack.

Martin Beck, Florian Kerschbaum

Consider two parties who want to compare their strings, e.g., genomes, but do not want to reveal them to each other. We present a system for privacy-preserving matching of strings, which differs from existing systems by providing a deterministic approximation instead of an exact distance. It is efficient (linear complexity), non-interactive and does not involve a third party which makes it particularly suitable for cloud computing. We extend our protocol, such that it mitigates iterated differential attacks proposed by Goodrich. Further an implementation of the system is evaluated and compared against current privacy-preserving string matching algorithms.