1. Introduction
In this part, we introduce Monero’s original signature scheme as described in van Saberhagen’s seminal Cryptonote paper [2]. The scheme is an adaptation of the Traceable Ring Signature introduced by Fujisaki and Suzuki [1]. The most recent version of Monero implements a different signature known as RingCT. It modifies the original scheme to accomodate confidential transactions. We will discuss it in detail in parts 7, 8 and 9.
Security analysis of ring schemes consisted primarily in proving a) correctness, b) resilience against EFACM attacks in the RO model (unforgeability), and c) anonymity (i.e., signer ambiguity according to e.g., definition # 1 or # 2 as previously described in part 3). However, none of these security metrics tells if 2 signatures were generated by the same user or not. Doing so does not necessarily break the anonymity of the signer, but rather establishes a relationship between pairs of signatures. Identifying whether 2 signatures are linked or not is essential when dealing with electronic cash for example. In this case, the network must not tolerate the double spending of the same unit of electronic currency on 2 different transactions. In an electronic cash setting, the message typically consists of an unspent transaction output (also known as UTXO) and the objective is to make sure that the owner of a UTXO does not sign it twice (i.e., double spend it). Whenever this happens, the incident must be flagged and proper measures taken.
Monero in particular, and cryptocurrencies in general are prone to the double spending problem. This motivates the need to have an additional security requirement to tell if 2 signatures were issued by the same user. This must be done without releasing the identity of the user. We refer to the new requirement as linkability. It can commonly be achieved by adding to the ring signature a new signerspecific component known as a tag or a keyimage.
Formally, we define a linkable ring signature scheme as a set of 4 algorithms:
 The signer’s key generation algorithm (as described in part 1)
 The ring signing algorithm (as described in part 1).
 The ring verification algorithm (as described in part 1)
 The ring linkability algorithm . Its input consists of a set of tags (keyimages) and a given signature . It checks if ‘s tag is included in the tag set. If so, it outputs Linked. Otherwise, it outputs Independent and adds the new tag to the set.
2. Cryptonote’s original linkable ring signature
Cryptonote is an application layer protocol that supports a number of cryptocurrencies. The first implementation of the Cryptonote protocol dates back to July 2012 and consisted of a cryptocurrency known as Bytecoin (different than Bitcoin). In April 2014, Monero was launched as a fork of Bytecoin.
The Cryptonote scheme [2] relies on a large finite group generated by a particular elliptic curve whose equation is given by:
For a concise introduction to elliptic curve cryptography, one could consult this post. The above equation is a polynomial over where is a very large prime and is a predefined element of . To simplify the notation, we refer to the group generated by this elliptic curve as . We note the following:
 Elements of are pairs that satisfy the above equation.
 Elliptic curve groups in general and in particular have a well defined addition operation that we denote by .
 contains a special element (not necessarily unique) that we refer to as the base point. The base point has order , where is a very large prime. That means that adding to itself times yields the identity element of . In other terms, . We simply write (the notation serves as a reminder that this is scalar multiplication associated with ).
 We let denote the group generated by under the operation of . We also let
 Solving the Discrete Logarithm (DL) problem on (and more generally on ) is thought to be intractable.
Cryptonote’s signature uses 2 distinct hash functions and (modeled as 2 ROs). With a slight divergence from [2], we first introduce a hash function before we define . The reason will become clearer in section 4 when we build the signing simulator to prove Cryptonote scheme’s resilience against EFACM.
takes an element and outputs a tuple . Here is a random element chosen according to a uniform distribution over . We then let . So , takes an element and returns an element where is randomly chosen in .
Note that [2] defines as a map from to . Here we restricted the domain and the range to instead. This is because as we will see shortly, is applied to public keys. Public keys are elements of that are scalar multiples of the base point . Moreover, the scalar is never equal to order() (we impose this constraint when we introduce the key generation algorithm next). We are then justified in restricting the domain to . The range is arbitrarily defined to be , which is permissible since it preserves the injective nature of the map.
The scheme is defined by a set of 4 algorithms:
 The key generation algorithm . On input ( is the security parameter that by design we require to satisfy , it produces a pair of matching secret and public keys. is randomly chosen in , and is calculated as . (Note that and are both elements of while is an element of .
In addition to the key pair, computes . is known as the key image (or tag). It is signerspecific since it depends only on the signer’s private and public keys. It allows the ring linkability algorithm to test for independence between different signatures. is modeled as a PPT Turing machine.
 The ring signing algorithm . Suppose a user decides to sign a message on behalf of the ring of users . has a key pair given by and a keyimage (or tag) given by . does the following:
 , choose random , . assign and .
 Choose random . Assign and .
 Assign .
 , assign and .
 Set and Here denotes regular scalar multiplication in modulo arithmetic.
outputs a signature . is a PPT algorithm.

The ring verification algorithm . Given a ring signature , a message , and the set of public keys of the ring members
 (Verification equations to ): computes
 (Verification equation ): checks whether
If equality holds, the signature is valid and outputs True. Else, it outputs False.
 (Verification equations to ): computes
 The ring linkability algorithm .It takes a verified valid signature . It checks if the keyimage was used in the past by comparing it to previous keyimages stored in a set . If a match is found, then with overwhelming probability the 2 signatures were produced by the same key pair (as will be justified in the exculpability section), and outputs Linked. Otherwise, its keyimage is added to and outputs Independent.
3. Security analysis – Correctness
Let be a generated signature. We compute:


, if (since dictates that and ).
 , if (since dictates that ). And since , the resulting quantity becomes .
We can then easily see that .



, if (since dictates that and ).

, if (since dictates that ). And since (by ‘s construction), the resulting quantity becomes .
We can then easily see that . Subsequently, we get
(by construction of ).
Hence generated signatures are valid.

4. Security analysis – Unforgeability visavis EFACM
For unforgeability proofs, we follow the 5step approach outlined earlier in part 1 (Recall that for ring signatures, we prove resilience against EFACM with respect to a fixed ring attack as described in part 3).
Step 1: To prove that this scheme is secure against EFACM in the RO model, we proceed by contradiction and assume that there exists a PPT adversary such that:
for nonnegligible in .
Step 2: Next, we build a simulator such that it:
 Does not have access to the private key of any signer.
 Has the same range as the original signing algorithm (i.e., they output signatures taken from the same pool of potential signatures over all possible choices of RO functions and random tapes and ).
 Has indistinguishable probability distribution from that of over this range.
The reason we introduced as opposed to introducing only is that the simulator makes use of the random element in order to set to the desired value. In other words, the simulator needs to have access to the random element that is used in the calculation of in order to ensure that equates to .
By construction, the output of will satisfy the verification equation. Moreover, it does its own random assignments to what otherwise would be calls to RO (i.e., bypasses RO ). Next, note the following:
 does not use any private key.
 and both have a range
s.t.
where
 and have the same probability distribution over . Indeed, , we have:
 For
The first factor is the probability of choosing the exact value in the set that is equal to . The second factor is the probability of choosing the exact values given by the ‘s and ‘s .
 For :
Note that the range of is equal to by construction of . And so the first factor is the probability of choosing the exact value in the set that is equal to . The second factor is the probability of choosing the exact values given by the ‘s and ‘s .
 For
With adequately built, we conclude that (refer to section 6 of part 1 for a justification):
, for nonnegligible in .
Step 3: We now show that the probability of faulty collisions is negligible (refer to section 6 of part 1 for an overview). The 2 tyes of collisions are:
 : A tuple that encounters — recall that makes its own random assignment to and bypasses RO — also appears in the list of queries that sends to RO . A conflict in the 2 values will happen with overwhelming probability and the execution will halt.
 : A tuple that encounters — recall that makes its own random assignment to — is the same as another tuple that encountered earlier — here too, would have made its random assignment to . Since the tuples are identical (i.e., ), the assignments must match (i.e., . However, the likelihood that the 2 are equal is negligible. Hence they will be different with overwhelming probability and the execution will halt.
The aforementioned collisions must be avoided. In order to do so, we first calculate the probability of their occurence. We assume that during an EFACM attack, can make a maximum of queries to RO , a maximum of queries to RO , and a maximum of queries to . , , and are all assumed to be polynomial in the security parameter , since the adversary is modeled as a PPT Turing machine.
.
Recalling that and are polynomial in , we conclude that is negligible in
Next, we compute
(since by design)
Recalling that is polynomial in , we conclude that is negligible in
Putting it altogether, we find that the below quantity is negligible in :
This allows us to conclude that the below quantity is nonnegligible in (refer to section 6 of part 1 for a justification):
Step 4: In this step, our objective is to show that if is a successful tuple that generated a first EFACM forgery, then the following quantity is nonnegligible in :
Here is an appropriate index that we will define in the proof. To further simplify the notation, we let and for all . ( and denote respectively the query to and to ).
Let’s take a closer look at
Any successful forgery must pass the verification equation given by:
where and
Notice that this equation takes the ‘s as argument before verifying the equality. So we distinguish between 3 scenarios (without loss of generality, we assume that all queries sent to RO are distinct from eachother. Similarly, all queries sent to RO are distinct from eachother. This is because we can assume that keeps a local copy of previous query results and avoid redundant calls):
 Scenario 1: was successful in its forgery, and
 No collisions occured, and
 It never queried RO on input .
 Scenario 2: was successful in its forgery, and
 No collisions occured, and
 It queried RO on input during execution, and
 such that it queried RO on input after it had queried RO on input .
 Scenario 3: was successful in its forgery, and
 No collisions occured, and
 It queried RO on input during execution, and
 , it queried RO on input before it queried RO on input .
The probability of scenario 1 is upperbounded by the probability that picks its ‘s for such that matches the value of . Here, is the value that RO returns to (the verification algorithm) when verifying the validity of the forged signature. And since can be any value in the range of (which was defined to be ) we get:
, which is negligible in .
In scenario 2, let be an index such that queried RO on input after it had queried RO on input . Note that during the verification process, will calculate and hence will make a call to on input (remember that is derived from ). The probability that the resulting matches the argument previously fed to is upperbounded by (since the range of ). Moreover, can be any index in . We get:
, which is negligible in
So we assume that a successful forgery will likely be of the Scenario 3 type.
, which is nonnegligible in
Note that can send queries to RO and RO in any order it chooses to. This gives 2 different ways of referencing the index of a particular query sent to RO . One way is to count the index as it appeared in the sequence of cumulative queries sent to both and . In this case, indices take on values in . The other way, is to do the counting with respect to queries only causing indices to take on values in . If is the index counted in the cumulative numbering system (i.e., the former system), we let be the equivalent index in the latter system. Clearly,
We define to be the index of the query sent by to RO during execution. Here, indexing is done with respect to the cumulative numbering system, and so . We let if query was never asked by . We also define the following condition:
This definition allows us to build the following sets:
In other terms, is the set of tuples that yield a successful EFACM forgery when no collisions occur, and when queried RO on input at some point during its execution such that condition is met. This is none other than scenario 3 that was described earlier.
In other terms, is the set of tuples that yield a successful EFACM forgery when no collisions occur, and when the index of the query sent to RO on input is equal to , and such that condition is met.
Recall that:
, (nonnegligible in ).
Clearly, partitions . So:
This implies that such that
If this were not the case, then one would get the following contradiction:
So we introduce the set consisting of all indices that meet the threshold, i.e.
We claim that .
Proof: By definition of the sets , we have:
The next step is to apply the splitting lemma to each . First note that:
Referring to the notation used in the splitting lemma (section 7 of part 1), we let:
is defined as the space of tuples of:
 All random tapes
 All random tapes
 All possibe RO answers to the first () queries sent by (note the usage of indexing since indexing is done with respect to RO queries only)
 All RO (this means all possible RO answers to the queries sent by ).
is defined as the space of all possible RO answers to the last queries sent by . (Recall that where is the query sent to RO ).
The splitting lemma guarantees the existence of a subset of tuples such that:
, we have:
, and so
We would like to compute the probability of finding a successful tuple given that was a successful tuple and such that . That means finding the following probability:
From the splitting lemma results, we have a (nonnegligible in ) lowerbound on:
Note however, that and are generally distinct sets. And so we cannot conclude that:
and therefore we cannot conclude that the following quantity is nonnegligible in
In order to show that the above quantity is nonnegligible in , we proceed differently. Suppose we can show that the following probability is nonnegligible in :
This would imply that with nonnegligible probability, we can find a tuple that belongs to (and hence corresponds to a successful forgery) and at the same time belongs to . We can then invoke the splitting lemma result just mentioned, to find a second tuple coresponding to a second forgery and that has the desired properties.
To prove the above, we proceed as follows:
since the ‘s are disjoint.
( result of splitting lemma above)
(by the claim proven earlier)
.
And so we conclude that:
which is nonnegligible in
So let be such an index and such a tuple. From the result above, we know that finding such a can be done with nonnegligible probability. And since , we must have . We can then invoke the consequence of the splitting lemma and write:
We still have one last constraint to impose and that is that . We show that the following quantity is nonnegligible:
To prove this, we use the same technique employed in part 2 and part 4 of this series. Note that if and are independent events, then we can write:
And so we get
This result allows us to write:
(because we chose )
, which is nonnegligible in
Step 5: The final step uses the 2 forgeries obtained earlier to solve an instance of the Discrete Logarithm (DL) problem. Here is a recap of Step 4 results:
 With nonnegligible probability of at least we get a successful tuple , s.t. for some index . By running a number of times polynomial in , we can find such a tuple.
 Once we find such a tuple, we’ve also shown that with nonnegligible probability of at least , we can find another successful tuple such that and .
Let correspond to forgery
and correspond to forgery
Recall that is the index of the query that sends to RO . Since the 2 experiments corresponding to the 2 successful tuples have:
 The same random tapes and
 The same RO
 ROs and behave the same way on the first queries,
we can be confident that the first queries sent to the 2 ROs and are identical.
In particular the two queries are the same. And so:
(by writing
Moreover, we have
(since is a valid forgery)
(by design of the forgery tuples)
(since is a valid forgery)
Since , then such that
That means that we can solve for in polynomial time, contradicting the intractability of DL on elliptic curve groups. We conclude that the signature scheme is secure against EFACM in the RO model.
5. Security analysis – Exculpability
We encountered the notion of exculpability when we introduced the 2 anonymity definitions in part 3. In that context, we said that a signer is exculpable if her identity can not be established even if her private key gets compromised. In other terms, no one can prove that she was the actual signer under any circumstance. This ensures her exculpability. In this section, we introduce a different notion of exculpability described in [1]. It has to do with unforgeability as opposed to anonymity.
Suppose private keys have been compromised in an ring setting. Let denote the index of the only noncompromised private key , and let denote the keyimage (or tag) associated with the key pair . We investigate whether it is likely to produce a valid forgery with keyimage . In what follows, we show that this can only happen with negligible probability. In essence, this means that a noncompromised honest ring member (by honest we mean a ring member that signs at most once using his private key) does not run the risk of encountering a forged signature that carries his keyimage. In the context of Cryptonote, this implies that a noncompromised honest ring member cannot be accused of signing twice using the same key image or tag, and hence is exculpable.
Note that since the adversary has access to the compromised private keys, it can easily calculate their corresponding public keys. Doing so will allow it to identify the public key of the noncompromised ring member. That means that it can determine the index of the noncompromised member in the ring . In order to prove the exculpability of the Cryptonote scheme, we follow an almost identical proof to that of the previous section (i.e., unforgeability visavis EFACM) and apply the same 5step approach.
Step 1: We proceed by contradiction and assume that there exists a PPT adversary such that:
for nonnegligible in .
We refer to “succeeds in creating a forgery” as . We rewrite the above equation as:
, for nonnegligible in .
The notation used makes it explicit that can access the set of compromised keys with excluded. Success is defined as issuing a forged signature with key image or tag equal to . (Recall that is derived from ).
Step 2: The next step consists in building a simulator such that it:
 Does not have access to the private key of any signer.
 Has the same range as the original signing algorithm (i.e., they output signatures taken from the same pool of potential signatures over all possible choices of RO functions and respective random tapes and ).
 Has indistinguishable probability distribution from that of over this range.
The simulator is the same as the one we built in the previous section. The only nuance is that does not choose a random index , since already knows the index of the noncompromised ring member.
Step 3: The logical reasoning and procedure are identical to those of the previous section. We conclude that:
Step 4: Here too, the logical reasoning and procedure are identical to those of the previous section. In particular, we define the following sets in a similar way:
and conclude that:
, which is nonnegligible in
Here , as before, is an appropriately defined index, , and for all .( denotes the query sent to RO).
Step 5: The final step uses the 2 forgeries obtained earlier to solve an instance of the Discrete Logarithm (DL) problem. Here is a recap of Step 4 results:
 With nonnegligible probability of at least we get a successful tuple , s.t. for some index . By running a number of times polynomial in , we can find such a tuple.
 Once we find such a tuple, we’ve also shown that with nonnegligible probability of at least , we can find another successful tuple such that and .
Let correspond to forgery
and correspond to forgery
Recall that is the index of the query that sends to RO . Since the 2 experiments corresponding to the 2 successful tuples have:
 The same random tapes and
 The same RO
 ROs and behave the same way on the first queries,
we can be confident that the first queries sent to the 2 ROs and are identical.
In particular the two queries are the same. And so:
, and
Let , and . For each , we get 2 identical systems of 2 equations dictated by ‘s verification computation:
, the first system is a linear system of 2 equations in variables and . Similarly, the second system is a linear system of 2 equations in variables and . The 2 systems are identical with different variable names. Hence, if is a unique solution to the first system and a unique solution to the second, we can be confident that and . (Note that when we previously proved resilience against EFACM in section 4, the 2 forged signatures did not necessarily share the same tag and so the 2 systems of linear equations would have been different from each other). For either system to admit a unique solution, the 2 equations must be linearly independent. We rewrite the 2 systems as follows:
If we multiply the second equation by (multiplication refers to ), we see that a sufficient condition for the system to be linearly independent is to have . Next, we show that with overwhelming probability, the system of linear equations is indeed independent for all :
 Recall that the range of is and that the order of
 Therefore, such that and
 We can then rewrite the sufficient condition as
 Note that given , and , there is at most one value of that satisfies . Otherwise, we would have , , and . This would imply that , a contradiction.
 Noting that each corresponds to a distinct , we conclude that given and there is at most one s.t. .
 Since is a RO outputing random values, the probability of getting the right value of is (negligible in ).
, we therefore conclude that with overwhelming probability we have . In other terms, we can be confident that the linear system of 2 equations has a unique solution. Hence, , we have , and
Moreover, we have:
(since is a valid forgery)
(by design of the forgery tuples)
(since is a valid forgery)
Since , we conclude that such that . But , we showed earlier that with overwhelming probability we have . We then conclude that with overwhelming probability .
Going back to the system of 2 equations associated with , we write:
That means that we can solve for in polynomial time, contradicting the intractability of DL on elliptic curve groups. We conclude that the signature scheme is exculpable and hence secure against in the RO model.
6. Security analysis – Anonymity
In this section, we show that Cryptonotes’ signature scheme satisfies the weaker anonymity definition #2 introduced in part 3. The reason it cannot satisfy the stronger definition #1 has to do with the inclusion of the key image or tag. Linkable signatures in general cannot satisfy anonymity definition #1. By introducing a tag that is fully determined by a ring member’s private key, anyone with access to the signature can ruleout or confirm whether a member was the author if the member releases her private key. To see this, suppose that ring member releases her private key , and let be a valid signature. Anyone can calculate and compare it to . If the 2 values differ, then the signature could not have originated from member who can now be ruled out. The identity of the signer is then confined to the remaining noncompromised members. On the other hand, if the 2 values match, then one can confidently assume that member was the author. The confidence is derived from the exculpability property of the scheme that we demonstrated earlier (i.e., with overwhelming probability, no one can forge a signature with a key image or tag corresponding to a noncompromised signer). This shows that a linkable signature scheme is not exculpable in the anonymitymetric sense, although it can be exculpable in the unforgeabilitymetric sense.
More formally, we let be a PPT adversary with random tape that takes 4 inputs:
 Any message .
 A ring of the public keys of the ring members. includes the public key of the actual signer.
 A list of compromised private keys of ring members . Note that can be empty. Also note that may be different than but we always have
 A valid signature on message , with ring and actual signer private key .
outputs an index corresponding to the ring member in that it thinks is the actual signer. Definition # 2 mandates that for any polynomial in security parameter , we have:
, if and
, if or
In the RO model, we allow to send a number of queries (polynomial in ) to RO and RO . The probability of ‘s success is then computed over the distributions of and . Making explicit the dependence on the ROs, definition # 2’s condition becomes:
, if and
, if or
In order to prove that anonymity holds in the above sense, we proceed by contradiction and rely on the intractability of another hard problem over cyclic groups known as the Decisional Diffie Hellman problem (DDH for short). A proof that relies on an intractable problem is referred to as a conditional proof. In what follows, we first introduce the DDH problem and then prove anonymity of the Cryptonote’s scheme.
DDH formulation: Let be a generator of a cyclic group of order . DDH states that if and are uniformly and independently chosen in , then the value of looks like a random element in the group. Intuitively, this means that the following 2 distributions of tuples are indistinguishable:
 , where and are randomly and independently chosen in .
 , where , , and are randomly and independently chosen in .
In other terms, we don’t know of any PPT algorithm that when given a tuple as input, can do better than random guessing as to whether or not. Formally, we describe the DDH problem as follows:
 Let be uniformly drawn from
 Let be uniformly drawn from , and let
 Let be uniformly drawn from
 Let . We don’t know any (probabilistic polynomial time in ) such that
for nonnegligible in
The previous formalization means that if we randomly decide whether a tuple that we send to is definitely a DDH instance or not, there is no known PPT() that can tell what was decided with probability better than random guessing. Concretely:
 We flip a coin and assign the value 0 or 1 to variable
 If , we feed a random tuple . There is a negligible probability that , but most likely and hence the tuple is not DDH.
 If on the other hand , we feed a tuple that we know for sure to be a DDH instance.
The objective is for to devise a mechanism to guess, depending on the input tuple, whether or . The intractability of DDH means that there does not exist in the set of PPT() that can outperform random guessing in that endeavour.
Note that if is a DDH instance, we write to make explicit the group generator . Clearly, a DDH instance by definition satisfies and so will satisfy . In general, if is a tuple with elements chosen from a group with generator , saying that is a DDH instance is equivalent to saying that . This is helpful when we are not given the powers , but rather the group elements and . We are now in a position to prove the anonymity of Cryptonote’s signature scheme.
Anonymity proof: We consider 3 separate cases.
Case 1: and
We proceed by contradiction. Suppose that in PPT() and nonnegligible in such that
, if and
Recall that since , one can automatically rule out all the compromised ring members as possible signers (the logic was described in the introductory paragraph of this section). One can then limit the guessing range of the identity of the signer to the uncompromised batch of remaining members.
We now build PPT() that colludes with to solve the DDH problem. The input of consists of 1) The tuple being tested for DDH, 2) A certain ring size ( randomly chosen), 3) A number of compromised members (randomly chosen), and 4) A message (randomly chosen).
will output a tuple consisting of 1) The message , 2) A randomly generated ring of size , 3) A randomly chosen set of compromised secret keys, and 4) A notnecessarily valid signature assigned to ring member such that .
feeds its output to . In order for to use its advantage in guessing the signer’s identity, it must be given a valid signature. For to be a valid signature, must be a DDH instance. Indeed, we have the following implications:
is DDH instance
By design of , we also have , . We then conclude that
is a valid signature.
On the other hand, if is not a DDH instance, then and with overwhelming probability
and is not a valid signature.
Recall that can send queries to and during execution. It is important to enforce consistency between and ‘s query results obtained from RO and RO on the same input. There are no risks of faulty collisions in so far as is concerned (by design of ). However, bypasses RO and conducts its own backpatching to . If queries on input , then with overwhelming probability, it will conflict with ‘s backpatched value causing the execution to halt. The aforementioned collision must be avoided. In order to do so, we first calculate the probability of its occurence. We assume that during execution, can make a maximum of queries to RO . is assumed to be polynomial in the security parameter , since the adversary is modeled as a PPT Turing machine.
and so we conclude that:
whenever and . Here, is nonnegligibale in
After execution, returns to an integer . then outputs 1 if , or outputs 0/1 with equal probability otherwise. The following diagram summarizes the process:
Using the setting described above, we now calculate the probability of guessing whether is DDH or not. In what follows we make use of the following notational simplifications:
 We refer to simply as
 We refer to simply as
We start by noticing that
 Case (): In this case, is a DDH instance and so as we saw earlier, will be a valid signature. would then use its hypothetical advantage to guess the index of the signer among the noncompromised ring members. We get:
(by design of ).Since is a valid signature, we have:
for nonnegligible inLet for some
Hence . We get:
 Case (): In this case, we do not know if is a DDH instance or not, and hence can not be sure whether is a valid signature. Consequently, can no longer use its advantage in guessing the index of the signer, because this advantage works only when it is fed a valid signature. We get:
(by design of ).and since can no longer use its advantage to guess the index of the signer, the best thing it can do is random guessing among noncompromised members. Hence:
and
We get:
Putting it altogether, we conclude that:
Since is nonnegligible in , the above probability outperforms random guessing. This contradicts the intractability of DDH. Similarly, we can show
is also bounded from below. We finally conclude that for any polynomial :
, if and
Case 2: and
In this case, can check if (the keyimage or tag of ) matches any of the compromised tags , for . With overwhelming probability, none of them will match since we proved that the scheme is exculpable and so no one can forge a signature with a tag of a noncompromised member. Proceeding by elimination, can then conclude that the signer is
Case 3:
In this case, can check which of the compromised tags matches (the keyimage or tag of ). Only one of them will match (due to exculpability), subsequently revealing the identity of the signer.
7. Security analysis – Linkability
In essence, the linkability property means that if a secret key is used to issue more than one signature, then the resulting signatures will be linked and flagged by (the linkability algorithm). We claim that:
A signature scheme is linkable
a ring of members, it is not possible to produce valid signatures with pairwise different keyimages such that all of them get labeled independent by
Proof of : Consider the case with . Then it is not possible to use ‘s secret key to produce 2 valid signatures such that they have different keyimages and both are labeled independent by . In other words, the signature scheme is linkable.
Proof of : We prove the contrapositive. Assume that a ring of members such that it can produce valid signatures with pairwise different keyimages, and such that all of them get labeled independent by . This implies that such that the ring member with public key produced at least 2 valid signatures with different keyimages, both labeled independent by . This means that the scheme is not linkable.
To prove that Cryptonote’s scheme is linkable we follow a reductio ad absurdum approach:
 Assume that the scheme is not linkable.
 The equivalence above would imply that such that it can produce valid signatures with pairwise different keyimages (i.e.,), and such that all of them get labeled independent by .
 This means that there must exist a signature (from the set of valid signatures) with keyimage such that . Denote this signature by .
 When verifying the validity of will first compute the following for all :
 , the system of 2 equations above can be equivalently written as:
 For a given , , and , this constitutes a system of 2 equations in variables and .
 Since , the system of 2 equations corresponding to each is independent and admits a unique solution for any given , and . That means that for given , and , the value is well defined.
 By virtue of being a valid signature, must satisfy ‘s verification equation. More specifically, it must be that . But RO is random by definition. The probability that it outputs a specific value is eqal to (recall that the range of ). And since by design we have , we conclude that the probability that is upperbounded by and is hence negligible. In other terms, the probability that is a valid signature is negligible.
We can then conclude that with overwhelming probability, the ring can not produce valid signatures with pairwise different keyimages and such that all of them get labeled independent by . Cryptonote’s scheme is hence linkable.
References
[1] E. Fujisaki and K. Suzuki. Traceable ring signatures. Public Key Cryptography, pages 181 (200, 2007).
[2] N. Van Saberhagen. Cryptonote 2.0., 2013.
Tags: anonymity, Cryptonote, Monero, Privacy, ring signature
No comments
Comments feed for this article
Trackback link: https://delfr.com/monero/cryptonoteringsignature/trackback/