Cryptology ePrint Archive: Report 2021/1213

DualRing: Generic Construction of Ring Signatures with Efficient Instantiations

Tsz Hon Yuen and Muhammed F. Esgin and Joseph K. Liu and Man Ho Au and Zhimin Ding

Abstract: We introduce a novel generic ring signature construction, called DualRing, which can be built from several canonical identification schemes (such as Schnorr identification). DualRing differs from the classical ring signatures by its formation of two rings: a ring of commitments and a ring of challenges. It has a structural difference from the common ring signature approaches based on accumulators or zero-knowledge proofs of the signer index. Comparatively, DualRing has a number of unique advantages.

Considering the DL-based setting by using Schnorr identification scheme, our DualRing structure allows the signature size to be compressed into logarithmic size via an argument of knowledge system such as Bulletproofs. We further improve on the Bulletproofs argument system to eliminate about half of the computation while maintaining the same proof size. We call this Sum Argument and it can be of independent interest. This DL-based construction, named DualRing-EC, using Schnorr identification with Sum Argument has the shortest ring signature size in the literature without using trusted setup.

Considering the lattice-based setting, we instantiate DualRing by a canonical identification based on M-LWE and M-SIS. In practice, we achieve the shortest lattice-based ring signature, named DualRing-LB, when the ring size is between 4 and 2000. DualRing-LB is also 5x faster in signing and verification than the fastest lattice-based scheme by Esgin et al. (CRYPTO'19).

Category / Keywords: public-key cryptography / Ring Signature, Generic Construction, Sum Argument, M-LWE/SIS

Original Publication (with major differences): IACR-CRYPTO-2021

Date: received 16 Sep 2021

Contact author: thyuen at cs hku hk

Available format(s): PDF | BibTeX Citation

Note: Full version of the paper in CRYPTO 2021.

Version: 20210917:092520 (All versions of this report)

Short URL: ia.cr/2021/1213


[ Cryptology ePrint archive ]