**Veksel: Simple, Efficient, Anonymous Payments with Large Anonymity Sets from Well-Studied Assumptions**

*Matteo Campanelli and Mathias Hall-Andersen*

**Abstract: **We propose Veksel, a simple generic paradigm for constructing efficient non-interactive coin mixes. The central component in our work is a concretely efficient proof $\pi_{one-many}$ that a homomorphic commitment $c^*$ is a rerandomization of a commitment $c \in \{c_1, \ldots, c_\ell \}$ without revealing $c$. We formalize anonymous account-based cryptocurrency as a universal composability functionality and show how to efficiently instantiate the functionality using $\pi_{one-many}$ in a straightforward way (Veksel). We instantiate and implement $\pi_{one-many}$ from Strong-RSA, DDH and random oracles targeting $\approx 112$ bits of security. The resulting NIZK has constant size ($|\pi_{one-many}| = 5.3 \text{KB}$) and constant proving/verification time ($\approx 90 \text{ms}$), on an already accumulated set.
Compared to Zerocashâ€”which offers comparable marginal verification cost and an anonymity set of every existing transactionâ€”our transaction are larger ($6.2$ KB) and verification is slower. On the other hand, Veksel relies on more well-studied assumptions, does not require an expensive trusted setup for proofs and is arguably simpler (from an implementation standpoint). Additionally we think that $\pi_{one-many}$ might be interesting in other applications, e.g. proving possession of some credential posted on-chain.
The efficiency of our concrete NIZK relies on a new Ristretto-friendly elliptic curve, Jabberwock, that is of independent interest: it can be used to efficiently prove statements on "committments on commitments" in Bulletproofs.

**Category / Keywords: **cryptographic protocols / payments, UC, zero-knowledge ,accumulators ,implementation

**Date: **received 11 Mar 2021, last revised 12 Mar 2021

**Contact author: **matteo at cs au dk, ma at cs au dk

**Available format(s): **PDF | BibTeX Citation

**Note: **Mention new curve in abstract.

**Version: **20210312:100830 (All versions of this report)

**Short URL: **ia.cr/2021/327

[ Cryptology ePrint archive ]