DualRing: Generic Construction of Ring Signatures

The classical ring signatures for a set of public keys are constructed by computing "pseudo-signatures" (the outputs computed from the verification function) sequentially in a ring structure first and then using one signer secret key to create a real signature. These signatures together form a ring signature on behalf of .

Abe et al.  generalized this idea in a generic construction (AOS ring signature), which can be built from two types of standard signatures: Type-H (Hash-and-one-way type, e.g., RSA signature) and Type-T (Three-move type, e.g., Schnorr signature). Borromean ring signatures used the ring structure in Abe et al. to compress multiple ring signatures. Its variant is used in privacy-preserving cryptocurrency Monero.

• Abe, M., Ohkubo, M., Suzuki, K.: 1-out-of-n signatures from a variety of keys. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 415–432. Springer, Heidelberg (2002).
• Maxwell, G., Poelstra, A.: Borromean ring signatures (2015).

The major drawback of the above ring structure approach is the signature size of . Therefore, researchers used other cryptographic primitives to build ring signatures.

An accumulator allows the signer to "compress" public keys into a constant size value and there is a witness showing that the signer's public key is in the set of public keys. The advantage of the accumulator-based ring signature is the constant signature size. However, most of the existing accumulators require a trusted setup, which is often not desirable.

• Dodis, Y., Kiayias, A., Nicolosi, A., Shoup, V.: Anonymous identification in Ad Hoc groups. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 609–626. Springer, Heidelberg (2004).

Another main approach to constructing an efficient ring signature is to use a zero-knowledge proof to prove knowledge of the secret key with respect to one of the public keys in the ring. The state-of-the-art proof size is by the use of one-out-of-many proof.

Groth, J., Kohlweiss, M.: One-out-of-many proofs: or how to leak a secret and spend a coin. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 253–280. Springer, Heidelberg (2015).

1DualRing: New Generic Construction of Ring Signature

In this paper, we revisit the classical ring structure approach and design a novel dual ring structure to build a new generic construction of ring signatures. Let us first recall how a Type-T signature works and how the AOS ring signature is built on top of it.

A Type-T signature involves the following three functions in its signing (we use Schnorr signature as a running example, with a secret key , a public key and a message ): a commit function , which outputs a commitment ; a hash function , which outputs a challenge ; and a response function , which outputs a response . A Type-T signature is then . For the verification algorithm, one runs a function to reconstruct from , and then runs to check if is correct .

Now, in a Type- AOS ring signature for public keys , the signer (with index ) follows the structure in Fig. 1 , where the signer is assumed to have corresponding to . In particular, (1) the signer picks a randomness to generate via the commit function . (2) The signer uses the commitment to compute the -th challenge by the hash function . (3) For by picking a random -th response and the public key of the -th user , the signer can reconstruct the -th commitment using the function as in verification and generate the th challenge by the hash function A ring is then formed sequentially. (4) The last step is to compute from using the response function . The final ring signature is composed of a single challenge and responses

Overview of DualRing.

We now describe our novel generic construction of ring signatures called DualRing. Let and be two commutative group operations (e.g., modular multiplication and modular addition). We first modify the definition of a Type- signature as follows:

• the verification function within the verification algorithm can be divided into two functions and ( is the public key, is the challenge and is the response) such that

Using this property, we construct a ring signature with a dual-ring structure as in Fig. 2.

Particularly, for a set of public keys and a secret key , (1) the signer first picks some randomness (2) He further picks random challenges , and (3) forms an R-ring using the group operation with the functions and . (4) Then he computes as:

After that, the signer forms a C-ring using the group operation , where the "missing" challenge (5) is computed as:

where is the inverse of

As a result, the following equation is satisfied

to form the link connecting the two rings for the input message and the list of public key pk. (6) Lastly, the response is computed by running . The final ring signature is composed of a single response and challenges , in contrast of the AOS signature which is composed of a single challenge and responses .

Advantages of DualRing over the AOS Ring Signature.

The advantage of DualRing is threefold.

Firstly, the AOS ring signature is composed of a single challenge and responses, while DualRing is composed of challenges and a single response. When instantiated with cryptosystems having a small challenge size and a large response size (e.g., lattice-based cryptosystem), it leads to a significant saving in terms of signature size.

Secondly, we observe that the AOS ring signature includes the hash function in the ring structure (Fig. 1), and this makes it difficult to further shorten the signature. On the other hand, DualRing uses two separate rings with simple group operations, which allows the use of an argument of knowledge to efficiently prove the relation. We instantiate this in the discrete logarithm (DL) setting with communication complexity .

Thirdly, our DualRing, when instantiated with the Schnorr identification, has a simpler security reduction when compared to the alternative construction of the AOS ring signature. They described that "the reduction is quite costly because we may have to have at most successful rewinding simulations" and hence they did not give a full proof. On the other hand, our instantiation does not incur such security loss.

2Our Contributions

Our contributions can be summarized as follows.

• The main contribution of our paper is the introduction of the novel dual ring structure DualRing to design generic construction of ring signatures, which differs significantly from the mainstream zero-knowledge-based or accumulator-based approaches.

• DualRing consists of challenges and a single response, while the AOS ring signature consists of a single challenge and responses. This significant difference allows us to produce much shorter signatures in both DL-based and lattice-based setting.

• In the DL-based setting, the DualRing structure allows the signature size to be compressed into size, where is the number of users in the ring, by using argument of knowledge system such as Bulletproofs. We further enhance the Bulletproofs by eliminating almost half of the computation while maintaining the same proof size and thus achieve much better efficiency. We call this new argument of knowledge Sum Argument which can be of independent interest. Our resulting DualRing-EC deploying Schnorr identification scheme with Sum Argument is the shortest ring signature in the literature without using trusted setup.

• In the lattice-based setting, we instantiate DualRing by constructing a canonical identification based on M-LWE and M-SIS assumptions. DualRing-LB is the shortest lattice-based ring signature for the most practical ring sizes of 4 up to We also implement DualRing-LB and show that it is at least 5 times faster in signing and verification than the state-of-the-art fastest construction (in terms of running times of signing and verification) .