k-out-of-n Proofs and Applications to Privacy-Preserving Cryptocurrencies

Cryptocurrencies enable transactions among mutually distrustful users. While UTXO-based cryptocurrencies offer mature solutions achieving strong privacy and supporting multi-receiver transfers, account-based cryptocurrencies currently lack practical solutions that simultaneously guarantee these properties.

To close this gap, we propose a generic framework for account-based cryptocurrencies that attains strong privacy and supports multi-receiver transfers, and then give a practical instantiation called Anonymous PGC. Our system also outperforms in efficiency: for a 64-sized anonymity set and 8 receivers, Anonymous PGC achieves 2.4$\times$ faster transaction generation, 5.7$\times$ faster verification, and 2.2$\times$ reduction in transaction size compared to state-of-the-art Anonymous Zether (IEEE S&P 2021), which offers only weak privacy and no multi-receiver support.

At the core of Anonymous PGC are two novel zero-knowledge proofs of partial knowledge. First, we generalize the Groth-Kohlweiss (GK) $1$-out-of-$n$ proof (EUROCRYPT 2015) to the $k$-out-of-$n$ case, resolving an open problem regarding its generalization. Particularly, the obtained proof lends itself to seamlessly solder with range proofs, yielding an efficient $k$-out-of-$n$ range proof that demonstrates $k$ witnesses among $n$ instances lie in specific ranges. Second, we extend the Attema-Cramer-Fehr (ACF) $k$-out-of-$n$ proof (CRYPTO 2021) to support distinct group homomorphisms, boosting its expressiveness while slashing both prover and verifier complexities from quadratic to linear. We believe these proofs are of independent interest in broader privacy-preserving applications.