Cryptology ePrint Archive: Report 2019/324

A Traceable Ring Signature Scheme based on Coding Theory

Pedro Branco and Paulo Mateus

Abstract: Traceable ring signatures are a variant of ring signatures which allows the identity of a user to be revealed, when it signs two different messages with respect to the same group of users. It has applications in e-voting and in cryptocurrencies, such as the well-known Monero. We propose the first traceable ring signature scheme whose security is based on the hardness of the Syndrome Decoding problem, a problem in coding theory which is conjectured to be unsolvable by both classical and quantum algorithms. To construct the scheme, we use a variant of Stern's protocol and, by applying the Fiat-Shamir transform to it in an ingenious way, we obtain a ring signature that allows traceability. We prove that the resulting protocol has the standard security properties for traceable ring signatures in the random oracle model: tag-linkability, anonymity and exculpability. As far as we know, this is the first proposal for a traceable ring signature scheme in the post-quantum setting.

Category / Keywords: cryptographic protocols / digital signatures

Original Publication (with minor differences): PQCrypto 2019

Date: received 25 Mar 2019

Contact author: pmbranco at math tecnico ulisboa pt

Available format(s): PDF | BibTeX Citation

Version: 20190329:130949 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]