# Accountable Monero System with Privacy Protection

Authors: Yifan Zhang; Haixia Xu
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Monero is one of the prominent cryptocurrencies bringing robust privacy safeguard levels. However, for Monero lacking accountability, it is easy to use anonymity and privacy for committing the crime without the leakage of identity. And some exchanges are not very receptive to Monero. The purpose of this study is to balance privacy and accountability in Monero. Specifically, we studied the way to provide accountability while keeping privacy. We develop an accountable Monero model. Our model isolates three kinds of roles, users, the trusted registration authority, and a trusted regulator. Accountability enables the trusted regulator to reveal the signer’s identity. Only the trusted regulator can trace users’ public keys as needed. We give a construction for the accountable Monero system by combining CryptoNote protocol with ElGamal encryption. Our instantiation is with a marginal influence on efficiency. The security of our scheme is based on the discrete logarithm and decisional Diffie–Hellman assumption.


---

## Body

## 1. Introduction

Cryptocurrencies are digital currencies using cryptographic primitives to ensure transaction security, control the supply of currency, and verify the ownership of coins. Quite a few cryptocurrencies build decentralized blockchain-based transaction ledgers and run on a peer-to-peer network. Such cryptocurrencies have the benefit of direct transactions among users. Issuing currency and managing transactions are completed by collaborative efforts between peers in the network. Among the decentralized cryptocurrencies, Bitcoin accounts for more than 50% of the entire cryptocurrency market capitalization. Its use of pseudonyms corresponds to Bitcoin address towards protecting users’ privacy. Nevertheless, Bitcoin relies on a shared transaction ledger and proof-of-work (PoW) consensus protocol to prevent double-spending. This requires all transactions to be public, linkable, and stored in the append-only ledger. Therefore, once a pseudonym is connected to a user’s true identity, all associated transactions undertaken by the pseudonym are revealed. Bitcoin’s reliance on pseudonyms to provide anonymity has been severely constrained. Different blockchain analysis techniques such as multisignature addressing techniques and network traffic analyzing techniques can break down user anonymity status [1].Many researchers show that Bitcoin has various privacy-related weaknesses. A multitude of privacy-enhancing technologies can be classified into two major categories, namely, mixing services and altcoins. In the first, mixing protocols consist of two modes: centralized mixing protocols and distributed mixing networks. The former, such as [2], are to hide the relationship between the user and the coins by a mixer that randomly mixes users’ coins. The latter, like [3], enable a set of untrusted users to mix their coins without being reliant on support from a third party. The second category is based on cryptographic technologies, such as Monero [4] using ring signatures and ZeroCash [5] using noninteractive zero-knowledge proofs.The two types of methods can be used in the construction of anonymous cryptocurrencies to meet the users’ demand for privacy protection. However, anonymous cryptocurrencies have become powerful weapons that help cyber-criminals perform various illicit activities, such as ransomware, tax evasion, black market trade, and money laundering while evading prosecution. As a typical member of the second privacy protection category, Monero was launched in 2014. Privacy and scalability are the main focus of Monero. In privacy protection aspects, the key innovation of Monero is the use of the ring confidential transaction (RingCT) protocol to hide the sender’s address and transaction amount, and the employment of stealth address to conceal the receiver’s address. Monero has become a medium of exchange on the black market. Three of the top five black markets accept Monero as a means of payment. In addition, Monero is used for paying off ransom. In 2017, the organization behind the WannaCry ransomware tried to convert the bitcoin ransoms received into Monero [6]. Cybercriminals have realized that using bitcoin allows blockchain transactions to expose their identity, so they increasingly demand ransom payments in Monero coins. It also affects the plans of some exchanges to list Monero, increasing the difficulty of exchange between Monero and legal tender and other cryptocurrencies. Moreover, adding accountability will help Monero to be acceptable to law enforcement agencies [7]. We aim to achieve a balance between accountability and privacy in Monero.


### 1.1. Our Contribution

We propose a new accountable Monero system based on the RingCT protocol. In the system, we add two roles: trusted registration authority and trusted regulator. The trusted registration authority interacts with users to generate certificates and keys for them. The trusted regulator can gain the secret index selected by the transaction payer and can expose the long-term public key of offenders. Anonymity can still be guaranteed except for the tracing of the trusted regulator. We take advantage of cryptographic techniques to design a scheme with privacy and accountability assurance. Specifically, our contributions are as follows:(1)
We propose a new accountable Monero system, which includes users, the trusted registration authority, and the trusted regulator. To make the tracing for a user in the system possible, we employ the certified public key as the user’s long-term public key. Our approach combines signature with rerandomizable keys, the signature of knowledge, and the RingCT protocol. The payer encrypts a randomization factor during spending, and the trusted regulator can obtain the payer’s one-time public key by decryption. Long-term public keys can be further traced.(2)
The combination with Monero’s RingCT protocol has produced the application of a more efficient accountable Monero system. We compare the efficiency and communication in our accountable Monero system, Monero, and the accountable Monero system in [8]. The performance analysis shows that our system has better computational efficiency in the most frequently used settings.


### 1.2. Related Work

Ring signature schemes generally include one-out-of-many proofs or membership proofs. The RingCT protocol used by Monero [9] is based on the discrete logarithm version of one-out-of-many signature in [10], which convinces a verifier that the signature is from one of n possible independent signers without revealing which one. In addition, an accumulator is a construction tool for ring signatures. Accumulators allow representing a set of elements Y=y1,y2,…,yn as a single value v whose size is independent of Y’s cardinality. For each set element y, there exists an efficiently computable witness w to prove that y is accumulated in v. In 2009, Au et al. [11] proposed the first dynamic universal accumulator. Dynamic accumulators can efficiently add and delete elements to the accumulated value. As the value is renewed, the witness w for each set element can be efficiently updated. The universality means that, for any element y¯ outside the set Y, there exists an efficiently computable witness w¯ to prove that y¯ is not accumulated in v. In 2004, Dodis et al. [12] proposed constant-size ring signatures based on an accumulator of the one-way domain.In 2004, Liu et al. [13] defined the linkability of ring signatures and proposed the first linkable spontaneous group signature (linkable ring signature) scheme. The linkability refers to the link between two signatures of the same signer. In 2005, Tsang and Wei [14] constructed the first short linkable ring signature scheme extended from a short ring signature scheme proposed by Dodis et al. [12]. In 2019, Wang et al. [15] proposed a general construction method to add linkability to arbitrary ring signature schemes with one-time signatures.In 2007, Fujisaki and Suzuki [16] proposed a traceable ring signature. The traceable ring signature contains a tag composed of a list of ring members and an issue that refers to an affair. Anyone who signs the same message again with the same tag can be linked, whereas anyone who signs two different messages with the same tag can be traced. In 2013, Au et al. [17] proposed the first ID-based event-oriented linkable ring signature, which provided a revocable option. Two signatures with the same secret key in the same event can reveal the signer’s identity. The traceability of these schemes is under linkable conditions. In these schemes, there is no way to revoke the anonymity of signers whose transactions are related to criminal behavior but are consistent with transaction generation rules. Bootle et al. [18] take care of this type of requirement in their work. They proposed an accountable ring signature scheme, which is based on the efficient one-out-of-many knowledge proof proposed in [19] and improved it. The signer can specify a public key, allowing the owner of it to revoke the signer’s anonymity.Using ring signature and one-time keys, CryptoNote for Monero conceals the signers and receivers of transactions. Extended by CryptoNote, RingCT protocol can allow the hiding of the amounts sent in a transaction. In 2017, Sun et al. [20] gave a rigorous security definition for RingCT protocol and proposed a new RingCT protocol (RingCT 2.0). Based on homomorphic commitment schemes, accumulators with one-way domain, and the signature of knowledge, RingCT 2.0 protocol constructs a constant size signature independent of the number of input accounts. It requires trusted public parameters. In 2020, Yuen et al. [21] proposed RingCT 3.0, which does not require trusted settings. The ring signature size is the logarithm of the input account number.In the matter of Monero’s accountability, there are not many studies currently. In 2019, Li et al. [8] proposed a traceable Monero system based on RingCT 2.0 and a variation of the ElGamal public key encryption scheme. The scheme allows a trusted regulator to trace the user’s one-time public key and long-term public key. Our solution is based on the RingCT protocol in Monero, certified key scheme [22] and the variant ElGamal encryption scheme. Consider that, since version v8 (2018-10), Monero uses a ring size of 11, and the latest recommended ring size is 15. Our scheme’s computation efficiency is independent of the length of the element in ℤq, which is 255 in CryptoNote 2.0. Therefore, when the ring size is less than the length of the element, our scheme is more efficient.In terms of certified keys used in signature schemes, in 2007, Groth [23] constructed a group signature scheme with a certified signature scheme, which allows users to pick signature verification keys. The verification keys can be certified by a certification authority. In 2014, Ateniese et al. [22] proposed certified Bitcoin. By using a self-certified public key, a user can efficiently generate the certified address. The scheme is fully compatible with the Bitcoin system.


## 1.1. Our Contribution

We propose a new accountable Monero system based on the RingCT protocol. In the system, we add two roles: trusted registration authority and trusted regulator. The trusted registration authority interacts with users to generate certificates and keys for them. The trusted regulator can gain the secret index selected by the transaction payer and can expose the long-term public key of offenders. Anonymity can still be guaranteed except for the tracing of the trusted regulator. We take advantage of cryptographic techniques to design a scheme with privacy and accountability assurance. Specifically, our contributions are as follows:(1)
We propose a new accountable Monero system, which includes users, the trusted registration authority, and the trusted regulator. To make the tracing for a user in the system possible, we employ the certified public key as the user’s long-term public key. Our approach combines signature with rerandomizable keys, the signature of knowledge, and the RingCT protocol. The payer encrypts a randomization factor during spending, and the trusted regulator can obtain the payer’s one-time public key by decryption. Long-term public keys can be further traced.(2)
The combination with Monero’s RingCT protocol has produced the application of a more efficient accountable Monero system. We compare the efficiency and communication in our accountable Monero system, Monero, and the accountable Monero system in [8]. The performance analysis shows that our system has better computational efficiency in the most frequently used settings.


## 1.2. Related Work

Ring signature schemes generally include one-out-of-many proofs or membership proofs. The RingCT protocol used by Monero [9] is based on the discrete logarithm version of one-out-of-many signature in [10], which convinces a verifier that the signature is from one of n possible independent signers without revealing which one. In addition, an accumulator is a construction tool for ring signatures. Accumulators allow representing a set of elements Y=y1,y2,…,yn as a single value v whose size is independent of Y’s cardinality. For each set element y, there exists an efficiently computable witness w to prove that y is accumulated in v. In 2009, Au et al. [11] proposed the first dynamic universal accumulator. Dynamic accumulators can efficiently add and delete elements to the accumulated value. As the value is renewed, the witness w for each set element can be efficiently updated. The universality means that, for any element y¯ outside the set Y, there exists an efficiently computable witness w¯ to prove that y¯ is not accumulated in v. In 2004, Dodis et al. [12] proposed constant-size ring signatures based on an accumulator of the one-way domain.In 2004, Liu et al. [13] defined the linkability of ring signatures and proposed the first linkable spontaneous group signature (linkable ring signature) scheme. The linkability refers to the link between two signatures of the same signer. In 2005, Tsang and Wei [14] constructed the first short linkable ring signature scheme extended from a short ring signature scheme proposed by Dodis et al. [12]. In 2019, Wang et al. [15] proposed a general construction method to add linkability to arbitrary ring signature schemes with one-time signatures.In 2007, Fujisaki and Suzuki [16] proposed a traceable ring signature. The traceable ring signature contains a tag composed of a list of ring members and an issue that refers to an affair. Anyone who signs the same message again with the same tag can be linked, whereas anyone who signs two different messages with the same tag can be traced. In 2013, Au et al. [17] proposed the first ID-based event-oriented linkable ring signature, which provided a revocable option. Two signatures with the same secret key in the same event can reveal the signer’s identity. The traceability of these schemes is under linkable conditions. In these schemes, there is no way to revoke the anonymity of signers whose transactions are related to criminal behavior but are consistent with transaction generation rules. Bootle et al. [18] take care of this type of requirement in their work. They proposed an accountable ring signature scheme, which is based on the efficient one-out-of-many knowledge proof proposed in [19] and improved it. The signer can specify a public key, allowing the owner of it to revoke the signer’s anonymity.Using ring signature and one-time keys, CryptoNote for Monero conceals the signers and receivers of transactions. Extended by CryptoNote, RingCT protocol can allow the hiding of the amounts sent in a transaction. In 2017, Sun et al. [20] gave a rigorous security definition for RingCT protocol and proposed a new RingCT protocol (RingCT 2.0). Based on homomorphic commitment schemes, accumulators with one-way domain, and the signature of knowledge, RingCT 2.0 protocol constructs a constant size signature independent of the number of input accounts. It requires trusted public parameters. In 2020, Yuen et al. [21] proposed RingCT 3.0, which does not require trusted settings. The ring signature size is the logarithm of the input account number.In the matter of Monero’s accountability, there are not many studies currently. In 2019, Li et al. [8] proposed a traceable Monero system based on RingCT 2.0 and a variation of the ElGamal public key encryption scheme. The scheme allows a trusted regulator to trace the user’s one-time public key and long-term public key. Our solution is based on the RingCT protocol in Monero, certified key scheme [22] and the variant ElGamal encryption scheme. Consider that, since version v8 (2018-10), Monero uses a ring size of 11, and the latest recommended ring size is 15. Our scheme’s computation efficiency is independent of the length of the element in ℤq, which is 255 in CryptoNote 2.0. Therefore, when the ring size is less than the length of the element, our scheme is more efficient.In terms of certified keys used in signature schemes, in 2007, Groth [23] constructed a group signature scheme with a certified signature scheme, which allows users to pick signature verification keys. The verification keys can be certified by a certification authority. In 2014, Ateniese et al. [22] proposed certified Bitcoin. By using a self-certified public key, a user can efficiently generate the certified address. The scheme is fully compatible with the Bitcoin system.


## 2. Definition of Accountable Monero System

An accountable Monero system is a tuple of algorithms (Setup, TKGen, RKGen, UKGen, Mint, Spend, Verify, BlockGen, BlockVer, Trace, Judge).pp←Setup1λ: Given the security parameter λ, it produces the public parameter pp.xT,yT←TKGenpp: Given the public parameter pp, it produces a public-private key pair xT,yT for the trusted registration authority.xR,yR←RKGenpp: Given the public parameter pp, it produces a public-private key pair xR,yR for the trusted regulator.sk,P←UKGenpp,yT: Given the public parameter pp and the public key of the trusted registration authority, it produces a signing key sk and a verification key P for the user.act,ask←MintP,a: Given a public key and an amount a, it produces a coin cn with amount a for a public key P. The corresponding coin key is ck. The coin cn and the public key P form an account denoted by act=pk,cn, and the corresponding account secret key is defined as ask=sk,ck.tx,I,CT,π,aux←Spendm,Kin,Ain,A,Pout,yR: The inputs include a description m∈0,1∗, a set of account private keys Kin, and input account set Ain, accounts A including Ain, the output stealth public keys Pout, and the trusted regulator’s public key yR. This algorithm outputs a transaction message tx, a set of serial numbers I, a proof π, a ciphertext CT, and some additional information aux.0/1←Verifytx,I,CT,π,aux: Given the transaction message tx, serial numbers I, the proof π, the ciphertext CT, and additional information aux, this algorithm checks, the transaction is valid or not and outputs 1 or 0, respectively.non,blkn←BlockGenTX,blkn−1: Given a set of transactions TX=tx,I,CT,π,aux and the previous block blkn−1, this algorithm outputs a nonce non and a block blkn.0/1←BlockVerblkn: Given the current block blkn, this algorithm verifies whether the block is valid or not and outputs 1 or 0, respectively.P,ψ←TracexR,TX,CT: Given the trusted regulator’s secret key xR, the transaction TX, and the ciphertext CT, it outputs the payer’s public key P and a trace proof ψ.0/1←JudgeP,ψ,yR,CT: Given the payer’s public key P, the trace proof ψ, trusted regulator’s public key yR, and the ciphertext CT, this algorithm checks whether the trace proof is valid or not and outputs 1 or 0, respectively.An accountable Monero system should be correct, balanced, anonymous, nonslanderous, and traceable as in [8, 20].Definition 1.
(Perfect Correctness).All transactions generated by theSpendalgorithm can pass theVerifyalgorithm. All traced public keys and corresponding proofs generated by theTracealgorithm can be verified by theJudgealgorithm. Specifically, an accountable Monero system is perfectly correct if for all PPT adversariesA,(1)PrVerifytx,I,CT,π,aux=1JudgeP,ψ,yR=1:pp←Setup1λ;xT,yT←TKGenpp;xR,yR←RKGenpp;m,A,Pout←App,Ain,KinwhereAin,Kin=act,asks.t.sk,P←UKGenpp,yT;act,ask←MintP,a;tx,I,CT,π,aux←Spendm,Kin,Ain,A,Pout,yR;P,ψ←TraceskR,tx,CT=1.Definition 2 (Balance).
This property requires that any malicious payers cannot (1) spend by using accounts that are not their own; (2) spend more than the amount in their accounts. Specifically, an accountable Monero system is balanced if for all PPT adversariesA,(2)Prpp←Setup1λ;Awins:acti′i=1μ,Sii=1ν←AAddGen,ActGen,Spend,Corruptpp≤neglλ.where the oracles are defined as follows:(i)
AddGeni: Given a query numberi, if algorithmTKGenhas not been run, runsxT,yT←TKGenpp. Then, it runs algorithmski,Pi←UKGenpp,yTand returns a public keyPi.(ii)
ActGeni,ai: Given the indexiand an amountai, it runs algorithmact,ask←MintPi,ai, addsi,acti=Pi,cnito the listsℐ,G, respectively and returnscni,ckiforPigenerated byAddGen. The corresponding private key isaski=ski,cki. The oracle usesaskito compute the serial numberIiof the accountactiand adds it to the listS.(iii)
Spendm,Ain,A,Pout: Given the inputs, if algorithmRKGenhas not been run, it runs algorithmxR,yR←RKGenpp. Then, it runs algorithmtx,I,CT,π,aux←Spendm,Kin,Ain,A,Pout,yR. Assume that at least one account inAinhas not been corrupted, whereAin⊂G. It addstx,I,CT,π,auxto the listTand returns it.(iv)
Corrupti: Given the indexi, it returnsskiand usesaskito determine the serial numberIiof accountacti, addsIi,Ii,aito the listsCandℬrespectively.
Finally,Aoutputs all his spending and some new accounts he createdact1′,…,actμ′,S1,…,Sν, whereSi=txi,ℐi,CTi,πi,auxi,i∈νand all transactions are paid to the challenger. Specifically, we callAwins if the following conditions are met:(1)
Verifytxi,Ii,CTi,πi,auxi=1, wherei∈ν.(2)
Si∉T∧Ii⊂S,i∈ν, andIj∩Ik=∅for any differentj,k∈ν.(3)
LetIi=Ii,jandE=∪i=1νai,j:Ii,j,ai,j∈ℬ∧Ii,j∈Ii∩C, it holds that∑ai,j∈Eai,j<∑k=1νaouti, whereaoutidenotes the balance of the output accounts inSi.Definition 3 (Anonymity).
The property requires that the accounts used by the payer cannot be distinguished. Specifically, an accountable Monero system is anonymous if for all PPT adversariesA,(3)Prb′=b:pp←Setup1λ;m,As0,As1,A,Pout←A1AddGen,ActGen,Spend,Corrupt,Tracepp;b←0,1,tx∗,I∗,CT∗,π∗,aux∗←Spendm,Ksb,Asb,A,Pout,yR;b′←A2Spend,Corrupt,Tracepp,tx∗,π∗,I∗,CT∗,aux∗−12≤neglλ.
The oracles are defined as before,Asi∈AandAsi⊂G, wherei∈0,1.Traceoracle is defined as follows:(i)
Tracetx,π. Given the queried transactiontxand the proofπ, it returns a public keyP. If the input istx∗,π∗, returns⊥.
Besides, the following conditions should be satisfied:(1)
None of the accounts inAs0andAs1have been corrupted.(2)
No query in the form of·,As,·,·s.t.As∩Asi≠∅has ever been queried toSpendoracle.Definition 4.
(Nonslanderability).The property requires that a malicious user cannot slander any honest user. Specifically, an accountable Monero system is nonslanderous if for all PPT adversariesA,(4)PrAWins:pp←Setup1λ;tx^,I^,CT^,π^,aux^,tx˜,I˜,CT˜,π˜,aux˜←AAddGen,ActGen,Spend,Corruptpp≤neglλ.where all oracles are defined as before, andtx^,I^,CT^,π^,aux^is one of the outputs ofSpendoracle. Specifically,Awins if the following conditions are met: (1)Verifytx˜,I˜,CT˜,π˜,aux˜=1; (2) tx˜,I˜,CT˜,π˜,aux˜∉T; (3)I^∩C=∅butI^∩I˜≠∅.
The nonslanderability property already covers the linkability property [20].Definition 5.
(Traceability).The property requires that the trusted regulator can trace the transaction payer and can prove the validity of tracing. Specifically, an accountable Monero system is traceable if for all PPT adversariesA,(5)PrTraceskR,tx,CT)=P,ψJudgeP,ψ,pkR,CT=1:pp←Setup1λ;tx,I,CT,π,aux←AAddGen,ActGen,Spend,Corruptpp;Verifytx,I,CT,π,aux=1=1.


## 3. Preliminaries

Definez=1,2,…,z. We use PPT, which stands for “probabilistic polynomial-time.” “‖” denotes the concatenation of strings. Besides, we recall here the tools and assumptions used throughout this paper.


### 3.1. Terminology

Monero uses terms according to [24] as follows:(i)
q is a prime number and the order of the underlying finite field;(ii)
ℤq is the underlying finite filed;(iii)
E is an elliptic curve defined on ℤq;(iv)
G⊆Eℤq is a subgroup of large prime order of the elliptic curve E over a finite field ℤq.(v)
G is a generator of G;(vi)
l is a prime order of G.Private ec-key is a standard elliptic curve private key, such as a∈1,l−1;Public ec-key is a standard elliptic curve public key, such that A=aG.


### 3.2. Hardness Assumptions

Discrete logarithm (DL) Assumption Let l,G,G be a tuple, where G=l and G∈G such that <G>=G. Given a tuple G,aG∈G2, where a∈ℤq∗, for all PPT adversaries A, the probability of computing a is negligible in security parameter λ, which can be expressed as AdvADLλ=PAG,aG=a≤neglλDecisional Diffie–Hellman (DDH) Assumption Let l,G,G, where G=l and G∈G such that <G>=G. The DDH assumption is as follows: given a tuple G,aG,bG,1−xab+xcG, where a,b,c∈ℤq∗, x∈0,1, for all PPT adversaries A,(6)AdvADDHλ=|PAG,aG,bG,abG−PAG,aG,bG,cG|≤neglλ.


### 3.3. Homomorphic Commitment Scheme [19]

A noninteractive commitment scheme includes a pair of polynomial-time algorithmsCGen,Comck: on inputting a security parameter λ, CGen1λ outputs a commitment key ck. Comckm,r generates a commitment C on the input message m and a randomness r, where ck is often omitted when it is clear in context.Security of HCom A noninteractive homomorphic commitment scheme HCom=CGen,Com is secure if it satisfies the following properties:Binding This property means that a committer cannot generate a commitment C, which can be opened as two different messages. More precisely, for all PPT adversaries A,(7)Prm0≠m1∧Comm0;r0=Comm1;r1:ck←CGen1λ;m0,r0,m1,r1⟵Ack≤neglλ.Hiding This property means that the commitment reveals nothing about m. More precisely, for all PPT adversaries A,(8)Prck←CGen1λ;AC=b:m0,m1←Ack;b←0,1;C←Comckmb−12≤neglλ.Homomorphic This property means that for all λ∈ℕ,ck←CGen1λ,m0,r0,m1,r1∈ℤq, it holds that(9)Comm0;r0·Comm1;r1=Comm0+m1;r0+r1.


### 3.4. Elliptic Curve ElGamal Encryption [25]

The EC-ElGamal encryption scheme consists of three algorithms.x,P←KeyGen1λ: Given a security parameter λ, this algorithm generates gk=l,G,G, where G=l and G∈G such that <G>=G. The private key x∈0,l−1 is chosen uniformly at random. The public key is computed as P=xG. It outputs the key pair x,P.C←EncP,m: Given a public key P and a message m, which has been embedded as a point M on the elliptic curve E over ℤq, it chooses a random α and outputs the ciphertext C=C1,C2=αG,αxG+M.M←Decx,C: Given the private key x and the ciphertext C=C1,C2, it outputs M=C2−xC1.The EC-ElGamal encryption is IND-CPA secure under the DDH assumption. And the EC-ElGamal ciphertexts are homomorphic.


### 3.5. Signatures with Rerandomizable Keys [26]

This primitive can consistently rerandomize the private and public keys of a signature scheme.


#### 3.5.1. Signatures with Rerandomizable Keys

A digital signature scheme with rerandomizable keys contains the following PPT algorithms:sk,vk←SGen1λ: Given the security parameter λ, this algorithm generates a public-private key pair sk,vk.σ←Sigsk,m: Given a signing key sk and a message m, this algorithm generates a signature σ.b←Vervk,m,σ: Given a verification key vk, a message m, and a signature σ, this algorithm outputs a bit b.sk′←RndSKsk,ρ: Given a signing key sk and a random number ρ, this algorithm outputs a new signing key sk′.vk′←RndVKvk,ρ: Given a verification key vk and a random number ρ, this algorithm outputs a new verification key vk′.If for allλ∈ℕ, all key-pairs sk,vk←SGen1λ, all messages m, Vervk,m,Sigsk,m=1 and for all ρ, VerRndVKvk,ρ,m,SigRndSKsk,ρ,m\\=1, this scheme is complete. The formal definition is in the following.


#### 3.5.2. Rerandomizable Keys

A signature scheme has perfectly rerandomizable keys if for allλ∈ℕ, all key-pairs sk,vk←SGen1λ and a uniformly chosen random number ρ, the following distributions are identical:(10)sk,vk,sk′,vk′=sk,vk,sk″,vk″where sk′,vk′←SGen1λ, sk′′←RndSKsk,ρ, and vk′′←RndVKvk,ρ.


#### 3.5.3. Unforgeability under Rerandomizable Keys

We say that a signature scheme achieves unforgeability under rerandomizable keys if all PPT adversaryA cannot be able to win the following game with nonnegligible probability:(1)
The challenger runssk,vk←SGen1λ and sends vk to A.(2)
A is allowed to access the signing oracle and randomized signing oracle to make signing queries. A signing query is for the input m,⊥, where m is the message. The challenger responds with Sigsk,m. A randomized signing query is for the input m,ρ, where m is the message, and ρ is randomness. The challenger responds with SigRndSKsk,ρ,m.(3)
A outputs a tuple m∗,σ∗,ρ∗.We say thatA wins the game if:(i)
For all queriesm,· to the signing oracle or randomized signing oracle, it holds that m≠m∗;(ii)
EitherVervk,m∗,σ∗=1 or VerRndVKvk,ρ∗,\\m∗,σ∗=1.


### 3.6. Signature of Knowledge [27]

A Signature of Knowledge (SoK) for an NP-relationℛ is a tuple of algorithms (Setup, Sign, Verify) as follows:par←Setup1λ: Given a security parameter λ, it outputs public parameters par.σSoK←Signpar,s,w,m : Given the public parameter par, a statement s, a witness w, and a message m, where s,w∈ℛ, it outputs a signature σSoK on m.0/1←Verfpar,s,m,σSoK: Given the public parameter par, a statement s, a message m, and a signature σSoK, it outputs 1 if σSoK is a valid signature or 0 otherwise.The security definition for SoK (SimExt-secure) requires correctness, simulatability, and extractability.


#### 3.6.1. Correctness

For any messagem and a pair s,w∈ℛ, such that(11)PrVerfpar,s,m,σSoK=1:par←Setup1λ;σSoK←Signpar,s,w,m≥1−neglλ.


#### 3.6.2. Simulatability

There exists PPT simulator Sim=(SimGen, SimSign), where SimGen1λ outputs public parameters par and a trapdoor τ and SimSign par,τ,s,m outputs a signature σSoK, such that for all PPT adversaries A,(12)|Prb=1:par,τ←SimGen1λ;b←ASimpar−Prb=1:par←Setup1λ;b←ASignpar|≤neglλ.


#### 3.6.3. Extractability

For all PPT adversariesA, there exists a polynomial-time extractor Ext, such that(13)Prs,w∈ℛ∨s,m∈Q∨Verfpar,s,m,σSoK=0:par,τ←SimGen1λm,s,σSoK←ASimparw←Extpar,τ,m,s,σSoK≥1−neglλ.where Q denotes the queries to the SimSign oracle that A made.


## 3.1. Terminology

Monero uses terms according to [24] as follows:(i)
q is a prime number and the order of the underlying finite field;(ii)
ℤq is the underlying finite filed;(iii)
E is an elliptic curve defined on ℤq;(iv)
G⊆Eℤq is a subgroup of large prime order of the elliptic curve E over a finite field ℤq.(v)
G is a generator of G;(vi)
l is a prime order of G.Private ec-key is a standard elliptic curve private key, such as a∈1,l−1;Public ec-key is a standard elliptic curve public key, such that A=aG.


## 3.2. Hardness Assumptions

Discrete logarithm (DL) Assumption Let l,G,G be a tuple, where G=l and G∈G such that <G>=G. Given a tuple G,aG∈G2, where a∈ℤq∗, for all PPT adversaries A, the probability of computing a is negligible in security parameter λ, which can be expressed as AdvADLλ=PAG,aG=a≤neglλDecisional Diffie–Hellman (DDH) Assumption Let l,G,G, where G=l and G∈G such that <G>=G. The DDH assumption is as follows: given a tuple G,aG,bG,1−xab+xcG, where a,b,c∈ℤq∗, x∈0,1, for all PPT adversaries A,(6)AdvADDHλ=|PAG,aG,bG,abG−PAG,aG,bG,cG|≤neglλ.


## 3.3. Homomorphic Commitment Scheme [19]

A noninteractive commitment scheme includes a pair of polynomial-time algorithmsCGen,Comck: on inputting a security parameter λ, CGen1λ outputs a commitment key ck. Comckm,r generates a commitment C on the input message m and a randomness r, where ck is often omitted when it is clear in context.Security of HCom A noninteractive homomorphic commitment scheme HCom=CGen,Com is secure if it satisfies the following properties:Binding This property means that a committer cannot generate a commitment C, which can be opened as two different messages. More precisely, for all PPT adversaries A,(7)Prm0≠m1∧Comm0;r0=Comm1;r1:ck←CGen1λ;m0,r0,m1,r1⟵Ack≤neglλ.Hiding This property means that the commitment reveals nothing about m. More precisely, for all PPT adversaries A,(8)Prck←CGen1λ;AC=b:m0,m1←Ack;b←0,1;C←Comckmb−12≤neglλ.Homomorphic This property means that for all λ∈ℕ,ck←CGen1λ,m0,r0,m1,r1∈ℤq, it holds that(9)Comm0;r0·Comm1;r1=Comm0+m1;r0+r1.


## 3.4. Elliptic Curve ElGamal Encryption [25]

The EC-ElGamal encryption scheme consists of three algorithms.x,P←KeyGen1λ: Given a security parameter λ, this algorithm generates gk=l,G,G, where G=l and G∈G such that <G>=G. The private key x∈0,l−1 is chosen uniformly at random. The public key is computed as P=xG. It outputs the key pair x,P.C←EncP,m: Given a public key P and a message m, which has been embedded as a point M on the elliptic curve E over ℤq, it chooses a random α and outputs the ciphertext C=C1,C2=αG,αxG+M.M←Decx,C: Given the private key x and the ciphertext C=C1,C2, it outputs M=C2−xC1.The EC-ElGamal encryption is IND-CPA secure under the DDH assumption. And the EC-ElGamal ciphertexts are homomorphic.


## 3.5. Signatures with Rerandomizable Keys [26]

This primitive can consistently rerandomize the private and public keys of a signature scheme.


### 3.5.1. Signatures with Rerandomizable Keys

A digital signature scheme with rerandomizable keys contains the following PPT algorithms:sk,vk←SGen1λ: Given the security parameter λ, this algorithm generates a public-private key pair sk,vk.σ←Sigsk,m: Given a signing key sk and a message m, this algorithm generates a signature σ.b←Vervk,m,σ: Given a verification key vk, a message m, and a signature σ, this algorithm outputs a bit b.sk′←RndSKsk,ρ: Given a signing key sk and a random number ρ, this algorithm outputs a new signing key sk′.vk′←RndVKvk,ρ: Given a verification key vk and a random number ρ, this algorithm outputs a new verification key vk′.If for allλ∈ℕ, all key-pairs sk,vk←SGen1λ, all messages m, Vervk,m,Sigsk,m=1 and for all ρ, VerRndVKvk,ρ,m,SigRndSKsk,ρ,m\\=1, this scheme is complete. The formal definition is in the following.


### 3.5.2. Rerandomizable Keys

A signature scheme has perfectly rerandomizable keys if for allλ∈ℕ, all key-pairs sk,vk←SGen1λ and a uniformly chosen random number ρ, the following distributions are identical:(10)sk,vk,sk′,vk′=sk,vk,sk″,vk″where sk′,vk′←SGen1λ, sk′′←RndSKsk,ρ, and vk′′←RndVKvk,ρ.


### 3.5.3. Unforgeability under Rerandomizable Keys

We say that a signature scheme achieves unforgeability under rerandomizable keys if all PPT adversaryA cannot be able to win the following game with nonnegligible probability:(1)
The challenger runssk,vk←SGen1λ and sends vk to A.(2)
A is allowed to access the signing oracle and randomized signing oracle to make signing queries. A signing query is for the input m,⊥, where m is the message. The challenger responds with Sigsk,m. A randomized signing query is for the input m,ρ, where m is the message, and ρ is randomness. The challenger responds with SigRndSKsk,ρ,m.(3)
A outputs a tuple m∗,σ∗,ρ∗.We say thatA wins the game if:(i)
For all queriesm,· to the signing oracle or randomized signing oracle, it holds that m≠m∗;(ii)
EitherVervk,m∗,σ∗=1 or VerRndVKvk,ρ∗,\\m∗,σ∗=1.


## 3.5.1. Signatures with Rerandomizable Keys

A digital signature scheme with rerandomizable keys contains the following PPT algorithms:sk,vk←SGen1λ: Given the security parameter λ, this algorithm generates a public-private key pair sk,vk.σ←Sigsk,m: Given a signing key sk and a message m, this algorithm generates a signature σ.b←Vervk,m,σ: Given a verification key vk, a message m, and a signature σ, this algorithm outputs a bit b.sk′←RndSKsk,ρ: Given a signing key sk and a random number ρ, this algorithm outputs a new signing key sk′.vk′←RndVKvk,ρ: Given a verification key vk and a random number ρ, this algorithm outputs a new verification key vk′.If for allλ∈ℕ, all key-pairs sk,vk←SGen1λ, all messages m, Vervk,m,Sigsk,m=1 and for all ρ, VerRndVKvk,ρ,m,SigRndSKsk,ρ,m\\=1, this scheme is complete. The formal definition is in the following.


## 3.5.2. Rerandomizable Keys

A signature scheme has perfectly rerandomizable keys if for allλ∈ℕ, all key-pairs sk,vk←SGen1λ and a uniformly chosen random number ρ, the following distributions are identical:(10)sk,vk,sk′,vk′=sk,vk,sk″,vk″where sk′,vk′←SGen1λ, sk′′←RndSKsk,ρ, and vk′′←RndVKvk,ρ.


## 3.5.3. Unforgeability under Rerandomizable Keys

We say that a signature scheme achieves unforgeability under rerandomizable keys if all PPT adversaryA cannot be able to win the following game with nonnegligible probability:(1)
The challenger runssk,vk←SGen1λ and sends vk to A.(2)
A is allowed to access the signing oracle and randomized signing oracle to make signing queries. A signing query is for the input m,⊥, where m is the message. The challenger responds with Sigsk,m. A randomized signing query is for the input m,ρ, where m is the message, and ρ is randomness. The challenger responds with SigRndSKsk,ρ,m.(3)
A outputs a tuple m∗,σ∗,ρ∗.We say thatA wins the game if:(i)
For all queriesm,· to the signing oracle or randomized signing oracle, it holds that m≠m∗;(ii)
EitherVervk,m∗,σ∗=1 or VerRndVKvk,ρ∗,\\m∗,σ∗=1.


## 3.6. Signature of Knowledge [27]

A Signature of Knowledge (SoK) for an NP-relationℛ is a tuple of algorithms (Setup, Sign, Verify) as follows:par←Setup1λ: Given a security parameter λ, it outputs public parameters par.σSoK←Signpar,s,w,m : Given the public parameter par, a statement s, a witness w, and a message m, where s,w∈ℛ, it outputs a signature σSoK on m.0/1←Verfpar,s,m,σSoK: Given the public parameter par, a statement s, a message m, and a signature σSoK, it outputs 1 if σSoK is a valid signature or 0 otherwise.The security definition for SoK (SimExt-secure) requires correctness, simulatability, and extractability.


### 3.6.1. Correctness

For any messagem and a pair s,w∈ℛ, such that(11)PrVerfpar,s,m,σSoK=1:par←Setup1λ;σSoK←Signpar,s,w,m≥1−neglλ.


### 3.6.2. Simulatability

There exists PPT simulator Sim=(SimGen, SimSign), where SimGen1λ outputs public parameters par and a trapdoor τ and SimSign par,τ,s,m outputs a signature σSoK, such that for all PPT adversaries A,(12)|Prb=1:par,τ←SimGen1λ;b←ASimpar−Prb=1:par←Setup1λ;b←ASignpar|≤neglλ.


### 3.6.3. Extractability

For all PPT adversariesA, there exists a polynomial-time extractor Ext, such that(13)Prs,w∈ℛ∨s,m∈Q∨Verfpar,s,m,σSoK=0:par,τ←SimGen1λm,s,σSoK←ASimparw←Extpar,τ,m,s,σSoK≥1−neglλ.where Q denotes the queries to the SimSign oracle that A made.


## 3.6.1. Correctness

For any messagem and a pair s,w∈ℛ, such that(11)PrVerfpar,s,m,σSoK=1:par←Setup1λ;σSoK←Signpar,s,w,m≥1−neglλ.


## 3.6.2. Simulatability

There exists PPT simulator Sim=(SimGen, SimSign), where SimGen1λ outputs public parameters par and a trapdoor τ and SimSign par,τ,s,m outputs a signature σSoK, such that for all PPT adversaries A,(12)|Prb=1:par,τ←SimGen1λ;b←ASimpar−Prb=1:par←Setup1λ;b←ASignpar|≤neglλ.


## 3.6.3. Extractability

For all PPT adversariesA, there exists a polynomial-time extractor Ext, such that(13)Prs,w∈ℛ∨s,m∈Q∨Verfpar,s,m,σSoK=0:par,τ←SimGen1λm,s,σSoK←ASimparw←Extpar,τ,m,s,σSoK≥1−neglλ.where Q denotes the queries to the SimSign oracle that A made.


## 4. Accountable Monero System

In this section, we present the procedure of the accountable Monero and describe the concrete scheme. Then, we give an instantiation of the SoK used in the system and the security analysis.


### 4.1. Accountable Monero System Workflow

Our accountable Monero system adds accountability to the original Monero system. It includes three types of subjects, namely, the trusted registration authority, denoted byT, the trusted regulator, denoted by R, and users. As shown in Figure 1, the main processes are Registration, Transaction, Transaction on the chain, and Tracing.Registration: To meet the demand of the trusted regulator tracing users’ long-term public keys, a user has to cooperate with the trusted registration authority to create the certificate and key pair. The user’s signing public key and certificate can be accessed in the system. It allows others to make a transaction with him.Transaction: The payer wants to transfer coins to others. Firstly, the payer produces the one-time public key for each payee. At the same time, the payer encrypts the necessary message with the trusted regulator’s public key to support the tracing of payees’ long-term public keys. Secondly, the payer mints coins for each payee. Thirdly, the payer randomizes his one-time keys, uses the trusted regulator’s public key to encrypt the random number used in randomization, and signs the transaction. Finally, he broadcasts the transaction to the P2P network.Transactions on the chain: Miners collect and verify new transactions in the P2P network. Then, they compete for a proof-of-work to add their block to the blockchain.Tracing: When tracing the one-time public key, the trusted regulator decrypts the ciphertext in the transaction to obtain the random number. Then, the regulator can recover the one-time public key from the randomized public key. Obtaining the one-time public key, the trusted regulator can decrypt the ciphertext generated along with the one-time public key to reveal the long-term public key.Figure 1
Workflow of our accountable Monero system.


### 4.2. Accountable Monero System Instantiation

Our accountable Monero system is designed as follows:Setup1λ: This algorithm generates the public parameters of the system. On inputting a security parameter λ, H,H˜,U are generators in G and their discrete logarithms regarding G are unknown. We denote par as par  = SoK.Setup1λ. It outputs pp=1λ,par,G,H,H˜,U,ℋs,ℋp,ξ, where ℋs:0,1∗⟶ℤq and ℋp:0,1∗⟶0,1∗ denote two cryptographic secure hash functions, and ξ is a fixed function from G to ℤq.TKGenpp: This algorithm generates the trusted registration authority’s key pair. Given input pp, it outputs xT,YT, where xT∈0,l−1 and YT=xTG.RKGenpp: This algorithm generates the trusted regulator’s key pair. Given input pp, it outputs xR,YR, where xR∈0,l−1 and YR=xRU.UKGenpp,YT: This algorithm generates the user’s public key. We use the certified key [22] generation method.A certified key is certified by the trusted registration authority. The Certified Key Generation protocol is executed between user U and the registration authorityT as follows:(1)
U picks uniformly at randomk in 0,l−1, computes Z=kG and sends Z to T.(2)
On receivingZ from user U, T picks uniformly at random k′ in 0,l−1 and computes Cu=Z+k′G,e=ξCu,x¯=k′+e·xT. Finally, T sends Cu, x¯ to user U.(3)
On receivingCu, x¯ from T, U computes x=x¯+k as his private key corresponding to his certified public key Yu=Cu+ξCuYT and verifies that(14)xG=Cu+ξCuYT.The user’s public keyYu and certificate Cu are publicly accessed. A payer obtains the payee’s long-term public key Yu=xG, where x is the payee’s long-term private key. The payer generates a one-time public key as a receiving public key for the payee, which can hide the payee’s real public key. In the process of generating a one-time public key, to simplify, we use one of the methods in [28]. The payer firstly chooses uniformly at random r∈0,l−1 and computes R=rG. The payee’s one-time public key is computed as P=ℋsrYuG+Yu, and the corresponding one-time private key is x+ℋsxR. The payer picks uniformly at random r˜∈0,l−1 and then encrypts ℋsrYuG with the trusted regulator’s public key YR as Ct1=r˜YR,Ct2=ℋsrYuG+r˜U. The ciphertext is denoted as CT1=Ct1,Ct2.And it produces SoK as follows:(15)SoKCu,Yu,r,r˜:Yu=Cu+ξCuYT∧P=Yu+ℋsrYuG∧R=rG∧Ct1=r˜YR∧Ct2=ℋsrYuG+r˜U.MintP,a: This algorithm mints a coin for the public key address P with an amount a as follows. It chooses uniformly at random r∈0,l−1 and computes the commitment C=Comck,a;r=rG+aH and then outputs Cn,ck=C,r,a. The account is denoted as act=P,C and the corresponding account private key is denoted as ask=sk,ck=sk,r,a.Spend(m,Kin,Ain,A,Pout,YR): This algorithm allows users to spend their coins while maintaining privacy. in is a secret index corresponding to the signer of the ring. Given the transaction message m∈0,1∗, account private keys Kin and the corresponding account set Ain, accounts A which contain Ain, a set of output public key Pout and the trusted regulator’s public key YR, it outputs a transaction, which contains a proof π, randomized spending public keys P∗ and serial numbers I associated with Ain. Without loss of generality, we denote Kin=askin,j=skin,j,rin,j,ain,jj∈m, Ain=actin,j=Pin,j,Cnin,jj∈m, A=acti,j=Pi,j,Cni,ji∈n,j∈m and the output public key set Pout=Pout,kk∈t. The process of spending coins is as follows:(1)
The payer sets the output amountaout,kk∈t for each output public key Pout,kk∈t such that the input sum is equal to the output sum, i.e., ∑j=1main,j=∑k=1taout,k. Then, the payer chooses uniformly at random rout,k∈0,l−1k∈t and mints coins Cnout,k=Cout,k=Comaout,k;rout,k=rout,kG+aout,kH for the output public keys. Afterward, the payer adds the output accounts actout,k=Pout,k,Cnout,kk∈t to receivers’ account set AR and sends ckout,k=rout,k,aout,k to the owner of a public key Pout,kk∈t through secret channels.(2)
The payer computesP˜i=∑j=1mPi,j+∑j=1mCni,j−∑k=1tCnout,k, where i∈n. If ∑j=1main,j=∑k=1taout,k, P˜in is a commitment to 0. P˜in=\\∑j=1mskin,j+rin,j−∑k=1trout,kG=sk˜inG, where sk˜in=∑j=1mskin,j+rin,j−∑k=1trout,k.(3)
The payer chooses uniformly at randomρ←0,l−1 and computes the randomized public keys Pj∗←Pin,j+ρG and the randomized private keys skj∗←skin,j+ρ, where j∈m. We denote P∗=P1∗,…,Pm∗. The payer computes I¯←ρH˜.(4)
The payer computesIj=skjH˜ and Ij∗=Ij+I¯=skj∗H˜, where j∈m. Let I denote I1,…,Im.(5)
The payer picks uniformly at randoma˜∈0,l−1 and then encrypts ρ with the trusted regulator’s public key YR as Ct1′=a˜YR,Ct2′=ρG+a˜U. The ciphertext is denoted as CT2=Ct1′,Ct2′. The SoK proof π is as follows:(16)SoKskjj=1m,in,ρ,sk˜in,α˜:Ct1′=α˜YR∧Ct2′=ρG+α˜U∧P˜in=sk˜inG∧P1∗=sk1+ρG∧I1=sk1H˜∧⋮Pm∗=skm+ρG∧Im=skmH˜tx.Finally, the payer outputsTX=tx,P∗,I¯,I,CT2,π, where tx=m,A,AR.Verifytx,P∗,I¯,I,CT,π: Receiving A and AR, the verifiers can compute Pi˜=∑j=1mPi,j+∑j=1mCni,j−∑k=1tCnout,k, where i∈n. Output 1 if π passes the verification of the SoK and the serial numbers of the transaction have never appeared on the blockchain. Output 0 otherwise.BlockGenTX,blkn−1: Monero uses the Proof-of-Work (PoW) consensus protocol. Firstly, miners collect some Monero transactions from the network and verify them. Validated transactions can be used to generate a Merkle tree. Information such as the root of the Merkle Tree and the hash value of the previous block are contained in the block. Finally, miners try different nonce to make the hash value of the new block meet the mining condition. It outputs the nonce and the block blkn.BlockVerblkn: Given the current block blkn, the miners in the network verify whether the hash value of the current block meets the mining condition and whether the transactions in the block are valid; then output 1 or 0, respectively.TracexR,TX,CT2: There are two ways to trace user public keys. One is to reveal the user’s one-time public key, and the other is to reveal the user’s long-term public key.(1)
Given the ciphertextCT2=Ct1′,Ct2′ in the transaction TX, the method to reveal the user’s one-time public key is as follows. The trusted regulator decrypts the ciphertext with his private key xR by computing P=ρG=Ct2′−skR−1Ct1′. Then, he looks up the list P1,j,…,Pn,j and verifies if P+Pi,j=Pj∗ is satisfied. If the condition is satisfied, then i is the index of the payer in the ring and Pi,j, where j∈m are the one-time public keys of the user being tracked. The trusted regulator can prove to others that Pi,j are the one-time public keys of the payer by generating the proof ψ=SoKxR:YR=xRU∧Ct1′=xRCt2′−ρG. He outputs Pi,j and ψ.(2)
After getting a one-time public keyPi,j of the user, the trusted regulator can reveal the user’s long-term public key. He finds where the one-time public key is generated on the blockchain and extracts the ciphertext CT1=Ct1,Ct2 from it. Then, he decrypts the ciphertext with his private key xR by computing ℋsrYG=Ct2−skR−1Ct1 and gets the user’s long-term public key by calculating Y=Pi,j−ℋsrYG. The trusted regulator proves to others that the public key Y is the long-term public key of the user by generating the proof ψ′=SoKxR:YR=xRU∧Ct1=xRCt2−ℋsrYG. He outputs Y and ψ′.JudgePk,ψψ′,YR,CT1CT2: Given the user’s public key, the proof is generated by the trusted regulator, the public key of the regulator, and the ciphertext. The verifier can verify the correctness of trace results by checking whether the proof is valid or not and outputs 1 or 0, respectively.Figure2 shows the transaction flow in our system. Similar to transaction from Payer to Payee-Payer, that from Payee-Payer to Payee is omitted. Figure 3 shows the transaction verification flow in our system. Figure 4 shows the tracing flow in our system. Figure 5 shows the judging flow in our system. In these figures, we only consider the communications relevant operations. Besides, except that ckout,k is sent through secret channels, all other messages are public. The transactions are assumed verified in Figures 4 and 5.Figure 2
Transaction flow of our system.Figure 3
Transaction verification flow of our system.Figure 4
Tracing flow of our system.Figure 5
Judging flow of our system.


### 4.3. Instantiation of SoK

The instantiation of SoK inUKGen uses ZKSnark. The SoK described in Spend can be instantiated as follows. We can divide it into three parts, and the first part is as follows:(17)PoK1in,ρ,sk˜in:Pj∗−Pin,j=ρG,wherej∈m∧I¯=ρH˜∧P˜in=sk˜inG.Pick uniformly at randomsi,j∈0,l−1,i∈n,j∈m+1 and select uniformly at random αin,j∈0,l−1, where j∈m+1, in∈n and compute(18)M←ℋpPout,1‖Cnout,1‖⋯‖Pout,t‖Cnout,t,Lin,j=αin,jG,j∈mRin,j=αin,jH˜,j∈mLin,m+1=αin,m+1G.then setcin+1=ℋsm,M,Lin,1,Rin,1,…,Lin,m,Rin,m,Lin,m+1.(19)Lin+1,j=sin+1,jG+cin+1Pj∗−Pin+1,j,j∈mRin+1,j=sin+1,jH˜+cin+1I¯,j∈mLin+1,m+1=sin+1,m+1G+cin+1P˜in+1.and repeat this, incrementing inmodn up to(20)Lin−1,j=sin−1,jG+cin−1Pj∗−Pin−1,j,j∈mRin−1,j=sin−1,jH˜+cin−1I¯,j∈mLin−1,m+1=sin−1,m+1G+cin−1P˜in−1cin=ℋsm,M,Lin−1,1,Rin−1,1,…,Lin−1,m,Rin−1,m,Lin−1,m+1.Solve forsin,j by αin,j=sin,j+cin·ρmodq,j∈m and solve for sin,m+1 by αin,m+1=sin,m+1+cin·sk˜inmodq. Finally, get π1=c1,s1,1,…,s1,m,s1,m+1,s2,1,…,s2,m,s2,m+1,sn,1,…,\\sn,m,sn,m+1.The second part of SoK is as follows:(21)PoK2skj∗j=1m:Ij∗=skj∗H˜∧Pj∗=skj∗G,j∈m.Pick uniformly at randomaj∈0,l−1, and compute the commitment Aj1=ajG,Aj2=ajH˜,j∈m, c2=ℋsI1∗,…,Im∗,P1∗,…,Pm∗,A11,…,Am1,A12,…,Am2 and zj=aj+c2·skj∗, where j∈m. Finally, get π2=A11,…,Am1,A12,…,Am2,z1,…,zm.The third part of SoK is as follows:(22)PoK3ρ,a˜:Ct1=a˜YR∧Ct2=ρG+a˜U∧I¯=ρH˜.Pick uniformly at randoma,b∈0,l−1, and compute the commitment A1′=aYR,A2′=aU+bG,B=bH˜, c3=ℋsCt1,Ct2,I¯,A1′,A2′,B and z1′=a+c3·a˜,z2′=b+c3·ρ. Finally, get π3=A1′,A2′,B,z1′,z2′.In conclusion,π=π1,π2,π3.The verification of the SoK is as follows. Parseπ as π1,π2,π3.(1)
Verifyπ1 as follows:(23)M←ℋpPout,1‖Cnout,1‖⋯‖Pout,t‖Cnout,t,L1,j=s1,jG+c1Pj∗−P1,j,j∈mR1,j=s1,jH˜+c1I¯,j∈mL1,m+1=s1,m+1G+c1P˜1c2=ℋsm,M,L1,1,R1,1,…,L1,m,R1,m,L1,m+1.And repeat this, incrementingimodn until they figure out all Li,j,Ri,j,ci, where j∈m,i∈n and Li,m+1, where i∈n, and then verify if cn+1=c1.(2)
ComputeIj∗=Ij·I¯, where j∈m. Verify π2=A11,…,Am1,…,A12,…,Am2,z1,…,zm by checking whether VerfIj∗,Pj∗,π2=1, where j∈m. The details are as follows:Computec2′=ℋsI1∗,…,Im∗,P1∗,…,Pm∗,A11,…,Am1,\\⋯,A12,…,Am2. Check whether the equations are satisfied, including Aj1=zjG−c2′Pj∗,Aj2=zjH˜−c2′Ij∗, where j∈m.(3)
Verifyπ3=A1′,A2′,B,z1′,z2′ by checking whether VerfI¯,Ct1,Ct2,YR,π3=1. The details are as follows:Computec3′=ℋsCt1,Ct2,I¯,A1′,A2′,B, and check whether the following equations are satisfied: A1′=z1′YR−c3′Ct1,A2′=z1′U+z2′G−c3′Ct2,B=z2′H˜−c3′I¯.The instantiation of SoK inTrace is similar to PoK2 in Spend.


### 4.4. Security Analysis

In this section, the security of our accountable Monero scheme is analyzed.Theorem 1.
Let SoK be a SimExt-secure signature of knowledge. The proposed accountable Monero scheme is balanced under the discrete logarithm (DL) assumption.Theorem 2.
Assume the SoK is SimExt-secure. The homomorphic commitment is perfectly hiding, and the encryption scheme is IND-CPA secure. The proposed accountable Monero scheme satisfies anonymity under the decisional Diffie–Hellman (DDH) assumption.Theorem 3.
Assume the SoK is a SimExt-secure. The proposed accountable Monero scheme satisfies nonslanderability under the discrete logarithm (DL) assumption.Theorem 4.
Assume the SoK and public key encryption are with perfect correctness. The SoK is sound and the certified address scheme satisfies unforgeability. The proposed accountable Monero scheme achieves traceability.


## 4.1. Accountable Monero System Workflow

Our accountable Monero system adds accountability to the original Monero system. It includes three types of subjects, namely, the trusted registration authority, denoted byT, the trusted regulator, denoted by R, and users. As shown in Figure 1, the main processes are Registration, Transaction, Transaction on the chain, and Tracing.Registration: To meet the demand of the trusted regulator tracing users’ long-term public keys, a user has to cooperate with the trusted registration authority to create the certificate and key pair. The user’s signing public key and certificate can be accessed in the system. It allows others to make a transaction with him.Transaction: The payer wants to transfer coins to others. Firstly, the payer produces the one-time public key for each payee. At the same time, the payer encrypts the necessary message with the trusted regulator’s public key to support the tracing of payees’ long-term public keys. Secondly, the payer mints coins for each payee. Thirdly, the payer randomizes his one-time keys, uses the trusted regulator’s public key to encrypt the random number used in randomization, and signs the transaction. Finally, he broadcasts the transaction to the P2P network.Transactions on the chain: Miners collect and verify new transactions in the P2P network. Then, they compete for a proof-of-work to add their block to the blockchain.Tracing: When tracing the one-time public key, the trusted regulator decrypts the ciphertext in the transaction to obtain the random number. Then, the regulator can recover the one-time public key from the randomized public key. Obtaining the one-time public key, the trusted regulator can decrypt the ciphertext generated along with the one-time public key to reveal the long-term public key.Figure 1
Workflow of our accountable Monero system.


## 4.2. Accountable Monero System Instantiation

Our accountable Monero system is designed as follows:Setup1λ: This algorithm generates the public parameters of the system. On inputting a security parameter λ, H,H˜,U are generators in G and their discrete logarithms regarding G are unknown. We denote par as par  = SoK.Setup1λ. It outputs pp=1λ,par,G,H,H˜,U,ℋs,ℋp,ξ, where ℋs:0,1∗⟶ℤq and ℋp:0,1∗⟶0,1∗ denote two cryptographic secure hash functions, and ξ is a fixed function from G to ℤq.TKGenpp: This algorithm generates the trusted registration authority’s key pair. Given input pp, it outputs xT,YT, where xT∈0,l−1 and YT=xTG.RKGenpp: This algorithm generates the trusted regulator’s key pair. Given input pp, it outputs xR,YR, where xR∈0,l−1 and YR=xRU.UKGenpp,YT: This algorithm generates the user’s public key. We use the certified key [22] generation method.A certified key is certified by the trusted registration authority. The Certified Key Generation protocol is executed between user U and the registration authorityT as follows:(1)
U picks uniformly at randomk in 0,l−1, computes Z=kG and sends Z to T.(2)
On receivingZ from user U, T picks uniformly at random k′ in 0,l−1 and computes Cu=Z+k′G,e=ξCu,x¯=k′+e·xT. Finally, T sends Cu, x¯ to user U.(3)
On receivingCu, x¯ from T, U computes x=x¯+k as his private key corresponding to his certified public key Yu=Cu+ξCuYT and verifies that(14)xG=Cu+ξCuYT.The user’s public keyYu and certificate Cu are publicly accessed. A payer obtains the payee’s long-term public key Yu=xG, where x is the payee’s long-term private key. The payer generates a one-time public key as a receiving public key for the payee, which can hide the payee’s real public key. In the process of generating a one-time public key, to simplify, we use one of the methods in [28]. The payer firstly chooses uniformly at random r∈0,l−1 and computes R=rG. The payee’s one-time public key is computed as P=ℋsrYuG+Yu, and the corresponding one-time private key is x+ℋsxR. The payer picks uniformly at random r˜∈0,l−1 and then encrypts ℋsrYuG with the trusted regulator’s public key YR as Ct1=r˜YR,Ct2=ℋsrYuG+r˜U. The ciphertext is denoted as CT1=Ct1,Ct2.And it produces SoK as follows:(15)SoKCu,Yu,r,r˜:Yu=Cu+ξCuYT∧P=Yu+ℋsrYuG∧R=rG∧Ct1=r˜YR∧Ct2=ℋsrYuG+r˜U.MintP,a: This algorithm mints a coin for the public key address P with an amount a as follows. It chooses uniformly at random r∈0,l−1 and computes the commitment C=Comck,a;r=rG+aH and then outputs Cn,ck=C,r,a. The account is denoted as act=P,C and the corresponding account private key is denoted as ask=sk,ck=sk,r,a.Spend(m,Kin,Ain,A,Pout,YR): This algorithm allows users to spend their coins while maintaining privacy. in is a secret index corresponding to the signer of the ring. Given the transaction message m∈0,1∗, account private keys Kin and the corresponding account set Ain, accounts A which contain Ain, a set of output public key Pout and the trusted regulator’s public key YR, it outputs a transaction, which contains a proof π, randomized spending public keys P∗ and serial numbers I associated with Ain. Without loss of generality, we denote Kin=askin,j=skin,j,rin,j,ain,jj∈m, Ain=actin,j=Pin,j,Cnin,jj∈m, A=acti,j=Pi,j,Cni,ji∈n,j∈m and the output public key set Pout=Pout,kk∈t. The process of spending coins is as follows:(1)
The payer sets the output amountaout,kk∈t for each output public key Pout,kk∈t such that the input sum is equal to the output sum, i.e., ∑j=1main,j=∑k=1taout,k. Then, the payer chooses uniformly at random rout,k∈0,l−1k∈t and mints coins Cnout,k=Cout,k=Comaout,k;rout,k=rout,kG+aout,kH for the output public keys. Afterward, the payer adds the output accounts actout,k=Pout,k,Cnout,kk∈t to receivers’ account set AR and sends ckout,k=rout,k,aout,k to the owner of a public key Pout,kk∈t through secret channels.(2)
The payer computesP˜i=∑j=1mPi,j+∑j=1mCni,j−∑k=1tCnout,k, where i∈n. If ∑j=1main,j=∑k=1taout,k, P˜in is a commitment to 0. P˜in=\\∑j=1mskin,j+rin,j−∑k=1trout,kG=sk˜inG, where sk˜in=∑j=1mskin,j+rin,j−∑k=1trout,k.(3)
The payer chooses uniformly at randomρ←0,l−1 and computes the randomized public keys Pj∗←Pin,j+ρG and the randomized private keys skj∗←skin,j+ρ, where j∈m. We denote P∗=P1∗,…,Pm∗. The payer computes I¯←ρH˜.(4)
The payer computesIj=skjH˜ and Ij∗=Ij+I¯=skj∗H˜, where j∈m. Let I denote I1,…,Im.(5)
The payer picks uniformly at randoma˜∈0,l−1 and then encrypts ρ with the trusted regulator’s public key YR as Ct1′=a˜YR,Ct2′=ρG+a˜U. The ciphertext is denoted as CT2=Ct1′,Ct2′. The SoK proof π is as follows:(16)SoKskjj=1m,in,ρ,sk˜in,α˜:Ct1′=α˜YR∧Ct2′=ρG+α˜U∧P˜in=sk˜inG∧P1∗=sk1+ρG∧I1=sk1H˜∧⋮Pm∗=skm+ρG∧Im=skmH˜tx.Finally, the payer outputsTX=tx,P∗,I¯,I,CT2,π, where tx=m,A,AR.Verifytx,P∗,I¯,I,CT,π: Receiving A and AR, the verifiers can compute Pi˜=∑j=1mPi,j+∑j=1mCni,j−∑k=1tCnout,k, where i∈n. Output 1 if π passes the verification of the SoK and the serial numbers of the transaction have never appeared on the blockchain. Output 0 otherwise.BlockGenTX,blkn−1: Monero uses the Proof-of-Work (PoW) consensus protocol. Firstly, miners collect some Monero transactions from the network and verify them. Validated transactions can be used to generate a Merkle tree. Information such as the root of the Merkle Tree and the hash value of the previous block are contained in the block. Finally, miners try different nonce to make the hash value of the new block meet the mining condition. It outputs the nonce and the block blkn.BlockVerblkn: Given the current block blkn, the miners in the network verify whether the hash value of the current block meets the mining condition and whether the transactions in the block are valid; then output 1 or 0, respectively.TracexR,TX,CT2: There are two ways to trace user public keys. One is to reveal the user’s one-time public key, and the other is to reveal the user’s long-term public key.(1)
Given the ciphertextCT2=Ct1′,Ct2′ in the transaction TX, the method to reveal the user’s one-time public key is as follows. The trusted regulator decrypts the ciphertext with his private key xR by computing P=ρG=Ct2′−skR−1Ct1′. Then, he looks up the list P1,j,…,Pn,j and verifies if P+Pi,j=Pj∗ is satisfied. If the condition is satisfied, then i is the index of the payer in the ring and Pi,j, where j∈m are the one-time public keys of the user being tracked. The trusted regulator can prove to others that Pi,j are the one-time public keys of the payer by generating the proof ψ=SoKxR:YR=xRU∧Ct1′=xRCt2′−ρG. He outputs Pi,j and ψ.(2)
After getting a one-time public keyPi,j of the user, the trusted regulator can reveal the user’s long-term public key. He finds where the one-time public key is generated on the blockchain and extracts the ciphertext CT1=Ct1,Ct2 from it. Then, he decrypts the ciphertext with his private key xR by computing ℋsrYG=Ct2−skR−1Ct1 and gets the user’s long-term public key by calculating Y=Pi,j−ℋsrYG. The trusted regulator proves to others that the public key Y is the long-term public key of the user by generating the proof ψ′=SoKxR:YR=xRU∧Ct1=xRCt2−ℋsrYG. He outputs Y and ψ′.JudgePk,ψψ′,YR,CT1CT2: Given the user’s public key, the proof is generated by the trusted regulator, the public key of the regulator, and the ciphertext. The verifier can verify the correctness of trace results by checking whether the proof is valid or not and outputs 1 or 0, respectively.Figure2 shows the transaction flow in our system. Similar to transaction from Payer to Payee-Payer, that from Payee-Payer to Payee is omitted. Figure 3 shows the transaction verification flow in our system. Figure 4 shows the tracing flow in our system. Figure 5 shows the judging flow in our system. In these figures, we only consider the communications relevant operations. Besides, except that ckout,k is sent through secret channels, all other messages are public. The transactions are assumed verified in Figures 4 and 5.Figure 2
Transaction flow of our system.Figure 3
Transaction verification flow of our system.Figure 4
Tracing flow of our system.Figure 5
Judging flow of our system.


## 4.3. Instantiation of SoK

The instantiation of SoK inUKGen uses ZKSnark. The SoK described in Spend can be instantiated as follows. We can divide it into three parts, and the first part is as follows:(17)PoK1in,ρ,sk˜in:Pj∗−Pin,j=ρG,wherej∈m∧I¯=ρH˜∧P˜in=sk˜inG.Pick uniformly at randomsi,j∈0,l−1,i∈n,j∈m+1 and select uniformly at random αin,j∈0,l−1, where j∈m+1, in∈n and compute(18)M←ℋpPout,1‖Cnout,1‖⋯‖Pout,t‖Cnout,t,Lin,j=αin,jG,j∈mRin,j=αin,jH˜,j∈mLin,m+1=αin,m+1G.then setcin+1=ℋsm,M,Lin,1,Rin,1,…,Lin,m,Rin,m,Lin,m+1.(19)Lin+1,j=sin+1,jG+cin+1Pj∗−Pin+1,j,j∈mRin+1,j=sin+1,jH˜+cin+1I¯,j∈mLin+1,m+1=sin+1,m+1G+cin+1P˜in+1.and repeat this, incrementing inmodn up to(20)Lin−1,j=sin−1,jG+cin−1Pj∗−Pin−1,j,j∈mRin−1,j=sin−1,jH˜+cin−1I¯,j∈mLin−1,m+1=sin−1,m+1G+cin−1P˜in−1cin=ℋsm,M,Lin−1,1,Rin−1,1,…,Lin−1,m,Rin−1,m,Lin−1,m+1.Solve forsin,j by αin,j=sin,j+cin·ρmodq,j∈m and solve for sin,m+1 by αin,m+1=sin,m+1+cin·sk˜inmodq. Finally, get π1=c1,s1,1,…,s1,m,s1,m+1,s2,1,…,s2,m,s2,m+1,sn,1,…,\\sn,m,sn,m+1.The second part of SoK is as follows:(21)PoK2skj∗j=1m:Ij∗=skj∗H˜∧Pj∗=skj∗G,j∈m.Pick uniformly at randomaj∈0,l−1, and compute the commitment Aj1=ajG,Aj2=ajH˜,j∈m, c2=ℋsI1∗,…,Im∗,P1∗,…,Pm∗,A11,…,Am1,A12,…,Am2 and zj=aj+c2·skj∗, where j∈m. Finally, get π2=A11,…,Am1,A12,…,Am2,z1,…,zm.The third part of SoK is as follows:(22)PoK3ρ,a˜:Ct1=a˜YR∧Ct2=ρG+a˜U∧I¯=ρH˜.Pick uniformly at randoma,b∈0,l−1, and compute the commitment A1′=aYR,A2′=aU+bG,B=bH˜, c3=ℋsCt1,Ct2,I¯,A1′,A2′,B and z1′=a+c3·a˜,z2′=b+c3·ρ. Finally, get π3=A1′,A2′,B,z1′,z2′.In conclusion,π=π1,π2,π3.The verification of the SoK is as follows. Parseπ as π1,π2,π3.(1)
Verifyπ1 as follows:(23)M←ℋpPout,1‖Cnout,1‖⋯‖Pout,t‖Cnout,t,L1,j=s1,jG+c1Pj∗−P1,j,j∈mR1,j=s1,jH˜+c1I¯,j∈mL1,m+1=s1,m+1G+c1P˜1c2=ℋsm,M,L1,1,R1,1,…,L1,m,R1,m,L1,m+1.And repeat this, incrementingimodn until they figure out all Li,j,Ri,j,ci, where j∈m,i∈n and Li,m+1, where i∈n, and then verify if cn+1=c1.(2)
ComputeIj∗=Ij·I¯, where j∈m. Verify π2=A11,…,Am1,…,A12,…,Am2,z1,…,zm by checking whether VerfIj∗,Pj∗,π2=1, where j∈m. The details are as follows:Computec2′=ℋsI1∗,…,Im∗,P1∗,…,Pm∗,A11,…,Am1,\\⋯,A12,…,Am2. Check whether the equations are satisfied, including Aj1=zjG−c2′Pj∗,Aj2=zjH˜−c2′Ij∗, where j∈m.(3)
Verifyπ3=A1′,A2′,B,z1′,z2′ by checking whether VerfI¯,Ct1,Ct2,YR,π3=1. The details are as follows:Computec3′=ℋsCt1,Ct2,I¯,A1′,A2′,B, and check whether the following equations are satisfied: A1′=z1′YR−c3′Ct1,A2′=z1′U+z2′G−c3′Ct2,B=z2′H˜−c3′I¯.The instantiation of SoK inTrace is similar to PoK2 in Spend.


## 4.4. Security Analysis

In this section, the security of our accountable Monero scheme is analyzed.Theorem 1.
Let SoK be a SimExt-secure signature of knowledge. The proposed accountable Monero scheme is balanced under the discrete logarithm (DL) assumption.Theorem 2.
Assume the SoK is SimExt-secure. The homomorphic commitment is perfectly hiding, and the encryption scheme is IND-CPA secure. The proposed accountable Monero scheme satisfies anonymity under the decisional Diffie–Hellman (DDH) assumption.Theorem 3.
Assume the SoK is a SimExt-secure. The proposed accountable Monero scheme satisfies nonslanderability under the discrete logarithm (DL) assumption.Theorem 4.
Assume the SoK and public key encryption are with perfect correctness. The SoK is sound and the certified address scheme satisfies unforgeability. The proposed accountable Monero scheme achieves traceability.


## 5. Efficiency Analysis

In this section, we analyze the performance of our accountable Monero system and compare it with that of Monero. Then, we compare our scheme with the accountable Monero system of [8] in the practical efficiency. Our system is constructed directly on RingCT protocol, the linkable ring signature used in Monero, while the scheme of [8] depends on the accumulator with a one-way domain, which compresses the ring signature size, so that it is independent of the number of groups. However, in practice, Monero’s ring size is small. Our scheme will obtain better efficiency. The comparison is given in Table 1.Table 1
Comparison of Monero systems.
Ref.PayerVerifierCommunication[9](2.2m n − 1.2 m + n).. Expq2.4mn expq(m n + 1) Zq[8]((n − 1)+1) (m + 1) exp 1 + (m + 1) exp T + (m + 1) p+1.2 l(m + 1) exp5.6l(m + 1) exp q + (4.2 + n + 1.2l) (m + 1) exp1 + 4(m + 1) exp T + 3(m + 1) p(l+4) (m + 1) G1 + (5l + 8) (m + 1) Zq p+5l(m + 1) + (m + 1) GTOurs(2m + 1) (n − 1) expq(2.4m n + 1.2n + 2.4 m + 3.9) expq(3m + 4) G + ((m+1) (n + 1) + 3) Zq“n”: the number of input account groups; “m”: the number of input accounts in each group; “l”: the length of the element in ℤq; “expq”: an exponentiation operation in the group G; “exp1”: an exponentiation operation in group G1 used in the accumulator of [8]; ”expT“: an exponentiation operation in the group GT used in the accumulator of [8]; “p”: a bilinear pairing operation; G,G1,GT, ℤq and ℤp are the lengths of the element in group G,G1,GT, ℤq and ℤp respectively.In the efficiency analysis, we only consider the expensive operations, including exponentiation and multiexponentiation, and ignore other lightweight calculations. We use the same optimization as in [8], where the double-exponentiation calculation costs 1.2 times as many as that of a single exponentiation, and the triple-exponentiation calculation cost is 1.5 times that of a single exponentiation, and we neglect the time consumption of operations that can be precomputed.The details of the analysis are as follows. For a payer,2m+1n−1·expq is required in PoK1. All the other computations in SoK can be precomputed. For a verifier, it needs 1.2·2m+1·n·expq in verifying PoK1, 2.4m·expq in verifying PoK2 and 3.9·expq in verifying PoK3. For the communication cost, as in [8], we consider the parameters to be stored and transferred to a verifier in SoK. In addition, we count the parameters P∗ and I¯ in our scheme. m+1G is required in P∗ and I¯, m+1·n+1ℤq is required in PoK1, 2mG+mℤq is required in PoK2 and 3G+2ℤq is required in PoK3.


## 6. Proof of Theorems

### 6.1. Proof of Theorem1

Proof.
Our proof is consistent with [8, 20], with only minor differences. If there exists an efficient adversary A that breaks the property of balance with nonnegligible probability ε, the DL problem can be solved by constructing an efficient algorithm A′.
Having DL instanceG,αG, the algorithm A′ runs SoK.Gen 1λ to generate par. Then, it lets H=αG and picks generators uniformly at random H˜,U∈G. The public parameter is pp=1λ,par,G,H,H˜,U,ℋs,ℋp,ξ, where ℋs:0,1∗⟶ℤq and ℋp:0,1∗⟶0,1∗ denote two cryptographic secure hash functions, and ξ is a function from G to ℤq. A can make queries to AddGen, ActGen, Spend and Corrupt Oracles at most qad,qac,qsp and qco times, respectively. First of all, A′ chooses a j∗∈qad and picks uniformly at random ski∈0,l−1, for all i∈qad as the private keys. The queried public keys are calculated as follows:(24)Pi=skiG,i≠j∗,skiH,i=j∗,
A′ simulates the oracles as follows:(i)
AddGeni: Return Pi for the i− th query.(ii)
ActGeni,ai: Given i and an amount ai, A′ chooses uniformly at random ri∈0,l−1 and sets Cni=Ci=riG+aiH. i, acti=Pi,Cni, and Ii=skiH˜ are added to the lists ℐ, G, and S, respectively.(iii)
Spendm,Ain,A,Pout: Given the inputs, if actj∗∉Ain, A′ generates tx,P∗,I¯,I,CT,π according to the scheme. Otherwise, A′ produces π by simulating SoK. Without witnesses, it is indistinguishable from A’s view. tx,P∗,I¯,I,CT,π is added to the list T.(iv)
Corrupti: Given i, if i=j∗, A′ aborts. Otherwise, A′ returns ski and adds Ii, Ii,ai to the list C and the list ℬ, respectively.
Finally,A outputs some new accounts he created and all his expenses act1′,…,actμ′,S1,…,Sν, where Si=txi,Pi∗,I¯i,Ii,πi,CTi, for all i∈ν. All transactions are paid to A′.
LetEi=ai,j:Ii,j,ai,j∈ℬ∧Ii,j∈Ii∩C, where i∈ν,j∈m, E=E1∪E2∪⋯∪Eν.(i)
Case 1:∀i∈ν,Ii\C=ϕ. According to the condition of a successful attack ∑ai,j∈Eai,j<∑k=1νaouti,whereaouti=∑k=1taout,ki, there exists some i∗∈ν, which have ∑ai∗,j∈Ei∗ai∗,j<aouti∗. From the serial numbers, A′ can find the set acti∗,j of accounts spent in Ai∗ from the list G, where acti∗,j=pki∗,j,Cni∗,j and the private key is aski∗,j=ski∗,j,ri∗,j,ai∗,j. Then, A′ can compute P˜i∗=∑j=1mPi∗,j+∑j=1mCni∗,j−Cnouti∗=∑j=1mski∗,j+∑j=1mri∗,j−routi∗G+α·∑j=1mai∗,j−aouti∗G. Si∉T for all i∈ν; thus, A′ can use Ext to extract the witness sk˜i∗. The DL instance can be solved by calculating(25)α=sk˜i∗−∑j=1mski∗,j+∑j=1mri∗,j−routi∗∑j=1mai∗,j−aouti∗,whereaouti∗=∑k=1taout,ki∗,routi∗=∑k=1trout,ki∗.(ii)
Case 2:∃i∈ν,Ii\C≠ϕ, Let J=i∈ν:Ii\C≠ϕ,IJ=∪i∈JIi/C. If Ij∗∈IJ, then ∃i∗∈J,Ij∗∈Ii∗. A′ can extract a piece of witness that contains skj∗′ and ρj∗′, namely, Pj∗=gskj∗′=gα·skj∗+ρj∗′. DL instance can be solved by calculating α=skj∗′−ρj∗′/skj∗.


### 6.2. Proof of Theorem2

Proof.
We definePrSucci as the probability that adversary A succeeds in Gamei.Game 0. Game 0 is the challenge game defined in anonymity. The challenger generates public parameters pp=1λ,par,G,H,H˜,U,ℋs,ℋp,ξ by executing Setup1λ and responds to all queries to AddGen, ActGen, Spend, Corrupt Oracles as in the real game. When receiving the challenge query m,As0,As1,A,Pout, where A=Pi,j,Cni,ji∈n,j∈m are the input accounts, Asb=Psb,j,Cnsb,jj∈m is the sb−th group of A, and Pout=Pout,kk∈t, the challenger chooses uniformly at random b∈0,1 and calculates according to the algorithm to get a response tx,P∗,I¯,I,CT. Finally, A outputs a guess b′. According to the definition of anonymity, we have(26)PrSucc0=Prb′=b.Game 1. Game 1 and Game 0 are the same, except that the algorithm Gen is replaced by SimGen, and all SoK are generated by calling the simulator Sim = (SimGen, SimSign). That means no witness is needed in the calculation during Spend Oracle queries and the challenge query. Specifically, for a challenge query m,As0,As1,A,Pout and allowed Spend queries m,As,A,Pout, it has As∩Asb=∅. For Spend queries, the challenger computes the statement M,P∗,I¯,I,CT and generates π=SimM,P∗,I¯,I,CT. For the challenge query m,As0,As1,A,Pout, the proof is generated in the same way. If the difference between the adversary’s success probability of Game 0 and in Game 1 is not negligible, we can use the adversary to construct an algorithm to break the SimExt property of SoK.(27)PrSucc1−PrSucc0≤neglλ.Game 2. The difference from Game 1 is that, in the challenge phase of Game 2, the challenger uniformly and randomly selects the transaction output addresses Pout,k, where k∈t. Specifically, the challenger picks uniformly at random α←0,l−1, sets H=αG and sets output coins Cnout,k=r^kG for addresses Pout,k∈Pout by choosing uniformly at random r^k∈0,l−1. The corresponding coin private keys satisfy ckout,k=r^k−α·aout,kb,aout,kb, where k∈t. Thus, the output accounts AR=Pout,k,Cnout,kk∈t are independent of the choice of b. In this case, Pi˜=∑j=1mPij+∑j=1mCnij−∑k=1tCnout,k,wherei∈n is independent of b. If the adversary’s success probability in Game 1 and Game 2 is different, we can use the adversary to construct an algorithm to break the perfect hiding property of homomorphic commitment.(28)PrSucc2=PrSucc1.Game 3. The difference between Game 3 and Game 2 is in the generation of serial numbers. When answering the challenge query, the challenger chooses uniformly at random Ij∈G, as the value of the serial numbers, where j∈m. Assume that no account in Asb is corrupted and has been asked in the Spend Oracle queries. Therefore, the serial numbers I˜=I1,…,Im are fresh to the adversary. If DDH assumption holds, the serial numbers are uniformly distributed. If the difference between the adversary’s success probability in Game 3 and Game 2 is not negligible, we can use the adversary to construct an algorithm to break DDH assumption. The adversary’s success probability satisfies(29)PrSucc3−PrSucc2≤neglλ.Game 4. When replying Spend Oracle queries, the challenger encrypts a random number μ to replace the original ciphertext. When replying Trace Oracle, if tx being queried is in the list T, the challenger returns ρG through searching the list. Otherwise, the simulator can obtain a witness through the SimExt-secure of SoK. And according to the IND-CPA security of the encryption scheme, the challenger gets a unique ρG. If the difference between the adversary’s success probability in Game 4 and Game 3 is not negligible, we can use the adversary to construct an algorithm to break the SimExt-secure of SoK and the IND-CPA of the encryption scheme. The adversary’s success probability satisfies(30)PrSucc4−PrSucc3≤neglλ.
InGame 4, the challenge transaction tx˜,P˜∗,I¯˜,I˜,π˜,CT˜ is independent of b. Hence, the probability of the adversary’s success in Game 4 is 1/2. In summary, the probability of success is 1/2+neglλ.


### 6.3. Proof of Theorem3

Proof.
Suppose that there is an adversaryA that can break the nonslanderability of the protocol with a nonnegligible probability. We can construct a polynomial-time algorithm A′ to solve the DL problem in G by calling A.
Given a DL instanceG,H=αG, the algorithm A′ runs Gen 1λ to produce par. A′ uniformly chooses a random β∈0,l−1, computes H˜=βG, selects a generator at random U∈G and sets pp=par,G,H,H˜,U,ℋs,ℋp,ξ, where ℋs:0,1∗⟶ℤq and ℋp:0,1∗⟶0,1∗ denote two cryptographic secure hash functions, and ξ is a function from G to ℤq. Assume that A can make queries to AddGen, ActGen, Spend and Corrupt Oracles at most qad,qac,qsp and qco times, respectively. First of all, A′ chooses a j∗∈qad and picks uniformly random ski∈0,l−1, as the private keys, where i∈qad. The queried public keys are calculated as follows:(31)Pi=skiG,i≠j∗,skiH,i=j∗,
A′ simulates AddGen, ActGen, Spend, and Corrupt Oracles, consistent with that in the proof of Theorem 1. Finally, A outputs tx^,P^∗,I¯^,I^,π^,CT^,tx˜,P˜∗,I¯˜,I˜,π˜,CT˜. If A succeeds in the nonslanderability game, that means (1) Verifytx˜,P˜∗,I¯˜,I˜,π˜,CT˜=1; (2) tx˜,P˜∗,I¯˜,I˜,π˜,\\CT˜∉T; (3) I^∩C=∅ but I^∩I˜≠∅. Checking if j∗∉I^∩I˜, A′ outputs a random bit guess. Otherwise, A′ can extract the witness of tx˜,P˜∗,I¯˜,I˜,π˜,CT˜, which includes sk˜j∗ and ρ˜j∗, namely, Pj∗∗˜=skj∗∗˜G=α·skj∗+ρj∗˜G. The discrete logarithm of H concerning G can be calculated as α=skj∗∗˜−ρj∗˜/skj∗.


### 6.4. Proof of Theorem4

Proof.
If the SoK proofπ in the transaction TX of Spend algorithm is correct and sound, Ct1′ and Ct2′ are in the correct form. The encrypted plaintext ρG is unique according to the perfect correctness of the public key encryption system. With ρG, P∗ and the input accounts A, the one-time public key P can be determined. According to the extractability of SoK in the KeyGen algorithm, r can be extracted. Y,R,P, and CT1 are all in the correct form. Because ℋs is a cryptographic secure hash function, the probability of finding a Y′ that satisfies logGP−Y′=HrY is negligible. Therefore, Y is the long-term public key of the real payee selected by the payer. Moreover, due to the unforgeability of the certified address and SoK’s soundness, Y has been certified by the trusted registration authority. The correctness of the encryption scheme means that we can get Y=P−Ct2−skR−1Ct1. The other part of the tracing output is the SoK proof ψψ′, which proves that the public key outputted is correct. The correctness and soundness of the SoK prove that it can be correctly verified.


## 6.1. Proof of Theorem1

Proof.
Our proof is consistent with [8, 20], with only minor differences. If there exists an efficient adversary A that breaks the property of balance with nonnegligible probability ε, the DL problem can be solved by constructing an efficient algorithm A′.
Having DL instanceG,αG, the algorithm A′ runs SoK.Gen 1λ to generate par. Then, it lets H=αG and picks generators uniformly at random H˜,U∈G. The public parameter is pp=1λ,par,G,H,H˜,U,ℋs,ℋp,ξ, where ℋs:0,1∗⟶ℤq and ℋp:0,1∗⟶0,1∗ denote two cryptographic secure hash functions, and ξ is a function from G to ℤq. A can make queries to AddGen, ActGen, Spend and Corrupt Oracles at most qad,qac,qsp and qco times, respectively. First of all, A′ chooses a j∗∈qad and picks uniformly at random ski∈0,l−1, for all i∈qad as the private keys. The queried public keys are calculated as follows:(24)Pi=skiG,i≠j∗,skiH,i=j∗,
A′ simulates the oracles as follows:(i)
AddGeni: Return Pi for the i− th query.(ii)
ActGeni,ai: Given i and an amount ai, A′ chooses uniformly at random ri∈0,l−1 and sets Cni=Ci=riG+aiH. i, acti=Pi,Cni, and Ii=skiH˜ are added to the lists ℐ, G, and S, respectively.(iii)
Spendm,Ain,A,Pout: Given the inputs, if actj∗∉Ain, A′ generates tx,P∗,I¯,I,CT,π according to the scheme. Otherwise, A′ produces π by simulating SoK. Without witnesses, it is indistinguishable from A’s view. tx,P∗,I¯,I,CT,π is added to the list T.(iv)
Corrupti: Given i, if i=j∗, A′ aborts. Otherwise, A′ returns ski and adds Ii, Ii,ai to the list C and the list ℬ, respectively.
Finally,A outputs some new accounts he created and all his expenses act1′,…,actμ′,S1,…,Sν, where Si=txi,Pi∗,I¯i,Ii,πi,CTi, for all i∈ν. All transactions are paid to A′.
LetEi=ai,j:Ii,j,ai,j∈ℬ∧Ii,j∈Ii∩C, where i∈ν,j∈m, E=E1∪E2∪⋯∪Eν.(i)
Case 1:∀i∈ν,Ii\C=ϕ. According to the condition of a successful attack ∑ai,j∈Eai,j<∑k=1νaouti,whereaouti=∑k=1taout,ki, there exists some i∗∈ν, which have ∑ai∗,j∈Ei∗ai∗,j<aouti∗. From the serial numbers, A′ can find the set acti∗,j of accounts spent in Ai∗ from the list G, where acti∗,j=pki∗,j,Cni∗,j and the private key is aski∗,j=ski∗,j,ri∗,j,ai∗,j. Then, A′ can compute P˜i∗=∑j=1mPi∗,j+∑j=1mCni∗,j−Cnouti∗=∑j=1mski∗,j+∑j=1mri∗,j−routi∗G+α·∑j=1mai∗,j−aouti∗G. Si∉T for all i∈ν; thus, A′ can use Ext to extract the witness sk˜i∗. The DL instance can be solved by calculating(25)α=sk˜i∗−∑j=1mski∗,j+∑j=1mri∗,j−routi∗∑j=1mai∗,j−aouti∗,whereaouti∗=∑k=1taout,ki∗,routi∗=∑k=1trout,ki∗.(ii)
Case 2:∃i∈ν,Ii\C≠ϕ, Let J=i∈ν:Ii\C≠ϕ,IJ=∪i∈JIi/C. If Ij∗∈IJ, then ∃i∗∈J,Ij∗∈Ii∗. A′ can extract a piece of witness that contains skj∗′ and ρj∗′, namely, Pj∗=gskj∗′=gα·skj∗+ρj∗′. DL instance can be solved by calculating α=skj∗′−ρj∗′/skj∗.


## 6.2. Proof of Theorem2

Proof.
We definePrSucci as the probability that adversary A succeeds in Gamei.Game 0. Game 0 is the challenge game defined in anonymity. The challenger generates public parameters pp=1λ,par,G,H,H˜,U,ℋs,ℋp,ξ by executing Setup1λ and responds to all queries to AddGen, ActGen, Spend, Corrupt Oracles as in the real game. When receiving the challenge query m,As0,As1,A,Pout, where A=Pi,j,Cni,ji∈n,j∈m are the input accounts, Asb=Psb,j,Cnsb,jj∈m is the sb−th group of A, and Pout=Pout,kk∈t, the challenger chooses uniformly at random b∈0,1 and calculates according to the algorithm to get a response tx,P∗,I¯,I,CT. Finally, A outputs a guess b′. According to the definition of anonymity, we have(26)PrSucc0=Prb′=b.Game 1. Game 1 and Game 0 are the same, except that the algorithm Gen is replaced by SimGen, and all SoK are generated by calling the simulator Sim = (SimGen, SimSign). That means no witness is needed in the calculation during Spend Oracle queries and the challenge query. Specifically, for a challenge query m,As0,As1,A,Pout and allowed Spend queries m,As,A,Pout, it has As∩Asb=∅. For Spend queries, the challenger computes the statement M,P∗,I¯,I,CT and generates π=SimM,P∗,I¯,I,CT. For the challenge query m,As0,As1,A,Pout, the proof is generated in the same way. If the difference between the adversary’s success probability of Game 0 and in Game 1 is not negligible, we can use the adversary to construct an algorithm to break the SimExt property of SoK.(27)PrSucc1−PrSucc0≤neglλ.Game 2. The difference from Game 1 is that, in the challenge phase of Game 2, the challenger uniformly and randomly selects the transaction output addresses Pout,k, where k∈t. Specifically, the challenger picks uniformly at random α←0,l−1, sets H=αG and sets output coins Cnout,k=r^kG for addresses Pout,k∈Pout by choosing uniformly at random r^k∈0,l−1. The corresponding coin private keys satisfy ckout,k=r^k−α·aout,kb,aout,kb, where k∈t. Thus, the output accounts AR=Pout,k,Cnout,kk∈t are independent of the choice of b. In this case, Pi˜=∑j=1mPij+∑j=1mCnij−∑k=1tCnout,k,wherei∈n is independent of b. If the adversary’s success probability in Game 1 and Game 2 is different, we can use the adversary to construct an algorithm to break the perfect hiding property of homomorphic commitment.(28)PrSucc2=PrSucc1.Game 3. The difference between Game 3 and Game 2 is in the generation of serial numbers. When answering the challenge query, the challenger chooses uniformly at random Ij∈G, as the value of the serial numbers, where j∈m. Assume that no account in Asb is corrupted and has been asked in the Spend Oracle queries. Therefore, the serial numbers I˜=I1,…,Im are fresh to the adversary. If DDH assumption holds, the serial numbers are uniformly distributed. If the difference between the adversary’s success probability in Game 3 and Game 2 is not negligible, we can use the adversary to construct an algorithm to break DDH assumption. The adversary’s success probability satisfies(29)PrSucc3−PrSucc2≤neglλ.Game 4. When replying Spend Oracle queries, the challenger encrypts a random number μ to replace the original ciphertext. When replying Trace Oracle, if tx being queried is in the list T, the challenger returns ρG through searching the list. Otherwise, the simulator can obtain a witness through the SimExt-secure of SoK. And according to the IND-CPA security of the encryption scheme, the challenger gets a unique ρG. If the difference between the adversary’s success probability in Game 4 and Game 3 is not negligible, we can use the adversary to construct an algorithm to break the SimExt-secure of SoK and the IND-CPA of the encryption scheme. The adversary’s success probability satisfies(30)PrSucc4−PrSucc3≤neglλ.
InGame 4, the challenge transaction tx˜,P˜∗,I¯˜,I˜,π˜,CT˜ is independent of b. Hence, the probability of the adversary’s success in Game 4 is 1/2. In summary, the probability of success is 1/2+neglλ.


## 6.3. Proof of Theorem3

Proof.
Suppose that there is an adversaryA that can break the nonslanderability of the protocol with a nonnegligible probability. We can construct a polynomial-time algorithm A′ to solve the DL problem in G by calling A.
Given a DL instanceG,H=αG, the algorithm A′ runs Gen 1λ to produce par. A′ uniformly chooses a random β∈0,l−1, computes H˜=βG, selects a generator at random U∈G and sets pp=par,G,H,H˜,U,ℋs,ℋp,ξ, where ℋs:0,1∗⟶ℤq and ℋp:0,1∗⟶0,1∗ denote two cryptographic secure hash functions, and ξ is a function from G to ℤq. Assume that A can make queries to AddGen, ActGen, Spend and Corrupt Oracles at most qad,qac,qsp and qco times, respectively. First of all, A′ chooses a j∗∈qad and picks uniformly random ski∈0,l−1, as the private keys, where i∈qad. The queried public keys are calculated as follows:(31)Pi=skiG,i≠j∗,skiH,i=j∗,
A′ simulates AddGen, ActGen, Spend, and Corrupt Oracles, consistent with that in the proof of Theorem 1. Finally, A outputs tx^,P^∗,I¯^,I^,π^,CT^,tx˜,P˜∗,I¯˜,I˜,π˜,CT˜. If A succeeds in the nonslanderability game, that means (1) Verifytx˜,P˜∗,I¯˜,I˜,π˜,CT˜=1; (2) tx˜,P˜∗,I¯˜,I˜,π˜,\\CT˜∉T; (3) I^∩C=∅ but I^∩I˜≠∅. Checking if j∗∉I^∩I˜, A′ outputs a random bit guess. Otherwise, A′ can extract the witness of tx˜,P˜∗,I¯˜,I˜,π˜,CT˜, which includes sk˜j∗ and ρ˜j∗, namely, Pj∗∗˜=skj∗∗˜G=α·skj∗+ρj∗˜G. The discrete logarithm of H concerning G can be calculated as α=skj∗∗˜−ρj∗˜/skj∗.


## 6.4. Proof of Theorem4

Proof.
If the SoK proofπ in the transaction TX of Spend algorithm is correct and sound, Ct1′ and Ct2′ are in the correct form. The encrypted plaintext ρG is unique according to the perfect correctness of the public key encryption system. With ρG, P∗ and the input accounts A, the one-time public key P can be determined. According to the extractability of SoK in the KeyGen algorithm, r can be extracted. Y,R,P, and CT1 are all in the correct form. Because ℋs is a cryptographic secure hash function, the probability of finding a Y′ that satisfies logGP−Y′=HrY is negligible. Therefore, Y is the long-term public key of the real payee selected by the payer. Moreover, due to the unforgeability of the certified address and SoK’s soundness, Y has been certified by the trusted registration authority. The correctness of the encryption scheme means that we can get Y=P−Ct2−skR−1Ct1. The other part of the tracing output is the SoK proof ψψ′, which proves that the public key outputted is correct. The correctness and soundness of the SoK prove that it can be correctly verified.


## 7. Conclusion

In this paper, an accountable Monero system based on the RingCT protocol is proposed. We utilize the signature with rerandomizable keys to randomize the one-time spend keys and exploit ElGamal public key encryption to encrypt the random number, which only enables the trusted regulator to reveal the public keys of the payers. And to enable the traceability of all users of the system, we replace the long-term public key with a certified long-term public key. The designed system maintains correctness, balance, nonslanderability, and traceability. Through security proof and analysis, we demonstrate the security and performance of the proposed system.



---

*Source: 7746341-2022-04-23.xml*