Cryptology ePrint Archive: Report 2018/107

Towards Practical Lattice-Based One-Time Linkable Ring Signatures

Carsten Baum and Huang Lin and and Sabine Oechsner

Abstract: Ring signatures, as introduced by Rivest, Shamir, and Tauman (Asiacrypt ’01), allow to generate a signature for a message on be half of an ad-hoc set of parties. To sign a message, only the public keys must be known and these can be generated independently. It is furthermore not possible to identify the actual signer based on the signature. Ring signatures have recently gained attention due to their applicability in the construction of practical anonymous cryptocurrencies, where they are used to secure transactions while hiding the identity of the actual spender. To be applicable in that setting, ring signatures must allow to determine when a party signed multiple transactions, which is done using a property called linkability. This work presents a linkable ring signature scheme constructed from a lattice-based collision-resistant hash function. We follow the idea of existing schemes which are secure based on the hardness of the discrete logarithm problem, but adapt and optimize ours to the lattice setting. In comparison to other designs for (lattice-based) linkable ring signatures, our approach avoids the standard solution for achieving linkability, which involves proofs about correct evaluation of a pseudorandom function using heavy zero-knowledge machinery.

Category / Keywords: public-key cryptography / lattice-based cryptography, ring signature scheme, anonymous cryptocurrency

Original Publication (with minor differences): ICICS 2018

Date: received 29 Jan 2018, last revised 30 Jan 2019

Contact author: oechsner at cs au dk

Available format(s): PDF | BibTeX Citation

Note: bugfix linkability definition

Version: 20190130:091851 (All versions of this report)

Short URL: ia.cr/2018/107