Post-Quantum Threshold Ring Signature Applications from VOLE-in-the-Head

Abstract

We propose efficient, post-quantum threshold ring signatures constructed from one-wayness of AES encryption and the VOLE-in-the-Head zero-knowledge proof system. Our scheme scales efficiently to large rings and extends the linkable ring signatures paradigm. We define and construct key-binding deterministic tags to achieve linkability. We then extend our threshold ring signatures to realize post-quantum anonymous ledger transactions in the spirit of Monero. Finally, our deterministic tags also enable succinct aggregation using approximate lower bound arguments of knowledge; this allows us to achieve succinct (approximate) multi-signatures without SNARKs. Our constructions assume symmetric key primitives only.