Paper 2025/113

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

James Hsin-Yu Chiang, Aarhus University
Ivan Damgård, Aarhus University
William R. Duro, University of Trento
Sunniva Engan, Norwegian University of Science and Technology
Sebastian Kolby, Aarhus University
Peter Scholl, Aarhus University
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 for signature linkability, that also enable succinct aggregation with approximate lower bound arguments of knowledge; this allows us to achieve succinct aggregation of our signatures without SNARKs. Finally, we extend our threshold ring signatures to realize post-quantum anonymous ledger transactions in the spirit of Monero. Our constructions assume symmetric key primitives only. Whilst it is common to build post-quantum signatures from the one-wayness property of AES and a post-quantum NIZK scheme, we extend this paradigm to define and construct novel security properties from AES that are useful for advanced signature applications. We introduce key-binding and pseudorandomness of AES to establish linkability and anonymity of our threshold ring signatures from deterministic tags, and similarly establish binding and hiding properties of block ciphers modeled as ideal permutations to build commitments from AES, a crucial building block for our proposed post-quantum anonymous ledger scheme.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Post-Quantum CryptographyRing SignaturesZero-Knowledge
Contact author(s)
jachiang @ cs au dk
ivan @ cs au dk
durowilliam @ gmail com
sunnibem @ gmail com
sk @ cs au dk
peter scholl @ cs au dk
History
2025-01-24: approved
2025-01-23: received
See all versions
Short URL
https://ia.cr/2025/113
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/113,
      author = {James Hsin-Yu Chiang and Ivan Damgård and William R. Duro and Sunniva Engan and Sebastian Kolby and Peter Scholl},
      title = {Post-Quantum Threshold Ring Signature Applications from {VOLE}-in-the-Head},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/113},
      year = {2025},
      url = {https://eprint.iacr.org/2025/113}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.