Cryptology ePrint Archive: Report 2020/018

Triptych: logarithmic-sized linkable ring signatures with applications

Sarang Noether and Brandon Goodell

Abstract: Ring signatures are a common construction used to provide signer ambiguity among a non-interactive set of public keys specified at the time of signing. Unlike early approaches where signature size is linear in the size of the signer anonymity set, current optimal solutions either require centralized trusted setups or produce signatures logarithmic in size. However, few also provide linkability, a property used to determine whether the signer of a message has signed any previous message, possibly with restrictions on the anonymity set choice. Here we introduce Triptych, a family of linkable ring signatures without trusted setup that is based on generalizations of zero-knowledge proofs of knowledge of commitment openings to zero. We demonstrate applications of Triptych in signer-ambiguous transaction protocols by extending the construction to openings of parallel commitments in independent anonymity sets. Signatures are logarithmic in the anonymity set size and, while verification complexity is linear, collections of proofs can be efficiently verified in batches. We show that for anonymity set sizes practical for use in distributed protocols, Triptych offers competitive performance with a straightforward construction.

Category / Keywords: applications / ring signatures, digital signatures

Date: received 6 Jan 2020, last revised 24 Jan 2020

Contact author: sarang noether at protonmail com,surae noether@protonmail com

Available format(s): PDF | BibTeX Citation

Note: Updated to include general multi-dimensional linkable ring signature construction.

Version: 20200124:195013 (All versions of this report)

Short URL: ia.cr/2020/018


[ Cryptology ePrint archive ]