DualRing: Generic Construction of Ring Signatures with Efficient Instantiations

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 5$\times$ faster in signing and verification than the fastest lattice-based scheme by Esgin et al. (CRYPTO’19).

1 Introduction

Ring signatures [35] allow a signer to dynamically choose a set of public keys (including his/her own) and to sign messages on behalf of the set, without revealing who the real signer is. In addition, it is impossible to check if two signatures are issued by the same signer. Ring signatures provide anonymity and they are widely used in privacy-preserving protocols such as e-voting, whistleblowing and privacy-preserving cryptocurrencies.

Classical Ring Structure. The classical ring signatures [35] for a set of n public keys pk are constructed by computing $n-1$ “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 n signatures together form a ring signature on behalf of pk.

Abe et al. [2] 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 [33] used the ring structure in [2] to compress multiple ring signatures. Its variant is used in privacy-preserving cryptocurrency Monero.

From Accumulator to Zero-Knowledge Proof. The major drawback of the above ring structure approach is the signature size of O(n). Therefore, researchers used other cryptographic primitives to build ring signatures.

An accumulator allows the signer to “compress” n 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 [17] is the constant signature size. However, most of the existing accumulators require a trusted setup, which is often not desirable.

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 $O(\log n)$ by the use of one-out-of-many proof [22].

1.1 DualRing: 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 [2] 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, indicated inside , with a secret key $\mathsf{sk}$, a public key $\mathsf{pk}=g^\mathsf{sk}$ and a message M): a commit function A, which outputs a commitment R ; a hash function H, which outputs a challenge c ; and a response function Z, which outputs a response z . A Type-T signature is then $\sigma = (c, z)$. For the verification algorithm, one runs a function V to reconstruct R from $\sigma$ , and then runs H to check if c is correct .

Fig. 1.

Structure of the AOS ring signature from a Type-T Signature in [2].

Now, in a Type-T AOS ring signature for public keys $\mathbf{pk} = \{ \mathsf{pk}_1, \ldots , \mathsf{pk}_n\}$, the signer (with index j) follows the structure in Fig. 1, where the signer is assumed to have $\mathsf{sk}_j$ corresponding to $\mathsf{pk}_j$. In particular, the signer picks a randomness $r_j$ to generate $R_j$ via the commit function A. The signer uses the commitment $R_j$ to compute the $(j+1)$-th challenge $c_{j+1}$ by the hash function H. For $i=j+1, \ldots , n, 1, \ldots , j-1$ by picking a random $(i+1)$-th response $z_{i}$ and the public key of the (i)-th user $\mathsf{pk}_{i}$, the signer can reconstruct the (i)-th commitment $R_{i}$ using the function V as in verification and generate the $(i+1)$-th challenge $c_{i+1}$ by the hash function H. A ring is then formed sequentially. The last step is to compute $z_j$ from $\mathsf{sk}_j, c_j, r_j$ using the response function Z. The final ring signature is composed of a single challenge $c_1$ and n responses $(z_1, \ldots , z_n)$.

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

• the verification function $V(\mathsf{pk}, z, c)$ within the verification algorithm can be divided into two functions $V_1(z)$ and $V_2(\mathsf{pk}, c)$ ($\mathsf{pk}$ is the public key, c is the challenge and z 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 pk = $(\mathsf{pk}_1, \ldots , \mathsf{pk}_n)$ and a secret key $\mathsf{sk}_j$, the signer first picks some randomness $r_j$. He further picks random challenges $c_1, \ldots , c_{j-1}, c_{j+1}, \ldots , c_n$, and forms an R-ring using the group operation $\odot$ with the functions A and $V_2$. Then he computes R as:

$$\begin{aligned} R&= A(\mathsf{sk}_j; r_j) \odot \\&\qquad V_2(\mathsf{pk}_{j+1}, c_{j+1}) \odot \cdots \odot V_2(\mathsf{pk}_{n}, c_{n}) \odot V_2(\mathsf{pk}_{1}, c_{1}) \odot \cdots \odot V_2(\mathsf{pk}_{j-1}, c_{j-1}). \end{aligned}$$

After that, the signer forms a C-ring using the group operation $\otimes$, where the “missing” challenge $c_j$ is computed as:

$$\begin{aligned} c_j = H(M, \mathbf{pk}, R) \oslash c_{j+1} \oslash \cdots \oslash c_{n} \oslash c_{1} \oslash \cdots c_{j-1} \text {(where} \oslash \text {is the inverse of } \otimes ). \end{aligned}$$

As a result, the following equation is satisfied

$$\begin{aligned} c_1 \otimes \cdots \otimes c_n = H(M, \mathbf{pk}, R) \end{aligned}$$

(1)

to form the link connecting the two rings for the input message M and the list of public key $\mathbf{pk}$. Lastly, the response z is computed by running $Z (\mathsf{sk}_j, c_j, r_j)$. The final ring signature is composed of a single response z and n challenges $(c_1, \ldots , c_n)$, in contrast of the AOS signature which is composed of a single challenge $c_1$ and n responses $(z_1, \ldots z_n)$.

Fig. 2.

Structure of DualRing construction

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 n responses, while DualRing is composed of n 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 H 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 in Eq. (1). We instantiate this in the discrete logarithm (DL) setting with communication complexity $O(\log n)$.

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 in the Appendix A of [2]. They described that “the reduction is quite costly because we may have to have at most n successful rewinding simulations” and hence they did not give a full proof. On the other hand, our instantiation does not incur such security loss.

Technical Challenges. One of technical challenges we solve in this paper is to give a security proof for DualRing, as well as the Type-T AOS ring signature which has not been formally proven. Note that it has been an open problem to prove the security of the generic construction of the Type-T AOS ring signature [2] (only a security proof for the instantiation using the Schnorr signature was previously given). We solve this open problem by using canonical identification [1] (which is a three-move identification scheme that can be transformed to a Type-T signature by the Fiat-Shamir heuristic) in the construction and the security proofs. While the Type-T signature restricts the input to the hash function to include the signer’s public key, the hash function H of the AOS ring signature takes the set of public keys pk as an input. This difference hinders the use of a forgery of the AOS ring signature to break the unforegability of the Type-T signature. On the other hand, the canonical identification does not have such a restriction on the generation of the challenge. The security proof of the Type-T AOS ring signature is given in the full version of the paper.

In order to prove the security of DualRing, we further define a variant called Type-T* canonical identification, with the following properties:

• 1. the verification $V(\mathsf{pk}, z, c)$ can be divided into two algorithms $V_1(z)$ and $V_2(\mathsf{pk}, c)$ such that $V(\mathsf{pk}, z, c) = V_1(z) \odot V_2(\mathsf{pk}, c)$;

• 2. $V_1$ is additively/multiplicatively homomorphic;

• 3. given the secret key $\mathsf{sk}$ corresponding to $\mathsf{pk}$ and a challenge c, there exists a function $\mathcal {T}$ which outputs $\hat{z} = \mathcal {T}(\mathsf{sk}, c)$ such that $V_1(\hat{z}) = V_2(\mathsf{pk}, c)$;

• 4. the challenge space $\varDelta _c$ is a group.

Property 1 of Type-T* canonical identification allows us to build the R-ring as in Fig. 2. Looking ahead, Property 3 is needed in the proof of DualRing’s unforgeability to calculate $\hat{z}_i$ such that $V_1(\hat{z}_i) = V_2(\mathsf{pk}_i, c_i)$ for $i \ne j$, and then we use Property 2 to combine z with all $\hat{z}_i$’s to break the Type-T* canonical identification. Property 4 is needed in the proof of DualRing’s anonymity to make sure that the challenge $c_j$ constructed in a specific way is indistinguishable from the others. We further define a new security model for canonical identification called special impersonation, which is a combination of the security models of impersonation and special soundness. Some standard identification schemes such as Schnorr identification and GQ identification [23] are examples of Type-T* canonical identification secure against special impersonation.

1.2 Efficient Instantiations of DualRing

DualRing-EC: Logarithmic DL-based Ring Signature by Sum Argument. Having established a secure generic construction, DualRing, we try to compress the n challenges $(c_1, \ldots c_n)$ via an argument of knowledge by exploiting the following simple algebraic structure:

$$ c_1 \otimes \cdots \otimes c_n = H(M, \mathbf{pk}, R). $$

This is theoretically a new approach to construct efficient ring signatures by combining the classical ring structure approach with the argument of knowledge¹.

In the DL setting, the group operation $\otimes$ is the modular addition. We improve the Bulletproof’s inner product argument [14] into a new proof system called Sum Argument, which allows a prover to convince a verifier that he/she has the knowledge of a vector of scalars ($c_1, \ldots , c_n$) such that their summation is a public value (i.e., $H(M, \mathbf{pk}, R)$). Our Sum Argument only requires about half of the computation of Bulletproof while keeping the same proof size. We show how to obtain it by removing one of the two vectors of the inner product argument required in Bulletproof and to achieve a proof of size $O(\log n)$.

Based on DualRing, Schnorr identification and the sum argument above, we design DualRing-EC, the shortest ring signature scheme in the literature without using trusted setup, as shown in Table 1. The signature size is $O(\log (n))$. When implemented on an elliptic curve with a 256-bit modulus, DualRing-EC is at least 54% (resp., 27%, 18%) shorter than [27] for a ring size of 2 (resp. 64, 4096). Our scheme is at least 46% (resp., 64%, 67%) shorter than [29] for a ring size of 2 (resp. 64, 4096) at the same security level of 128-bit. Therefore, DualRing-EC is highly efficient and is useful for real world applications.

Table 1. $O(\log n)$-size DL-based ring signature schemes for n public keys, where p is a 256-bit prime.

DualRing-LB: Shortest Lattice-based Ring Signature for Ring Size between 4 and 2000. We instantiate DualRing in the M-LWE/SIS setting and obtain DualRing-LB, the shortest lattice-based ring signature for a ring size between 4 and 2000. As mentioned above, DualRing-LB consists of a single response and n challenges. The size of a challenge (around 256 bits) in lattice-based identification is often much smaller than the size of a response (around a few KB). As a result, we obtain a compact lattice-based ring signature even without requiring a lattice-based sum argument. We compare with the shortest linear-size ring signature in [30] and shortest logarithmic-size ring signatures in [10, 21] in Table 2. DualRing-LB is shorter than [10, 21] for ring size less than about 2000 (note that our ring size can be arbitrary number). [30] is longer for all the ring sizes larger than 4, and it is based on a stronger NTRU assumption. The isogeny-based construction in [10] is at a much lower security level (60 bits of quantum security), is extremely slow (in the order of minutes), and has longer signatures than ours in the range around 5–300.

It is estimated in [19] that the running time of [19] is faster than Raptor for medium/large-sized rings ($n\ge 1024$) and also the estimated runtimes of [19] are significantly faster than those in [10]. The construction in [21] is an optimized version of that in [19] to reduce the signature length at the cost of computational efficiency. Therefore, the scheme by Esgin et al. [19] is the fastest scalable ring signature from lattices. We implement DualRing-LB together with the scheme in [19] and find that our scheme is at least 5 times faster in terms of sign and verify. We, therefore, expect an optimized implementation of our scheme to run faster than Raptor [30] and Falafl [10] as well for most ring sizes.

Table 2. Lattice-based ring signatures for n public keys.

1.3 Our 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 n challenges and a single response, while the AOS ring signature consists of a single challenge and n 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 $O(\log n)$ size, where n is the number of users in the ring, by using argument of knowledge system such as Bulletproofs [14]. 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 2000.² 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) in [19].

2 Related Work

Accumulator-Based Approach. Ring signatures can be constructed by accumulators [17]. The advantage of the accumulator approach is the constant signature size. However, the existing RSA-based and pairing-based accumulators both require a trusted setup for generating system parameters, which is not desirable for systems without a mutually trusted party. There exists a lattice-based accumulator [28] with no trusted setup, but it is not practical (the signature size is in the order of several MBs). Merkle-tree based accumulator does not require trusted setup. However, the membership proof of Merkle-tree based accumulator involves expensive zero-knowledge proof on hash function input.

Zero-Knowledge Proof Based Approach. The mainstream approach to construct a ring signature is to use a zero-knowledge proof on a signer index with the corresponding secret key. Most efficient schemes in the literature is to design a specific zero-knowledge proof for the designated cryptosystem (e.g., DL-based, RSA-based or lattice-based). In particular, a one-out-of-many proof [22] shows that the prover knows an opening of one out of n commitments. The index of such commitment can be expressed as a binary string $(b_1, \ldots b_{\log n})$. The zero-knowledge proof demonstrates the correctness of such an index, and hence the proof size is $O(\log n)$. Since a public key can be viewed as a commitment to zero³, there are multiple ring signature schemes proposed using one-out-of-many proofs, including the DL-based setting [11, 22] and lattice-based setting [19,20,21]. These ring signatures have size of $O(\log n)$.

Logarithmic-Size Generic Construction. The logarithmic-size generic construction of ring signature in [3] is secure in the standard model by using a public key encryption, a standard signature, a somewhere perfectly binding hash function with private local opening, and a non-interactive witness-indistinguishable (NIWI) proof systems. Their DL-based construction has a signature size of $2(\log n)^2 + 4$ elements in $\mathbb {G}$ and $2\log n$ elements in $\mathbb {Z}_p$ with an additional NIWI proof (not instantiated in [3]), and hence it is not as efficient as the schemes in Table 1. The lattice-based construction in [3] is also not efficient.

3 Preliminaries

Notations. In this paper, we use $\lambda$ as the security parameter. For the notion $a\leftarrow _s S$, it means that we randomly pick an element a from a set S. We use bold letters such as $\mathbf{a}$ to represent a vector (or matrix for lattice-based construction).

Argument of Knowledge. An argument consists of three PPT algorithms $(\textsf {S},\mathcal {P},\mathcal {V})$, which are CRS (Common Reference String) generator $\textsf {S}$, the prover $\mathcal {P}$ and the verifier $\mathcal {V}$. A CRS $\hat{\sigma }$ is produced by $\textsf {S}$ on input $\lambda$ and a transcript tr is produced by $\mathcal {P}$ and $\mathcal {V}$ on inputs s and t, which is denoted by $\mathsf{tr} \leftarrow \langle \mathcal {P}(s),\mathcal {V}(t)\rangle$. We write $\langle \mathcal {P}(s),\mathcal {V}(t)\rangle =b$ to denote that the verifier $\mathcal {V}$ accepts $b=1$ or rejects $b=0$. We define the language:

$$ \mathcal {L}=\left\{ x\mid \exists w:(\hat{\sigma },x,w)\in \mathcal {R}\right\} , $$

where w is a witness and x is a set of statements u in the relation $\mathcal {R}$.

An argument of knowledge $(\textsf {S},\mathcal {P},\mathcal {V})$ should satisfy perfect completeness and statistical witness-extended emulation [12]. Informally, completeness means that a prover with a witness w for $x \in \mathcal {L}$ can convince the verifier of this fact. Statistical witness-extended emulation means that given an adversary that produces an acceptable argument with probability $\epsilon$, there exists an emulator that produces a similar argument with probability $\epsilon$ together with a witness w.

Definition 1

(Perfect completeness). For any non-uniform polynomial time adversary $\mathcal {A}$, $(\textsf {S},\mathcal {P},\mathcal {V})$ has perfect completeness if

Definition 2

(Statistical Witness-Extended Emulation). For any deterministic polynomial time prover $\mathcal {P}^*$, $(\textsf {S},\mathcal {P},\mathcal {V})$ has witness-extended emulation if there is a polynomial time emulator $\mathcal {E}$ such that for any pair of interactive adversaries $\mathcal {A}_1$ and $\mathcal {A}_2$ such that

where the oracle $\mathcal {O}=\langle \mathcal {P}^*(\hat{\sigma },u,s),\mathcal {V}(\hat{\sigma },u)\rangle$ can rewind to some point and resume with new randomness for the verifier $\mathcal {V}$ from this point onward.

Such an emulation above is used to define knowledge-soundness [12]. We consider s (which is the output of the adversary $A_2$ in the above equation) as the internal state of $\mathcal {P}^*$ with randomness, which follows that $\mathcal {E}$ can extract a witness whenever $\mathcal {P}^*$ generates a convincing argument in s.

4 Security Model

We review the security model of a ring signature in [8]. A ring signature consists of four PPT algorithms as follows:

$$\begin{aligned} \text {RS}\left\{ \begin{array}{ll} \textsf {Setup}(\lambda )&{}\rightarrow \mathsf{param}\\ \textsf {KeyGen}(\mathsf{param})&{}\rightarrow (\mathsf{pk},\mathsf{sk})\\ \textsf {Sign}(\mathsf{param}, M,\mathbf {pk},\mathsf{sk})&{}\rightarrow \sigma \\ \textsf {Verify}(\mathsf{param}, M, \mathbf {pk},\sigma )&{}\rightarrow 1/0 \end{array}\right. \end{aligned}$$

We use $\mathbf {pk}$ to represent a vector of public keys $(\mathsf{pk}_1, \ldots , \mathsf{pk}_n)$. For simplicity, we omit the input of system parameters param to algorithms other than Setup in the rest of this paper.

Unforgeability w.r.t. insider corruption. Unforgeability w.r.t. insider corruption [8] means that the adversary $\mathcal {A}$ cannot generate a valid signature without a secret key, even if he can adaptively corrupt some honest participants and obtain their secret keys.

Definition 3

(Unforgeability w.r.t. Insider Corruption). For any polynomial time adversary $\mathcal {A}$, a ring signature is unforgeable if for some integer $q_k$ polynomial in $\lambda$:

where the oracles given to $\mathcal {A}$ is defined as:

• $\mathcal {CO}(i)$ outputs $\hat{\mathsf{sk}}_i$. We denote C as the set of corrupted users queried in $\mathcal {CO}$.

• $\mathcal {SO}(M,\mathbf {pk}, j)$: On input a message M, a vector of public keys $\mathbf {pk}$ and the signer index j, the Signing Oracle outputs $\bot$ if $\hat{\mathsf{pk}}_j \notin \mathbf {pk}$. Otherwise, it outputs a signature $\sigma \leftarrow \textsf {Sign}(M,\mathbf {pk},\hat{\mathsf{sk}}_j)$.

Anonymity against full key exposure. We use the strong anonymity model in [8] that the adversary $\mathcal {A}$ is given all randomness to generate the secret keys.

Definition 4

(Anonymity against Full Key Exposure). For any polynomial time adversary $(\mathcal {A}_1, \mathcal {A}_2)$, a ring signature is anonymous if for some integer $q_k$ polynomial in $\lambda$:

Note that the set of public keys $\mathbf {pk}^*$ chosen by $\mathcal {A}_1$ can include adversarially generated public keys.

5 DualRing: Generic Ring Signature Construction

In this section, we show how to construct a generic ring signature scheme, DualRing, from a special kind of canonical identification scheme.

5.1 AOS Ring Signature

The AOS ring signature [2] can be constructed from a standard signature of Type-H or Type-T. We review the definition of Type-T in Algorithm 1.

• The Sign algorithm uses the algorithm A to generate a commitment R using a randomness r (chosen from a randomness domain $\varDelta _r$). Then, the message and R are hashed by H to obtain the hash value c (within the range of hash function $\varDelta _c$). Finally, the algorithm uses the function Z to generate the signature using the secret key $\mathsf{sk}$, r and c.

• The Verify algorithm allows the reconstruction of $R'$ from the public key $\mathsf{pk}$, z and c using the function V. The signature is validated by using H on the message and $R'$.

Schnorr signature, Guillou-Quisquater signature [23], Katz-Wang signature [24] and EdDSA [9] are examples of Type-T signatures. Using Type-T signatures, a Type-T AOS ring signature can be constructed as shown in Fig. 1. However, as mentioned before, there is no security proof for this generic construction in [2], but only the instantiation with Schnorr signature is proven secure in [2]. We formally prove its security in the full version of the paper.

5.2 Canonical Identification

Canonical identification [1] is a three-move public-key authentication protocol of a specific form. We first give canonical identification in Algorithm 2, based on the definition of Type-T signature in [2]. We add the additional checking in line 17 of Algorithm 2, which is useful for lattice-based construction. It is known that after applying the Fiat-Shamir transformation to canonical identification, we obtain a Type-T signature.

We define a new security notion of special impersonation under key only attack for canonical identification. It can be viewed as a combination of the special soundness and the impersonation attack: the adversary wins by outputting two valid transcripts with the same commitment.

Definition 5

A canonical identification is secure against special impersonation under key only attack for any polynomial time adversary $\mathcal {A}$:

We use this new definition instead of special soundness together with key recovery under key only attack in this paper, because the standard special soundness definition [25] is not satisfied by the efficient lattice-based identification scheme used in Section 7. This stems from the so-called ‘knowledge gap’ in efficient lattice-based zero-knowledge proofs. In particular, the knowledge extractor in such schemes is not guaranteed to recover a secret key of a given public key, but rather recovers an ‘approximate’ witness of a relaxed relation closely related to the relation satisfied by a public-secret key pair. Therefore, to keep the generality of our results, we use the special impersonation under key only attack. We refer the reader to earlier works such as [19, 20, 31, 32] for further discussion about this knowledge/soundness gap issue.

We also note that for the settings where the knowledge/soundness gap issue do not arise (i.e., standard special soundness is satisfied) such as the DL-setting, ‘special impersonation under key only attack’ implies the standard ‘key recovery under key only attack’ [25] since the knowledge extractor in that case recovers a secret key $\mathsf{sk}^*$ with $(\mathsf{sk}^*,\mathsf{pk})\in \text {KeyGen}()$ given a public key $\mathsf{pk}$ and two accepting transcripts.

Type-T* Canonical Identification. Next, we define Type-T* canonical identification, which is a canonical identification with the following properties.

• 1. The function V in the verify algorithm consists of two functions $V_1$ and $V_2$ during the reconstruction of $R'$, such that line 14 in Algorithm 2 becomes:

  $$ R' = V_1(z) \odot V_2 (\mathsf{pk}, c), $$

  where $\odot$ is a commutative group operation for the domain of $R'$.

• 2. The function $V_1$ is additively/multiplicatively homomorphic, i.e., $V_1 (z_1) \odot V_1(z_2) = V_1 (z_1 \oplus z_2)$, where $\oplus$ is the additive/multiplicative operation. The homomorphic operation should be efficiently computable.

• 3. Given the secret key $\mathsf{sk}$ corresponding to $\mathsf{pk}$ and c, there exists a function $\mathcal {T}$ that outputs $\hat{z} = \mathcal {T}(\mathsf{sk}, c)$ such that $V_1(\hat{z}) = V_2(\mathsf{pk}, c)$.

• 4. The challenge space $\varDelta _c$ is a group with operation “$\otimes$”. We denote the inverse operation of $\otimes$ as $\oslash$. (For example, if $\otimes$ is defined as “$+$”, $\oslash$ will be “−”.) If $c_1$ and $c_2$ are uniformly distributed in $\varDelta _c$, then $c_1 \otimes c_2$ is also uniformly distributed in $\varDelta _c$.

It is easy to see that Schnorr identification and Guillou-Quisquater identification [23] are examples of Type-T* canonical identification. There are in fact many more examples from the literature. For many identification schemes reviewed in [6], the verification function V can be split into $V_1(z)$ and $V_2(pk, c)$, such as the FFS family, FF family, and Hs family. Apart from the above schemes, the identification scheme from Katz-Wong signature [24], Chaum-Pedersen identification [15] and the Okamoto-Schnorr identification are some examples of Type-T* canonical identification. Type-T* canonical identification can also be applied to the lattice-based setting, in particular, effectively to all “Fiat-Shamir with Aborts” [31, 32]-based identification schemes (as shown in Sect. 7).

Schnorr identification. The Setup algorithm outputs a cyclic group $\mathbb {G}$ of prime order p, with a generator g. For each KeyGen execution, the algorithm picks a random $\mathsf{sk}\in \mathbb {Z}_p$ and computes $\mathsf{pk}= g^{\mathsf{sk}}$. The functions $A, Z, V_1, V_2$ are defined as:

$$\begin{aligned} R&= A(\mathsf{sk}; r) := g^r,\\ z&= Z(\mathsf{sk}, r, c) := r - c \cdot \mathsf{sk}\mod p,\\ R'&= V_1(z) \odot V_2(\mathsf{pk}, c) := g^z \cdot \mathsf{pk}^c. \end{aligned}$$

Note that $V_1$ is additively homomorphic: $V_1(z_1) \odot V_1(z_2) = g^{z_1} \cdot g^{z_2} = g^{z_1 + z_2} = V_1(z_1 + z_2)$. Given the secret key $\mathsf{sk}$ corresponding to $\mathsf{pk}$ and c, it is easy to compute $\hat{z} = \mathcal {T}(\mathsf{sk}, c) := \mathsf{sk}\cdot c$ mod p such that $V_1 (\hat{z}) = g^{\mathsf{sk}\cdot c} = \mathsf{pk}^c = V_2(\mathsf{pk}, c)$. The challenge space $\mathbb {Z}_p$ is a group under addition modulo p. Therefore, Schnorr identification is a Type-T* canonical identification.

Theorem 1

Schnorr identification is secure against special impersonation under key only attack if the DL assumption holds.

Proof

Suppose that $\mathcal {A}$ is an adversary breaking the special impersonation under key only attack. The algorithm $\mathcal {B}$ is given a DL problem (g, y) for a cyclic group $\mathbb {G}$ of prime order p. $\mathcal {B}$ gives $\mathsf{param} = (\mathbb {G}, p, g)$ and $\mathsf{pk}= y$ to $\mathcal {A}$.

$\mathcal {A}$ returns $(c, z, c', z')$ where $c \ne c'$. Then we have:

$$ g^z \cdot \mathsf{pk}^c = g^{z'} \cdot \mathsf{pk}^{c'}. $$

Therefore $\mathcal {B}$ can extract the secret key $\mathsf{sk}= \frac{z- z'}{(c'-c)}$ as the solution to the DL problem.   $\square$

Guillou-Quisquater (GQ) identification [23]. The Setup algorithm outputs a pair (N, e), where $N = pq$, p and q are large prime numbers, e is a prime number less than N/4 and gcd$(e, \phi (N)) = 1$. For each KeyGen execution, the algorithm picks a random $\mathsf{sk}\in \mathbb {Z}_N$ and calculates $\mathsf{pk}= \mathsf{sk}^e$. The functions $A, Z, V_1, V_2$ are defined as:

$$\begin{aligned} R&= A(\mathsf{sk}; r) := r^e,\\ z&= Z(\mathsf{sk}, r, c) := \mathsf{sk}^c \cdot r \mod N,\\ R'&= V_1(z) \odot V_2(\mathsf{pk}, c) := z^e \cdot \mathsf{pk}^{-c} \mod N. \end{aligned}$$

Note that $V_1$ is multiplicatively homomorphic: $V_1(z_1) \odot V_1(z_2) = z_1^e \cdot z_2^e = (z_1 z_2)^e = V_1(z_1 \cdot z_2)$. Given the secret key $\mathsf{sk}$ corresponding to $\mathsf{pk}$ and c, it is easy to compute $\hat{z} = \mathcal {T}(\mathsf{sk}, c) := \mathsf{sk}^{-c}$ mod N such that $V_1 (\hat{z}) = \hat{z}^e = \mathsf{sk}^{-ce}= \mathsf{pk}^{-c} = V_2(\mathsf{pk}, c)$. The challenge space of GQ identification is $\mathbb {Z}_e$ and it is a group under addition. Therefore, GQ identification is a Type-T* canonical identification.

Theorem 2

GQ identification is secure against special impersonation under key only attack if the RSA assumption holds.

Proof

Suppose that $\mathcal {A}$ is an adversary breaking the special impersonation under key only attack. The algorithm $\mathcal {B}$ is given a RSA problem (N, e, y). $\mathcal {B}$ gives $\mathsf{param} = (N, e)$ and $\mathsf{pk}= y$ to $\mathcal {A}$.

$\mathcal {A}$ returns $(c, z, c', z')$, where $c \ne c'$, we have $z^e \cdot \mathsf{pk}^{-c} = {z'}^e \cdot \mathsf{pk}^{-c'}$. Then:

$$\begin{aligned} (z/z')^e&= \mathsf{pk}^{(c-c')} \end{aligned}$$

Since e is a prime and $c, c' \in \mathbb {Z}_e$, $\mathcal {B}$ can compute integers A and B such that:

$$ A \cdot e + B \cdot (c-c') = \text{ gcd }(e, (c-c')) = 1, $$

by the Euclidean algorithm. Hence we have:

$$\begin{aligned} (z/z')^{Be}&= \mathsf{pk}^{1 - A e}. \end{aligned}$$

Therefore we can extract the secret key $\mathsf{sk}= (z/z')^{B} \mathsf{pk}^A$ as the solution to the RSA problem.   $\square$

5.3 Our Construction: DualRing

We denote a Type-T* canonical identification scheme by T*. We use the symbol $\bigodot$ and $\bigotimes$ to represent consecutive $\odot$ and $\otimes$ operations, respectively:

$$\begin{aligned} \bigodot _{i=1}^n a_i&:= a_1 \odot a_2 \odot \ldots \odot a_{n-1} \odot a_n, \quad \bigotimes _{i=1}^n b_i := b_1 \otimes b_2 \otimes \ldots \otimes b_{n-1} \otimes b_n. \end{aligned}$$

DualRing is shown in Algorithm 3. The high level idea is that we use $V_2$ to add the decoy public keys $\mathsf{pk}_i$ and their corresponding challenge values $c_i$ to the commitment R first. After getting the real challenge value c, the signer with index j computes $c_j = c \oslash \bigotimes _{i \ne j} c_i \in \varDelta _c$. The signer computes z according to the canonical identification scheme. To verify, the commitment R is reconstructed from all public keys and their corresponding challenge values. The value $\bigotimes _{\forall i} c_i$ should be equal to the real challenge value c.

Theorem 3

DualRing is unforgeable w.r.t. insider corruption in the random oracle model if T* is secure against special impersonation under key only attack and $|\varDelta _c| > q_s(q_h + q_s - 1)$, where $q_s$ and $q_h$ are the number of queries to the signing oracle and the H oracle respectively.

Proof

Denote $\mathcal {A}$ as a PPT adversary breaking the unforgeability w.r.t. insider corruption of DualRing. We build an algorithm $\mathcal {B}$ to break the special impersonation under key only attack of T*. Suppose the algorithm $\mathcal {B}$ is given a system parameters $\mathsf{param}$ and a public key $\mathsf{pk}^*$ from its challenger $\mathcal {C}$.

Setup. $\mathcal {B}$ picks a random index $i^* \in [1, q_k]$. $\mathcal {B}$ runs $(\hat{\mathsf{pk}}_i, \hat{\mathsf{sk}}_i) \leftarrow \textsf {KeyGen}()$ for $i \in [1,q_k], i \ne i^*$. $\mathcal {B}$ sets $\hat{\mathsf{pk}}_{i^*} = \mathsf{pk}^*$. $\mathcal {B}$ gives param and $S := \{ \hat{\mathsf{pk}}_i \}_{i=1}^{q_k}$ to $\mathcal {A}$.

Oracle Simulation. $\mathcal {B}$ answers the oracle queries as follows.

• H: $\mathcal {B}$ simulates H as a random oracle.

• $\mathcal {CO}$: On input i, $\mathcal {B}$ returns $\hat{\mathsf{sk}}_i$ (If $i = i^*$, $\mathcal {B}$ declares failure and exits.).

• $\mathcal {SO}$: On input a message M, a set of public key $\mathbf{pk} = (\mathsf{pk}_1, \ldots , \mathsf{pk}_n)$ and the signer index j, it outputs $\bot$ if $\hat{\mathsf{pk}}_j \notin \mathbf{pk}$. If $j \ne i^*$, then $\mathcal {B}$ returns $\sigma \leftarrow$ Sign($\mathsf{param}, M, \mathbf{pk}, \hat{\mathsf{sk}}_j)$.

  Otherwise, $\mathcal {B}$ picks random $c_1, \ldots , c_n \in \varDelta _c$ and z from the domain of response $\varDelta _z$ according to the distribution of the output of $Z(\cdot )$. $\mathcal {B}$ computes $R = V_1(z) \odot \bigodot _{i=1}^n V_2 (\mathsf{pk}_i, c_i)$. $\mathcal {B}$ sets $H(M, \mathbf{pk}, R) = \bigotimes _{i=1}^n c_i$ in the random oracle. If such value has been set in the random oracle, $\mathcal {B}$ declares failure and exits. $\mathcal {B}$ returns $\sigma = (c_1, \ldots , c_n, z)$.

Challenge. $\mathcal {A}$ returns a forgery $(M^*, \{\hat{\mathsf{pk}}_{i_j} \}_{j=1}^{n}, \sigma ^* = (c^*_1$, $\ldots$, $c^*_{n^*}$, $z^*))$. If $\mathsf{pk}^* \ne \hat{\mathsf{pk}}_{i_j}$ for all $j \in [1,n]$, $\mathcal {B}$ declares failure and exits. Otherwise, we denote $j^*$ as the index such that $\mathsf{pk}^* = \hat{\mathsf{pk}}_{i_{j^*}}$. Denote $\mathbf{pk}^* = \{\hat{\mathsf{pk}}_{i_j}\}_{j=1}^{n}$ and compute $R^*$ as in the Verify algorithm. $\mathcal {B}$ rewinds to the point that $(M^*, \mathbf{pk^*}, R^*)$ is queried to H and returns a different $c'$ instead. $\mathcal {A}$ returns another signature $\sigma ' = (c'_1, \ldots , c'_{n}, z')$. Since both $\sigma ^*$ and $\sigma '$ are valid signatures, We have:

$$ R^* = V_1(z^*) \odot \bigodot _{j=1}^{n} V_2 (\hat{\mathsf{pk}}_{i_j}, c^*_j) = V_1(z') \odot \bigodot _{j=1}^{n} V_2 (\hat{\mathsf{pk}}_{i_j}, c'_j). $$

Note that it is impossible to have $c^*_j = c'_j$ for all $j \in [1,n]$ (since $\bigotimes _{j=1}^{n} c^*_j \ne \bigotimes _{j=1}^{n} c'_j$). If $c^*_{j^*} = c'_{j^*}$, $\mathcal {B}$ declares failure and exits. With probability at least 1/n, we have $c^*_{j^*} \ne c'_{j^*}$. Observe that:

$$\begin{aligned}&V_1(z^*) \odot \bigodot _{j=1}^{n} V_2 (\hat{\mathsf{pk}}_{i_j}, c^*_j) \\ =&V_1(z^* \oplus \hat{z}^*_1 \oplus \ldots \oplus \hat{z}^*_{j^* - 1} \oplus \hat{z}^*_{j^* + 1} \oplus \ldots \oplus \hat{z}^*_{n}) \odot V_2 (\mathsf{pk}^*, c^*_{j^*}) \\ =&V_1(\tilde{z^*}) \odot V_2 (\mathsf{pk}^*, c^*_{j^*}), \end{aligned}$$

where $\hat{z}^*_i = \mathcal {T}(\hat{\mathsf{sk}}_i, c^*_i)$ for $i \in [1, n]\setminus j^*$ and $\tilde{z^*} = z^* \oplus \hat{z}^*_1 \oplus \ldots \oplus \hat{z}^*_{j^* - 1} \oplus \hat{z}^*_{j^* + 1} \oplus \ldots \oplus \hat{z}^*_{n}$. Similarly we have $V_1(z') \odot \bigodot _{j=1}^{n} V_2 (\hat{\mathsf{pk}}_{i_j}, c'_j) = V_1(\tilde{z'}) \odot V_2 (\mathsf{pk}^*, c'_{j^*})$ for some $\tilde{z'}$. Then $\mathcal {B}$ can return $(c^*_{j^*}, \tilde{z^*}, c'_{j^*}, \tilde{z'})$ to its challenger $\mathcal {C}$.

Probability Analysis. We analyse the probability of success (i.e., not aborting) in the above simulation. For $q_c$ queries to the $\mathcal {CO}$, the probability of success in the first query is $(1-\frac{1}{q_k})$. The probability of success in the second query is at least $(1-\frac{1}{q_k-1})$. The probability of success after $q_c$ queries is at least $(1-\frac{1}{q_k}) (1-\frac{1}{q_k- 1}) \cdots (1-\frac{1}{q_k-q_c+1}) = \frac{q_k-q_c}{q_k} = 1-\frac{q_c}{q_k}$. (It is implied by the security model that $q_k > q_c + n$.)

For $q_s$ queries to the $\mathcal {SO}$, the probability of success in the first query is at least $(1 - \frac{q_h}{|\varDelta _c|})$, where $q_h$ is the number queries to the H oracle. The probability of success after $q_s$ queries to $\mathcal {SO}$ is at least

$$\begin{aligned} (1 - \frac{q_h}{|\varDelta _c|})(1 - \frac{q_h+1}{|\varDelta _c|}) \cdots (1 - \frac{q_h+q_s-1}{|\varDelta _c|}) \ge 1 - \frac{q_s(q_h+q_s-1)}{|\varDelta _c|}. \end{aligned}$$

Here we assume that $|\varDelta _c| > q_s(q_h + q_s - 1)$.

The probability of $\mathsf{pk}^* \ne \hat{\mathsf{pk}}_{i_j}$ in the challenge phase is $(1-\frac{1}{q_k-q_c})(1-\frac{1}{q_k-q_c-1}) \cdots (1-\frac{1}{q_k-q_c-n+1}) = \frac{q_k-q_c-n}{q_k - q_c}$. If the probability of forgery by $\mathcal {A}$ is $\epsilon$, then the probability of $\mathcal {B}$ does not return failure before rewinding is

$$\begin{aligned} \epsilon _b&:= \epsilon (1-\frac{q_c}{q_k})(1 -\frac{q_s(q_h+q_s-1)}{|\varDelta _c|})(1-\frac{q_k-q_c-n}{q_k - q_c}) \\&= \epsilon (1 -\frac{q_s(q_h+q_s-1)}{|\varDelta _c|})(\frac{n}{q_k}). \end{aligned}$$

By the generalized forking lemma [4], the probability of a successful rewinding is at least $\frac{\epsilon _b}{8}$ if $|\varDelta _c| > 8 q_h/\epsilon _b$ (it runs in time $\tau \cdot 8q_n/\epsilon _b \cdot \ln (8n/\epsilon _b)$ if $\mathcal {A}$ runs in time $\tau$). Finally we have $c^*_{j^*} \ne c'_{j^*}$ with probability at least 1/n. As a result, the probability $\epsilon '$ of $\mathcal {B}$ breaking the special impersonation is:

$$\begin{aligned} \epsilon '&\ge (\frac{\epsilon n}{8q_k}) (1 -\frac{q_s(q_h+q_s-1)}{|\varDelta _c|}). \end{aligned}$$

if $|\varDelta _c| > q_s(q_h + q_s - 1)$ and $|\varDelta _c| > 8 q_h/\epsilon _b$⁴. We can further simplify the probability $\epsilon '$ if we take $|\varDelta _c| \ge 2 q_s(q_h+q_s-1)$. Then if $|\varDelta _c| > \frac{16 q_h q_k}{\epsilon n}$, we have $\epsilon ' \ge \frac{\epsilon n}{16q_k}$.   $\square$

Theorem 4

DualRing is anonymous in the random oracle model, if $|\varDelta _c| > q_s(q_h + q_s - 1)$, where $q_s$ and $q_h$ are the number of queries to the signing oracle and the H oracle respectively.

Proof

We show how to build an algorithm $\mathcal {B}$ providing perfect anonymity in the random oracle model.

Setup. $\mathcal {B}$ runs $\mathsf{param} \leftarrow$ Setup$(\lambda )$. $\mathcal {B}$ runs $(\mathsf{pk}_i, \mathsf{sk}_i) \leftarrow \textsf {KeyGen}(\mathsf{param}; \omega _i)$ for $i \in [1,q_k]$ with randomness $\omega _i$. $\mathcal {B}$ gives param and $S := \{ \mathsf{pk}_i \}_{i=1}^{q_k}$ to $\mathcal {A}_1$.

Oracle Simulation. $\mathcal {B}$ answers the oracle queries as follows.

• $\mathcal {SO}$: On input a message m, a set of public key $\mathbf{pk}$ with the signer index j, $\mathcal {B}$ returns $\sigma \leftarrow$ Sign($\mathsf{param}, m, \mathbf{pk}, \mathsf{sk}_j)$.

• H: $\mathcal {B}$ simulates H as a random oracle.

Challenge. $\mathcal {A}_1$ gives $\mathcal {B}$ a message m and a vector of public keys $\mathbf {pk}$ and two indices $i_0, i_1$. $\mathcal {B}$ picks random $c_1, \ldots , c_n \in \varDelta _c$ and picks z from the domain of response $\varDelta _z$ according to the distribution of the output of $Z(\cdot )$. $\mathcal {B}$ computes $R = V_1(z) \odot \bigodot _{i=1}^n V_2 (\mathsf{pk}_i, c_i)$. $\mathcal {B}$ sets $H(m, \mathbf{pk}, R) = \bigotimes _{i=1}^n c_i$ in the random oracle. By Property 4, the distribution is correct. If the hash value is already set by the H oracle, $\mathcal {B}$ declares failure and exits. $\mathcal {B}$ returns $\sigma = (c_1, \ldots , c_n, z)$ and $\{ \omega _i\}_{i =1}^{q_k}$ to $\mathcal {A}_2$. $\mathcal {B}$ picks a random bit b.

Output. Finally, $\mathcal {A}_2$ outputs a bit $b'$. Observe that b is not used in the generation of $\sigma$. Therefore, $\mathcal {A}_2$ can only win with probability 1/2.

Probability Analysis. We analyse the probability of success (i.e., not aborting) in the above simulation. For $q_h$ queries to the H oracle and $q_s$ queries to the $\mathcal {SO}$, the probability of success in the first query is at least $(1 - \frac{q_h}{|\varDelta _c|})$. The probability of success after $q_s$ queries to $\mathcal {SO}$ is at least

$$\begin{aligned} (1 - \frac{q_h}{|\varDelta _c|})(1 - \frac{q_h+1}{|\varDelta _c|}) \cdots (1 - \frac{q_h+q_s-1}{|\varDelta _c|}) \ge 1 - \frac{q_s(q_h+q_s-1)}{|\varDelta _c|}. \end{aligned}$$

Here we assume that $|\varDelta _c| > q_s(q_h + q_s - 1)$. If $\mathcal {B}$ does not abort, then no PPT adversary can win with non-negligible probability over half.    $\square$

Difference with AOS Ring Signature. Our ring signature is a bit different from the AOS ring signature. The AOS ring signature allows a mixture of different types of public keys, such as keys from the Schnorr signature and the RSA signature. The security proof for the generic construction of the AOS ring signature was not formally given in [2]. On the other hand, our scheme allows different types of public keys from different Type-T* canonical identification schemes, with the restriction that these canonical identification schemes should use the same $V_1$ function⁵ (Otherwise, we do not know which $V_1$ function to use in the Verify algorithm). The security proof for our generic construction holds for different Type-T* canonical identification schemes satisfying the requirement above.

The AOS ring signature is generated sequentially by forming a “ring” of $c_i$ in a loop and calculating $z_i$ for n times. On the other hand, our signature is generated by forming a “R-ring” in one-shot during the commit phase, forming a “C-ring” in one-shot after getting the challenge c and calculating z for one time only. Therefore, our scheme is more efficient than the AOS ring signature.

Finally, our dual ring technique cannot be applied to the Type-H signature in [2]. Recall that for our Type-T* DualRing, we require the use of $V_2(\mathsf{pk}_i, c_i)$ (for all non-signer indices) to generate R. For Type-H, $\mathsf{pk}_i$ is tied with z by the one-way function $F(z, \mathsf{pk}_i)$. Hence, we cannot separate z and $\mathsf{pk}_i$ into $V_1$ and $V_2$ to form the R-ring similarly.

Difference with CDS OR-proofs. The C-Ring in DualRing is similar to the use of secret sharing in CDS 1-out-of-n OR proof [16]. Our construction of R-Ring leads to a single R and hence a single z in the signature. On the contrary, [16] does not have the formation of R-Ring and still has n commitments $R_i$’s. It results in n responses $z_i$’s. So, the ring signature constructed by [16] consists of $(c_i, z_i)$ for $i \in [n]$. There is no trivial way to combine all $z_i$’s, because each $z_i$ is only related to $R_i$ and $c_i$, and not to other $z_j$’s. Hence, [16] does not (easily) achieve an $O(\log n)$ size ring signature in the DL-based setting.

6 DualRing-EC: Our Succinct DL-based Ring Signature

We give a new sum argument of knowledge which is useful to reduce the signature size of DualRing from linear to logarithmic in the DL-based setting. The group operation $\otimes$ of the challenge space is modular addition. This is the first combination of the classical ring structure with the argument of knowledge.

Notations and Assumptions. For a security parameter $\lambda$, we use $\mathbb {G}$ to represent a cyclic group of prime order p. We use [n] to denote the numbers 1, 2, ..., n.

We use the following notations for vectors for our DL-based construction: $\mathbf {a}_{[:l]}$ and $\mathbf {a}_{[l:]}$ represent $(a_1,...,a_l)$ and $(a_{l+1},...,a_n)$. $\mathbf {a}\circ \mathbf {b}$ is the Hadamard product $(a_1b_1,a_2b_2,...,a_nb_n)$. $\langle \mathbf {a},\mathbf {b}\rangle$ is the inner product $\sum _{i=1}^{n}a_ib_i$. $\mathbf {a}^b$, $\mathbf {a}+b$ and $\mathbf {a}^\mathbf {b}$ represent $(a_1^b,a_2^b,...,a_n^b)$, $(a_1+b,a_2+b,...,a_n+b)$ and $\prod _{i=1}^{n}a_i^{b_i}$ respectively. $\sum \mathbf {a}$ and $\prod \mathbf {a}$ denotes $\sum _{i=1}^{n}a_i$ and $\prod _{i=1}^{n}a_i$.

Definition 6

(Discrete Logarithm Assumption). For all PPT adversaries $\mathcal {A}$ such that

$$\begin{aligned} \Pr \left[ y = g^a | {g},y \leftarrow _s\mathbb {G}, a \leftarrow \mathcal {A}(\mathbb {G},{g},y) \right] \le \mathsf{negl}(\lambda ). \end{aligned}$$

6.1 Sum Arguments of Knowledge

The sum argument of knowledge is a variant of inner product argument in [14]. The inner product argument is an efficient proof system for the following relation:

$$\begin{aligned} \left\{ \begin{aligned} (\mathbf {g},\mathbf {h}\in \mathbb {G}^n,P\in \mathbb {G},c\in \mathbb {Z}_p;\mathbf {a},\mathbf {b}\in \mathbb {Z}_p^n): P=\mathbf {g}^\mathbf {a}\mathbf {h}^\mathbf {b}\wedge c=\langle \mathbf {a},\mathbf {b}\rangle \end{aligned} \right\} \end{aligned}$$

in which a prover $\mathcal {P}$ convinces a verifier $\mathcal {V}$ that c is the inner product of two committed vectors $\mathbf {a},\mathbf {b}$. Bootle et al. [12] presented an efficient zero-knowledge proof for inner product argument, with communication complexity of $6\log _2(n)$ (n is the dimension of vectors). Based on their works, Bünz et al. proposed Bulletproofs [14] to reduce the communication complexity to $2\log _2(n)$. They achieve $O(\log n)$ complexity by running a recursive Pf algorithm, such that in each round two vectors $\mathbf{a}, \mathbf{b}$ of size n are committed into two commitments (L, R), and two vector of proofs $\mathbf{a}', \mathbf{b}'$ of size n/2 are computed for challenge x, where $L^{x^2} P R^{x^{-2}}$ is equal to the commitment of $\mathbf{a}', \mathbf{b}'$ and $\langle \mathbf{a}', \mathbf{b}' \rangle$. In the next round, run the Pf algorithm with input vectors $\mathbf{a}', \mathbf{b}'$ and the recursion ends when $n = 1$.

From Inner Product Argument to Sum Argument. To construct our logarithmic size ring signature, we propose a new argument of knowledge named Sum Argument. First we give the relation:

$$\begin{aligned} \left\{ \begin{aligned} (\mathbf {g}\in \mathbb {G}^n,P\in \mathbb {G},c\in \mathbb {Z}_p;\mathbf {a}\in \mathbb {Z}_p^n): P=\mathbf {g}^\mathbf {a}\wedge c=\sum \mathbf {a} \end{aligned} \right\} \end{aligned}$$

(2)

In a sum argument, a prover convinces a verifier that he/she has the knowledge of a vector of scalars $\mathbf {a}$, such that $P=\mathbf {g}^\mathbf {a}$ and $c=\sum \mathbf {a}$. Our sum argument looks like an inner product argument, where a vector of generators and a computation of multi-exponentiation is used. Although an inner product argument can be converted into a sum argument by setting the vector $\mathbf {b}$ to $\mathbf {1}^n$, this yields a less efficient protocol than ours.

Assume that the system parameter $\mathsf{param}$ includes a generator $u \in \mathbb {G}$ in group $\mathbb {G}$ with order p and two hash functions $H_Z, H'_Z: \{0,1\}^* \rightarrow \mathbb {Z}_p$. A Non-interactive Sum Argument (NISA) consists of a Proof algorithm which takes $(\mathsf{param},\mathbf {g},P, c, \mathbf {a})$ and outputs a proof $\pi$; and a Verify algorithm which takes$(\mathsf{param},\mathbf {g},P, c, \pi )$ and outputs a bit 1/0. Our NISA is given in Algorithm 4. Observe that for the k-th recursion in Pf, the value of $\mathbf{b}$ is $\prod _{i=1}^k (x_i + x_i^{-1}) \mathbf{1} ^{\frac{n}{2^k}}$, where $x_i$ is the i-th output of $H_Z$. This $\mathbf{b}$ is known to the verifier and hence we do not need a vector of generators $\mathbf {h}$ to commit $\mathbf {b}$ in L, R as in [12]. As a result, we can set $\mathbf {h}$ as $\mathbf{1} ^n$ and can save almost half of the exponentiation during the recursion. In addition, the computation of P is also not needed by the prover.

Theorem 5

Our sum argument has statistical witness-extended emulation for non-trivial discrete logarithm relation among $\mathbf {g},u$ or a valid witness $\mathbf {a}$.

We defer its security proof to the full version of the paper.

Compared with [14], our protocol is simpler. In each iteration, we compute $(4n'+2)$ exponentiations to generate a proof, then compute a multi-exponentiation of size $(1+n+2\log _2(n))$ to verify. For an inner product argument [14], the corresponding computations are $(8n'+8)$ exponentiations and a multi-exponentiation of size $(1+2n+2\log _2(n))$, respectively. The proof sizes are similar; however we omit almost half of exponentiations.

6.2 Logarithmic Size DL-based Ring Signature

We give the full construction of compact DL-based ring signature, by combining DualRing with the sum argument of knowledge and Schnorr identification. Then, we compare the efficiency with the existing ring signature schemes.

Matching Sum Argument with Ring Signature. Notice that the sum argument proves the relation for some $a_i \in \mathbb {Z}_p$, given $g_i, P \in \mathbb {G}$ and $c \in \mathbb {Z}_p$:

$$ P = \prod _{i=1}^n g_i^{a_i} \quad \wedge \quad c = \sum _{i=1}^n a_i. $$

On the other hand, the verification of our generic ring signature includes:

$$ R \odot (V_1(z))^{-1} = \bigodot _{i=1}^n V_2(\mathsf{pk}_i, c_i) \quad \wedge \quad H(m, \mathsf{pk}, R)= \bigotimes _{i=1}^n c_i. $$

Interestingly, the two examples (DL- and RSA-based) of the Type-T* canonical identification have $V_2(\mathsf{pk}_i, c_i) = \mathsf{pk}_i^{c_i}$. Therefore, we can use the sum argument for the relation:

$$ R \cdot (V_1(z))^{-1} = \prod _{i=1}^n \mathsf{pk}_i^{c_i} \quad \wedge \quad H(m, \mathsf{pk}, R)= \sum _{i=1}^n c_i. $$

As a result, we can give a logarithmic size ring signature from Type-T* canonical identification scheme with matching non-interactive sum argument.

DualRing-EC Construction. Our DL-based construction DualRing-EC is shown in Algorithm 5, by using DualRing and NISA for Relation 2.

Theorem 6

DualRing-EC is unforgeable w.r.t. insider corruption if DualRing is unforgeable w.r.t. insider corruption and the NISA has statistical witness-extended emulation.

Proof

Suppose that $\mathcal {A}$ is an adversary breaking the unforgeability w.r.t. insider corruption of DualRing-EC. Then, we can construct an algorithm $\mathcal {B}$ breaking the unforgeability of DualRing. $\mathcal {B}$ is given the system parameter $\mathsf{param}'$ and a set of public keys S from the challenger of DualRing. $\mathcal {B}$ picks a random generator $u \in \mathbb {G}$ and returns $\mathsf{param} = (\mathsf{param}', u)$ to $\mathcal {A}$.

When $\mathcal {A}$ asks for a signing oracle query, $\mathcal {B}$ asks the signing oracle of DualRing and obtains $\sigma ' = (c_1, \ldots , c_n, z)$. $\mathcal {B}$ computes R by running DualRing.Verify on $\sigma '$. $\mathcal {B}$ computes $c = c_1 + \cdots + c_n$ and $P = R \odot (V_1(z))^{-1}$. $\mathcal {B}$ runs the NISA.Proof and obtains $\pi$. $\mathcal {B}$ returns $(c, z, R, \pi )$.

In the challenge phase, $\mathcal {A}$ returns a signature $\sigma ^* = (c^*, z^*, R^*, \pi ^*)$ with respect to a message $M^*$ and $\{\mathsf{pk}^*_i\}_{i=1}^n$. By the statistical witness-extended emulation of NISA, $\mathcal {B}$ can run an extractor $\mathcal {E}$ to obtain $(c^*_1, \ldots , c^*_n)$, where $P^* = R^* \odot (V_1(z^*))^{-1} = \bigodot _{i=1}^n V_2(\mathsf{pk}_i^*, c^*_i)$. Then $\mathcal {B}$ returns the signature $\sigma ' = (c^*_1, \ldots , c^*_n, z^*)$, the message $M^*$ and $\{\mathsf{pk}^*_i\}_{i=1}^n$ to the challenger of DualRing.    $\square$

Theorem 7

DualRing-EC is anonymous if DualRing is anonymous.

Proof

Suppose that $\mathcal {A}$ is an adversary breaking the anonymity of DualRing-EC. Then, we can construct an algorithm $\mathcal {B}$ breaking the anonymity of DualRing. $\mathcal {B}$ is given $\mathsf{param}'$ and the set S from its challenger. $\mathcal {B}$ picks a random generator $u \in \mathbb {G}$ and gives $\mathsf{param} = (\mathsf{param}', u)$ to $\mathcal {A}$.

When $\mathcal {A}$ asks for a signing oracle query, $\mathcal {B}$ simulates it as in the proof of unforgeability. In the challenge phase, $\mathcal {A}$ gives $M^*, \boldsymbol{\mathsf{pk}}^*, i_0, i_1)$ to $\mathcal {B}$ and $\mathcal {B}$ forwards it to its challenger. $\mathcal {B}$ receives $((c^*_1, \ldots , c^*_n, z^*), \{\omega _i\}_{i=1}^{q_k})$. $\mathcal {B}$ computes $\sigma ^*$ by line 7–9 of the Sign algorithm and returns $(\sigma ^*, \{\omega _i\}_{i=1}^{q_k})$ to $\mathcal {A}$.

Finally $\mathcal {A}$ returns a bit $b'$ and $\mathcal {B}$ sends $b'$ to its challenger to break the anonymity of DualRing.   $\square$

6.3 Efficiency Analysis

Signature Size. We compare our DL-based instantiation for n public keys with other $O(\log n)$-size DL-based ring signatures without trusted setup in Table 1. Most accumulator-based O(1)-size ring signatures require trusted setup. The lattice-based logarithmic ring signatures [19, 20, 28] are still at least 100 times longer than DL-based construction. Our ring signature is 789/921 bytes for the ring size = 1024/4096 with $\lambda = 128$. We can see that DualRing-EC (Algorithm 5 with Schnorr Identification) is the shortest ring signature without trusted setup. Figure 3 shows the concrete signature size when an element in $\mathbb {Z}_p$ is represented by 32 bytes and an element in $\mathbb {G}$ is represented by 33 bytes. Note that the signature size for a ring with size $[\log (n-1) + 1, \log n]$ is the same. Therefore, the signature size increases for ring size 1025, 2049, 4097, etc.

Fig. 3.

The signature size of ring signature schemes for n public keys, when implemented on elliptic curve with $\lambda =128$.

Computational Efficiency. We implement our DualRing-EC in Python, using the P256 curve in the fastecdsa library. It is tested on a computer with Intel Core i5 2.3 GHz, 8 GB RAM with MacOS 10. The running time is shown in Fig. 4.

We compare the asymptotic running time of our scheme with [11, 22]⁶. The running time of the signer for both [22] and [11] are both dominated by $O(n\log n)$ exponentiations. On the other hand, the signer’s running time for DualRing-EC is O(n) exponentiations only. Comparing with [27, 36], the major difference for the signer’s running time is the use of the inner product argument in [27, 36] and the use of NISA in our scheme. As discussed in the section of NISA, we only use half of the exponentiation used in the inner product argument. Verification time for out scheme is dominated by Line 17 of Algorithm 4, which contains $n+2\log n +1$ exponentiations for a ring size of n. [27, 36] used Bulletproof which contains $2n+2\log n +1$ exponentiations in verification. To conclude, our DualRing-EC outperforms [11, 22, 27, 36] in terms of signature size and the running time of the signer and the verifier.

Fig. 4.

Running times of DualRing-EC

7 DualRing-LB: Our Lattice-Based Ring Signature

In this section, we give a concrete ring signature construction based on standard (module) lattice assumptions using DualRing.

Notations and Assumptions. We define q as an odd modulus and $R_q$ as a ring $\mathbb {Z}_q[X]/(X^d+1)$ of dimension d. Define $\boldsymbol{I}_n$ as the identity matrix with size n, $\mathfrak {U}_k$ as a set of polynomials in $\mathbb {Z}[X]/(X^d+1)$ with infinity norm at most $k\in \mathbb {Z}^+$, and $\mathcal {U}$ as the uniform distribution. The Euclidean $\left\| \cdot \right\|$ and infinity $\Vert \cdot \Vert _{_\infty }$ norms of a polynomial (or a vector of polynomials) are defined in the standard fashion w.r.t. the coefficient vector of the polynomial. Define the following challenge space:

$$\begin{aligned} \mathcal {C}= \{ \, c \in \mathbb {Z}[X]/(X^d+1) \, : \, \Vert c\Vert _{_\infty }=1 \, \}. \end{aligned}$$

(3)

Observe that $|\mathcal {C}|=3^d$. That is, for $d=128$, we have $|\mathcal {C}|=3^{128}>2^{202}$.

We review the hardness of Module-SIS (M-SIS) (defined in “Hermite normal form” as in [5]) and Module-LWE (M-LWE) problems [19].

Definition 7

(M-SIS$_{n,m,q,\beta _{SIS}}$ Assumption). For all PPT adversaries $\mathcal {A}$,

$$\begin{aligned} \Pr \left[ \begin{array}{l} \boldsymbol{A}' \leftarrow _s \mathcal {U}(R_q^{n\times (m-n)}), \\ \boldsymbol{A} = [\boldsymbol{I}_n || \boldsymbol{A}'], \boldsymbol{z} \leftarrow \mathcal {A}(\boldsymbol{A}) \end{array} : \begin{array}{l} \boldsymbol{A} \boldsymbol{z} = \boldsymbol{0} \in R_q^n, \\ 0 < \Vert \boldsymbol{z}\Vert \le \beta _{SIS} \end{array} \right] \le \mathsf{negl}(\lambda ). \end{aligned}$$

Definition 8

(M-LWE$_{n,m,q,\chi }$ Assumption). Let $\chi$ be a distribution over $R_q$ and $\boldsymbol{s}\leftarrow _s \chi ^n$ be a secret key. Define LWE$_{q,s}$ as the distribution obtained by sampling $\boldsymbol{a}\leftarrow _s R_q^n, e \leftarrow _s \chi$ and outputting $(\boldsymbol{a}, \langle \boldsymbol{a}, \boldsymbol{s}\rangle + e)$. For all PPT adversaries $\mathcal {A}$, the probability of distinguishing between m samples from LWE$_{q,s}$ and $\mathcal {U}(R_q^{n}, R_q)$ is $\mathsf{negl}(\lambda )$.

7.1 Lattice-Based Canonical Identification

We give a Type-T* canonical identification from M-LWE/SIS in Algorithm 6. We use the rejection sampling technique from [31] to make sure that no information about the signer’s secret key is revealed in the response.

We can observe the following

• 1. The function $V_1$ is additively homomorphic:

  $$ V_1(\boldsymbol{z}_1) + V_1(\boldsymbol{z}_2) = - \boldsymbol{G} \cdot \boldsymbol{z}_1 - \boldsymbol{G} \cdot \boldsymbol{z}_2 = - \boldsymbol{G} \cdot (\boldsymbol{z}_1 + \boldsymbol{z}_2) = V_1(\boldsymbol{z}_1 + \boldsymbol{z}_2). $$

• 2. Given $\mathsf{sk}, \mathsf{pk}$ and c, we can compute $\tilde{\boldsymbol{z}} = - c \cdot \mathsf{sk}$ such that $V_1(\tilde{\boldsymbol{z}}) = \boldsymbol{G} \cdot (c \cdot \mathsf{sk}) = V_2(\mathsf{pk}, c)$.

• 3. The challenge space $\mathcal {C}$ is a group under addition mod 3.

Theorem 8

Algorithm 6 is secure against special impersonation under key only attack if M-SIS$_{k,m+1,q,\beta _{\text {SIS}}}$ (in HNF) for $\beta _{\text {SIS}}\approx 2d^2\sqrt{m} \cdot \left( 1 + m\sqrt{d} \right)$ and M-LWE$_{m-k,k,q,\mathfrak {U}_1}$ are hard.

Proof

Suppose that $\mathcal {A}$ is an adversary breaking the special impersonation under key only attack. Suppose that $\mathcal {B}$ is given $\boldsymbol{\hat{G}}=\left[ \, \boldsymbol{I}_k \, \Vert \, \boldsymbol{G}' \, \Vert \, \boldsymbol{g} \, \right] \in R_q^{k\times (m+1)}$ as the M-SIS matrix where $\boldsymbol{G}'$ and $\boldsymbol{g}$ are sampled uniformly at random. Denote $\boldsymbol{G}=\left[ \, \boldsymbol{I}_k \, \Vert \, \boldsymbol{G}' \, \right]$, which is used as the commitment key in the oracle simulations by $\mathcal {B}$. The number of public keys generated by the challenger is $q_k$. $\mathcal {B}$ sets

$$\begin{aligned} {\mathsf{pk}} = \boldsymbol{G}\cdot \boldsymbol{r} + \boldsymbol{g} \end{aligned}$$

(4)

for $\boldsymbol{r}\leftarrow \mathfrak {U}_1^m$. Observe that $\left\| \boldsymbol{r}'\right\| \le \sqrt{md+1} \quad \text {for } \boldsymbol{r}'=\left( \begin{array}{c} \boldsymbol{r} \\ 1 \end{array}\right) .$ Also, note that we can write $\boldsymbol{G}\cdot \boldsymbol{r} = \boldsymbol{r}_0+\boldsymbol{G}'\cdot \boldsymbol{r}_1$ for $\boldsymbol{r}_0\in \mathfrak {U}_1^k$ and $\boldsymbol{r}_1\in \mathfrak {U}_1^{m-k}$. Therefore, by M-LWE$_{m-k,k,q,\mathfrak {U}_1}$ assumption, $\boldsymbol{G}\cdot \boldsymbol{r}$ is computationally indistinguishable from a random element in $R_q^k$ and so is ${\mathsf{pk}} = \boldsymbol{G}\cdot \boldsymbol{r} + \boldsymbol{g}$. $\mathcal {B}$ gives $\mathsf{param} = (k,m,d,q, \boldsymbol{G}, \mathcal {H})$ and ${\mathsf{pk}}$ to $\mathcal {A}$.

$\mathcal {A}$ returns $(c, \boldsymbol{z}, c', \boldsymbol{z}')$, where $c \ne c'$, we have:

$$\begin{aligned} - \boldsymbol{G} \cdot \boldsymbol{z} + c \cdot \mathsf{pk}&= - \boldsymbol{G} \cdot \boldsymbol{z'} + c' \cdot \mathsf{pk}\\ (c - c') \cdot \mathsf{pk}&=\boldsymbol{G} \cdot (\boldsymbol{z}-\boldsymbol{z}') = \hat{\boldsymbol{G}} \cdot \left( \begin{array}{c} \boldsymbol{z}-\boldsymbol{z}' \\ 0 \end{array}\right) \end{aligned}$$

Further, multiplying Eq. (4) by $(c - c')$, we have

$$\begin{aligned} (c - c') \cdot {\mathsf{pk}}&= \boldsymbol{G}\cdot (c - c') \cdot \boldsymbol{r} + (c - c') \cdot \boldsymbol{g} = \hat{\boldsymbol{G}} \cdot (c - c') \cdot \left( \begin{array}{c} \boldsymbol{r} \\ 1 \end{array}\right) . \end{aligned}$$

Therefore, we get:

$$ \hat{\boldsymbol{G}} \cdot (c - c') \cdot \left( \begin{array}{c} \boldsymbol{r} \\ 1 \end{array}\right) = \hat{\boldsymbol{G}} \cdot \left( \begin{array}{c} \boldsymbol{z}-\boldsymbol{z}' \\ 0 \end{array}\right) . $$

That is, $\hat{\boldsymbol{G}} \cdot \boldsymbol{s} = 0$ over $R_q$ for $\boldsymbol{s} = (c - c') \cdot \left( \begin{array}{c} \boldsymbol{r} \\ 1 \end{array}\right) - \left( \begin{array}{c} \boldsymbol{z}-\boldsymbol{z}' \\ 0 \end{array}\right) .$ Observe that $\boldsymbol{s}$ cannot be the zero vector as $c \ne c'$ and the last coordinate of $\boldsymbol{s}$ is $(c-c')$. Since $\Vert \boldsymbol{z}\Vert _{_\infty },\Vert \boldsymbol{z}'\Vert _{_\infty }\le md^2-d$, we also have

$$\begin{aligned} \left\| \boldsymbol{s}\right\|&\le 2d\sqrt{d}\sqrt{md+1} + 2\cdot (md^2\sqrt{md}) \approx 2d^2\sqrt{m} \cdot \left( 1 + m\sqrt{d} \right) . \end{aligned}$$

Hence, $\boldsymbol{s}$ is a solution to M-SIS$_{k,m+1,q,\beta _{\text {SIS}}}$ for $\beta _{\text {SIS}}\approx 2d^2\sqrt{m} \left( 1 + m\sqrt{d} \right) .$    $\square$

Remark. It is not known how to build an efficient lattice-based ZK proof for sum argument. There is a theoretical work on constructing a lattice analog of Bulletproofs in [13]. However, in practice, the construction is inefficient. As the lattice analog of the Sum Argument cannot be constructed efficiently, the signature size of our lattice-based construction remains at O(n), while [10, 19] achieve $O(\log n)$ signature size. Hence, after some point (around 1100), our construction eventually produces longer signatures.

7.2 Efficiency Analysis of DualRing-LB

Signature Size. The practical security estimations of M-SIS and M-LWE against known attacks are done by following the methodology detailed in [18, Section 3.2.4]. In particular, we aim for a “root Hermite factor” of around 1.0045. The root Hermite factor is a common metric used in lattice-based cryptography to measure practical hardness. We refer to [18] for further discussion. We refer to Table 3 for the concrete parameter setting. In general, for $d=128$, the signature length can be approximated by the following formula:

$$\begin{aligned} |\sigma |=|\boldsymbol{z}| + n\cdot |c_i| \approx 4536 + 26n \text { bytes}. \end{aligned}$$

(5)

The above formula stems from the fact that $|c_i|=d\log 3/8$ bytes and $|\boldsymbol{z}|=md\log (2md^2)/8$ bytes since $\boldsymbol{z}\in R^m$ with $\Vert \boldsymbol{z}\Vert _{_\infty }\le md^2$. Plugging in $(d, m) = (128, 15)$ yields (5).

Table 3. The parameter setting of DualRing-LB. The root Hermite factor for both M-SIS and M-LWE are $\le 1.0045$. $d=128$ always. The sizes are in KB.

Although Theorems 3 and 8 imply that DualRing-LB is secure, they do not provide all the information required in the concrete parameter setting. Unlike the classical DL- or factoring-based constructions, in the lattice setting, it is important for the concrete parameter setting to know the precise (Euclidean) norm bound $\beta _{\text {SIS}}$ of M-SIS solution that arises in the security reduction. This is because the practical security estimations depend on the $\beta _{\text {SIS}}$ parameter of the M-SIS problem. Therefore, we also need to investigate in more detail the M-SIS solution length $\beta _{\text {SIS}}$ for the ring signature (not the underlying Type-T* canonical identification as in Theorem 8) and see how it depends on the parameters. We do this in the full version of the paper and show concretely what the length of the M-SIS solution is for the ring signature, which gives $\beta _{\text {SIS}}\approx 2d\sqrt{md} \cdot \left( md + n \right)$. The proof follows the same blueprint in the generic unforgeability proof of DualRing (Theorem 3), but we keep track of the norms as the proof proceeds.

Computational Efficiency. First, the modulus q is always less than 32 bits in length for the parameters in Table 3. Therefore the values in our construction fit into 32-bit registers, boosting the computational efficiency. Another advantage of our construction is that no (discrete) Gaussian sampling is required, making the implementation easier to protect against side-channel attacks.

We show the running times of DualRing-LB in Fig. 5. The code is written in Python, using the polynomial arithmetic and NTT transform in the sympy library. It is tested on a computer with Intel Core i5 2.3GHz, 8GB RAM with MacOS 10. For our scheme, the expected number of iterations due to rejection sampling in $\text {{Sign}}$ is about 2.72 and our experiment matches this prediction. The running time for a single run of sign and verify algorithms are about the same. However, the expected number of iterations for sign is 2.72. Therefore, we have the running time for sign as in Fig. 5.

The construction in [19] is at least 5 times slower than DualRing-LB for both sign and verify. Some of the possible reasons include: (1) their expected number of iterations due to rejection sampling in $\text {{Sign}}$ is about 4.757, (2) they use a polynomial of degree $d = 256$. Their scheme does not exhibit a linear increase in running time since [19] changes the system parameters (e.g., matrix dimension, degree of polynomial) for different ring size to optimize their signature size.

Fig. 5.

Lattice-based ring signatures

8 Conclusion

In this paper, we propose a generic construction of ring signature scheme using a dual ring structure. When we instantiate in the DL-setting, it is the shortest ring signature scheme without using trusted setup. When instantiated in M-LWE/SIS, we have the shortest ring signature for ring size between 4 and 2000.