Paper 2021/327

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

Matteo Campanelli and Mathias Hall-Andersen


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.

Note: Mention new curve in abstract.

Available format(s)
Cryptographic protocols
Publication info
Contact author(s)
matteo campanelli @ gmail com
matteo @ cs au dk
ma @ cs au dk
2021-12-21: last of 2 revisions
2021-03-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Matteo Campanelli and Mathias Hall-Andersen},
      title = {Veksel: Simple, Efficient, Anonymous Payments with Large Anonymity Sets from Well-Studied Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2021/327},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.