# Revocable One-Time Ring Signature from Pairings

Authors: Xu Han; Dawei Zhang; Zongmin Huang; Shuang Yao; Zuodong Wu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Ring signature is an anonymous signature that allows a person to sign a message on behalf of a self-formed group while concealing the identification of the signer. However, due to its anonymity and unlinkability, malicious or irresponsible signers can easily attack the signature without any responsibility in some scenarios. In this paper, we propose a novel revocable one-time ring signature (roRS) scheme from bilinear pairings, which introduces linkability and mandatory revocability into ring signature. In particular, linkability can resist the double-signing attack and mandatory revocability guarantees that a revocation authority can identify the actual signer when a suspicious signer appears in any situation. The computational complexity of pairing computations is constant, and the time of the revocation phase is more efficient than previous schemes. Furthermore, our scheme is provable secure in the random oracle model, using DL, CDH, and DBDH assumptions.


---

## Body

## 1. Introduction

Ring signature, initially proposed in 2001 by Rivest [1], is a variant of digital signature, which can prove that one among a set of spontaneous parties has already signed a message, without revealing the actual signer. And these spontaneous parties compose a particular set called a “ring.” More specifically, a ring member can sign the signature without reveal any identity information, namely, a verifier who uses ring members’ public keys only know whether the signature is true or not and cannot find out the actual signer, and the verifier has no clue who the signer is. As shown in Figure 1, first step, the actual signer uses private key skj and randomly chooses rj∈ℤp∗ to generate Lj by using the commit function Cskj,rj; then, the signer uses Lj to compute the (j +1)-th challenge cj+1 by hash function H; signer randomly picks a response zj+1 and the (j +1)-th user’s public key pkj+1 to reconstruct the Lj+1 by the verify function Ver and generates cj+2 by hash function H; then, the ring is formed sequentially; finally, the signer uses skj,cj,rj to compute zj by the response function Z. In the whole process of generating a ring, we only need the actual signer’s private key skj and a set of users’ public keys which contains pkj. In the view of the actual signer, users except the actual signer can be seen as decoys. When the verifier does the verifications, he/she does not know any information about the knowledge of the actual signer. As for security, ring signature not only provides regular properties, such as correctness and unforgeability which any signature schemes must possess, but also has the special feature, anonymity. Correctness requires a ring member who represents a ring to sign a message and unforgeability demands that an efficient adversary cannot forge a signature on behalf of a ring which the adversary knows nothing about one secret key of ring members. As for anonymity, it allows that ring signature schemes cannot leak any information about the identity of the actual signer, that is, no one can tell which key was used to produce a signature.Figure 1
Ring signature.As an extension of ring signature, one-time ring signature can be known as linkable ring signature; the slight difference between these two kinds of ring signature is that signers in one-time ring signature use one-time key images to sign a signature, while signers in linkable ring signature take static ones. So we just need to introduce linkable ring signature in this section. Liu et al. [2] first put forward the concept of linkable ring signature (lRS). Beside the regular properties of ring signature, lRS provides two more special properties: non-slanderability and linkability. Non-slanderability guarantees that a ring member should not be entrapped that he has signed twice. Linkability requires that two signatures with the same ring on random messages must be linked if signed by the identical signer; thus, it can defeat the double-signing (double-spending) attack. This property is suitable in some practical applications; one scenario is on detecting double-voting in e-voting [3] systems. At the beginning of e-voting systems, we use ring signature schemes to implement the systems for its spontaneity, and there is no registration phase. The only requirement is that everyone has a public key pair which is considered as a well-known assumption in a ring. However, using classic ring signature as e-voting has a main problem. Anyone can vote more than once without being detected as ring signature schemes are unlinkable and anonymous. Thus, using lRS can solve this problem as double voting (double signing) can be detected easily, and anyone only can vote once in the system. Beside e-voting systems, lRS can also apply in other actual scenarios, such as ad hoc network authentication [4], blockchain-based applications [5, 6], and cryptocurrencies (Monero [7]). But in some actual transactions based on ring signature, when a ring signer has committed an offence, such as money laundering, online extortion, and terrorist financing, the authority needs to find out who is the actual signer among the ring members. Since lRS cannot let the actual signer be identified, the revocability of ring signature becomes necessary. Revocability requires that the authority can revoke the anonymity of ring signers when a suspicious signer does a transaction.In order to solve the above problem, we propose a novel revocable one-time ring signature (roRS) scheme. Our scheme can be applied in some blockchain transactions. For example, by using the functionality of ring signature, Monero [7] protects the privacy of the signer’s identity and provides autonomous mixing in transactions, but the unconditional anonymity of the ring signature makes difficult to regulate transactions for authorities. As for our scheme, a verifier can prevent the user’s double-spending behavior according to the linkability during the transactions, and a revocation authority can recover the public key of the transaction user by using the revocability of our scheme, thus restoring the transaction user’s identity.


### 1.1. Related Work

Rivest et al. [1] in 2001 proposed the first ring signature scheme, using trapdoor permutation based on the discrete logarithm problem assumption. Hereafter, many of schemes [8–11] followed this idea, but using different techniques has come out. For instance, Boneh et al. [12] first proposed a ring signature using bilinear pairings based on co-computational Diffie-Hellman (co-CDH) assumption. Cayrel et al. [13] presented a lattice-based ring signature scheme with modifying Melchor’s code-based method [14] to make the short integer solution (SIS) problem as a security assumption. As for proving the membership problem in ring signature, most of these schemes use non-interactive witness indistinguishable (NIWI) proofs [15] or dynamic accumulator [16] to be more efficient, and readers who want to learn more refer to [17–21].Then, Liu et al. [2] first proposed a linkable ring signature (lRS) scheme in 2004. This scheme inherits the anonymity of ring signature and provides a new property called linkability to resist double-spending attempts in real transactions, and it is proven to be secured in the random oracle model. Tsang et al. [22] constructed the first separable linkable ring signature scheme with introducing the security notions of accusatory linkability and non-slanderability. Liu and Wong [23] enhanced the security model for adapting to new attacking scenarios, and proposed two polynomial-structured lRS schemes based on zero knowledge proof. In 2007, Zheng [24] designed an lRS scheme based on linear feedback shift register under discrete logarithm assumption. In 2014, Liu et al. [25] put forward the first unconditional anonymous lRS scheme and provide mandatory linkability. Recently, Noether [26] proposed a dual lRS scheme which key images are tied to both output one-time public keys in a dual, and this can be considered using in non-interactive refund transactions in Monero. Tang et al. [27] presented an identity-based lRS scheme by employing trapdoor generation and rejection sampling as the basic building tool under the SIS problem on NTRU lattice. Hu et al. [28] designed a lattice-based lRS scheme under the well-studied standard lattice assumptions (SIS and LWE) in the standard model.Revocable ring signature, also called traceable ring signature, is presented to reduce and even revoke the anonymity of the signers mainly. In 2007, Liu et al. [29] first proposed a revocable ring signature that authorities can mandatory revoke the anonymity of the actual signer when authorities need in some scenarios, but this scheme cannot provide linkability against the double-signing attack. Fujisaki et al. [30] put forward a traceable ring signature which only can trace a signer who was double-signing, that is, the traceability is not mandatory. The similar constructions can be found in [17–21]. In [31], Fujisaki presented the first secure traceable ring signature scheme without random oracles in the common reference string model, and the signature size grows linearly with n where n is the number of users in the ring. Au et al. [32] adapted traceable ring signature to the identify-based setting with constant signature size and enhanced privacy. Recently, Feng et al. [33] designed a logarithmic-size traceable ring signature scheme from lattices which proved to be secure in the quantum random oracle model.


### 1.2. Motivation and Contributions

In this section, to be more concrete, we summarize that the contribution of our paper is as follows:(i)
We present a novel revocable one-time ring signature scheme and define a perfect security model which provides the security properties: unforgeability, anonymity, linkability, non-slanderability, and revocability. And revocability of our scheme is mandatory(ii)
We show that our scheme is provable secure in the random oracle model under the assumptions that discrete logarithm (DL) problem, computational Diffie-Hellman (CDH) problem, and decisional bilinear Diffie-Hellman (DBDH) problem are intractable(iii)
We compare the efficiency of our scheme and previous schemes. Our scheme requires 4 times pairing computations which is independent of the size in the ring. Besides, the computational complexity in revocation part is more efficient than previous ones, and it only requires one scalar multiplication computation and one additional computation


## 1.1. Related Work

Rivest et al. [1] in 2001 proposed the first ring signature scheme, using trapdoor permutation based on the discrete logarithm problem assumption. Hereafter, many of schemes [8–11] followed this idea, but using different techniques has come out. For instance, Boneh et al. [12] first proposed a ring signature using bilinear pairings based on co-computational Diffie-Hellman (co-CDH) assumption. Cayrel et al. [13] presented a lattice-based ring signature scheme with modifying Melchor’s code-based method [14] to make the short integer solution (SIS) problem as a security assumption. As for proving the membership problem in ring signature, most of these schemes use non-interactive witness indistinguishable (NIWI) proofs [15] or dynamic accumulator [16] to be more efficient, and readers who want to learn more refer to [17–21].Then, Liu et al. [2] first proposed a linkable ring signature (lRS) scheme in 2004. This scheme inherits the anonymity of ring signature and provides a new property called linkability to resist double-spending attempts in real transactions, and it is proven to be secured in the random oracle model. Tsang et al. [22] constructed the first separable linkable ring signature scheme with introducing the security notions of accusatory linkability and non-slanderability. Liu and Wong [23] enhanced the security model for adapting to new attacking scenarios, and proposed two polynomial-structured lRS schemes based on zero knowledge proof. In 2007, Zheng [24] designed an lRS scheme based on linear feedback shift register under discrete logarithm assumption. In 2014, Liu et al. [25] put forward the first unconditional anonymous lRS scheme and provide mandatory linkability. Recently, Noether [26] proposed a dual lRS scheme which key images are tied to both output one-time public keys in a dual, and this can be considered using in non-interactive refund transactions in Monero. Tang et al. [27] presented an identity-based lRS scheme by employing trapdoor generation and rejection sampling as the basic building tool under the SIS problem on NTRU lattice. Hu et al. [28] designed a lattice-based lRS scheme under the well-studied standard lattice assumptions (SIS and LWE) in the standard model.Revocable ring signature, also called traceable ring signature, is presented to reduce and even revoke the anonymity of the signers mainly. In 2007, Liu et al. [29] first proposed a revocable ring signature that authorities can mandatory revoke the anonymity of the actual signer when authorities need in some scenarios, but this scheme cannot provide linkability against the double-signing attack. Fujisaki et al. [30] put forward a traceable ring signature which only can trace a signer who was double-signing, that is, the traceability is not mandatory. The similar constructions can be found in [17–21]. In [31], Fujisaki presented the first secure traceable ring signature scheme without random oracles in the common reference string model, and the signature size grows linearly with n where n is the number of users in the ring. Au et al. [32] adapted traceable ring signature to the identify-based setting with constant signature size and enhanced privacy. Recently, Feng et al. [33] designed a logarithmic-size traceable ring signature scheme from lattices which proved to be secure in the quantum random oracle model.


## 1.2. Motivation and Contributions

In this section, to be more concrete, we summarize that the contribution of our paper is as follows:(i)
We present a novel revocable one-time ring signature scheme and define a perfect security model which provides the security properties: unforgeability, anonymity, linkability, non-slanderability, and revocability. And revocability of our scheme is mandatory(ii)
We show that our scheme is provable secure in the random oracle model under the assumptions that discrete logarithm (DL) problem, computational Diffie-Hellman (CDH) problem, and decisional bilinear Diffie-Hellman (DBDH) problem are intractable(iii)
We compare the efficiency of our scheme and previous schemes. Our scheme requires 4 times pairing computations which is independent of the size in the ring. Besides, the computational complexity in revocation part is more efficient than previous ones, and it only requires one scalar multiplication computation and one additional computation


## 2. Preliminaries

In this section, we introduce bilinear pairing and complex assumptions. They are utilized in the construction and provable security for our scheme. The notations used throughout the paper are described in Table1.Table 1
The symbol description.
SymbolDescriptionκA security parameterpA large prime numberℤp∗The set consisting of positive integers less thanpG1,PThe additive group withp order and a generatorGTThe multiplicative group with prime numberp ordereA bilinear pairing, wheree:G1×G1⟶GTpkrevokeA revocation authority’s public key, wherepkrevoke=y^=skrevokeP=x^PHA cryptographic hash function, whereH:0,1∗⟶ℤp∗H1A deterministic hash function, whereH1:EG1⟶EG1H2A cryptographic hash function, whereH2:G1⟶ℤp∗


### 2.1. Bilinear Pairing

LetG1 and GT be cyclic groups of a large prime order p. We write G1 additively and GT multiplicatively. We assume that the discrete logarithm problems in G1 and GT are intractable.LetG be a bilinear group generator that, on input of a security parameter κ, outputs a description of bilinear groups (G1,GT,e,P) such that G1 and GT are cyclic groups of prime order p, P is a generator of G1, and a map e:G1×G1⟶GT satisfies the following properties:
(i)
Bilinear:∀P∈G1 and a,b∈ℤp∗: eaP,bP=eP,Pab(ii)
Non-degenerate: There exists∀P∈G1, such that eP,P≠1(iii)
Computability: The mapeP,P is efficiently computability for any P∈G1


### 2.2. Complexity Assumptions

Definition 1 Discrete logarithm (DL) assumption.
We say that the DL assumption holds if for any polynomial-time adversaryA, the following advantage εDL is negligible function in κ:
(1)εDL≔PrADLP,aP=a:p,G1⟵Gκ;P⟵G1;a⟵ℤp∗;=neglκ.Definition 2 Computational Diffie-Hellman (CDH) assumption.
LetG be a group generator that, on input of a security parameter κ, outputs a cyclic group. We say that the CDH assumption holds if for any polynomial-time adversary A, the following advantage εCDH is negligible function in κ:
(2)εCDH≔PrACDHP,aP,bP=abP:p,G1⟵Gκ;P⟵G1;a,b⟵ℤp∗;=neglκ.Definition 3 Decisional bilinear Diffie-Hellman (DBDH) assumption.
Lete:G1×G1⟶GT be a bilinear pairing, P∈G1. For Z∈GT, given the tuples P,aP,bP,cP,Z, we say that the DBDH assumption holds if for any polynomial-time adversary A, the following advantage εDBDH is negligible function in κ:
(3)εDBDH≔PrADBDHP,aP,bP,cP,eP,Pabc=1−PrADBDHP,aP,bP,cP,Z=1=neglκ.


## 2.1. Bilinear Pairing

LetG1 and GT be cyclic groups of a large prime order p. We write G1 additively and GT multiplicatively. We assume that the discrete logarithm problems in G1 and GT are intractable.LetG be a bilinear group generator that, on input of a security parameter κ, outputs a description of bilinear groups (G1,GT,e,P) such that G1 and GT are cyclic groups of prime order p, P is a generator of G1, and a map e:G1×G1⟶GT satisfies the following properties:
(i)
Bilinear:∀P∈G1 and a,b∈ℤp∗: eaP,bP=eP,Pab(ii)
Non-degenerate: There exists∀P∈G1, such that eP,P≠1(iii)
Computability: The mapeP,P is efficiently computability for any P∈G1


## 2.2. Complexity Assumptions

Definition 1 Discrete logarithm (DL) assumption.
We say that the DL assumption holds if for any polynomial-time adversaryA, the following advantage εDL is negligible function in κ:
(1)εDL≔PrADLP,aP=a:p,G1⟵Gκ;P⟵G1;a⟵ℤp∗;=neglκ.Definition 2 Computational Diffie-Hellman (CDH) assumption.
LetG be a group generator that, on input of a security parameter κ, outputs a cyclic group. We say that the CDH assumption holds if for any polynomial-time adversary A, the following advantage εCDH is negligible function in κ:
(2)εCDH≔PrACDHP,aP,bP=abP:p,G1⟵Gκ;P⟵G1;a,b⟵ℤp∗;=neglκ.Definition 3 Decisional bilinear Diffie-Hellman (DBDH) assumption.
Lete:G1×G1⟶GT be a bilinear pairing, P∈G1. For Z∈GT, given the tuples P,aP,bP,cP,Z, we say that the DBDH assumption holds if for any polynomial-time adversary A, the following advantage εDBDH is negligible function in κ:
(3)εDBDH≔PrADBDHP,aP,bP,cP,eP,Pabc=1−PrADBDHP,aP,bP,cP,Z=1=neglκ.


## 3. Security Model

In this section, we give the security model and the security notions of our revocable one-time ring signature.


### 3.1. Definition of Revocable One-Time Ring Signature

#### 3.1.1. Revocable One-time Ring Signature

Revocable one-time ring signature (roRS) scheme is the tuples (Setup, KeyGen, Sign, Verify, Link, and Revoke).(i)
pp⟵Setupκ: The setup algorithm is a probabilistic polynomial time algorithm which takes as input a security parameter κ∈N and outputs a set of public parameters pp(ii)
ski,pki⟵KeyGenpp: The key generation algorithm is a probabilistic polynomial time algorithm which takes as input public parameters pp and outputs a private/public key pair ski,pki. Respectively, we denote SK and PK as the domain of possible private keys and possible public keys(iii)
σ⟵SignI,sk,Y,pkrevoke,M: The signing algorithm is a probabilistic polynomial time algorithm which takes as input a key image I, a private key sk, a message M, a revocation authority’s public key pkrevoke∈PK, and a list Y of public keys in PK which includes the one corresponding to sk and produces a signature σ(iv)
accept/reject⟵VerifyI,Y,M,pkrevoke,σ: The signature verification algorithm is a probabilistic polynomial time algorithm which takes as input the key image I, a set Y of public keys in PK, a revocation authority’s public key pkrevoke∈PK, a message M, and a signature σ and returns accept or reject(v)
linked/unlinked⟵LinkI1,I2,Y1,Y2,M1,M2,σ1,σ2: The linking algorithm which takes as input key images I1,I2, a set Y1 of public keys in PK, and a set Y2 of public keys in PK, messages M1 and M2, and signatures σ1 and σ2, such that VerifyI1,Y1,M1,σ1=accept and VerifyI2,Y2,M2,σ2=accept and returns linked or unlinked(vi)
pk⟵RevokeY,σ,skrevoke: The revoking algorithm is a probabilistic polynomial time algorithm which takes as input a set Y of public keys in PK, a valid signature σ, and a secret key skrevoke of the revocation authority and returns a public key pk in Y


#### 3.1.2. Correctness

A revocable one-time ring signature scheme should satisfy the following:(i)
Verification correctness: A signature signed by honest signers is verified to be valid as follows:(4)PrVerifyI,Y,M,pkrevoke,σ∗=accept:pp⟵Setupκ;ski,pki⟵KeyGenpp;σ⟵SignI,sk,Y,pkrevoke,M;=1.(ii)
Linking correctness: Two signatures with the same event description generated by the same secret key of the identical signer must be linkable(iii)
Revocation Correctness: The revocation authority can reveal an honest signer’s public key with overwhelming probability


### 3.2. Notions of Security

Security of our roRS scheme has five aspects: unforgeability, anonymity, linkability, non-slanderability, and revocability.Formally, we capture attack behaviors as adversarial queries to oracles implemented by a challengerS. We provide adversary A the following oracles.
(i)
JO (joining oracle).Ojoin: pki⟵JO⊥. A queries this oracle for adding a new user to the system. S keeps track of this type of queries by maintaining a list Tjoin, which is initially empty. Upon receiving a fresh query, S responds as below: picks random public parameters pp, runs ski,pki⟵KeyGenpp to obtain ski,pki. S records ski,pki in Tjoin, and then returns pkipki∈PK to A. This type of oracle captures A can observe the public keys of honest users in the system(ii)
CO (corruption oracle).Ocorrupt: ski⟵COpki. A queries this oracle with a public key pki∈PK in Tjoin. S keeps track of this type of queries by maintaining a list Tcorrupt, which is initially empty. Upon receiving a fresh query, S records pki in Tcorrupt. S returns the associated ski∈SK to A and moves this entry to Tcorrupt. This oracle captures A can corrupt some honest users and return private key ski(iii)
SO (signing oracle).Osign: σ′⟵SOI,Y,pkrevoke,M. A queries this oracle with I,Y,pkrevoke,M (a key image I, a set Y of public keys, a revocation authority’s public key pkrevoke∈PK, and a message M) and subjects to the restriction that pks∈Tjoins=1,⋯,n. S keeps track of this type of queries by maintaining a list Tsign, which is initially empty. Upon receiving a fresh query, S responds as below: S runs σ′⟵SignI,sk,pkrevoke,Y,M, records σ′ on the list Tsign, and then sends σ′ to A. This oracle captures A can generate a signature itself


#### 3.2.1. Unforgeability

We define unforgeability via the following security experimentExptAunforge between A and S:
(5)AdvAunforgeκ=PrVerifyI,Y,pkrevoke,M,σ∗=accept∧pki∈Tjoin∧σ∗∉Tsign:pp⟵Setupκ;I,Y,M,σ∗⟵AJO,CO,SOpp;.Here,n∈ℕ, Y=pk1,pk2,⋯,pkn∈PK, and I is a key image. pkrevoke is a revocation authority’s public key, and all public keys are in Tjoin. No public keys are in Tcorrupt. σ∗ is not in Tsign. AdvAunforgeκ is the successful probability of adversary A who wins the unforgeability security experiment.The process of unforgeability security experimentExptAunforge is briefly described as follow:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin, Ocorrupt, and Osign according to any adaptive strategy(3)
A outputs a forgery signature σ∗The conditions thatA wins the experiment are as follows:
(1)
All public keys are outputs ofJO(2)
VerifyI,Y,pkrevoke,M,σ∗=accept, and σ is not the output of SO(3)
No public keys have been queried toCOOur roRS satisfies unforgeability if no PPT adversary has non-negligible advantage in the above experiment.Definition 4 Unforgeability.
A revocable one-time ring signature scheme is unforgeable, if for every probabilistic polynomial-time adversaryA, the advantage AdvAunforgeκ is negligible in κ.


#### 3.2.2. Anonymity

We define anonymity via the following security experimentExptAanonymous between A and S:
(6)AdvAanonymousκ=Prs=s′:pp⟵Setupκ;I,Y,M⟵AJOpp;s⟵R1,⋯,n;σs⟵SignI,sk,Y,pkrevoke,M;s′⟵Aσs;−1n.Here,n∈ℕ, Y=pk1,pk2,⋯,pkn∈PK, and I is a key image. pkrevoke is a revocation authority’s public key, and pki is chosen by A in Tjoin. sks is a corresponding private key of pks. AdvAanonymousκ is the successful probability of adversary A who wins the anonymity security experiment.The process of anonymity security experimentExptAanonymous is briefly described as follow:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin according to any adaptive strategy(3)
A gives S a set Y of public keys in PK such that all of the public keys in Y are query outputs of JO, a key image I and a message M. Parse the set Y as pk1,pk2,⋯,pkn. S randomly picks s∈1,⋯,n and computes σs=SignI,Y,sks,M, where sks is a corresponding private key of pks. σs is given to A(4)
A outputs a guess s′∈1,⋯,nSo our roRS satisfies anonymity if no PPT adversary has non-negligible advantage in the above experiment.Definition 5 Anonymity.
A revocable one-time ring signature scheme is anonymous, if for every probabilistic polynomial-time adversaryA, the advantage AdvanonymousAκ is negligible in κ.


#### 3.2.3. Linkability

We define linkability via the following security experimentExptAlinkable between A and S:
(7)AdvAlinkableκ=PrVerifyI,Y,pkrevoke,M,σ∗=accept∧pp⟵Setupκ;pki∈Tjoin∧σi∉Tsign∧:I,Y,M,σ∗⟵AJO,CO,SOpp;Linkσ1,σ2=unlinked,i=1,2.Here,ni∈ℕ, i=1,2; Yi=pk1,pk2,⋯,pkni∈PK, a message M and signature σi, i=1,2; I is a key image, and pkrevoke is a revocation authority’s public key. All pki chosen by A are in Tjoin. σi are not in Tsign, CO has been queried less than 2 times. AdvAlinkableκ is the successful probability of adversary A who wins the linkability security experiment.The process of linkability security experimentExptAlinkable is briefly described as follows:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin, Ocorrupt, and Osign according to any adaptive strategy(3)
A outputs a forgery signature σThe conditions thatA wins the experiment are as follows:
(1)
All public keys are outputs ofJO(2)
VerifyI,Y,pkrevoke,M,σ=accept, and σ is not the output of SO(3)
A can only at most queried 1 time and at most have one user’s private key(4)
Linkσ1,σ2= unlinkedSo our roRS satisfies linkability if no PPT adversary has non-negligible advantage in the above experiment.Definition 6 Linkability.
A revocable one-time ring signature scheme is linkable, if for every probabilistic polynomial-time adversaryA, the advantage AdvAlinkableκ is negligible in κ.


#### 3.2.4. Non-slanderability

We define non-slanderability via the following security experimentExptAnon−slanderous between A and S:
(8)AdvAnon−slanderousκ=PrVerifyI,Y∗,pkrevoke,M∗,σ∗=accept∧pp⟵Setupκ;σ∗≠σ′∧σ∗∉Tsign∧I,Y,M,pks⟵AJO,CO,SOpp;pks∉Tcorrupt∧pks∉Tsign∧:σ′⟵Signsks,Y,pkrevoke,M;Linkσ∗,σ′=linkedI,Y∗,M∗,σ∗⟵AJO,CO,SOσ′;.Here,Y,Y∗∈PK, message M,M∗, and signature σ′,σ∗; pkrevoke is a revocation authority’s public key, and I is a key image. A is subject to the restriction that pks chosen by A is not allowed to be either in Tcorrupt or Tsign. All of the public keys in Y∗ and Y are in Tjoin. σ∗≠σ′ and σ∗ are not in Tsign. AdvAnon−slanderousκ is the successful probability of adversary A who wins the non-slanderability security experiment.The process of non-slanderability security experimentExptAnon−slanderous is briefly described as follows:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin, Ocorrupt, and Osign according to any adaptive strategy(3)
A outputs a forgery signature σ∗The conditions thatA wins the experiment are as follows:
(1)
VerifyI,Y∗,pkrevoke,M∗,σ∗=accept(2)
σ∗ is not an output of SO(3)
pks has not been queried to CO(4)
All public keys are inY∗; Y are query outputs of JO(5)
Linkσ′,σ∗=linkedSo our roRS satisfies non-slanderability if no PPT adversary has non-negligible advantage in the above experiment.Definition 7 Non-slanderability.
A revocable one-time ring signature scheme is non-slanderous, if for every probabilistic polynomial-time adversaryA, the advantage AdvAnon−slanderousκ is negligible in κ.


#### 3.2.5. Revocability

We define revocability via the following security experimentExptArevocable between A and S:
(9)AdvArevocableκ=PrVerifyI,Y,pkrevoke,M,σ=accept∧pp⟵Setupκ;pki∈Tjoin∧σ∉Tsign∧:sks⟵ACOpp;pkj=RevokeY,σ,skrevoke,j≠sI,Y,M,σ⟵AJO,CO,SOpp;.Here,n∈ℕ, Y=pk1,pk2,⋯,pkn∈PK, signature σ, and pkrevoke is a revocation authority’s public key, and I is a key image. All pki chosen by A are in Tjoin. σ are not in Tsign, CO has been queried less than 2 times, that is, A can only obtain at most one private key denotes as sks, and pkrevoke is the corresponding public key of skrevoke. AdvrevocableAκ is the successful probability of adversary A who wins the revocability security experiment.The process of revocability security experimentExptArevocable is briefly described as follows:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin, Ocorrupt, and Osign according to any adaptive strategy(3)
A outputs a forgery signature σThe conditions thatA wins the experiment are as follows:
(1)
VerifyI,Y,pkrevoke,M,σ=accept(2)
σ∗ is not an output of SO(3)
All public keys are query outputs ofJO(4)
CO has been queried less than 2 times, that is, A can only obtain at most one private key denotes as sks(5)
yj=RevokeY,σ,skrevoke for j≠sSo our roRS satisfies revocability if no PPT adversary has non-negligible advantage in the above experiment.Definition 8 Revocability.
A revocable one-time ring signature scheme is revocable, if for every probabilistic polynomial-time adversaryA, the advantage AdvArevocableκ is negligible in κ.


## 3.1. Definition of Revocable One-Time Ring Signature

### 3.1.1. Revocable One-time Ring Signature

Revocable one-time ring signature (roRS) scheme is the tuples (Setup, KeyGen, Sign, Verify, Link, and Revoke).(i)
pp⟵Setupκ: The setup algorithm is a probabilistic polynomial time algorithm which takes as input a security parameter κ∈N and outputs a set of public parameters pp(ii)
ski,pki⟵KeyGenpp: The key generation algorithm is a probabilistic polynomial time algorithm which takes as input public parameters pp and outputs a private/public key pair ski,pki. Respectively, we denote SK and PK as the domain of possible private keys and possible public keys(iii)
σ⟵SignI,sk,Y,pkrevoke,M: The signing algorithm is a probabilistic polynomial time algorithm which takes as input a key image I, a private key sk, a message M, a revocation authority’s public key pkrevoke∈PK, and a list Y of public keys in PK which includes the one corresponding to sk and produces a signature σ(iv)
accept/reject⟵VerifyI,Y,M,pkrevoke,σ: The signature verification algorithm is a probabilistic polynomial time algorithm which takes as input the key image I, a set Y of public keys in PK, a revocation authority’s public key pkrevoke∈PK, a message M, and a signature σ and returns accept or reject(v)
linked/unlinked⟵LinkI1,I2,Y1,Y2,M1,M2,σ1,σ2: The linking algorithm which takes as input key images I1,I2, a set Y1 of public keys in PK, and a set Y2 of public keys in PK, messages M1 and M2, and signatures σ1 and σ2, such that VerifyI1,Y1,M1,σ1=accept and VerifyI2,Y2,M2,σ2=accept and returns linked or unlinked(vi)
pk⟵RevokeY,σ,skrevoke: The revoking algorithm is a probabilistic polynomial time algorithm which takes as input a set Y of public keys in PK, a valid signature σ, and a secret key skrevoke of the revocation authority and returns a public key pk in Y


### 3.1.2. Correctness

A revocable one-time ring signature scheme should satisfy the following:(i)
Verification correctness: A signature signed by honest signers is verified to be valid as follows:(4)PrVerifyI,Y,M,pkrevoke,σ∗=accept:pp⟵Setupκ;ski,pki⟵KeyGenpp;σ⟵SignI,sk,Y,pkrevoke,M;=1.(ii)
Linking correctness: Two signatures with the same event description generated by the same secret key of the identical signer must be linkable(iii)
Revocation Correctness: The revocation authority can reveal an honest signer’s public key with overwhelming probability


## 3.1.1. Revocable One-time Ring Signature

Revocable one-time ring signature (roRS) scheme is the tuples (Setup, KeyGen, Sign, Verify, Link, and Revoke).(i)
pp⟵Setupκ: The setup algorithm is a probabilistic polynomial time algorithm which takes as input a security parameter κ∈N and outputs a set of public parameters pp(ii)
ski,pki⟵KeyGenpp: The key generation algorithm is a probabilistic polynomial time algorithm which takes as input public parameters pp and outputs a private/public key pair ski,pki. Respectively, we denote SK and PK as the domain of possible private keys and possible public keys(iii)
σ⟵SignI,sk,Y,pkrevoke,M: The signing algorithm is a probabilistic polynomial time algorithm which takes as input a key image I, a private key sk, a message M, a revocation authority’s public key pkrevoke∈PK, and a list Y of public keys in PK which includes the one corresponding to sk and produces a signature σ(iv)
accept/reject⟵VerifyI,Y,M,pkrevoke,σ: The signature verification algorithm is a probabilistic polynomial time algorithm which takes as input the key image I, a set Y of public keys in PK, a revocation authority’s public key pkrevoke∈PK, a message M, and a signature σ and returns accept or reject(v)
linked/unlinked⟵LinkI1,I2,Y1,Y2,M1,M2,σ1,σ2: The linking algorithm which takes as input key images I1,I2, a set Y1 of public keys in PK, and a set Y2 of public keys in PK, messages M1 and M2, and signatures σ1 and σ2, such that VerifyI1,Y1,M1,σ1=accept and VerifyI2,Y2,M2,σ2=accept and returns linked or unlinked(vi)
pk⟵RevokeY,σ,skrevoke: The revoking algorithm is a probabilistic polynomial time algorithm which takes as input a set Y of public keys in PK, a valid signature σ, and a secret key skrevoke of the revocation authority and returns a public key pk in Y


## 3.1.2. Correctness

A revocable one-time ring signature scheme should satisfy the following:(i)
Verification correctness: A signature signed by honest signers is verified to be valid as follows:(4)PrVerifyI,Y,M,pkrevoke,σ∗=accept:pp⟵Setupκ;ski,pki⟵KeyGenpp;σ⟵SignI,sk,Y,pkrevoke,M;=1.(ii)
Linking correctness: Two signatures with the same event description generated by the same secret key of the identical signer must be linkable(iii)
Revocation Correctness: The revocation authority can reveal an honest signer’s public key with overwhelming probability


## 3.2. Notions of Security

Security of our roRS scheme has five aspects: unforgeability, anonymity, linkability, non-slanderability, and revocability.Formally, we capture attack behaviors as adversarial queries to oracles implemented by a challengerS. We provide adversary A the following oracles.
(i)
JO (joining oracle).Ojoin: pki⟵JO⊥. A queries this oracle for adding a new user to the system. S keeps track of this type of queries by maintaining a list Tjoin, which is initially empty. Upon receiving a fresh query, S responds as below: picks random public parameters pp, runs ski,pki⟵KeyGenpp to obtain ski,pki. S records ski,pki in Tjoin, and then returns pkipki∈PK to A. This type of oracle captures A can observe the public keys of honest users in the system(ii)
CO (corruption oracle).Ocorrupt: ski⟵COpki. A queries this oracle with a public key pki∈PK in Tjoin. S keeps track of this type of queries by maintaining a list Tcorrupt, which is initially empty. Upon receiving a fresh query, S records pki in Tcorrupt. S returns the associated ski∈SK to A and moves this entry to Tcorrupt. This oracle captures A can corrupt some honest users and return private key ski(iii)
SO (signing oracle).Osign: σ′⟵SOI,Y,pkrevoke,M. A queries this oracle with I,Y,pkrevoke,M (a key image I, a set Y of public keys, a revocation authority’s public key pkrevoke∈PK, and a message M) and subjects to the restriction that pks∈Tjoins=1,⋯,n. S keeps track of this type of queries by maintaining a list Tsign, which is initially empty. Upon receiving a fresh query, S responds as below: S runs σ′⟵SignI,sk,pkrevoke,Y,M, records σ′ on the list Tsign, and then sends σ′ to A. This oracle captures A can generate a signature itself


### 3.2.1. Unforgeability

We define unforgeability via the following security experimentExptAunforge between A and S:
(5)AdvAunforgeκ=PrVerifyI,Y,pkrevoke,M,σ∗=accept∧pki∈Tjoin∧σ∗∉Tsign:pp⟵Setupκ;I,Y,M,σ∗⟵AJO,CO,SOpp;.Here,n∈ℕ, Y=pk1,pk2,⋯,pkn∈PK, and I is a key image. pkrevoke is a revocation authority’s public key, and all public keys are in Tjoin. No public keys are in Tcorrupt. σ∗ is not in Tsign. AdvAunforgeκ is the successful probability of adversary A who wins the unforgeability security experiment.The process of unforgeability security experimentExptAunforge is briefly described as follow:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin, Ocorrupt, and Osign according to any adaptive strategy(3)
A outputs a forgery signature σ∗The conditions thatA wins the experiment are as follows:
(1)
All public keys are outputs ofJO(2)
VerifyI,Y,pkrevoke,M,σ∗=accept, and σ is not the output of SO(3)
No public keys have been queried toCOOur roRS satisfies unforgeability if no PPT adversary has non-negligible advantage in the above experiment.Definition 4 Unforgeability.
A revocable one-time ring signature scheme is unforgeable, if for every probabilistic polynomial-time adversaryA, the advantage AdvAunforgeκ is negligible in κ.


### 3.2.2. Anonymity

We define anonymity via the following security experimentExptAanonymous between A and S:
(6)AdvAanonymousκ=Prs=s′:pp⟵Setupκ;I,Y,M⟵AJOpp;s⟵R1,⋯,n;σs⟵SignI,sk,Y,pkrevoke,M;s′⟵Aσs;−1n.Here,n∈ℕ, Y=pk1,pk2,⋯,pkn∈PK, and I is a key image. pkrevoke is a revocation authority’s public key, and pki is chosen by A in Tjoin. sks is a corresponding private key of pks. AdvAanonymousκ is the successful probability of adversary A who wins the anonymity security experiment.The process of anonymity security experimentExptAanonymous is briefly described as follow:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin according to any adaptive strategy(3)
A gives S a set Y of public keys in PK such that all of the public keys in Y are query outputs of JO, a key image I and a message M. Parse the set Y as pk1,pk2,⋯,pkn. S randomly picks s∈1,⋯,n and computes σs=SignI,Y,sks,M, where sks is a corresponding private key of pks. σs is given to A(4)
A outputs a guess s′∈1,⋯,nSo our roRS satisfies anonymity if no PPT adversary has non-negligible advantage in the above experiment.Definition 5 Anonymity.
A revocable one-time ring signature scheme is anonymous, if for every probabilistic polynomial-time adversaryA, the advantage AdvanonymousAκ is negligible in κ.


### 3.2.3. Linkability

We define linkability via the following security experimentExptAlinkable between A and S:
(7)AdvAlinkableκ=PrVerifyI,Y,pkrevoke,M,σ∗=accept∧pp⟵Setupκ;pki∈Tjoin∧σi∉Tsign∧:I,Y,M,σ∗⟵AJO,CO,SOpp;Linkσ1,σ2=unlinked,i=1,2.Here,ni∈ℕ, i=1,2; Yi=pk1,pk2,⋯,pkni∈PK, a message M and signature σi, i=1,2; I is a key image, and pkrevoke is a revocation authority’s public key. All pki chosen by A are in Tjoin. σi are not in Tsign, CO has been queried less than 2 times. AdvAlinkableκ is the successful probability of adversary A who wins the linkability security experiment.The process of linkability security experimentExptAlinkable is briefly described as follows:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin, Ocorrupt, and Osign according to any adaptive strategy(3)
A outputs a forgery signature σThe conditions thatA wins the experiment are as follows:
(1)
All public keys are outputs ofJO(2)
VerifyI,Y,pkrevoke,M,σ=accept, and σ is not the output of SO(3)
A can only at most queried 1 time and at most have one user’s private key(4)
Linkσ1,σ2= unlinkedSo our roRS satisfies linkability if no PPT adversary has non-negligible advantage in the above experiment.Definition 6 Linkability.
A revocable one-time ring signature scheme is linkable, if for every probabilistic polynomial-time adversaryA, the advantage AdvAlinkableκ is negligible in κ.


### 3.2.4. Non-slanderability

We define non-slanderability via the following security experimentExptAnon−slanderous between A and S:
(8)AdvAnon−slanderousκ=PrVerifyI,Y∗,pkrevoke,M∗,σ∗=accept∧pp⟵Setupκ;σ∗≠σ′∧σ∗∉Tsign∧I,Y,M,pks⟵AJO,CO,SOpp;pks∉Tcorrupt∧pks∉Tsign∧:σ′⟵Signsks,Y,pkrevoke,M;Linkσ∗,σ′=linkedI,Y∗,M∗,σ∗⟵AJO,CO,SOσ′;.Here,Y,Y∗∈PK, message M,M∗, and signature σ′,σ∗; pkrevoke is a revocation authority’s public key, and I is a key image. A is subject to the restriction that pks chosen by A is not allowed to be either in Tcorrupt or Tsign. All of the public keys in Y∗ and Y are in Tjoin. σ∗≠σ′ and σ∗ are not in Tsign. AdvAnon−slanderousκ is the successful probability of adversary A who wins the non-slanderability security experiment.The process of non-slanderability security experimentExptAnon−slanderous is briefly described as follows:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin, Ocorrupt, and Osign according to any adaptive strategy(3)
A outputs a forgery signature σ∗The conditions thatA wins the experiment are as follows:
(1)
VerifyI,Y∗,pkrevoke,M∗,σ∗=accept(2)
σ∗ is not an output of SO(3)
pks has not been queried to CO(4)
All public keys are inY∗; Y are query outputs of JO(5)
Linkσ′,σ∗=linkedSo our roRS satisfies non-slanderability if no PPT adversary has non-negligible advantage in the above experiment.Definition 7 Non-slanderability.
A revocable one-time ring signature scheme is non-slanderous, if for every probabilistic polynomial-time adversaryA, the advantage AdvAnon−slanderousκ is negligible in κ.


### 3.2.5. Revocability

We define revocability via the following security experimentExptArevocable between A and S:
(9)AdvArevocableκ=PrVerifyI,Y,pkrevoke,M,σ=accept∧pp⟵Setupκ;pki∈Tjoin∧σ∉Tsign∧:sks⟵ACOpp;pkj=RevokeY,σ,skrevoke,j≠sI,Y,M,σ⟵AJO,CO,SOpp;.Here,n∈ℕ, Y=pk1,pk2,⋯,pkn∈PK, signature σ, and pkrevoke is a revocation authority’s public key, and I is a key image. All pki chosen by A are in Tjoin. σ are not in Tsign, CO has been queried less than 2 times, that is, A can only obtain at most one private key denotes as sks, and pkrevoke is the corresponding public key of skrevoke. AdvrevocableAκ is the successful probability of adversary A who wins the revocability security experiment.The process of revocability security experimentExptArevocable is briefly described as follows:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin, Ocorrupt, and Osign according to any adaptive strategy(3)
A outputs a forgery signature σThe conditions thatA wins the experiment are as follows:
(1)
VerifyI,Y,pkrevoke,M,σ=accept(2)
σ∗ is not an output of SO(3)
All public keys are query outputs ofJO(4)
CO has been queried less than 2 times, that is, A can only obtain at most one private key denotes as sks(5)
yj=RevokeY,σ,skrevoke for j≠sSo our roRS satisfies revocability if no PPT adversary has non-negligible advantage in the above experiment.Definition 8 Revocability.
A revocable one-time ring signature scheme is revocable, if for every probabilistic polynomial-time adversaryA, the advantage AdvArevocableκ is negligible in κ.


## 3.2.1. Unforgeability

We define unforgeability via the following security experimentExptAunforge between A and S:
(5)AdvAunforgeκ=PrVerifyI,Y,pkrevoke,M,σ∗=accept∧pki∈Tjoin∧σ∗∉Tsign:pp⟵Setupκ;I,Y,M,σ∗⟵AJO,CO,SOpp;.Here,n∈ℕ, Y=pk1,pk2,⋯,pkn∈PK, and I is a key image. pkrevoke is a revocation authority’s public key, and all public keys are in Tjoin. No public keys are in Tcorrupt. σ∗ is not in Tsign. AdvAunforgeκ is the successful probability of adversary A who wins the unforgeability security experiment.The process of unforgeability security experimentExptAunforge is briefly described as follow:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin, Ocorrupt, and Osign according to any adaptive strategy(3)
A outputs a forgery signature σ∗The conditions thatA wins the experiment are as follows:
(1)
All public keys are outputs ofJO(2)
VerifyI,Y,pkrevoke,M,σ∗=accept, and σ is not the output of SO(3)
No public keys have been queried toCOOur roRS satisfies unforgeability if no PPT adversary has non-negligible advantage in the above experiment.Definition 4 Unforgeability.
A revocable one-time ring signature scheme is unforgeable, if for every probabilistic polynomial-time adversaryA, the advantage AdvAunforgeκ is negligible in κ.


## 3.2.2. Anonymity

We define anonymity via the following security experimentExptAanonymous between A and S:
(6)AdvAanonymousκ=Prs=s′:pp⟵Setupκ;I,Y,M⟵AJOpp;s⟵R1,⋯,n;σs⟵SignI,sk,Y,pkrevoke,M;s′⟵Aσs;−1n.Here,n∈ℕ, Y=pk1,pk2,⋯,pkn∈PK, and I is a key image. pkrevoke is a revocation authority’s public key, and pki is chosen by A in Tjoin. sks is a corresponding private key of pks. AdvAanonymousκ is the successful probability of adversary A who wins the anonymity security experiment.The process of anonymity security experimentExptAanonymous is briefly described as follow:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin according to any adaptive strategy(3)
A gives S a set Y of public keys in PK such that all of the public keys in Y are query outputs of JO, a key image I and a message M. Parse the set Y as pk1,pk2,⋯,pkn. S randomly picks s∈1,⋯,n and computes σs=SignI,Y,sks,M, where sks is a corresponding private key of pks. σs is given to A(4)
A outputs a guess s′∈1,⋯,nSo our roRS satisfies anonymity if no PPT adversary has non-negligible advantage in the above experiment.Definition 5 Anonymity.
A revocable one-time ring signature scheme is anonymous, if for every probabilistic polynomial-time adversaryA, the advantage AdvanonymousAκ is negligible in κ.


## 3.2.3. Linkability

We define linkability via the following security experimentExptAlinkable between A and S:
(7)AdvAlinkableκ=PrVerifyI,Y,pkrevoke,M,σ∗=accept∧pp⟵Setupκ;pki∈Tjoin∧σi∉Tsign∧:I,Y,M,σ∗⟵AJO,CO,SOpp;Linkσ1,σ2=unlinked,i=1,2.Here,ni∈ℕ, i=1,2; Yi=pk1,pk2,⋯,pkni∈PK, a message M and signature σi, i=1,2; I is a key image, and pkrevoke is a revocation authority’s public key. All pki chosen by A are in Tjoin. σi are not in Tsign, CO has been queried less than 2 times. AdvAlinkableκ is the successful probability of adversary A who wins the linkability security experiment.The process of linkability security experimentExptAlinkable is briefly described as follows:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin, Ocorrupt, and Osign according to any adaptive strategy(3)
A outputs a forgery signature σThe conditions thatA wins the experiment are as follows:
(1)
All public keys are outputs ofJO(2)
VerifyI,Y,pkrevoke,M,σ=accept, and σ is not the output of SO(3)
A can only at most queried 1 time and at most have one user’s private key(4)
Linkσ1,σ2= unlinkedSo our roRS satisfies linkability if no PPT adversary has non-negligible advantage in the above experiment.Definition 6 Linkability.
A revocable one-time ring signature scheme is linkable, if for every probabilistic polynomial-time adversaryA, the advantage AdvAlinkableκ is negligible in κ.


## 3.2.4. Non-slanderability

We define non-slanderability via the following security experimentExptAnon−slanderous between A and S:
(8)AdvAnon−slanderousκ=PrVerifyI,Y∗,pkrevoke,M∗,σ∗=accept∧pp⟵Setupκ;σ∗≠σ′∧σ∗∉Tsign∧I,Y,M,pks⟵AJO,CO,SOpp;pks∉Tcorrupt∧pks∉Tsign∧:σ′⟵Signsks,Y,pkrevoke,M;Linkσ∗,σ′=linkedI,Y∗,M∗,σ∗⟵AJO,CO,SOσ′;.Here,Y,Y∗∈PK, message M,M∗, and signature σ′,σ∗; pkrevoke is a revocation authority’s public key, and I is a key image. A is subject to the restriction that pks chosen by A is not allowed to be either in Tcorrupt or Tsign. All of the public keys in Y∗ and Y are in Tjoin. σ∗≠σ′ and σ∗ are not in Tsign. AdvAnon−slanderousκ is the successful probability of adversary A who wins the non-slanderability security experiment.The process of non-slanderability security experimentExptAnon−slanderous is briefly described as follows:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin, Ocorrupt, and Osign according to any adaptive strategy(3)
A outputs a forgery signature σ∗The conditions thatA wins the experiment are as follows:
(1)
VerifyI,Y∗,pkrevoke,M∗,σ∗=accept(2)
σ∗ is not an output of SO(3)
pks has not been queried to CO(4)
All public keys are inY∗; Y are query outputs of JO(5)
Linkσ′,σ∗=linkedSo our roRS satisfies non-slanderability if no PPT adversary has non-negligible advantage in the above experiment.Definition 7 Non-slanderability.
A revocable one-time ring signature scheme is non-slanderous, if for every probabilistic polynomial-time adversaryA, the advantage AdvAnon−slanderousκ is negligible in κ.


## 3.2.5. Revocability

We define revocability via the following security experimentExptArevocable between A and S:
(9)AdvArevocableκ=PrVerifyI,Y,pkrevoke,M,σ=accept∧pp⟵Setupκ;pki∈Tjoin∧σ∉Tsign∧:sks⟵ACOpp;pkj=RevokeY,σ,skrevoke,j≠sI,Y,M,σ⟵AJO,CO,SOpp;.Here,n∈ℕ, Y=pk1,pk2,⋯,pkn∈PK, signature σ, and pkrevoke is a revocation authority’s public key, and I is a key image. All pki chosen by A are in Tjoin. σ are not in Tsign, CO has been queried less than 2 times, that is, A can only obtain at most one private key denotes as sks, and pkrevoke is the corresponding public key of skrevoke. AdvrevocableAκ is the successful probability of adversary A who wins the revocability security experiment.The process of revocability security experimentExptArevocable is briefly described as follows:
(1)
A runs Setupκ with security parameter κ and sends the public parameter pp to A(2)
A is allowed to make queries to Ojoin, Ocorrupt, and Osign according to any adaptive strategy(3)
A outputs a forgery signature σThe conditions thatA wins the experiment are as follows:
(1)
VerifyI,Y,pkrevoke,M,σ=accept(2)
σ∗ is not an output of SO(3)
All public keys are query outputs ofJO(4)
CO has been queried less than 2 times, that is, A can only obtain at most one private key denotes as sks(5)
yj=RevokeY,σ,skrevoke for j≠sSo our roRS satisfies revocability if no PPT adversary has non-negligible advantage in the above experiment.Definition 8 Revocability.
A revocable one-time ring signature scheme is revocable, if for every probabilistic polynomial-time adversaryA, the advantage AdvArevocableκ is negligible in κ.


## 4. Construction

In this section, we propose our new revocable one-time ring signature (roRS) scheme. Our scheme is constructed as follows:Setup: Let G1 and GT be two groups with prime order p>2κ; G1 is an additive group and GT is a multiplicative group. P is the generator of G1 and a bilinear pairing e:G1×G1⟶GT. Let H:0,1∗⟶ℤp∗ and H2:G1⟶ℤp∗ be two cryptographic hash functions and H1:EG1⟶EG1 be a deterministic hash function. And the public parameters params=G1,GT,e,P,H,H1,H2,p..KeyGen: A ring user i randomly picks xi∈ℤp∗ and computes pki=xiP∈G1. So the user i has secret key and public key pair ski,pki=xi,xiP. The secret key skrevoke of the revocation authority is x^, and the corresponding public key pkrevoke is y^ = x^P.Sign: Let Y=pk1,pk2,⋯,pkn be a set of users’ public keys in the ring. So a ring user s1≤s≤n has his own key pair sks,pks=xs,xsP. Additionally, the user has given a message M∈0,1∗; then, the user s with the knowledge of xs computes a signature of knowledge as follows:
(1)
Compute the key imageI: First, use a hash function with pks to make one signer only have the corresponding one key image.K=H1pks; then, compute the key image I with the signer’s private key xs and K,I=xsK.
(2)
Randomly chooseω∈ℤp∗, and compute: First make proof of knowledge for private key xs, B1=ωP and then construct B2 for the revoking phase and B3 for the verification phase:(10)B2=ωy^+pks,B3=eωpks,K.(3)
Randomly chooseci∈ℤp∗, where i=1,2,⋯,n; and randomly choose zi∈G1, where i=1,2,⋯,s−1,s+1,⋯,ni≠s. Then, set the following transformations for all users in the ring:(11)Ci=ciP,ifi=sciP+pksH2zi,ifi≠sandZi=ciK,ifi=sciK+IH2zi,ifi≠s.(4)
Get the non-interactive challenge:(12)z=HM,C1,⋯,Cn,Z1,⋯,Zn.(5)
Randomly chooseΦi∈G1, where i=1,2,⋯,s−1,s+1,⋯,n and i≠s. Then when i≠s, make a hash function hi to be a random number for verifiers. Compute hi=HΦi,Y,I,M,B3, where i≠s(6)
Then, wheni=s, use notions above and compute:ComputeΦs as a random number:
(13)Φs=zP−∑i=1,i≠snhipki+Φi∈G1,then make a hash function hs as a random number for i=s:
(14)hs=HΦs,Y,I,M,B3∈ℤp∗,use private key xs to make the response V when i=s:
(15)V=z+hsxs⋅B1∈G1.(7)
To close the ring, setli=cs−xsH2Φs,ifi=sci,ifi≠s(8)
Output the signatureσ=l1,⋯,ln,Φ1,⋯,Φn,V,I,B1,B2Verify: Given the tuples σ,Y,M, the verifier carries out the following steps:
(1)
ComputeCi′=liP+pksH2Φi and Zi′=liH1pks+IH2Φi, B3=eB1,I, and hi=HΦi,Y,I,M,B3∈ℤp∗, where i=1,2,⋯,n(2)
Check whether∑i=1nhipki+Φi=HM,C1′,⋯,Cn′,Z1′,⋯,Zn′⋅P and eP,V=e∑i=1nhipki+Φi,B1. If two equalities hold, accept the signature; otherwise, reject itLink: On receive the tuples:(16)σ1=⋅,I1,Y1,M1,σ2=⋅,I2,Y2,M2.The verifier checks if both σ1 and σ2 are two valid signatures. If yes, then outputs link if I1=I2. Otherwise, reject.Revoke: On receive the tuples Y,σ,skrevoke. The revocation authority first checks whether σ is a valid signature. If it holds, continue; otherwise, reject. In order to revoke the anonymity of the actual signer, the revocation authority makes as follows:If there existsys∈Y, such that ys=B2−x^B1, where ys is the public key of the actual signer.


## 5. Correctness Analysis

### 5.1. Verification Correctness

On correctness, using the bilinearity and nondegeneracy of the pairinge, a signature is correctly verified by the Verify algorithm as follows:
(17)B3=eB1,I=eωP,xsK=eωxsP,K=eωpks,K,e∑i=1nhi⋅pki+Φi,B1=e∑i=1,i≠snhi⋅pki+Φi+hs⋅pks+Φs,B1=ez⋅P+hs⋅pks,B1=eP,V.


#### 5.1.1. Linking Correctness

On linking correctness, the signer computes the key image as follows:(18)I=xiH1pki.Therefore, the user can only compute the key image once with the same event description.


#### 5.1.2. Revoking Correctness

On revoking correctness, the revocation authority can successfully identify the actual signer’s public key as follows:(19)ys=B2−x^B1=ωy^+pks−x^ωP=pks,where x^ is the revocation authority’s private key and ys is the actual signer’s public key.


## 5.1. Verification Correctness

On correctness, using the bilinearity and nondegeneracy of the pairinge, a signature is correctly verified by the Verify algorithm as follows:
(17)B3=eB1,I=eωP,xsK=eωxsP,K=eωpks,K,e∑i=1nhi⋅pki+Φi,B1=e∑i=1,i≠snhi⋅pki+Φi+hs⋅pks+Φs,B1=ez⋅P+hs⋅pks,B1=eP,V.


### 5.1.1. Linking Correctness

On linking correctness, the signer computes the key image as follows:(18)I=xiH1pki.Therefore, the user can only compute the key image once with the same event description.


### 5.1.2. Revoking Correctness

On revoking correctness, the revocation authority can successfully identify the actual signer’s public key as follows:(19)ys=B2−x^B1=ωy^+pks−x^ωP=pks,where x^ is the revocation authority’s private key and ys is the actual signer’s public key.


## 5.1.1. Linking Correctness

On linking correctness, the signer computes the key image as follows:(18)I=xiH1pki.Therefore, the user can only compute the key image once with the same event description.


## 5.1.2. Revoking Correctness

On revoking correctness, the revocation authority can successfully identify the actual signer’s public key as follows:(19)ys=B2−x^B1=ωy^+pks−x^ωP=pks,where x^ is the revocation authority’s private key and ys is the actual signer’s public key.


## 6. Security Analysis

In this section, the security proofs of the proposed scheme are given.Theorem 9 Unforgeability.
Our proposed scheme is unforgeable in the random oracle model with the CDH assumption.Proof.
Suppose there exists a PPT adversaryA with advantage ε, which means that A can forge a valid signature with probability ε. Then, we use a simulator S to solve the CDH problem. Let P,aP,bP be a given instance, where a,b is randomly picked in ℤp∗ and P∈G1. Through the adversary A, we use the simulator S which outputs the CDH solution abP. S randomly selects j∈1,⋯,n as the actual signer in the simulation. So the simulator S simulates the oracles by interacting with the adversary A in the nature way as follows:
(1)
Setup:S sets pkj=aP and B1=bP. S randomly chooses u∈ℤp∗ and sets y^=uP. A is given the public parameters G1,GT,p,e,P,H,H1,H2, and the public keys Y=pk1,pk2,⋯,pkn(2)
Queries:A queries the oracles H,H1,H2,JO, CO, and SO in this phase, and S sets several lists to record the queries and answers. These lists are initially empty(i)
H-queries: S maintains and checks a corresponding list LH as A queries hash values. If an entry for the query is found in LH, S returns the same answer to A. Otherwise, S generates a random value as an answer to A, and then the query and the answer are added in LH(ii)
H1-queries: S maintains a list LH1. When A issues a query H1αi, S randomly chooses f1∈G1 and sets H1αi=f1 as the answer. The query and the answer then are stored in list LH1(iii)
H2-queries: S maintains a list LH2. When A issues a query H1βi, S randomly chooses f2∈ℤp∗ and sets H2βi=f2 as the answer. The query and the answer then are stored in list LH2(iv)
JO-queries: When A queries JO at the jth query, S returns the corresponding public key pkj=aP to A. When A queries JO at the ith query(i≠j), S randomly chooses di∈ℤp∗ and returns diP as the corresponding public key. The query and the answer then are stored in list LJO(v)
CO-queries: When A queries CO with the public key pki which is an output of JO, S first checks if i=j. If yes, S fails and stops. Otherwise, S returns the corresponding di as the corresponding secret key. The query and the answer then are stored in list LCO(vi)
SO-queries: When A queries SO with a tuple event,M,Y,pkj. If pki≠pkj, S outputs a signature σ by Sign algorithm. Otherwise, S maintains a list Lsign with a tuple event,pkj,I and performs as follows:
(1)
S retrieves the list Lsign, if pkj,I is found, and then takes the value I. If not, randomly selects a new value I∈G1 and adds pkj,I to the list Lsign(2)
S computes B1=bP,B2=buP+aP,B3=eB1,I(3)
S chooses a random j∈1,⋯,n(4)
S chooses li∈ℤp∗ and Φi∈RG1 randomly, where
i=1,2,⋯,j−1,j+1,⋯,n and i≠j; and S computes Ci=liP+f2aP and Zi=lif1+f2I and then selects hi∈ℤp∗ in LH such that HΦi,M,Y,I,B3=hi(5)
S randomly picks z,hj∈ℤp∗ and computes(20)Φj=z⋅P−hj⋅pkj+∑i=1,i≠jnhipki+Φi,
and stores the valuehj=HΦj,M,Y,I,B3 to LH. If there has a collision with hash values in LH, do Step (5) again until no collision happen
(6)
S computes V=zB1 and then outputs σ=l1,⋯,ln,Φ1,⋯,Φn,V,I,B1,B2 as a response to A
Since each response is independently and uniformly distributed, all responses in the simulation are as in the real attack. Besides, all responses toSO are valid, and the output σ=l1,⋯,ln,Φ1,⋯,Φn,V,I,B1,B2 in signing query can be verified with the Verify algorithm. Therefore, from A’s view, the simulation is indistinguishable from the real attack. Now, A has the tuple σ=l1,⋯,ln,Φ1,⋯,Φn,V,I,B1,B2,h1,⋯,hn, then by using Forking Lemma for ring signature [34], S rewinds the same random tape to let A obtain another tuple σ′=l1,⋯,ln,Φ1,⋯,Φn,V′,I,B1,B2,h1′,⋯,hn′ such that hj≠hj′ for all i∈1,⋯,n and i≠j. Then, there exists V−V′=hj−hj′⋅a⋅B1=hj−hj′⋅a⋅bP, that is,
(21)V−V′hj−hj′=abP.
Therefore,S can compute abP as a solution to solve CDH problem. Due to the Forking Lemma, the probability of successful rewind simulation is at least ε/4. Then, S can solve the CDH problem with probability ε/4 at least.Theorem 10 Anonymity.
Our proposed scheme is anonymous in the random oracle model with the DBDH assumption.Proof.
Suppose there exists a PPT adversaryA with advantage ε. Then, we use a simulator S to solve the DBDH problem. Let aP,bP,cP,Z be a given instance, where a,b,c is random picked in Zp∗, Z∈GT, and P∈G1. Through the adversary A, the simulator S’s objective is to determine whether Z=eP,Pabc.
So the simulatorS simulates the oracles by interacting with the adversary A as follows:
(1)
Setup: The challenge signature is created using the randomly picked public key inY. S randomly chooses u∈ℤp∗ and sets y^=uP. In addition, S sets pkj=aP and K=bP. A is given the system parameters P and the public keys Y=pk1,pk2,⋯,pkn of signers(2)
Queries:A does the same queries with the oracles (H,H1,H2,JO and CO) as Theorem 9(3)
Then,A queries SO, and S performs the steps as follows:(1)
S retrieves the list Lsign, if pkj,I is found, and then takes the value I. If not, randomly selects a new value I∈G1 and adds pkj,I to the list Lsign(2)
S sets B1=cP and B3=Z∈GT and computes B2=cuP+bP(3)
S chooses a random j∈1,⋯,n(4)
S chooses li∈ℤp∗ and Φi∈RG1 randomly, where i=1,2,⋯,j−1,j+1,⋯,n and i≠j; and S computes Ci=liP+f2aP and Zi=lif1+f2I and then selects hi∈ℤp∗ in LH such that(22)HΦi,M,Y,I,Z=hi(5)
S randomly picks z,hj∈ℤp∗ and computes(23)Φj=z⋅P−hj⋅pkj+∑i=1,i≠jnhipki+Φi,and stores the value hj=HΦj,M,Y,I,Z to LH. If there has a collision with hash values in LH, do this step again until no collision happens.
(6)
S computes V=zB1 and then outputsσ=l1,⋯,ln,Φ1,⋯,Φn,V,I,B1,B2 as a response to A
S gives σ to A, and A can query the random oracles adaptively and returns a bit η∈0,1. Suppose A guesses that the signer’s index is j∈1,n. If A cannot identify a signer, S returns 0. If j=s, it returns 1; if j=0, it returns 0; otherwise, it returns 1/0 with equal probability. If Z=eP,Pbcd, then B3=eωpkj,K=ecaP,bP=eP,Pabc=Z. And when S returns 0, from A’s view, all signers has equal probability to sign the signature. Suppose A has advantage ε in the simulation, then we set PrZ=eP,Pabc=1/2+ε. The probability of the right choice is computed as
(24)PrZ=eP,Pbcd≥12PrZ=eP,PbcdS⟵1+PrZ=eP,PbcdS⟵0≥1212+12n+ε2+12−12n=12+ε4.
Therefore,S can determine whether Z=eP,Pabc with the probability than 1/2 if A can win, contradiction occurs.Theorem 11 Linkability.
Our proposed scheme is linkable in the random oracle model with the discrete logarithm assumption.Proof.
In order to prove linkability of our roRS scheme, we perform the same setting of oracle queries as the proof in Theorem9, and we allow S to give A the public parameters, where S has at most one private key sks, and this private key can correspond to two different keys in ring group Y for i=1,2. (When A queries the CO, A can only get one private key. A can be allowed to get only one private key.)
So through the queries,A can output two valid signatures:
(25)σ1=⋅,Φ11,⋯,Φn1,V1,I1,σ2=⋅,Φ12,⋯,Φn2,V2,I2,and the key image of σ1 is Is1=xsH1pks, and the key image of σ2 is Is2=xs′H1pks.
Forσ1, S rewinds the same tape with a different value to obtain another valid signature σ~1. Then, we obtain
(26)σ~1=⋅,Φ~11,⋯,Φ~n1,V~1,I1.
IfΦs1=Φ~s1, abort. If Φs1≠Φ~s1, we have
(27)V~1−V1=z+h~s1xsP−z+hs1xsP,xs=logPV~1−V1h~s1−hs1,
whereI1=xsH1pks and ys=xsP=pks.
Forσ2, S rewinds the same tape with a different value to obtain another valid signature σ~2. Then, we obtain
(28)σ~2=⋅,Φ~12,⋯,Φ~n2,V~2,I2,B1,B2.
IfΦs2=Φ~s2, abort. If Φs2≠Φ~s2, we have
(29)V~2−V2=z+h~s2xs′P−z+hs2xs′P,xs′=logPV~2−V2h~s2−hs2.
Therefore,xs=xs′ and I1=I2. Two signatures σ1,σ2 are linked. S can break DLP, and the advantage of A is negligible since the rewind simulation is successful.Theorem 12 Non-slanderability.
Our proposed scheme is non-slanderable in the random oracle model with the discrete logarithm assumption.Proof.
In order to prove non-slanderability of our roRS scheme, we perform the same setting of oracle queries as the proof in Theorem9; the adversary A can query CO to get any public key, but A cannot be allowed to query the signer’s public key pks. But A can give simulator S the tuples pks,Y,M,pkrevoke. S uses the tuple to generate a valid signature σ=⋅,I which I is the key image computed using xs. (A can keep querying oracles with the restriction of submitting pks to CO.)
SupposeA generates another valid signature σ"=⋅,I" which I" is computed by xs" and σ" is not an output of SO. Additionally, σ and σ" are linked. Therefore, I=I" which means I=xsH1pks=I"=xs"H1pks. So xs=xs", it can imply that A knows the secret key xs corresponding to pks. This is opposite to our assumption that A cannot query CO to get the secret key of pks.Theorem 13 Revocability.
Our proposed scheme is revocable in the random oracle model if the construction is unforgeable.Proof.
In order to prove revocability of our roRS scheme, we perform the same setting of oracle queries as the proof in Theorem9, and we allow S give A the public parameters, where A can get one private key denoted as sks=xs corresponding to pks=ys in Y from CO. Due to the fact that pk1,⋯,pks−1,pks+1,⋯,pkn is randomly and independently distributed, A cannot tell out the corresponding secret keys according to our assumption. Then, we suppose that A can generate a valid signature σ=l1,⋯,ln,Φ1,⋯,Φn,V,I,B1,B2 successfully for contradiction. The valid signature must be generated by sks=xs because our proposed scheme is unforgeable. There exists a case that can break revocability in our scheme. We consider one case that can break revocability of our scheme. A randomly selects j∈1,⋯,s−1,s+1,⋯,nj≠s and performs the Sign algorithm; but on behalf of closing the ring, A must know the secret key xj(xj≠xs). Due to our assumption that A can only get one private key, contradiction occurs.


## 7. Efficiency Analysis

In this section, performance analysis is shown in Table2. The efficiency computational cost and signature size between our proposed scheme and several signature schemes such as revocable ring signature [29], traceable ring signature [30] and so on. Then, we have several computational notions need to define as follows in Table 3.Table 2
Comparison of ring signature schemes.
SchemeSignature sizeSignVerifyAssumptionSecurity modelZhang et al. [35]nG12n−1Smn+1Pairqs-CAAROMSchäge et al. [36]n+1G1n+2Sm+naddn+2Pair+naddCDHStanMLiu et al. [25]2n+3GT3n+4Sm+4n+3add2n+5Pair+3n+1addCDHStanMroRSnG1+nΖp∗n+1Sm+Pair4Pair+nSmDL, DBD, CDHROMTable 3
The notions in comparison.
NotionDescriptionℤp∗The length of the elements inℤp∗G1The size of the underlying group inG1G2The size of the underlying group inG2GTThe size of the underlying group inGTaddThe time required for an addition computationδmThe time required for a scalar multiplication computationPairThe time required for a pairing computationROMThe abbreviation for random Oracle modelStanMThe abbreviation for standard modelWe do the comparison about computation cost on the size of signature schemes and the timings of signing and verifying with [25, 29, 30, 35, 36], where n is the number users included in the group.From Table2, we compare our scheme with [25, 35, 36] in signature size, signing, verifying, assumption and security model. We can see that roRS and [25, 35, 36] have the same level of computational complexity in terms of signature size and signature signing. As for verifying, we only need the constant pairing computations which show more efficient than [25, 35, 36] constructed from bilinear pairings similarly. And our security model is built in the random oracle model that is different from [25, 36] built in the standard model.In Table4, in relation to the revocation phase, we only need one scalar multiplication computation and one addition computation compared with n pairing computations in [29] and 2n addition computations and 2n scalar multiplication computations in [30]. As for the functionality of roRS and [29, 30], [29] cannot achieve the linkability, and [30] cannot provide mandatory revocability; nevertheless, we have accomplished the linkability and the mandatory revocation simultaneously in the random oracle.Table 4
Comparison in [29, 30] and roRS.
SchemeSignature sizeRevokeAssumptionLinkabilityMandatory RevocabilityLiu et al. [29]2n+2Ζp∗nPairDBDH✘√Fujisaki et al. [30]2n+1Ζp∗``2nadd+2nSmDl, DDH√✘roRSnG1+nΖp∗Sm+addDl, DBDH,CDH√√


## 8. Conclusion

In this literature, we proposed a novel revocable one-time ring signature scheme based on bilinear pairings, which is provable secure under the DL, DBDH, and CDH assumptions in the random oracle model. In our scheme, we have simultaneously introduced linkability and mandatory revocability to distinguish from other ring signature schemes. In particular, linkability can prevent the double-signing attack, and mandatory revocability guarantees that a revocation authority can identify the actual signer when the actual signer commits a crime in transactions. The scheme about revocation phase requires only one scalar multiplication computation and one additional computation, and the pairing computations in the timings of verifying phase is constant. And constructing provable security revocable one-time ring signature schemes from lattices to resist quantum attackers is an interesting problem that we leave open for further research.



---

*Source: 8021267-2022-08-18.xml*