Bitcoin and other cryptocurrencies have recently introduced support for Schnorr signatures whose cleaner algebraic structure, as compared to ECDSA, allows for simpler and more practical constructions of highly demanded ''t-of-n'' threshold signatures. However, existing Schnorr threshold signature schemes still fall short of the needs of real-world applications due to their assumption that the network is synchronous and due to their lack of robustness, i.e., the guarantee that t honest signers are able to obtain a valid signature even in the presence of other malicious signers who try to disrupt the protocol. This hinders the adoption of threshold signatures in the cryptocurrency ecosystem, e.g., in second-layer protocols built on top of cryptocurrencies.

MuSig is a multi-signature scheme for Schnorr signatures, which supports key aggregation and is secure in the plain public key model. Standard derandomization techniques for discrete logarithm-based signatures such as RFC~6979, which make the signing procedure immune to catastrophic failures in the randomness generation, are not applicable to multi-signatures as an attacker could trick an honest user into producing two different partial signatures with the same randomness, which would reveal the user's secret key.

Monero is the largest cryptocurrency with built-in cryptographic privacy features. The transactions are authenticated using zero-knowledge spend proofs, which provide a certain level of anonymity by hiding the source accounts from which the funds are sent among a set of other accounts. Due to its similarities to ring signatures, this core cryptographic component is called Ring Confidential Transactions (RingCT). Because of its practical relevance, several works attempt to analyze the security of RingCT. Since RingCT is rather complex, most of them are either informal, miss fundamental functionalities, or introduce undesirable trusted setup assumptions. Regarding efficiency, Monero currently deploys a scheme in which the size of the spend proof is linear in the ring size. This limits the ring size to only a few accounts, which in turn limits the acquired anonymity significantly and facilitates de-anonymization attacks. As a solution to these problems, we present the first rigorous formalization of RingCT as a cryptographic primitive. We then propose a generic construction of RingCT and prove it secure in our formal security model. By instantiating our generic construction with new efficient zero-knowledge proofs, we obtain Omniring, a fully-fledged RingCT scheme in the discrete logarithm setting that provides the highest concrete and asymptotic efficiency as of today. Omniring is the first RingCT scheme which 1) does not require a trusted setup or pairing-friendly elliptic curves, 2) has a proof size logarithmic in the size of the ring, and 3) allows to share the same ring between all source accounts in a transaction, thereby enabling significantly improved privacy level without sacrificing performance. Our zero-knowledge proofs rely on novel enhancements to the Bulletproofs framework (S&P 2018), which we believe are of independent interest.

Abstract 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 practicality of PathShuffle by performing path mixing in Ripple.

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.

We present a generic computational soundness result for interactive cryptographic primitives. Our abstraction of interactive primitives leverages the Universal Composability (UC) framework, and thereby offers 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. Our generic result is formulated in the CoSP framework for computational soundness proofs and supports any equivalence property expressible in CoSP 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 $$\pi $$ -calculus. This enables us to verify the untraceability of Chaum’s payment protocol in ProVerif in a computationally sound manner.

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.