Cryptology ePrint Archive: Report 2020/688

Lin2-Xor Lemma and Log-size Linkable Ring Signature

Anton A. Sokolov

Abstract: In this paper we introduce a novel method for constructing an efficient linkable ring signature without a trusted setup in a group where decisional Diffie-Hellman problem is hard and no bilinear pairings exist. Our linkable ring signature is logarithmic in the size of the signer anonymity set, its verification complexity is linear in the anonymity set size and logarithmic in the signer threshold. A range of the recently proposed setup-free logarithmic size signatures is based on the commitment-to-zero proving system by Groth and Kohlweiss or on the Bulletproofs inner-product compression method by Bünz et al. In contrast, we construct our signature from scratch using the Lin2-Xor and Lin2-Selector lemmas that we formulate and prove here. With these lemmas we construct an n-move public coin special honest verifier zero-knowledge membership proof protocol and instantiate the protocol in the form of a general-purpose setup-free signer-ambiguous linkable ring signature in the random oracle model.

Category / Keywords: applications / ring signature, linkable ring signature, log-size signature, membership proof, signer-ambiguity, zero- knowledge, disjunctive proof

Date: received 9 Jun 2020, last revised 2 Oct 2020

Contact author: acmxddk at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20201002:234044 (All versions of this report)

Short URL: ia.cr/2020/688