Tim Ruffing

I'm a computer science PhD student at Saarland University in Germany. I am co-supervised by Aniket Kate (now at Purdue University) and Dominique Schröder (now at Friedrich-Alexander University Erlangen-Nürnberg).

I work in the field of cryptographic systems and privacy-enhancing technologies. My current research focuses on crypto currencies such as Bitcoin. Previously, I also worked on censorship-resistant communication, imperfect randomness in cryptography, and the computational soundness of formal abstractions of cryptography.

Publications

PathShuffle: Mixing Credit Paths for Anonymous Transactions in Ripple

Proceedings on Privacy Enhancing Technologies, 2017(3) (PoPETs). To appear.

The I owe you (IOU) credit network Ripple is one of the most prominent alternatives in the burgeoning field of decentralized payment systems. Ripple’s path-based transactions set it apart from cryptocurrencies such as Bitcoin. Its pseudonymous nature, while still maintaining some regulatory capabilities, has motivated several financial institutions across the world to use Ripple for processing their daily transactions. Nevertheless, with its public ledger, a credit network such as Ripple is no different from a cryptocurrency in terms of weak privacy; recent demonstrative deanonymization attacks raise important concerns regarding the privacy of the Ripple users and their transactions. However, unlike for cryptocurrencies, there is no known privacy solution compatible with the existing credit networks such as Ripple.

In this paper, we present PathShuffle, the first path mixing protocol for credit networks. PathShuffle is fully compatible with the current credit networks. As its essential building block, we propose PathJoin, a novel protocol to perform atomic transactions in credit networks. Using PathJoin and the P2P mixing protocol DiceMix, PathShuffle is a decentralized solution for anonymizing path-based transactions. We demonstrate the practical- ity of PathShuffle by performing path mixing in Ripple.

Mixing Confidential Transactions: Comprehensive Transaction Privacy for Bitcoin

Tim Ruffing, Pedro Moreno-Sanchez
4th Workshop on Bitcoin and Blockchain Research (BITCOIN'17).

The public nature of the blockchain has been shown to be a severe threat for the privacy of Bitcoin users. Even worse, since funds can be tracked and tainted, no two coins are equal, and fungibility, a fundamental property required in every currency, is at risk. With these threats in mind, several privacy-enhancing technologies have been proposed to improve transaction privacy in Bitcoin. However, they either require a deep redesign of the currency, breaking many currently deployed features, or they address only specific privacy issues and consequently provide only very limited guarantees when deployed separately.

The goal of this work is to overcome this trade-off. Building on CoinJoin, we design ValueShuffle, the first coin mixing protocol compatible with Confidential Transactions, a proposed enhancement to the Bitcoin protocol to hide payment values in the blockchain. ValueShuffle ensures the anonymity of mixing participants as well as the confidentiality of their payment values even against other possibly malicious mixing participants. By combining CoinJoin with Confidential Transactions and additionally Stealth Addresses, ValueShuffle provides comprehensive privacy (payer anonymity, payee anonymity, and payment value privacy) without breaking with fundamental design principles or features of the current Bitcoin system. Assuming that Confidential Transactions will be integrated in the Bitcoin protocol, ValueShuffle makes it possible to mix funds of different value as well as to mix and spend funds in the same transaction, which overcomes the two main limitations of previous coin mixing protocols.

Switch Commitments: A Safety Switch for Confidential Transactions

Tim Ruffing, Giulio Malavolta
4th Workshop on Bitcoin and Blockchain Research (BITCOIN'17).

Cryptographic agility is the ability to switch to larger cryptographic parameters or different algorithms in the case of security doubts. This very desirable property of cryptographic systems is inherently difficult to achieve in cryptocurrencies due to their permanent state in the blockchain: for example, if it turns out that the employed signature scheme is insecure, a switch to a different scheme can only protect the outputs of future transactions but cannot fix transaction outputs already recorded in the blockchain, exposing owners of the corresponding money to risk of theft. This situation is even worse with Confidential Transactions, a recent privacy-enhancing proposal to hide transacted monetary amounts in homomorphic commitments. If an attacker manages to break the computational binding property of a commitment, he can create money out of thin air, jeopardizing the security of the entire currency. The obvious solution is to use statistically or perfectly binding commitment schemes but they come with performance drawbacks due to the need for less efficient range proofs.

In this paper, our aim is to overcome this dilemma. We introduce switch commitments, which constitute a cryptographic middle ground between computationally binding and statistically binding commitments. The key property of this novel primitive is the possibility to switch existing commitments, e.g., recorded in the blockchain, from computational bindingness to statistical bindingness if doubts in the underlying hardness assumption arise. This switch trades off efficiency for security. We provide a practical and simple construction of switch commitments by proving that ElGamal commitments with a restricted message space are secure switch commitments.

P2P Mixing and Unlinkable Bitcoin Transactions

Network and Distributed System Security Symposium 2017 (NDSS'17).

Starting with Dining Cryptographers networks (DC-nets), several peer-to-peer (P2P) anonymous communication protocols have been proposed. However, despite their strong anonymity guarantees, none of them have been employed in practice so far: Most protocols fail to simultaneously address the crucial problems of slot collisions and disruption by malicious peers, while the remaining ones handle f malicious peers with O(f²) communication rounds. We conceptualize these P2P anonymous communication protocols as P2P mixing, and present a novel P2P mixing protocol, DiceMix, that needs only four communication rounds in the best case, and 4+2f rounds in the worst case with f malicious peers. As every individual malicious peer can force a restart of a P2P mixing protocol by simply omitting his messages, we find DiceMix with its worst-case complexity of O(f) rounds to be an optimal P2P mixing solution.

On the application side, we employ DiceMix to improve anonymity in crypto-currencies such as Bitcoin. The public verifiability of their pseudonymous transactions through publicly available ledgers (or blockchains) makes these systems highly vulnerable to a variety of linkability and deanonymization attacks. We use DiceMix to define CoinShuffle++, a coin mixing protocol that enables pseudonymous peers to perform unlinkable transactions in a manner fully compatible with the current Bitcoin system. Moreover, we demonstrate the efficiency of our protocols with a proof-of-concept implementation. In our evaluation, DiceMix requires less than eight seconds to mix 50 messages (160 bits, i.e., Bitcoin addresses), while the best protocol in the literature requires almost three minutes in the same setting.

Finally, we present a deanonymization attack on existing P2P mixing protocols that guarantee termination in the presence of disruptive peers. We generalize the attack to demonstrate that no P2P mixing protocol simultaneously supports arbitrary input messages, provides anonymity, and terminates in the presence of disruptive peers. DiceMix resists this attack by requiring fresh input messages, e.g., cryptographic keys never used before.

Liar, Liar, Coins on Fire! — Penalizing Equivocation By Loss of Bitcoins

22nd Conference on Computer and Communications Security (CCS'15). ACM, 2015.

We show that equivocation, i.e., making conflicting statements to others in a distributed protocol, can be monetarily disincentivized by the use of crypto-currencies such as Bitcoin. To this end, we design completely decentralized non-equivocation contracts, which make it possible to penalize an equivocating party by the loss of its money. At the core of these contracts, there is a novel cryptographic primitive called accountable assertions, which reveals the party's Bitcoin credentials if it equivocates.

Non-equivocation contracts are particularly useful for distributed systems that employ public append-only logs to protect data integrity, e.g., in cloud storage and social networks. Moreover, as double-spending in Bitcoin is a special case of equivocation, the contracts enable us to design a payment protocol that allows a payee to receive funds at several unsynchronized points of sale, while being able to penalize a double-spending payer after the fact.

Computational Soundness for Interactive Primitives

20th European Symposium on Research in Computer Security (ESORICS'15). LNCS 9326. Springer, 2015.

We present a generic computational soundness result for interactive cryptographic primitives. Our abstraction of interactive primitives leverages the Universal Composability (UC) framework, and thereby allows us to achieve strong composability properties for our computational soundness result: Given a computationally sound Dolev-Yao model for non-interactive primitives, and given UC-secure interactive primitives, we obtain computational soundness for the combined model that encompasses both the non-interactive and the interactive primitives. This generic method supports equivalence properties such as strong secrecy and anonymity.

In a case study, we extend an existing computational soundness result by UC-secure blind signatures. We obtain computational soundness for blind signatures in uniform bi-processes in the applied π-calculus. This enables us to verify the untraceability of Chaum’s payment protocol in ProVerif in a computationally sound manner.

Secrecy without Perfect Randomness: Cryptography with (Bounded) Weak Sources

13th International Conference on Applied Cryptography and Network Security (ACNS'15). LNCS 9092. Springer, 2015.

Cryptographic protocols are commonly designed and their security proven under the assumption that the protocol parties have access to perfect (uniform) randomness. Physical randomness sources deployed in practical implementations of these protocols often fall short in meeting this assumption, but instead provide only a steady stream of bits with certain high entropy. Trying to ground cryptographic protocols on such imperfect, weaker sources of randomness has thus far mostly given rise to a multitude of impossibility results, including the impossibility to construct provably secure encryption, commitments, secret sharing, and zero-knowledge proofs based solely on a weak source. More generally, indistinguishability-based properties break down for such weak sources.

In this paper, we show that the loss of security induced by using a weak source can be meaningfully quantified if the source is bounded, e.g., for the well-studied Santha-Vazirna (SV) sources. The quantification relies on a novel relaxation of indistinguishability by a quantitative parameter. We call the resulting notion differential indistinguishability in order to reflect its structural similarity to differential privacy. More concretely, we prove that indistinguishability with uniform randomness implies differential indistinguishability with weak randomness. We show that if the amount of weak randomness is limited (e.g., by using it only to seed a PRG), all cryptographic primitives and protocols still achieve differential indistinguishability.

CoinShuffle: Practical Decrentralized Coin Mixing for Bitcoin

19th European Symposium on Research in Computer Security (ESORICS'14). LNCS 8713. Springer, 2014.

The decentralized currency network Bitcoin is emerging as a potential new way for performing financial transactions across the globe. Its use of pseudonyms towards protecting users' privacy has been an attractive feature to many of its adopters. Nevertheless, due to the inherent public nature of the Bitcoin transaction ledger, users' privacy is severely restricted to linkable anonymity, and a few Bitcoin transaction deanonymization attacks have been reported so far.

In this paper, we propose CoinShuffle, a completely decentralized Bitcoin mixing protocol that allows users to utilize Bitcoin in a truly anonymous manner. CoinShuffle is inspired from the accountable anonymous group communication protocol Dissent and enjoys several advantages over its predecessor Bitcoin mixing protocols. It does not require any (trusted, accountable or untrusted) third party and it is perfectly compatible with the current Bitcoin system. CoinShuffle introduces only a small communication overhead for its users, while it completely avoids additional anonymization fees and minimizes the computation and communication overhead for the rest of the Bitcoin system.

Computational Soundness Results for ProVerif — Bridging the Gap from Trace Properties to Uniformity

3rd Conference on Principles of Security and Trust (POST'14). LNCS 8414. Springer, 2014.

Dolev-Yao models of cryptographic operations constitute the foundation of many successful verification tools for security protocols, such as the protocol verifier ProVerif. Research over the past decade has shown that many of these symbolic abstractions are computationally sound, i.e., the absence of attacks against the abstraction entails the security of suitable cryptographic realizations. Most of these computational soundness (CS) results, however, are restricted to trace properties such as authentication, and the few promising results that strive for CS for the more comprehensive class of equivalence properties, such as strong secrecy or anonymity, either only consider a limited class of protocols or are not amenable to fully automated verification.

In this work, we identify a general condition under which CS for trace properties implies CS for uniformity of bi-processes, i.e., the class of equivalence properties that ProVerif is able to verify for the applied pi-calculus. As a case study, we show that this general condition holds for a Dolev-Yao model that contains signatures, public-key encryption, and corresponding length functions. We prove this result in the CoSP framework (a general framework for establishing CS results). To this end, we extend the CoSP framework to equivalence properties, and we show an existing embedding of the applied pi-calculus to CoSP can be re-used for uniform bi-processes. On the verification side, as analyses in ProVerif with symbolic length functions often do not terminate, we show how to combine the recent protocol verifier APTE with ProVerif. As a result, we establish a computationally sound automated verification chain for uniformity of bi-processes in the applied pi-calculus that use public-key encryption, signatures, and length functions.

Identity-Based Steganography and Its Applications to Censorship Resistance

Tim Ruffing, Jonas Schneider, Aniket Kate
6th Workshop on Hot Topics in Privacy Enhancing Technologies (HotPETs'13)

The use of public-key steganography has been proposed for several censorship-resistance systems. However, distribution of the employed public keys presents an availability, scalability, and security challenge in many of these. To mitigate this problem, we introduce the notion of identity-based steganography. In particular, we define identity-based steganographic tagging (IBST), which allows a sender to produce a steganographic tag for a recipient’s identity such that the tag can only be recognized by the intended recipient using her (identity-based) private key.
We instantiate our definition by an efficient IBST scheme, provably secure under the bilinear decisional Diffie-Hellman assumption. We find IBST to be particularly useful when the censors are able to impede distribution of cryptographic keys or break forward security by compromising system agents. As two representative applications of IBST to censorship resistance systems, we first present an efficient and dynamic solution for the key distribution problem in Collage and second, we demonstrate that IBST can improve the scalability of Message in a Bottle.