Anonymity and rewards in peer rating systems 1

Abstract

When peers rate each other, they may rate inaccurately to boost their own reputation or unfairly lower another’s. This could be mitigated by having a reputation server incentivise accurate ratings with a reward. However, assigning rewards becomes challenging when ratings are anonymous, since the reputation server cannot tell which peers to reward for rating accurately. To address this, we propose an anonymous peer rating system in which users can be rewarded for accurate ratings, and we formally define its model and security requirements. In our system ratings are rewarded in batches, so that users claiming their rewards only reveal they authored one in this batch of ratings. To ensure the anonymity set of rewarded users is not reduced, we also split the reputation server into two entities, the Rewarder, who knows which ratings are rewarded, and the Reputation Holder, who knows which users were rewarded. We give a provably secure construction satisfying all the security properties required. For our construction we use a modification of a Direct Anonymous Attestation scheme to ensure that peers can prove their own reputation when rating others, and that multiple feedback on the same subject can be detected. We then use Linkable Ring Signatures to enable peers to be rewarded for their accurate ratings, while still ensuring that ratings are anonymous. Our work results in a system which allows accurate ratings to be rewarded, whilst still providing anonymity of ratings with respect to the central entities managing the system.

Keywords

Reputation incentives anonymity

1. Introduction

Anonymity has long been a sought-after property in many cryptographic primitives, such as public-key encryption [4], identity-based encryption [1,16], and a defining one in others, such as group signatures [19] and ring signatures [52]. A plethora of more complex protocols, from broadcast encryption [41] to cryptocurrencies [38], have been enhanced by user anonymity.

An example of such protocols are rating systems, also referred to as reputation systems, in which users can be rated by providing feedback on goods or services, with the support of a reputation server. Each user has a reputation value based on these ratings, which can be used to evaluate their trustworthiness. In this context, the value of anonymity lies in the fact that users are able to give honest feedback without fear of repercussions. This may occur when there is a lack of trust for the reputation server, or when users are concerned about retaliation.

Anonymity has received a great amount of attention in this area and abundant existing literature covers a range of anonymous rating systems in both the centralised and distributed settings. Distributed systems, e.g., [44], have no reputation server and use local reputation values, i.e., reputation values created by users on other users. For example, a user may generate a reputation value based on feedback from querying other users. This means a user does not have a unique reputation value, but many other users hold their own reputation value for them. In this setting, privacy preserving decentralised reputation systems [49] are designed to maintain anonymity when answering queries from other users.

We focus on centralised systems, since the reputation systems used by most service providers such as Airbnb, Uber and Amazon are of this type. In the centralised setting, a central reputation server enrols users and forms reputation values on these users. In [9,10,20,21,26] anonymity of a rating is provided to all except the reputation server, and multiple ratings cannot be given on the same subject. In [57], multiple reputation servers are used so that anonymity of ratings holds, unless all reputation servers collude. Other works provide anonymity of ratings in the presence of a corrupted reputation server [29,31,50,53]. In [2,7] anonymity is achieved with a different approach. The reputation server still enrols users, but no longer forms reputations. Instead users collect tokens based on anonymous ratings from other users and prove their own reputation.

Whilst the benefits of anonymity are clear, it is also understood that this same property can provide an opportunity for malicious users to misbehave. They may “bad mouth” other users, for instance competitors, giving dishonest negative feedback to these users to decrease their reputation. Or they may collude and give each other positive feedback in order to inflate their own reputation. To avoid this, the system can provide either a mechanism to revoke the malicious user’s anonymity (typically achieved through a traceability property), or incentivize good behaviour by rewarding users. The rating systems proposed so far approach this issue via user tracing. Indeed, in schemes where the reputation server can de–anonymise ratings [10,20,21,26], inaccurate ratings can be punished.

We take a different approach by rewarding honest ratings in anonymous peer rating systems, where users are peers and anonymously rate each other. Examples include peer-to-peer file sharing [33], collaborative knowledge production [13,32,46], and shared knowledge of internet and software vulnerabilities [36,54]. In such systems the rewarding approach works well since raters are also participating within the system and so have an interest in rating accurately to increase their reputation through rewards. The use of incentives to encourage accurate feedback has already been discussed in [48,56], but ratings are not anonymous.

Privacy-preserving incentive schemes [8,11,35,39,45], where users can be incentivised anonymously without their transactions being linked, have also been proposed. In [45] it is described how such incentives could contribute towards a reputation value. However, these schemes do not capture the ability to reward accurate ratings. Firstly, ratings must be incentivised as they are submitted, at which point it is not known whether a rating is accurate. When accurate ratings are determined it is then difficult to return the incentive to the relevant user. Secondly, in [8,11,35,39], a user’s balance is updated each time a user receives an incentive. However, a user may have submitted k accurate rating on other users, which are unlinkable. Then their balance of n should increase by k, but instead they receive k updated tokens for a balance of $n + 1$ . Finally, in [8,11,35,45] a user would have to participate in an interactive protocol to rate others.

Therefore the challenge remains to rewards users that rate accurately, whilst preserving the anonymity of their ratings even with respect to the reputation server. This is what we address in this paper.

1.1. Our work

We consider an anonymous peer rating system in which, at each round of interaction, users rate each other by providing feedback to the reputation server.

Our contribution is to allow accurate ratings to be incentivised and weighted by reputation, whilst still ensuring anonymity of ratings. Achieving this is challenging for two reasons. First, the reputation used to weight feedback could be used to de-anonymise a user. We can partially mitigate this by ensuring reputation is coarse-grained as in [7] (by rounding the reputation value, for instance), which ensures that a user who has a unique reputation score does not reveal their identity. The trade off between precision of reputation and size of anonymity sets is further discussed in [51]. Second, and crucially, accurate ratings must be incentivised without being de-anonymised. We achieve this by incentivising a large set of ratings simultaneously, and rewarding the users responsible for such ratings. With this approach, however, the anonymity set can be reduced substantially. Indeed, a malicious reputation server could decide to only reward a small number of ratings it seeks to de-anonymise, and then check which users are rewarded with an increase in reputation. These users then must have authored these ratings.

A way to lessen the impact in both cases is to restrict access to reputation. A specific trusted entity, the Reputation Holder, holds the reputations of users, and the latter should only be revealed sparingly. We do not specify exactly when and how reputations should be revealed in order to allow for a flexible scheme, and because this has been discussed in the existing literature. For example, in [31,53], users can prove their reputation and so can decide which users to reveal it to. A simpler example is that a user would have to demonstrate a good reason to learn another’s reputation from the Reputation Holder.

We go further and introduce a new entity, the Rewarder, who chooses which ratings to reward, and who cannot see which users have their reputation increase. As the Reputation Holder no longer knows which ratings were rewarded, they cannot compare these ratings with the users that claim rewards and so reduce the anonymity set. We formalise this in the Anonymity of Ratings under a Corrupt Reputation Holder requirement. For completeness, we also consider the case that the Reputation Holder and the Rewarder collude or are the same entity. Clearly they learn that each user that was rewarded n times, authored n of the ratings rewarded, however they should learn no more than this. We formalise this in our Anonymity of Ratings under Full Corruption requirement.

Although we are aware that using reputation values and incentivising accurate ratings both inescapably reduce the anonymity sets of ratings, in this work we aim to provide the best anonymity achievable given the functionality. Furthermore, we also must ensure that users do not attempt to subvert the system by claiming rewards that they are not entitled to, by providing multiple ratings on the same user per round, by lying about their reputation, or by framing other users so that they seem to be cheating. We formalise this in our Fair Rewards, Traceability,2

²
Traceability here refers to the requirement that multiple ratings cannot be given on the same subject per round.

Unforgeability of Reputation and Non-Frameability requirements.

We first provide a model and security requirements for an anonymous peer rating system $APR$ , which formalises the necessary privacy and security properties discussed above. We use property-based definitions, which are intuitive and useful when proving security. We then give a construction that is provably secure given these security requirements. Our construction makes use of Direct Anonymous Attestation (DAA) [12], which we use to sign feedback. This ensures that, whilst signed feedback are unlinkable, multiple feedback on the same user can be detected, due to the user controlled linkability feature of DAA. We modify the DAA primitive so that when giving feedback a user can prove they have a particular reputation for that round, so that feedback can be weighted. We then make use of Linkable Ring Signatures [42] to allow to incentivise users who rate accurately. For every rating a freshly generated verification key is attached, encrypted under the Rewarder’s public key. When the Rewarder rewards a rating, they publish the corresponding decrypted verification keys. The user can then sign a linkable ring signature with the corresponding secret key and claim their incentive from the Reputation Holder. The linkability of the signature scheme can be used to detect if a user tries to claim for the same incentive twice, whilst its anonymity ensures that ratings remain anonymous.

Although DAA and Linkable Ring Signature schemes are similar primitives, we note that they have subtly different properties that make them exactly suited to their particular role in building an $APR$ scheme. As ring signature key pairs can be generated without involving any central entity, this allows a new verification key to be generated for every rating. The fact that a central entity, in our case the Reputation Holder, must authorise the creation of a new DAA key pair, prevents sybil attacks. Otherwise, users could easily create multiple identities and rate other users as many times as they wish per round. Unlike group signatures [19], DAA schemes do not allow a trusted opener to de–anonymise signatures, ensuring that anonymity of ratings holds with respect to the Rewarder.

In this work we provide an extended version of the paper published at SCN 2020 [30]. This includes security proofs for our construction, the full security model for the modified DAA primitive, and the modified DAA construction that provably satisfies this model.

While the main aim of our anonymous peer rating system is to ensure anonymous and honest feedback, it is also important to consider how it is affected by many other conventional attacks on rating systems. The unfair ratings attack [24] is mitigated by the detection of multiple ratings per subject per round. The incentives also encourage users to give more accurate feedback. The self–rating or self–promoting attack [37] is mitigated by encouraging all users to give feedback on their own performance. Sybil attacks [25], where a user creates multiple identities to join the system to give unfair feedback, can be mitigated by making joining the system expensive, and by a robust registration process. This also mitigates against whitewashing attacks [22], where a user leaves and rejoins to shed a bad reputation. The on-off attack [55], where a user behaves honestly to increase their reputation before behaving dishonestly, can be somewhat mitigated by adjusting the weighting of the final reputation formation in our system, so that bad behaviour will cause the reputation to deteriorate quickly. Reputation lag exploitation [40], where a user exploits the interval before the latest round of ratings takes effect, cannot be prevented but, as before, we can mitigate it by making the reputation deteriorate faster on bad behaviour.

2. Anonymous peer rating systems: Definitions and security models

In this section, we introduce and formally define an anonymous peer rating ( $APR$ ) system, and the security and privacy properties it should satisfy. We consider a set of users $U = {{uid}_{i}}$ interacting with each other in rounds. At the end of each round they rate each other’s performance, by anonymously sending a numerical feedback alongside their reputation to the Rewarder. The Rewarder collects ratings, discards multiple ratings on the same subject, and rewards accurate feedback by outputting a set of incentives. A user claims to the Reputation Holder that they were responsible for a number of these incentives. The final reputation held by the Reputation Holder on a user is based on three components: weighted feedback from other users, the number of incentives they have successfully claimed, and their previous reputation. We present an illustration of our model in Fig. 1 and formally capture this as follows.

Fig. 1.

Diagram illustrating our model.

Setup & Key Generation The Reputation Holder and Rewarder generate their own key pairs. The group public key $gpk = (param, rwpk, rhpk)$ consists of the public keys of both entities.

Setup (1^{τ}, f_{1}, f_{2}) \to param

input a security parameter $1^{τ}$ , and two generic functions $f_{1}$ and $f_{2}$ which calculate the reputations of users. The function $f_{1}$ is input the number of ratings a user is being rewarded for, and outputs the second component, $r^{″}$ , of their reputation for this round. The function $f_{2}$ is input the two components of a user’s reputation for this round, and their reputation from the previous round, and outputs their final reputation for this round.3

For example, in [56], $f_{1}$ is simply the number of incentives received multiplied by some weight, and $f_{2}$ is the weighted sum of these components.

Setup

outputs the public parameters

param

which include

f_{1}

f_{2}

RHKeyGen (param) \to (rhsk, rhpk)

performed by the Reputation Holder, outputs the Reputation Holder’s secret key $rhsk$ and public key $rhpk$ .

RWKeyGen (param) \to (rwsk, rwpk)

performed by the Rewarder, outputs the Rewarder’s secret key $rwsk$ and public key $rwpk$ .

Join When a user joins the system they engage in an interactive protocol with the Reputation Holder after which they are issued with secret keys used to provide anonymous ratings and to collect rewards for giving honest feedback. We assume users must join the system before a round of ratings begins.

⟨ Join (gpk), Issue (rhsk, gpk) ⟩

a user $uid$ joins the system by engaging in an interactive protocol with the Reputation Holder. The user $uid$ and Reputation Holder perform algorithms $Join$ and $Issue$ respectively. These are input a state and an incoming message $M_{in}$ , and output an updated state, an outgoing message $M_{out}$ , and a decision, either cont, accept, or reject, which denote whether the protocol is still ongoing, has ended in acceptance or has ended in rejection respectively. (States are values necessary for the next stage of the protocol.) The initial input to $Join$ is the group public key, $gpk$ , whereas the initial input to $Issue$ is the Reputation Holder’s secret key, $rhsk$ , and the group public key $gpk$ . If the user $uid$ accepts, $Join$ privately outputs the user’s secret key $gsk [uid]$ , and $Issue$ outputs $reg [uid]$ , which stores the user’s registration and will be used to later allocate that user a reputation.

Ratings at Roundl Each user $uid$ has a reputation $r [uid, l]$ at round l, also held by the Reputation Holder. We assume that reputation is coarse-grained, which lessens the impact on anonymity with respect to the Reputation Holder. At Round l, a user $uid$ with reputation r forms a rating ρ with $Rate$ on user ${uid}^{'}$ based on a numerical feedback $fb$ , which is sent to the Rewarder via a secure anonymous channel.4

⁴

We require a secure channel to prevent the Reputation Holder from accessing the ratings, and determining which ratings will be rewarded by following the strategy of the Rewarder. This knowledge would allow the Reputation Holder to decrease the anonymity set of the users claiming incentives, as in the case when both the Rewarder and Reputation Holder are corrupted.

For flexibility we do not specify the form of

fb

, in [56] this a real number between 0 and 1. The user stores a trapdoor

td

for each rating for later use when claiming incentives. The Rewarder can verify ratings with

Verify

After collecting the valid ratings weighted by reputation, the Rewarder calculates an intermediate value $r^{'} [uid, l]$ for each $uid$ with $FormRep1$ , through which it also detect multiple ratings on the same subject. This value captures the average feedback given on $uid$ weighted by the reputation of the rater, and is sent to the Reputation Holder via a secure authenticated channel.

Rate (gsk [uid], gpk, fb, {uid}^{'}, l, r, ω) \to (ρ, td)

performed by the user with identifier $uid$ , with input the user’s secret key $gsk [uid]$ , the group public key $gpk$ , a feedback $fb$ , the user who they are rating ${uid}^{'}$ , the current round l, their reputation r, and a reputation token ω output in the previous round by $AllocateRep$ . Outputs a rating ρ and a trapdoor $td$ .

Verify (fb, {uid}^{'}, l, r, ρ, gpk) \to {0, 1}

a public function that is performed by the Rewarder when receiving a rating tuple $(fb, {uid}^{'}, r, ρ)$ . Outputs 1 if ρ is valid on the feedback $fb$ for user ${uid}^{'}$ at round l for reputation r under the group public key $gpk$ , and 0 otherwise.

FormRep1 (uid, l, ({fb}_{1}, r_{1}, ρ_{1}), \dots, ({fb}_{k}, r_{k}, ρ_{k}), gpk) \to r^{'} [uid, l]

performed by the Rewarder with input k valid rating tuples ${({fb}_{i}, uid, r_{i}, ρ_{i}) : i \in [1, k]}$ on user $uid$ at round l, and the group public key $gpk$ . Outputs $r^{'} [uid, l] = \frac{\sum_{i = 1}^{k} r_{i} {fb}_{i}}{\sum_{i = 1}^{k} r_{i}}$ if all ratings originate from different users’ secret keys. Otherwise outputs ⊥ (in practice also outputs ratings that should be discarded).

Incentivising accurate feedback The Rewarder compares each feedback on ${uid}^{'}$ . If this is close to $r^{'} [{uid}^{'}, l]$ then this rating will be considered to be accurate and will be given an incentive. We define accurate as close to $r^{'}$ . However, our model could simply be adapted to incorporate different metrics of accuracy.

The Rewarder inputs the k accurate ratings in this round to $Incent$ , which outputs k incentives which are broadcast publicly to all users. $Incent$ must be deterministic, to allow users to identify which incentives match their ratings.

A user collects all its incentives and can then use $CollectIncent$ , along with the trapdoors stored earlier, to output an incentive claim σ for each of their incentives. They send these incentive claims to the Reputation Holder over a secure authenticated channel. Incentive claims are verified by the Reputation Holder with $VerifyIncent$ . After gathering all the valid incentive claims, the Reputation Holder calculates the second component $r^{″} [uid, l + 1]$ of a user’s reputation at round l with $FormRep2$ , which also checks that no user has claimed the same incentive twice. This value reflects how in line the feedback of $uid$ is with respect to other users’ feedback, incentivising users to give honest feedback.

Incent (({fb}_{1}, {uid}_{1}, r_{1}, ρ_{1}), \dots, ({fb}_{k}, {uid}_{k}, r_{k}, ρ_{k}), l, rwsk, gpk) \to t_{1}, \dots, t_{k}

a deterministic function performed by the Rewarder on input k rating tuples ${({fb}_{i}, {uid}_{i}, r_{i}, ρ_{i}) : i \in [1, k]}$ from round l and its secret key $rwsk$ . Outputs k incentives $t_{1}, \dots, t_{k}$ .

CollectIncent (uid, (fb, {uid}^{'}, l, r, ρ, td), t_{1}, \dots, t_{k}, gpk) \to σ

performed by the user $uid$ who gave the rating tuple $(fb, {uid}^{'}, r, ρ)$ for round l corresponding to trapdoor $td$ , with input the incentives output by the Rewarder $t_{1}, \dots, t_{k}$ . Outputs an incentive claim σ if the rating tuple $(fb, {uid}^{'}, r, ρ)$ corresponds to an incentive in list $t_{1}, \dots, t_{k}$ and ⊥ otherwise.

VerifyIncent (uid, σ, t_{1}, \dots, t_{k}, gpk) \to {0, 1}

performed by the Reputation Holder when receiving an incentive claim σ from user $uid$ on incentives $t_{1}, \dots, t_{k}$ . Outputs 1 if the incentive claim is valid on $uid$ , $t_{1}, \dots, t_{k}$ and 0 otherwise.

FormRep2 (uid, σ_{1}, \dots, σ_{k_{1}}, t_{1}, \dots, t_{k_{2}}, gpk) \to r^{″} [uid, l]

performed by the Reputation Holder with input a user $uid$ , $k_{1}$ valid incentive claims $σ_{1}, \dots, σ_{k_{1}}$ and $k_{2}$ incentives $t_{1}, \dots, t_{k_{2}}$ . Outputs $r^{″} [uid, l] = f_{1} (k_{1})$ if no incentive has been claimed twice, and otherwise ⊥.

Allocate reputation for next round For the first round, all users’ reputations are set to an initial value. The reputation of user $uid$ for round $l + 1$ , $r [uid, l + 1]$ , is set by the Reputation Holder as $f_{2} (r^{'} [uid, l], r^{″} [uid, l], r [uid, l])$ combining the user’s previous reputation and the two intermediate values $r^{'} [uid, l]$ , $r^{″} [uid, l]$ . This reputation value $r [uid, l + 1]$ , which we refer to as r, and a reputation token ω obtained from $AllocateRep$ are given to the user via a secure authenticated channel to allow them to prove they have this reputation in the next round.

AllocateRep (uid, r, l, rhsk, reg) \to ω

performed by the Reputation Holder with input a user $uid$ with reputation r during round l, the Reputation Holder’s secret key $rhsk$ and the registration table $reg$ . Outputs reputation token ω.

2.1. Security requirements

An $APR$ system must satisfy Correctness, as well as the following security requirements: Anonymity of Ratings under Full Corruption, which formalises the strongest anonymity that can be achieved when the Rewarder and Reputation Holder are corrupted; Anonymity of Ratings under a Corrupt Reputation Holder, which ensures that ratings cannot be de-anonymised or linked by the Reputation Holder;5

⁵
The case of a corrupt Rewarder is captured in the Anonymity of Ratings under Full Corruption requirement.

Traceability, which ensures that multiple ratings cannot be given on the same user per round; Non-Frameability, which ensures that users cannot be impersonated when giving ratings or claiming incentives; Unforgeability of Reputation, which ensures that a user cannot lie about their reputation, and Fair Rewards, which ensures that users can only successfully claim for the number of incentives they were awarded.

Fig. 2.

Oracles used in our security requirements.

We provide definitions in the computational model of cryptography. These are typically formulated as experiments in which an adversary, having access to a certain number of oracles, is challenged to produce an output. Such an output captures an instance of the system in which the security requirement does not hold. In Fig. 2, we provide the oracles used in our security requirements: $AddU$ , $SndToU$ , $SndToRH$ , $AllocateRep$ , $USK$ , $Rate$ , $TD$ , $Incent$ , $Collect$ , based on notation from [5]. We note that $cont$ , $accept$ and reject are as defined in the description of $⟨ Join, Issue ⟩$ . We give a high level description below:

$AddU$ (Add User): creates an honest user $uid$ .

$SndToU$ (Send to User): creates honest users when the adversary has corrupted the Reputation Holder. The adversary impersonates the RH, and engages in a $⟨ Join, Issue ⟩$ protocol with an honest user.

$SndToRH$ (Send to RH): creates corrupted users, when the adversary has not corrupted the Reputation Holder. The adversary impersonates a user and engages in a $⟨ Join, Issue ⟩$ protocol with an honest RH.

$AllocateRep$ : allows an adversary to obtain outputs of $AllocateRep$ .

$USK$ : allows an adversary to obtain the secret key of an honest user.

$Rate$ : allows an adversary to perform $Rate$ on behalf of an honest user.

$TD$ : allows an adversary to obtain a trapdoor associated to a rating that has been obtained through the $Rate$ oracle.

$Incent$ : allows an adversary to obtain outputs of $Incent$ .

$Collect$ : allows an adversary to obtain outputs of $CollectIncent$ for a rating that has been output by the $Rate$ oracle and then input to the $Incent$ oracle.

All oracles have access to the following records maintained as global state which are initially set to ∅:

List of $uid$ s of honest users. New honest users can be added by queries to the $AddU$ oracle (for an honest RH) or $SndToU$ oracle (for a corrupt RH).

List of corrupt users that have requested to join the group. New corrupt users can be added through the $SndToRH$ oracle if the RH is honest. If the RH is corrupt, we do not keep track of corrupt users.

List of all queries to the $AllocateRep$ oracle for corrupt users.

List of queries and outputs from the $Rate$ oracle.

TDL

List of queries to the $TD$ oracle.

List of queries, and outputs of the $Incent$ oracle.

CLL

List of queries, and outputs of the $Collect$ oracle.

2.1.1. Correctness

An $APR$ system is correct, if when $Rate$ is input an honestly generated secret key and a reputation token, it will output a valid rating. Provided all ratings input to $FormRep1$ originate from different users it will output the correct function. Also, if $Incent$ and $CollectIncent$ are performed honestly on k valid ratings, the resulting incentive claims will be valid. Provided each incentive is only claimed once, $FormRep2$ will output $f_{1} (k)$ . We give the full requirement in Appendix A.

2.1.2. Anonymity of ratings

We now give the requirements for both corruption settings that ensure ratings cannot be de-anonymised or linked by user, provided multiple ratings on the same user per round are not given. We also must ensure that ratings cannot be linked to the corresponding incentive claim. This is crucial to ensuring ratings are anonymous, as incentive claims are sent fully authenticated and so, if linkable to the corresponding rating, they could be used to de-anonymise such ratings.

Anonymity of Ratings under Full Corruption. We first formally define anonymity of ratings in the case both the Rewarder and the Reputation Holder have been corrupted. In this setting, the following attack can always be mounted: The adversary, having corrupted the Rewarder and Reputation Holder, wishes to de-anonymise a specific rating and so simply only rewards this rating. The author of the rating then claims their reward from the Reputation Holder, revealing their identity. Such an attack is unavoidable when incentivising accurate feedback.

However, we can still provide some guarantee of anonymity, namely that the adversary should learn no more than the following: a user that has been rewarded n times per round is responsible for n of the rewarded ratings for that round. When $n = 1$ the above attack still holds, but this dishonest behaviour of the Rewarder can be detected as only one incentive would be publicly broadcast. Our security requirement achieves this by allowing the challenge rating to be input to the $Collect$ oracle, on the condition that an additional rating authored by the other challenged user is added to the inputs. By including ratings originating from both challenged users, the incentives claimed by both of these users will increase by 1, and so the adversary cannot use this to trivially win. We note that this notion implies the anonymity requirement when just the Rewarder is corrupted, i.e., it is the strongest of the two requirements.

In the security game the Reputation Holder and Rewarder are corrupted, and so the adversary can create corrupted users. The adversary chooses two honest users, as well as a feedback, a user who is the subject of the feedback, and a reputation. The adversary must give reputation tokens for each user for this reputation. The adversary is returned with a challenge rating authored by one of these users, with this reputation, on this feedback and user (subject), and they must guess which user authored the rating. The challenge rating as well as another rating authored by the other challenged user is saved in $RL$ , for later use in the $Collect$ oracle. The adversary can create honest users with the $SndToU$ oracle and obtain their ratings with the $Rate$ oracle. However they cannot query to the $Rate$ oracle either of the users that were challenged as well as the challenge subject/round. Otherwise the $FormRep1$ algorithm could be used to trivially win, due to the detection of multiple ratings on the same user/round. We also must check that both ratings computed from the challenged users are valid, to ensure that both $ω_{0}$ or $ω_{1}$ output by the adversary were correctly formed. The adversary can also reveal the trapdoor from each $Rate$ oracle query with the $TD$ oracle, but not for the challenge ratings as this would lead to a trivial win by detecting double claims with $FormRep2$ . They also have access to an $Incent$ oracle. The adversary can query incentives from the $Incent$ oracle, that originate from the $Rate$ oracle, to the $Collect$ oracle. If they include the challenge rating, an additional rating from the other challenged user is added to the inputs. The adversary is returned with the incentive claims for these ratings along with the user who claims them. This captures the fact that claiming incentives should not violate the anonymity of ratings. We give the full game below:

An $APR$ system satisfies Anonymity of Ratings under Full Corruption if for all functions $f_{1}$ , $f_{2}$ , for all polynomial time adversaries $A$ , the following advantage is negligible in τ: $\begin{matrix} | Pr [{Exp}_{A, APR}^{anon-fullcorr} (τ, f_{1}, f_{2}) = 1] - 1 / 2 | . \end{matrix}$

Anonymity of Ratings under a Corrupt Reputation Holder. We next define anonymity in the setting where the Reputation Holder has been corrupted, but not the Rewarder. This means that the adversary now does not know which ratings have been rewarded. The challenge rating and a rating authored by the other challenged user are now stored in list ${RL}^{†}$ . The adversary has full access to the $Collect$ oracle, modelling the role of the Reputation Holder. However, if the challenge rating is input to the $Incent$ oracle, the rating authored by the other challenged user stored in ${RL}^{†}$ is also added to the inputs. The $Incent$ oracle shuffles the outputs. This represents that the Reputation Holder no longer knows which rating is linked to each incentive.

An $APR$ system satisfies Anonymity of Ratings under a Corrupt Reputation Holder if for all $f_{1}$ , $f_{2}$ , for all polynomial time adversaries $A$ , the following advantage is negligible in τ: $\begin{matrix} | Pr [{Exp}_{A, APR}^{anon-rh} (τ, f_{1}, f_{2}) = 1] - 1 / 2 | . \end{matrix}$

2.1.3. Fair rewards

This requirement ensures that an adversary cannot increase the number of incentives they were allocated, or steal incentives allocated to other users.

In the security game the Rewarder and the Reputation Holder are corrupted, so the adversary can create corrupted users. The adversary is given the $SndToU$ and $Rate$ oracles to create honest users, and obtain their ratings. They have access to the $Collect$ oracles to obtain incentive claims on incentives obtained from the $Rate$ oracle followed by the $Incent$ oracle. They have access to the trapdoor oracle, to obtain trapdoors associated to ratings output by $Rate$ . The adversary must choose $k_{1}$ incentives obtained from the $Incent$ oracle, and $k_{2}$ valid incentive claims, not output by the $Collect$ oracle, corresponding to a single user identifier. If $FormRep2$ doesn’t detect cheating, and more incentive claims are output than incentives corresponding to ratings not obtained through the $Rate$ oracle or queried to the trapdoor oracle, then the adversary wins. We give the full game below:

An $APR$ system satisfies Fair Rewards if for all functions $f_{1}$ , $f_{2}$ , for all polynomial time adversaries $A$ , the advantage $Pr [{Exp}_{A, APR}^{fair-rew} (τ, f_{1}, f_{2}) = 1]$ is negligible in τ.

2.1.4. Traceability

This requirement ensures that only registered users can give ratings, and multiple ratings on the same user during the same round can be detected.

In the security game the adversary has corrupted the RW, but not corrupted the RH as otherwise they would be able to arbitrarily create new user secret keys. The adversary has access to the $AddU$ oracle to create honest users, the $Rate$ oracle to obtain their ratings and the $TD$ oracle to obtain the associated trapdoors. They also can create corrupted users with the $SndToRH$ oracle. They can obtain reputation tokens with the $AllocateRep$ oracle. The adversary must output more valid ratings on the same user, for the same round, than the number of corrupt users, without using the $Rate$ oracle, such that $FormRep1$ will not detect multiple feedback. We give the full game below:

An $APR$ system satisfies Traceability if for all functions $f_{1}$ , $f_{2}$ , for all polynomial time adversaries $A$ , the advantage $Pr [{Exp}_{A, APR}^{trace} (τ, f_{1}, f_{2}) = 1]$ is negligible in τ.

2.1.5. Non-frameability

This requirement ensures that an adversary cannot impersonate an honest user. This requires firstly that an adversary should not be able to output a valid rating that links to the rating of an honest user under $FormRep1$ , causing this rating to be discarded. Secondly an adversary should not be able to produce a valid incentive claim, that links to the incentive claim of an honest user under $FormRep2$ , and so causes this claim to be discarded. For ease of notation, the two requirements are captured with two separate security games within the same experiment.

In the first security game both the RW and RH are corrupted. The adversary is given the $SndToU$ , $Rate$ , $TD$ oracles to create honest users, and obtain their ratings and trapdoors. They then must output a valid rating, not obtained through the $Rate$ oracle, that links to the rating of an honest user $uid$ under $FormRep1$ .

In the second security game the RW and RH are again corrupted. The adversary is given the $SndToU$ , $USK$ , $Rate$ , $Incent$ , $Collect$ oracles to create honest users, reveal their private keys, and obtain their ratings and trapdoors, as well as to obtain incentive claims from ratings from the $Rate$ oracle. They must output a valid incentive claim, not returned by the $Collect$ oracle, for an honest user $uid$ , such that it links to another honestly generated incentive claim, for the same user under $FormRep2$ . We give the full game below:

An $APR$ system satisfies Non-Frameability if for all functions $f_{1}$ , $f_{2}$ , for all polynomial time adversaries $A$ , the advantage $Pr [{Exp}_{A, APR}^{non-frame} (τ, f_{1}, f_{2}) = 1]$ is negligible in τ.

2.1.6. Unforgeability of reputation

This requirement ensures that users cannot lie about their reputation. They can only claim to have a particular reputation for a round if they were allocated this by the Reputation Holder in $AllocateRep$ .

In the security game the RW is corrupted but not the RH, because otherwise the adversary could perform $AllocateRep$ . The adversary is given the $SndToRH$ oracle to create corrupted users, and the $AddU$ , $Rate$ and $TD$ oracles to create honest users and obtain their ratings and trapdoors. The $AllocateRep$ oracle provides them with reputation tokens for honest and corrupted users. The adversary then must output more valid ratings for a particular reputation, round and user (subject), than the number of queries for different corrupted users to the $AllocateRep$ oracle for this reputation and round. These ratings must be unlinkable under $FormRep1$ . Therefore, essentially this requirement ensures that the adversary cannot use a reputation r more times than the number of corrupted users whose allocated reputation is r. We give the full game below:

An $APR$ system satisfies Unforgeability of Reputation if for all functions $f_{1}$ , $f_{2}$ , for all polynomial time adversaries $A$ , the advantage $\begin{array}{l} Pr [{Exp}_{A, APR}^{uf-rep} (τ, f_{1}, f_{2}) = 1] is neglible in τ . \end{array}$

3. Our construction

We propose a construction for an APR system which makes use of four building blocks: Linkable Ring Signatures ( $LRS$ ), a modified Direct Anonymous Attestation ( $DAA*$ ) scheme, a signature proof of knowledge, and a public–key encryption scheme.

Ring signatures [52] allow users to sign on behalf of a ring of users, without revealing their identity within the ring. There is no central entity involved, and users generate their own signing and verification keys. Linkable ring signatures [42] allow for the public linking of signatures by signer. We exploit these features to allow for incentivising accurate ratings as follows. Each rating includes a freshly generated verification key encrypted under the public key of the Rewarder, and the user who has generated the rating stores the corresponding signing key as a trapdoor. The Rewarder publishes these decrypted verification keys as incentives. Then to claim an incentive the user uses the signing key to sign a ring signature on their user identifier with respect to the ring of verification keys given as incentives. The anonymity of Linkable Ring Signatures ensures that claiming incentives will not de-anonymise ratings. The unforgeability property ensures that only users that have been rewarded can claim an incentive, and the linking function ensures that only one reward can be claimed per rating.

Direct Anonymous Attestation (DAA) [12] allows users to sign on behalf of a group, whilst remaining anonymous within the group. The user-controlled linkability feature, where two signatures on the same basename by the same user are linked, whilst all other signatures are unlinkable, can be used to detect multiple feedback on the same subject. In our setting, the basename can be set to be the user who is the subject of the feedback and the round. In our system we also wish to ensure feedback is weighted by reputation. However, this must also be balanced with anonymity of feedback. For this to be possible the reputation of users must be coarse-grained enough that they cannot be identified by their reputation. To ensure this, we bind reputation into a Direct Anonymous Attestation scheme, which we will call a $DAA*$ scheme. Now a user proves their reputation when signing, allowing for the weighting of feedback.

3.1. Public-key encryption schemes

Our scheme makes use of a public–key encryption scheme, which consists of the following: $EncSetup (1^{τ})$ , which is input the security parameter $1^{τ}$ and outputs parameters ${param}_{Enc}$ ; $EncKeyGen ({param}_{Enc})$ , which is input the parameters and outputs secret key $sk$ and the public key $pk$ ; $Enc (pk, m)$ , which is input the public key $pk$ and a message m from the message space, and outputs a ciphertext c; and $Dec (sk, c)$ , which is input the secret key $sk$ and a ciphertext c, and outputs a message m or a decryption failure ⊥. We require the encryption scheme to be correct and satisfy indistinguishability under adaptive chosen ciphertext attacks.

3.2. Proof protocols

We follow the notation defined in [15] when referring to zero-knowledge proofs of knowledge. For example, $PK {(a, b, c) : y = g^{a} h^{b} \land \tilde{y} = {\tilde{g}}^{a} {\tilde{h}}^{c}}$ denotes a zero knowledge proof of knowledge of integers a, b and c such that $y = g^{a} h^{b}$ and $\tilde{y} = {\tilde{g}}^{a} {\tilde{h}}^{c}$ hold. $SPK$ denotes a signature proof of knowledge, that is a non-interactive transformation of a proof $PK$ , e.g., using the Fiat–Shamir heuristic [27] in the random oracle model. Using the Fiat–Shamir heuristic, the witness can be extracted from these proofs by rewinding the prover and programming the random oracle. Alternatively, these proofs can be extended to be online-extractable, by verifiably encrypting the witness to a public key defined in the common reference string. Clearly this requires a trusted common reference string. We underline the values that we need to be online-extractable in our proofs.

We require the proof system to be simulation-sound and zero-knowledge. The latter roughly says that there must exist a simulator that can generate simulated proofs which are indistinguishable from real proofs from the view of the adversary. The simulation-soundness is a strengthened version of normal soundness and guarantees that an adversary, even after having seen simulated proofs of false statements of his choice, cannot produce a valid proof of a false statement.

3.3. Linkable ring signatures

We use the model in [3] for one-time linkable ring signatures, which gives the strongest security yet. The scheme from [3] has the shortest signatures to date. We give the security requirements: Correctness Linkability, Linkable Anonymity, Non-Frameability and Unforgeability in Appendix B.

Definition 1 (Linkable ring signatures).

A linkable ring signature scheme $LRS$ is given by polynomial time algorithms $(LRKeyGen, LRSign, LRVerify, LRLink)$ :

$LRKeyGen (1^{τ})$ : takes as input the security parameter $1^{τ}$ and outputs a pair $(v k, s k)$ of verification and signing keys.

$LRSign (sk, m, R)$ : takes as input a signing key $sk$ , a message m, and a list of verification keys $R = ({vk}_{1}, \dots, {vk}_{q})$ , and outputs a signature Σ.

$LRVerify (R, m, Σ)$ : takes as input a ring $R = ({vk}_{1}, \dots, {vk}_{q})$ , a message m, and a signature Σ, and outputs either 0 or 1.

$LRLink (Σ_{1}, Σ_{2}, m_{1}, m_{2})$ : is input two signatures/ messages, outputs 0 or 1.

3.4. $DAA*$ signatures

The security model of $DAA*$ closely follows that of pre–DAA signatures [6]. We first give the syntax of a $DAA*$ scheme and then provide the security requirements.

Definition 2 (DAA*).

A $DAA*$ scheme consists of the following algorithms:

DAA*Setup $(1^{τ})$ : input the security parameter τ, outputs parameters $param$ .

DAA*KeyGen $(param)$ : input the parameters $param$ , outputs the group public key $gpk$ , and the issuing secret key $isk$ .

$⟨ DAA*Join (gpk), DAA*Issue (isk, gpk) ⟩$ : a user $uid$ joins the group by engaging in an interactive protocol with the Issuer. The user $uid$ and Issuer perform algorithms $DAA*Join$ and $DAA*Issue$ respectively. These are input a state and an incoming message respectively, and output an updated state, an outgoing message, and a decision, either cont, accept, or reject. The initial input to $DAA*Join$ is the group public key, whereas the initial input to $DAA*Issue$ is the issuer secret key, $isk$ , and the group public key. If the issuer accepts, $DAA*Join$ has a private output of $gsk [uid]$ , $DAA*Issue$ has a private output of $reg [uid]$ .

DAA*Update $(r, t, isk, uid, reg, gpk)$ : input a reputation r, a time t, the issuing secret key $isk$ , a user $uid$ , the registration list $reg$ , $gpk$ . Outputs a token ω.

DAA*Sign $(bsn, m, gsk [uid], ω, gpk, r, t)$ : input a basename $bsn$ , a message m, a user secret key $gsk [uid]$ , a token ω output by DAA*Update, a group public key $gpk$ , a reputation r and time t. It checks that ω is valid for user $uid$ , reputation r and time t and outputs a signature Ω. Otherwise it outputs ⊥.

DAA*Verify $(bsn, m, r, t, Ω, gpk)$ : input a basename $bsn$ , a message m, a reputation r, time t, a signature Ω, and a group public key $gpk$ . It outputs 1 if Ω is valid, and 0 otherwise.

DAA*Link $(({bsn}_{0}, m_{0}, r_{0}, t_{0}, Ω_{0}), ({bsn}_{1}, m_{1}, r_{1}, t_{1}, Ω_{1}), gpk)$ : input two signatures $Ω_{0}$ , $Ω_{1}$ each on a basename, a message, a reputation, a time, and a group public key $gpk$ . It outputs 1 if both signatures are valid, ${bsn}_{0} = {bsn}_{1}$ and the two signatures have the same author, and 0 otherwise.

${DAA*Identify}_{T} (T, gsk)$ : outputs 1 if $T$ corresponds to a valid transcript of $⟨ DAA*Join, DAA*Issue ⟩$ , with output $gsk$ to $DAA*Join$ , and otherwise 0.

${DAA*Identify}_{S} (bsn, m, r, t, Ω, gsk)$ : outputs 1 if the signature Ω could have been produced with user secret key $gsk$ , and 0 otherwise.

The security requirements for a $DAA*$ scheme are Correctness, Anonymity, Traceability, Non-Frameability, similarly to in [6], and the additional Unforgeability of Reputation requirement similarly to in [31], which ensures that a user cannot lie about their reputation.

In Fig. 3, we provide the oracles used in our security requirements: $AddU$ , $SndToU$ , $SndToI$ , $USK$ , $GSig$ , $Update$ . We give a high level description below:

$AddU$ : creates an honest user $uid$

$SndToU$ : creates honest users when the adversary has corrupted the issuer. The adversary impersonates an issuer, and engages in a $⟨ DAA*Join, DAA*Issue ⟩$ protocol with an honest user.

$SndToI$ : creates corrupted users when the adversary has not corrupted the issuer. The adversary impersonates a user and engages in a $⟨ DAA*Join, DAA*Issue ⟩$ protocol with the honest issuer.

$USK$ : allows an adversary to obtain the secret key of an honest user.

$GSig$ : allows an adversary to perform $DAA*Sign$ on behalf of an honest user.

$Update$ : allows an adversary to obtain outputs of $DAA*Update$ .

Fig. 3.

Oracles used in our $DAA*$ security requirements.

Fig. 4.

Experiments capturing the correctness, anonymity and traceability security requirements for $DAA*$ .

Correctness. In Fig. 4, ${Exp}_{A, DAA*}^{corr} (τ)$ gives the Correctness requirement. This ensures that given a user is honestly joined to the scheme, and $DAA*Update$ and $DAA*Sign$ are performed correctly, with the user private key resulting from the user’s join protocol, then the signature output will verify correctly. It also ensures that signatures generated honestly using the same user private key and basename will be linked under $DAA*Link$ , and that ${DAA*Identify}_{S}$ and ${DAA*Identify}_{T}$ correctly identify signatures to the user private key and the transcript respectively. This requirement only differs from [6], because the correctness of $DAA*Update$ needs to be included.

A $DAA*$ scheme satisfies correctness, if for all polynomial time adversaries $A$ , the advantage $Pr [{Exp}_{A, DAA*}^{corr} (τ) = 1]$ is negligible in τ.

Anonymity. In Fig. 4, ${Exp}_{A, DAA*}^{anon} (τ)$ gives the anonymity requirement. This ensures that a user’s signatures cannot be de-anonymised, and signatures with different basenames but the same signer cannot be linked. In the security game the adversary has corrupted the issuer. They choose two honest users and a message, basename, reputation and time, as well as providing valid update tokens for both users for the reputation and time given. They are returned with a challenge signature and they must guess which of the two users was the author. They can create honest users using the $SndToU$ oracle, obtain their signatures with the $GSig$ oracle and corrupt them with the $USK$ oracle. However they cannot corrupt either of the challenged honest users, or query one of these users and the challenge basename to $GSig$ , as otherwise the $DAA*Link$ algorithm could be used to trivially win.

This requirement differs from [6] because of the tokens provided by the adversary for both users. As the adversary has corrupted the issuer, we allow them to provide the update tokens for both users that are input to $DAA*Sign$ . However, to avoid trivial wins, they fail if either would output ⊥ under $DAA*Sign$ and so are invalid.

A $DAA*$ scheme satisfies anonymity, if for all polynomial time adversaries $A$ , the advantage $| Pr [{Exp}_{A, DAA*}^{anon} (τ) = 1] - 1 / 2 |$ is negiglible in τ.

Traceability. In Fig. 4, ${Exp}_{A, DAA*}^{trace} (τ)$ gives the traceability requirement. This requirement ensures firstly that all signatures identify under ${DAA*Identify}_{S}$ to a secret key obtained through a $⟨ DAA*Join, DAA*Issue ⟩$ protocol, and secondly that signatures that identify to the same secret key under ${DAA*Identify}_{S}$ and have the same basename are always linked under $DAA*Link$ .

In the first security game the adversary has not corrupted the issuer as otherwise they could simply create their own unregistered users. They are given the $SndToI$ oracle to create corrupt users, and the $Update$ oracle, so they can obtain tokens. They then must output a secret key corresponding to every accepted $SndToI$ query under ${DAA*Identify}_{T}$ , and a valid signature that does not identify to any of these secret keys under ${DAA*Identify}_{S}$ .

In the second security game the adversary has corrupted the issuer. They must output a basename, user secret key, and two valid signatures on this basename. They win if the two signatures are not linked under $DAA*Link$ but do identify to the same secret key.

The only difference in this requirement from [6] is the additional $Update$ oracle provided to the adversary.

A $DAA*$ scheme satisfies traceability if, for all polynomial time adversaries $A$ , the advantage $Pr [{Exp}_{A, DAA*}^{trace} (τ) = 1]$ is negligible in τ.

Fig. 5.

Experiments capturing our non-frameability and unforgeability of reputation security requirements for $DAA*$ signature schemes.

Non-frameability. In Fig. 5, ${Exp}_{A, DAA*}^{non-frame} (τ)$ gives the non-frameability requirement. This requirement ensures that an adversary cannot impersonate an honest user, by forging signatures linking to theirs. This requires firstly that an adversary should not be able to output a valid signature that identifies to the secret key of an honest user under ${DAA*Identify}_{S}$ , and secondly that they should not be able to output two valid linked signatures, that either have different basenames or identify under ${DAA*Identify}_{S}$ to different secret keys.

In the first security game the adversary has corrupted the issuer. They are given the $SndToU$ , $USK$ , $GSig$ oracles to create honest users, reveal their private keys, and obtain signatures from these honest users. They then must output a valid signature, not obtained through $GSig$ , that identifies under ${DAA*Identify}_{S}$ to the secret key of an honest user, that wasn’t revealed under the $USK$ oracle.

In the second security game the adversary has again corrupted the issuer. They must output two valid linked signatures and a user secret key. They win if either the basenames of the two signatures are different or only one of the signatures identifies under ${DAA*Identify}_{S}$ to the secret key.

A $DAA*$ scheme satisfies non-frameability if, for all polynomial time adversaries $A$ , the advantage $Pr [{Exp}_{A, DAA*}^{non-frame} (τ) = 1]$ is negligible in τ.

Unforgeability of reputation. In Fig. 5, ${Exp}_{A, DAA*}^{unforge-rep} (τ)$ gives the unforgeability of reputation requirement. This requirement is new to the $DAA*$ model because of the binding of reputation to signatures. It ensures that users cannot lie about their reputation, and can only claim to have a particular reputation at a particular time if they were allocated this by the issuer in $DAA*Update$ .

In the security game the adversary has not corrupted the issuer, because otherwise they could perform $DAA*Update$ . They are given access to the $SndToI$ oracle to create corrupted users, and the $Update$ oracle. They then must output a secret key corresponding to every accepted $SndToI$ query under ${DAA*Identify}_{T}$ ; a valid signature for reputation r, time t, that only identifies to one of these secret keys ${gsk}^{*}$ under ${DAA*Identify}_{S}$ ; and an honest user ${uid}^{*}$ that identifies to ${gsk}^{*}$ under ${DAA*Identify}_{T}$ , without using the $Update$ oracle for $({uid}^{*}, r, t)$ .

A $DAA*$ scheme satisfies unforgeability of reputation if, for all polynomial time adversaries $A$ , the advantage $Pr [{Exp}_{A, DAA*}^{unforge-rep} (τ) = 1]$ is negligible in τ.

3.5. Our construction

We now present our construction that securely realizes an $APR$ system, using a PKE scheme, an $SPK$ , an $LRS$ scheme and a $DAA*$ scheme. We give our construction in Fig. 6, except for the joining protocol which we describe as follows: The $APR$ joining protocol is $⟨ DAA*Join (gpk), DAA*Issue (rhsk, rhpk) ⟩$ , with the following modification. The last message sent by the user should additionally include $π = SPK {(\overline{gsk}) : {DAA*Identify}_{T} (T, gsk) = 1}$ , where $T$ is the transcript of the protocol so far. The issuer must verify this proof before proceeding as usual.

Fig. 6.

All algorithms in our $APR$ construction.

4. Security of our construction

We show that our construction satisfies the security requirements for an $APR$ system defined in Section 2.

Theorem 1.
The construction presented in Fig. 6 is a secure $APR$ , as defined in Section 2 , if the $LRS$ scheme, $DAA$ scheme and PKE scheme used are secure, and the* $SPK$ is online extractable, simulation sound, and zero-knowledge.

The correctness of $DAA$ ensures that honestly generated ratings will verify correctly and $FormRep1$ will output the correct function. The correctness of the encryption scheme and $LRS$ scheme ensure that, if $Incent$ and $CollectIncent$ are performed honestly on k valid ratings, the resulting incentive claims will be valid, and that $FormRep2$ will output the correct function. Therefore, our $APR$ construction satisfies correctness.

We now give detailed proofs of Lemmata 1–6, which ensure our construction satisfies: Anonymity of Ratings under Full Corruption, Anonymity of Ratings under a Corrupt Reputation Holder, Traceability, Non-Frameability, Unforgeability of Reputation, and Fair Rewards.
Lemma 1.
The construction satisfies Anonymity of Ratings under Full–Corruption if the* $LRS$ and $DAA$ schemes satisfy Anonymity, and the* $SPK$ is zero-knowledge.
Proof.
Assuming the $LRS$ scheme satisfies Linkable Anonymity, the $DAA$ scheme used also satisfies Anonymity and the $SPK$ is zero knowledge, then the APR construction satisfies the Anonymity of Ratings under Full Corruption requirement.

We define Game 0 to be the Anonymity of Ratings under Full Corruption experiment, with b chosen randomly at the beginning, using the APR construction. Let $S_{0}$ be the event that an adversary $A$ correctly guesses b after Game 0.

We define Game 1 to be identical to Game 0 except for in the $Collect$ oracle, with probability $1 / 2$ the user identifiers of the challenge rating and the additional rating will be swapped. We give Game 1 in Fig. 7. Let $S_{1}$ be the event that the adversary $A$ correctly guesses b after Game 1.

Fig. 7.
Game 1.

We show that Game 0 and Game 1 are indistinguishable assuming the linkable anonymity of the $LRS$ scheme used in our construction. We give a distinguishing algorithm $D$ for functions $f_{1}$ , $f_{2}$ in Fig. 8, and below explain why $D$ simulates inputs to $A$ that are distributed identically to in Game 0 if in the linkable anonymity experiment the bit $b = 0$ was chosen, and $D$ simulates inputs to $A$ that are distributed identically to in Game 1 if in the Linkable anonymity experiment the bit b was chosen randomly.

Fig. 8.
$D$ a distinguishing algorithm that breaks the anonymity of linkable ring signatures.

Clearly all inputs to $A$ other than the $Collect$ oracle and $ρ_{0}^{}$ , $ρ_{1}^{}$ are identical in both Game 0 and 1. $ρ_{0}^{}$ and $ρ_{1}^{}$ are distributed identically in both Game 0 and Game 1 because $\tilde{{vk}_{0}^{}}$ , $\tilde{{vk}_{1}^{}}$ are encrypted honestly generated verification keys for ring signatures, and $Ω_{0}^{}$ , $Ω_{1}^{}$ are computed identically. $RL$ is defined identically to in Game 0, except that as the trapdoor is unknown, instead this is set to $(⊥, b^{'})$ . If the challenge signature is queried to the $Collect$ oracle, then these trapdoors cannot be used in $CollectIncent$ . Therefore instead the challenge oracle is used from the linkable anonymity game for ring signatures. If $b = 0$ was chosen in the linkable anonymity game, then this will return a correctly distributed incentive claim as in Game 0. If b is chosen randomly in the linkable anonymity game, then the incentive will be generated from the correct user’s key, with the same probability as in Game 1.

Therefore the probability that $D$ outputs 1 given $b = 0$ in the Linkable Anonymity game is $Pr [S_{0}]$ . The probability that $D$ outputs 1 given the bit was chosen randomly in the Linkable Anonymity game is $Pr [S_{1}]$ . Let $s^{}$ be the probability $D$ outputs 1 given $b = 1$ in the Linkable Anonymity game. Then $Pr [S_{1}] = 1 / 2 s^{} + 1 / 2 Pr [S_{0}]$ , and so $s^{} = 2 Pr [S_{1}] - Pr [S_{0}]$ . Therefore, the advantage of $D$ is then $| 2 Pr [S_{1}] - Pr [S_{0}] - Pr [S_{0}] | = 2 | Pr [S_{0}] - Pr [S_{1}] |$ . Therefore $| Pr [S_{0}] - Pr [S_{1}] | = ϵ / 2$ , where ϵ is the advantage of an adversary in the Linkable Anonymity security game. Therefore, provided the linkable ring signature scheme satisfies Linkable Anonymity, Games 0 and Games 1 will be indistinguishable.

Next, we show that $| Pr [S_{1}] - 1 / 2 | ⩽ ϵ_{DAA, anon}$ , where $ϵ_{DAA, anon}$ is the advantage in breaking anonymity for the $DAA$ scheme. We build an adversary $A^{'}$ , that breaks Anonymity for the $DAA$ scheme, given $A$ for functions $f_{1}$ , $f_{2}$ that successfully guesses b in Game 1 with $Pr [S_{1}]$ . We give $A^{'}$ in Fig. 9, and below explain why the simulation input to $A$ given in Fig. 9 is identically distributed to Game 1, and why $A^{'}$ successfully breaks Anonymity for the $DAA$ scheme.

Fig. 9.
$A^{'}$ breaks anonymity of the $DAA$ scheme using $A$ .

We first show inputs to $A$ are identically distributed to in Game 1. $(gpk, rwsk, rhsk)$ is identical to in Game 1, because $(rhpk, rhsk)$ and $({gpk}_{DAA}, isk)$ are identically distributed.

The $SndToU$ oracles in both the Anonymity of $DAA$ security requirement and the Anonymity of Ratings requirement are identical, and the $⟨ Join, Issue ⟩$ protocol are identical for the $DAA$ scheme and the APR construction, except for the $SPK$ that can be simulated due to the zero knowledge property. Therefore the $SndToU$ oracle is distributed identically to in Game 1. The $Rate$ oracle is also distributed identically in Game 1, because $(vk, td)$ are computed identically, and $GSig$ will output $DAA$ signatures as in $Rate$ .

The $TD$ and $Incent$ oracles are identical to in Game 1. We note that $RL$ is input to $Collect$ . For $ρ^{}$ , the entry in $RL$ is identical to in Game 1. For the other signature, $\tilde{{vk}^{'}}$ and ${td}^{'}$ are generated identically to $Rate$ , the only difference is the $DAA$ signature is set to be ⊥. However this is not used in $Incent$ or $CollectIncent$ . Therefore, the $Collect$ oracle is distributed identically.

$ρ^{}$ is distributed identically in Game 1, because $({vk}^{}, {td}^{})$ are chosen identically, and $A^{'}$ is returned with a $DAA$ signature for either ${uid}_{0}$ or ${uid}_{1}$ .

If $A$ wins with probability greater than $1 / 2$ , they output $ω_{1}$ , $ω_{1}$ so that $Ω_{0}^{}$ , $Ω_{1}^{} \neq ⊥$ . Therefore as $A^{'}$ also outputs $ω_{1}$ , $ω_{1}$ then they will not fail because of this. $A^{'}$ never queries the $USK$ oracle. If $A$ wins with probability greater than $1 / 2$ , they never query $({uid}_{0}^{}, {uid}^{'}^{}, l^{}, \cdot, \cdot, \cdot)$ or $({uid}_{1}^{}, {uid}^{'}^{}, l^{}, \cdot, \cdot, \cdot)$ to the $Rate$ oracle, and therefore $A^{'}$ never queries $(({uid}^{'}^{}, l^{}), \cdot, {uid}_{1}^{}, \cdot, \cdot, \cdot)$ or $(({uid}^{'}^{}, l^{}), \cdot, {uid}_{0}^{}, \cdot, \cdot, \cdot)$ to the $GSig$ oracle. $A^{'}$ successfully guesses b, if $A$ has successfully guessed b. Therefore $Pr [S_{1}] - 1 / 2 | ⩽ ϵ_{DAA, anon}$ , and so our construction satisfies Anonymity of Ratings under Full Corruption. □
Lemma 2.
The construction satisfies Anonymity of Ratings under a Corrupt Reputation Holder if the* $DAA$ scheme satisfies Anonymity and the PKE scheme satisfies indistinguishability under adaptive chosen ciphertext attacks, and the* $SPK$ is zero-knowledge.
Proof.
Assuming the encryption scheme used is indistinguishable under adaptive chosen ciphertext attacks, the $DAA$ scheme used also satisfies Anonymity, and the $SPK$ is zero knowledge then the APR construction satisfies the Anonymity of Ratings under a Corrupt Reputation Holder requirement.

We define Game 0 to be the Anonymity of Ratings under a Corrupt Reputation Holder experiment, with b chosen randomly at the beginning, using the APR construction. Let $S_{0}$ be the event that an adversary $A$ correctly guesses b after Game 0.

We define Game 1 to be identical to Game 0 except for in the $Collect$ oracle, with probability $1 / 2$ the user identifiers of the challenge rating and the additional rating will be swapped. We give Game 1 in Fig. 10. Let $S_{1}$ be the event that the adversary $A$ correctly guesses b after Game 1.

Fig. 10.
Game 1.

We show that Game 0 and Game 1 are indistinguishable for all functions $f_{1}$ , $f_{2}$ , assuming the ind–cca2 security of the encryption scheme used in our construction. We give a distinguishing algorithm $D$ in Fig. 11, and below explain why $D$ simulates inputs to $A$ that are distributed identically in Game 0 if in the ind-cca2 experiment the bit $b = 0$ was chosen, and $D$ simulates inputs to $A$ that are distributed identically in Game 1 if in the ind–cca2 experiment the bit b was chosen randomly.

Fig. 11.
$D$ a distinguishing algorithm that breaks the ind–cca2 security of the encryption scheme.

Clearly all inputs to $A$ other than the $Incent$ , $Collect$ oracles and $ρ_{b}^{}$ are identical in both Game 0 and 1, because $rwpk$ is a public key of the encryption scheme. $ρ_{b}^{}$ is distributed identically in both Game 0 and Game 1 because $\tilde{{vk}_{b}^{}}$ is an encrypted honestly generated verification key for ring signatures, and $Ω_{b}^{}$ is computed identically. Only the challenge rating is included in ${RL}^{†}$ and as the trapdoor is unknown, instead this is set to ⊥. However, these missing entries will not be used later. If the challenge signature is queried to the $Incent$ oracle, then the decryption oracle cannot be used in the ind–cca2 game. Therefore, instead incentives corresponding to both of the ring signature verification keys ${vk}_{0}^{}$ , ${vk}_{1}^{}$ will be output corresponding to the challenge signature and the added extra signature of the other challenged user. All other incentives are generated using the decryption oracle. If either of the incentives ${vk}_{0}^{}$ , ${vk}_{1}^{}$ are queried to the $Collect$ oracle, then the corresponding trapdoors can be used in $CollectIncent$ . The user ${uid}_{b}^{}$ claims the incentive ${vk}_{0}^{}$ and the user ${uid}_{1 - b}^{}$ claims the incentive ${vk}_{1}^{}$ . If the bit chosen in the ind–cca2 game was 0, then this is identically distributed to in Game 0, because the challenge signature contains an encryption of ${vk}_{0}^{}$ . If b is chosen randomly in the ind–cca2 game, then the user claiming the incentive will be correct with the same probability as in Game 1.

Therefore, the probability that $D$ outputs 1 given the bit is 0 in the ind-cca2 game is $Pr [S_{0}]$ . The probability that $D$ outputs 1 given the bit was chosen randomly in the ind–cca2 game is $Pr [S_{1}]$ . Let $s^{}$ be the probability $D$ outputs 1 given the bit was 1 in the ind–cca2 game. Then $Pr [S_{1}] = 1 / 2 s^{} + 1 / 2 Pr [S_{0}]$ , and so $s^{} = 2 Pr [S_{1}] - Pr [S_{0}]$ . Therefore, the advantage of $D$ is then $| 2 Pr [S_{1}] - Pr [S_{0}] - Pr [S_{0}] | = 2 | Pr [S_{0}] - Pr [S_{1}] |$ . Therefore $| Pr [S_{0}] - Pr [S_{1}] | = ϵ / 2$ , where ϵ is the advantage of an adversary in the ind–cca2 security game. Therefore, provided the encryption scheme is ind–cca2 secure, Games 0 and Games 1 will be indistinguishable.

Next, we show that $| Pr [S_{1}] - 1 / 2 | ⩽ ϵ_{DAA, anon}$ , where $ϵ_{DAA, anon}$ is the advantage in breaking anonymity for the $DAA$ scheme used. We build an adversary $A^{'}$ , that breaks Anonymity for the $DAA$ scheme used, given $A$ for functions $f_{1}$ , $f_{2}$ , that successfully guesses b in Game 1 with $Pr [S_{1}]$ . We give $A^{'}$ in Fig. 12, and below explain why the simulation input to $A$ given in Fig. 12 is identically distributed to Game 1, and why $A^{'}$ successfully breaks Anonymity for the $DAA$ scheme.

Fig. 12.
$A^{'}$ breaks anonymity of the $DAA$ scheme using $A$ .

$(gpk, rwsk, rhsk)$ are distributed identically to in Game 1, because $(rhpk, rhsk)$ and $({gpk}_{DAA}, isk)$ are identically distributed.

The $SndToU$ oracles in both the Anonymity of $DAA$ security requirement and the Anonymity of Ratings requirement are identical, and the $⟨ Join, Issue ⟩$ protocol is identical for the $DAA$ scheme and the APR construction, except for the $SPK$ that can be simulated due to the zero knowledge property. Therefore the $SndToU$ oracle is distributed identically in Game 1. The $Rate$ oracle is also distributed identically in Game 1, because $(vk, td)$ are computed identically, and $GSig$ will output $DAA$ signatures as in $Rate$ . The $TD$ is oracles are identical to in Game 1.

The $Incent$ oracle is distributed identically as only $\tilde{{vk}^{'}}$ will be necessary for $Incent$ , the first part of the rating is not used. The $Collect$ oracle is distributed identically to Game 1, because with probability 1/2, the challenge users will be swapped in ${RL}^{†}$ . This is identical to in Game 1.

$ρ^{}$ is distributed identically in Game 1, because $({vk}^{}, {td}^{}, {\tilde{vk}}^{})$ are chosen identically, and $A^{'}$ is returned with a $DAA$ signature for either ${uid}_{0}$ or ${uid}_{1}$ .

If $A$ wins with probability greater than $1 / 2$ , they output $ω_{1}$ , $ω_{1}$ so that $Ω_{0}^{}$ , $Ω_{1}^{} \neq ⊥$ . Therefore, as $A^{'}$ also outputs $ω_{1}$ , $ω_{1}$ then they will not fail because of this. $A^{'}$ never queries the $USK$ oracle. If $A$ wins with probability greater than $1 / 2$ , they never query $({uid}_{0}^{}, {uid}^{'}^{}, l^{}, \cdot, \cdot, \cdot)$ or $({uid}_{1}^{}, {uid}^{'}^{}, l^{}, \cdot, \cdot, \cdot)$ to the $Rate$ oracle, and therefore $A^{'}$ never queries $(({uid}^{'}^{}, l^{}), \cdot, {uid}_{1}^{}, \cdot, \cdot, \cdot)$ or $(({uid}^{'}^{}, l^{}), \cdot, {uid}_{0}^{}, \cdot, \cdot, \cdot)$ to the $GSig$ oracle. $A^{'}$ successfully guesses b, if $A$ has successfully guessed b. Therefore $Pr [S_{1}] - 1 / 2 | ⩽ ϵ_{DAA, anon}$ , and so our construction satisfies Anonymity of Ratings under a Corrupt Reputation Holder. □
Lemma 3.
The construction satisfies Traceability if the* $DAA$ scheme satisfies both Traceability and Non-Frameability, and the* $SPK$ is online extractable and simulation sound.
Proof.
Assuming that the $DAA$ scheme used satisfies the Traceability and Non Frameability requirements, and the $SPK$ is online extractable and simulation sound, then the APR construction satisfies traceability.

First we show that if there exists an adversary $A$ such that $Pr [{Exp}_{A, APR}^{trace} (τ, f_{1}, f_{2}) = 1] = ϵ$ , where ϵ is non-negligible, then we can build either an adversary $A_{1}^{'}$ that breaks the Non-Frameability of $DAA$ signatures or an adversary $A_{2}^{'}$ that breaks the Traceability of $DAA$ signatures, with non-negligible probability. We give the detailed descriptions of $A_{1}^{'}$ , $A_{2}^{'}$ in Figs 13 and 14, and explain here how they work.

We first describe two potential strategies that $A$ could take, firstly they could output at least one rating whose DAA signature component identifies under ${DAAIdentify}_{S}$ to the secret key of an honest user resulting from a query to $AddU$ . Or all ratings output could not identify to the secret key of an honest user under ${DAAIdentify}_{S}$ . In the first case we will build an adversary $A_{1}^{'}$ , which we will give in Fig. 13, that breaks the Non-Frameability requirement of $DAA$ signatures. In the second case we will build an adversary $A_{2}^{'}$ , which we will give in Fig. 14, that breaks the Traceability requirement of $DAA$ signatures

We now explain why the simulation $A_{1}^{'}$ gives to $A$ is identically distributed to in the Traceability experiment with the APR construction, and explain how $A_{1}^{'}$ breaks Non-Frameability for $DAA$ signatures, provided $A$ successfully breaks Traceability following the first strategy.

Fig. 13.
$A_{1}^{'}$ which breaks the non-frameability of $DAA$ signatures, using $A$ which breaks the traceability requirement of the APR construction following the first strategy with probability ϵ.

All inputs that $A_{1}^{'}$ provides to $A$ are distributed identically in the Traceability experiment. This is because $({param}_{DAA}, {gpk}_{DAA}, isk)$ are the outputs of $DAASetup$ , $DAAKeyGen$ and so $(param, gpk, rwsk, rhsk)$ are distributed identically. The ${SndToU}_{DAA}$ oracle can be used to simulate the role of the honest user for $AddU$ . The $SndToRH$ and $AllocateRep$ oracles are identical to in the original security game. The $Rate$ oracle is also distributed identically to in the security game, because $(vk, \tilde{vk}, td)$ are computed identically, and $GSig$ will output $DAA$ signatures as in $Rate$ . The $TD$ oracle is identical.

Therefore if $A$ successful breaks Traceability, and outputs a signature that identifies with an honest user generated through $AddU$ , then $A_{1}^{'}$ will be successful with probability $1 / k | HL |$ . This is because $A_{1}^{'}$ outputs a valid signature that was not obtained through $GSig$ (because otherwise $A$ would have obtained this through the $Rate$ oracle), and an honest user that has not been queried to the $USK$ oracle. There is a $1 / k$ chance that $A_{1}^{'}$ has chosen the signature that identifies to the honest user, and a $1 / | HL |$ probability that $A_{1}^{'}$ has chosen the correct honest user.

We now switch to the case of an adversary that breaks the Traceability of an APR construction by submitting signatures that do not identify to an honest user obtained by $AddU$ . We explain why the simulation $A_{2}^{'}$ gives to $A$ is identically distributed to in the Traceability experiment with the APR construction, and explain how $A_{2}^{'}$ breaks Traceability for $DAA$ signatures provided $A$ successfully breaks Traceability following the second strategy.

Fig. 14.
$A_{2}^{'}$ which breaks the traceability of $DAA$ signatures, using $A$ which breaks the traceability requirement of the APR construction following the second strategy with probability ϵ.

All inputs that $A_{2}^{'}$ provides to $A$ are distributed identically in the Traceability experiment. This is because $({param}_{DAA}, {gpk}_{DAA})$ are the outputs of $DAASetup$ , $DAAKeyGen$ and so $(param, gpk, rwsk)$ are distributed identically.

Simulating the* $AddU$ oracle. The $AddU$ oracle is identical except instead of performing $Issue$ , instead $SndToRH$ is used.

Simulating the $SndToRH$ oracle. In the case of $SndToRH$ , $gsk [uid]$ can be extracted from the online-extractable $SPK$ . As the ${SndToI}_{DAA}$ oracle is identical to $SndToRH$ and the join/ issue protocols of $DAA$ / APR are identical, $SndToRH$ is distributed identically in the Traceability requirement.

Simulating the $AllocateRep$ oracle. As $DAAUpdate$ and $AllocateRep$ are the same, and the $AllocateRep$ and $Update$ oracles are the same, $AllocateRep$ is distributed identically in the Traceability requirement.

Simulating the* $Rate$ and $TD$ oracles. The $Rate$ and $TD$ oracles are identical to in the Traceability game, because $A_{2}^{'}$ can use the secret keys of honest users.

Reduction to breaking traceability of $DAA$ signatures.* Assume $A$ is successful, and follows the second strategy. Then it outputs $k > | CL |$ valid signatures that are not output by the $Rate$ oracle, do not identify to any of the secret keys of honest users, and are unlinkable under $FormRep1$ . Then if all signature identify to a corrupted user in $CL$ (such that the join protocol accepted), then two signatures must identify to the same user as $k > | CL |$ . This would allow $A_{2}^{'}$ to break the second game in the Traceability requirement for $DAA$ signatures. Therefore, at least one signature must not identify to any corrupted users (such that the join protocol accepted) under ${DAAIdentify}_{S}$ . Therefore $A_{2}^{'}$ will be successful, because it outputs secret keys corresponding to all completed $SndToI$ transcripts, and a valid signature that does not identify to any of these secret keys (because it also will not identify to any honest users as we assume $A$ follows the second strategy).

Therefore, if $A$ is successful with probability ϵ and follows the second strategy, $A^{'}$ breaks traceability of $DAA$ signatures. □
Lemma 4.
The construction satisfies Non-Frameability if the* $LRS$ and $DAA$ schemes both satisfy Non-Frameability, and the* $SPK$ is zero-knowledge.
Proof.
Assuming the $DAA$ scheme satisfies the Non-Frameability requirement, the Ring Signature scheme also satisfies Non-Frameability, and the $SPK$ is zero knowledge, then the APR construction satisfies Non-Frameability.

First we show that if there exists an adversary $A$ for the first game of the Non-Frameability requirement such that $Pr [{Exp}_{A, APR}^{non-frame} (τ, f_{1}, f_{2}) = 1] = ϵ$ , where ϵ is non-negligible, then we can build an adversary $A^{'}$ , that breaks the Non-Frameability of $DAA$ signatures with non-negligible probability. We give the detailed description of $A^{'}$ in Fig. 15, and explain here how $A^{'}$ works.

We explain why the simulation $A^{'}$ gives to $A$ is identically distributed to in the first game of the Non-Frameability experiment with the APR construction, and explain how $A^{'}$ breaks Non-Frameability for $DAA$ signatures provided $A$ successfully breaks Non-Frameability.

Fig. 15.
$A^{'}$ which breaks the non-frameability of $DAA$ signatures, using $A$ which breaks the non-frameability requirement of the APR construction with probability ϵ.

Simulating the input to $A$ . All inputs that $A^{'}$ provides to $A$ are distributed identically in the Non-Frameability experiment. This is because $({param}_{DAA}, {gpk}_{DAA}, isk)$ are the outputs of $DAASetup$ , $DAAKeyGen$ and so $(param, gpk, rwsk, rhsk)$ are distributed identically. The $SndToU$ oracles in both the Non-Frameability of $DAA$ security requirement and the APR Non-Frameability requirement are identical, and the $⟨ Join, Issue ⟩$ protocol is identical for the $DAA$ scheme and the APR construction, except for the $SPK$ that can be simulated due to the zero knowledge property. Therefore the $SndToU$ oracle is distributed identically. The $Rate$ oracle is also distributed identically, because $(vk, \tilde{vk}, td)$ are computed identically, and $GSig$ will output $DAA$ signatures. The $TD$ oracle is identical to in the Non-Frameability requirement because the trapdoor $td$ is computed identically in the $Rate$ oracle.

Reduction to breaking non-frameability of* $DAA$ signatures.* Assume $A$ is successful, for $A^{'}$ to be successful it must satisfy four requirements: the $DAA$ signature output must be valid, the user output must be in $HL$ but not corrupted with $USK$ , the signature must not be output by the signing oracle, and the signature must identify to the secret key of the honest user output. As $A$ is successful and does not have access to a $USK$ oracle, the first three are clearly satisfied. As $A$ is successful, the signature links to another signature returned by the signing oracle authored by $uid$ and with the same basename $({uid}^{'}, l)$ . This signature is honestly generated and so will identify to the user $uid$ under ${DAAIdentify}_{S}$ . If the signature output by $A^{'}$ does not identify to $uid$ under ${DAAIdentify}_{S}$ , then this would break the second game of the $DAA$ Non-Frameability requirement. Otherwise $A^{'}$ will be successful.

Fig. 16.
$A^{'}$ which breaks the non-frameability of linkable ring signatures, using $A$ which breaks the non-frameability requirement of the APR construction with probability ϵ.

Next, we show that if there exists an adversary $A$ for the second game of the Non-Frameability requirement such that $Pr [{Exp}_{A, APR}^{non-frame} (τ, f_{1}, f_{2}) = 1] = ϵ$ , where ϵ is non-negligible, then we can build an adversary $A^{'}$ , that breaks the Non-Frameability of Linkable Ring signatures with non-negligible probability. We give the detailed description of $A^{'}$ in Fig. 16, and explain here how $A^{'}$ works.

We explain why the simulation $A^{'}$ gives to $A$ is identically distributed to in the second game of the Non-Frameability experiment with the APR construction, and explain how $A^{'}$ breaks Non-Frameability for Linkable Ring signatures provided $A$ successfully breaks Non-Frameability.

All inputs that $A^{'}$ provides to $A$ are distributed identically in the Non-Frameability experiment. This is because the only difference to the Non-Frameability game is during the $Rate$ oracle, ring signature verification keys are generated using the ${AddU}_{RS}$ oracle, which outputs verification keys identical to those generated in $LRKeyGen$ . However, the $Collect$ oracle no longer has access to the trapdoor for these ratings, therefore the ${Sign}_{RS}$ oracle is used to generate the incentive claim.

Reduction to breaking non-frameability of linkable ring signatures. If $A$ is successful with probability ϵ, $A^{'}$ breaks Non-Frameability of Linkable Ring Signatures with probability at least ϵ, provided $A^{'}$ does not abort. In the second stage, as $A$ is successful then a signature will be found in $CLL$ , and so $A^{'}$ will output a second signature. Clearly both signatures $A^{'}$ outputs are clearly valid and link, as $A$ is successful. As $A$ is successful, they will not return an incentive claim that has been obtained from the $Collect$ oracle, therefore the first signature output was not returned from the ${Sign}_{RS}$ oracle. As the $Corrupt$ oracle is not used the ring output will not contain any corrupted verification keys. The second ring output only contains verification keys generated from ${AddU}_{RS}$ , because the $Collect$ oracle only accepts incentives originating from ratings generated with the $Rate$ oracle. Therefore all the conditions are satisfied and so $A^{'}$ is successful. □
Lemma 5.
The construction satisfies Unforgeability of Reputation if the $DAA$ scheme satisfies Unforgeability of Reputation and Traceability, and the* $SPK$ is online extractable and simulation sound.
Proof.
Assuming that the $DAA$ scheme used satisfies the Unforgeability of Reputation requirement, and the $SPK$ is online extractable and simulation sound, then the APR construction satisfies Unforgeability of Reputation.

First we show that if there exists an adversary $A$ such that $Pr [{Exp}_{A, APR}^{uf-rep} (τ, f_{1}, f_{2}) = 1] = ϵ$ , where ϵ is non-negligible, then we can build an adversary $A^{'}$ , that breaks the Unforgeability of Reputation of $DAA$ signatures with non-negligible probability. We give the detailed description of $A^{'}$ in Fig. 17, and explain here how $A^{'}$ works.

We explain why the simulation $A^{'}$ gives to $A$ is identically distributed to the Unforgeability of Reputation experiment with the APR construction, and explain how $A^{'}$ breaks Unforgeability of Reputation for $DAA$ signatures provided $A$ successfully breaks Unforgeability of Reputation.

Fig. 17.
$A^{'}$ which breaks the unforgeability of reputation of $DAA$ signatures, using $A$ which breaks the unforgeability of reputation requirement of the APR construction with probability ϵ.

All inputs that $A^{'}$ provides to $A$ are distributed identically in the Unforgeability of Reputation experiment. This is because $({param}_{DAA}, {gpk}_{DAA})$ are the outputs of $DAASetup$ , $DAAKeyGen$ and so $(param, gpk, rwsk)$ are distributed identically.

Simulating the $AddU$ oracle. The $AddU$ oracle is identical except instead of performing $Issue$ , ${SndToI}_{DAA}$ is used. Therefore the $AddU$ oracle is distributed identically.

Simulating the* $SndToRH$ oracle. We now show that answers to $SndToRH$ queries are correctly distributed. As the ${SndToI}_{DAA}$ oracle is identical to the $SndToRH$ oracle and the issue protocols of $DAA$ / APR are identical, $SndToRH$ is distributed identically in the Unforgeability of Reputation requirement. $gsk [uid]$ can be extracted whenever the protocol completes due to the online-extractable $SPK$ .

Simulating the $AllocateRep$ oracle. As $DAAUpdate$ and $AllocateRep$ are the same, $AllocateRep$ is distributed identically in the Unforgeability of Reputation requirement.

Simulating the* $Rate$ and $TD$ oracles. The $Rate$ and $TD$ oracles are identical to in the Unforgeability of Reputation game, because $A^{'}$ can use the secret keys of honest users.

Reduction to breaking unforgeability of reputation of $DAA$ signatures.* Assume $A$ is successful, we show that $A^{'}$ is also successful. If a signature is output by $A$ that does not identify to any honest or corrupt user (whose join protocol completed), then $A^{'}$ can break Traceability defined in the first game. Therefore, if the number of different users that the signatures output by $A$ identify to under ${DAAIdentify}_{S}$ is strictly less than k, then there must be at least two signatures which identify to the same user. This would break Traceability of $DAA$ signatures, defined in the second game. Therefore there must be at least k users that signatures identify to. As $A$ is successful, there has been less than k queries to the $Update$ oracle for $(l, r)$ for different users. Therefore at least one user musn’t have been queried to the $Update$ oracle for $(l, r)$ . So $A^{'}$ will definitely find a user and signature to output.

In order for $A^{'}$ to be successful the signature, user and list of secret keys must satisfy the following four conditions. The signature must be valid, which is clearly true as $A$ was successful. For every completed $SndToI$ transcript, a secret key must be output that identifies to this transcript under ${DAAIdentify}_{T}$ , which is clearly true as all honest and corrupted user secret keys have been output by $A^{'}$ . The signature output must identify to the secret key that identifies with the user’s transcript, which is clearly true, as the signature identifies to the user’s secret key. Finally the $Update$ oracle should also have not been queried for $(uid, l, r)$ , which was the condition for the user to have been returned.

Therefore, if $A$ is successful with probability ϵ, $A^{'}$ breaks Unforgeability of Reputation of $DAA$ signatures with probability at least ϵ. □
Lemma 6.
The construction satisfies Fair Rewards if the $LRS$ scheme satisfies Linkability and Non-Frameability.
Proof.
Assuming that the Linkable Ring Signature scheme used satisfies the Linkability and Non-Frameability requirements, then the APR construction satisfies Fair Rewards.

First we show that if there exists an adversary $A$ such that $Pr [{Exp}_{A, APR}^{fair-rew} (τ, f_{1}, f_{2}) = 1] = ϵ$ making $n_{1}$ queries to the $Rate$ , where ϵ is non-negligible, then we can build either an adversary $A_{1}^{'}$ , that breaks the Non-Frameability of Linkable Ring Signatures signatures or an adversary $A_{2}^{'}$ that breaks the Linkability of Linkable Ring signatures, with non-negligible probability. We give the detailed description of $A_{1}^{'}$ , $A_{2}^{'}$ in Figs 18 and 19, and explain here how $A_{1}^{'}$ , $A_{2}^{'}$ work.

We first describe two potential strategies that $A$ could take.

Let $VK$ be the incentives output by $A$ which correspond to ratings obtained from the $Rate$ that have not been trapdoored, if for some rating $({uid}^{}, {uid}^{'}^{}, {fb}^{}, r^{}, ρ^{}, {td}^{}, l) \in SL$ corresponding to incentive $t \in VK$ , we have that $σ = CollectIncent (0, ({fb}^{}, {uid}^{'}^{}, l, r^{}, ρ^{}, {td}^{}), t, gpk)$ links to $σ^{}$ also output by the adversary, we say that $A$ adopts the first strategy. Otherwise we say $A$ adopts the second strategy. In the first case we will build an adversary $A_{1}^{'}$ , which we will give in Fig. 18, that breaks the Non-Frameability requirement of Linkable Ring signatures. In the second case we will build an adversary $A_{2}^{'}$ , which we will give in Fig. 19, that breaks the Linkability requirement of Linkable Ring Signatures.

We now explain why the simulation $A_{1}^{'}$ gives to $A$ is identically distributed to in the Fair Rewards experiment with the APR construction, and explain how $A_{1}^{'}$ breaks Non-Frameability for Linkable Ring Signatures signatures provided $A$ successfully breaks Fair Rewards following the first strategy.

Fig. 18.
$A_{1}^{'}$ which breaks the non-frameability of linkable ring signatures, using $A$ which breaks the fair rewards requirement of the APR construction following the first strategy with probability ϵ.

All inputs that $A_{1}^{'}$ provides to $A$ are distributed identically in the Fair Rewards experiment. This is because the only difference to in the Fair Rewards game is during the $Rate$ oracle when one ring signature verification key is generated using the ${AddU}_{RS}$ oracle. This is identically distributed to generating this with $LRKeyGen$ . However, the $Collect$ oracle no longer has access to the trapdoor, therefore the ${Sign}_{RS}$ oracle is used to generate the incentive claims. If this rating is queried to the trapdoor oracle, $A_{1}^{'}$ aborts.

If $A$ successfully breaks Fair Rewards and follows the first strategy, then $A_{1}^{'}$ will be successful, provided they do not abort early. This is because both signatures $A_{1}^{'}$ outputs are clearly valid and link, as $A$ is successful. As $A$ is successful, they will not return an incentive claim that originated from the $Collect$ oracle, therefore the first signature output was not returned from the ${Sign}_{RS}$ oracle. As the $Corrupt$ oracle is not used, the first ring output will not contain any corrupted verification keys. The second ring output only contains a verification key generated from ${AddU}_{RS}$ .

$A_{i}^{'}$ aborts early in three cases. Firstly, the rating $ρ^{}$ is input to the trapdoor oracle. Say the number of ratings submitted to the trapdoor oracle is $n_{2}$ , then the probability of this not occurring and so $A_{1}^{'}$ not aborting here is $(n_{1} - n_{2}) / n_{1}$ . Secondly, the incentive associated to $ρ^{}$ is not output by $A$ , say $A$ outputs $n_{3}$ incentives associated to ratings from the $Rate$ oracle that have not been trapdoored. Then the probability of this not occurring and so $A_{1}^{'}$ not aborting here is $n_{3} / (n_{1} - n_{2})$ . Finally, no incentive claim is found that links to $σ^{}$ . We know that for all the incentives output by $A$ that are associated to ratings from the $Rate$ that were not trapdoored, at least one will produce a signature that will link to some $σ_{j}$ . Therefore, the probability that $A_{1}^{'}$ does not abort here is at least $1 / n_{3}$ . We note that as the first strategy is followed: $n_{1}, n_{1} - n_{2}, n_{3} \neq 0$ .

Putting this all together the probability $A_{1}^{'}$ does not abort is $1 / n_{1}$ . Therefore, if $A$ is successful with probability ϵ and follows the first strategy, $A_{1}^{'}$ breaks the Non-Frameability of Linkable Ring signatures with probability at least $ϵ / n_{1}$ .

We now address the case of an adversary that breaks the Fair Rewards of an APR construction by following the second strategy given above. We explain why the simulation $A_{2}^{'}$ gives to $A$ is identically distributed to in the Fair Rewards experiment with the APR construction, and explain how $A_{2}^{'}$ breaks Linkability for Ring Signatures provided $A$ successfully breaks Fair Rewards following the second strategy above.

Fig. 19.
$A_{2}^{'}$ which breaks the linkability of linkable ring signatures, using $A$ which breaks the fair rewards requirement of the APR construction following the second strategy with probability ϵ.

All inputs that $A_{2}^{'}$ provides to $A$ are distributed identically in the Fair Rewards experiment, because they are computed identically.

Reduction to breaking linkability of linkable ring signatures.* Assume $A$ is successful, and follows the second strategy. Then $A_{2}^{'}$ will be successful. This is because clearly all ring signatures output are valid, as $A$ is successful. All rings output are also clearly a subset of the verification keys output. As $A$ is successful, the ring signatures in set ${((t_{1}, \dots, t_{k_{1}}), uid, σ_{i}) : i \in k_{2}}$ are clearly unlinkable to each other. In the second set all linkable ring signatures are signed using different secret keys, as they are all from different $Rate$ queries, therefore they are unlinkable to each other. As $A$ follows the second strategy clearly no signature from the first set links to the second set. Therefore all the signatures output are unlinkable. As $A$ is successful, more incentive claims are output by $A$ than the ratings they output that are not obtained from the $Rate$ oracle or were trapdoored. Therefore $k_{2} > k_{1} - | L |$ , and so $k_{2} + | L | > k_{1}$ . Therefore more signatures are output by $A_{2}^{'}$ than verification keys, and so $A^{'}$ is successful.

Therefore, if $A$ is successful with probability ϵ and follows the second strategy, $A_{2}^{'}$ breaks the Linkability of Linkable Ring signatures with probability at least ϵ. □
5. Concrete instantiation and efficiency

Concrete instantiation. The CDL* construction, which we give in Sections 5.1 and 5.2, satisfies the security requirements for a $DAA*$ scheme given in Section 3.4. We give formal proofs for this in Appendix C.

The CDL* construction is a modification of the DAA scheme from [14], which we will refer to as the CDL construction. This scheme is indistinguishable from the ideal functionality given in [14], and therefore satisfies the state of the art security definition for Direct Anonymous Attestation. We have modified this scheme so that the user is not split between a Trusted Platform Module and a host, as this is not necessary in this context. We have further modified the scheme, in CDL*, in an analogous way to [31]. This modification binds the reputation value to the signatures visibly, using an updated secret key received during CDL*Update. Therefore, when signing, users are forced to reveal their reputation.

The algorithm $CDL*Update$ provides the user with the tokens they need to prove they have a particular reputation. $CDL*Sign$ must now check the update tokens input are correct, and otherwise output ⊥. In CDL, β is a secret key of the issuer, $Y = G_{2}^{β}$ is a public key of the issuer. This modification in CDL* involves switching to $β + γ H_{2} (r, t)$ instead of β in both $CDL*Sign$ and $CDL*Verify$ , where $CDL*Verify$ can be performed by switching to $Y Z^{H_{2} (r, t)} = G_{2}^{β + γ H_{2} (r, t)}$ instead of $Y = G_{2}^{β}$ . The user is given a token in $CDL*Update$ that allows them to obtain a user private key for $Y Z^{H_{2} (r, t)}$ instead of Y.

The $⟨ DAA*Join, DAA*Issue ⟩$ protocol in CDL* already contains a suitable $SPK$ of the user secret key. A linkable ring signature scheme that securely realises the model in Section 3.3 is given in [3].

Efficiency. An incentive claim would have size $log (l) poly (τ)$ , where l is the number of incentives. This is the current state of the art for linkable ring signatures, and is reasonable, albeit large. Ratings are reasonably small, and consist of 7 τ-bit elements, and an encryption of 3 commitments.

5.1. CDL* construction

5.1.1. Preliminaries

Details on the proof protocols used in the CDL* construction are given in Section 3.2.

Bilinear Maps and the LRSW assumption Let $G_{1}$ , $G_{2}$ , $G_{T}$ be cyclic groups of prime order p. A map $e : G_{1} \times G_{2} \to G_{T}$ must satisfy the following conditions: bilinearity, i.e., $e (g_{1}^{x}, g_{2}^{y}) = e {(g_{1}, g_{2})}^{x y}$ ; non-degeneracy, i.e., for all generators $g_{1} \in G_{1}$ and $g_{2} \in G_{2}$ , $e (g_{1}, g_{2})$ generates $G_{T}$ ; and efficiency, i.e., there exists an efficient algorithm $G (1^{τ})$ that outputs a bilinear group $(p, G_{1}, G_{2}, G_{T}, e, g_{1}, g_{2})$ , and an efficient algorithm to compute $e (a, b)$ for all $a \in G_{1}$ , $b \in G_{2}$ .

We use type-3 pairings [28] in this work, i.e., we do not assume $G_{1} = G_{2}$ or the existence of an isomorphism between both groups in our scheme and security proofs. The advantage of type-3 pairings is that they enjoy the most efficient curves.

Definition 3 (LRSW assumption).

In $(G_{1}, G_{2})$ an adversary is given generators $G_{1}$ , $G_{2}$ of $G_{1}$ , $G_{2}$ respectively, $X = G_{2}^{α}$ , $Y = G_{2}^{β}$ for some $α, β \in Z_{p}^{*}$ and access to an oracle that when f is input, outputs $(A, A^{β}, A^{α}, A^{α} A^{f α β})$ where $A = G_{2}^{r}$ for uniform $r \in Z_{p}^{*}$ . It is hard for the adversary to output $(f, A, B, C)$ such that $A \in G_{1}$ , $B = A^{β}$ , $C = A^{α} A^{f α β}$ , and f has not been queried to the oracle.

5.1.2. CDL* construction

We give the $CDL*Setup$ , $CDL*KeyGen$ , $CDL*Update$ , $CDL*Sign$ , $CDL*Verify$ , $CDL*Link$ , ${CDL*Identify}_{T}$ , ${CDL*Identify}_{S}$ algorithms in Fig. 20, and the $⟨ CDL*Join, CDL*Issue ⟩$ protocol in Fig. 21.

Fig. 20.

The algorithms of CDL*.

Fig. 21.

The $⟨ CDL*Join, CDL*Issue ⟩$ protocol.

We prove that the CDL* construction securely realizes a $DAA*$ scheme in Appendix C, assuming the LRSW assumption [43], the DDH assumption and the random oracle model.

5.2. Concrete instantiation of CDL*

The non-interactive zero-knowledge proofs of knowledge in CDL* are as follows: $π_{F}$ and $π_{cre}$ used in the join protocol, π used in $CDL*Sign$ , and $π_{U}$ used in $CDL*Update$ . For $π_{F}$ , $π_{U}$ and $π_{cre}$ we need the witnesses to be online extractable. For this, we additionally encrypt the witness under a public key that needs to be added to $param$ (and to which in security proof we will know the secret key for), and extend the proof to prove that the additional encryption contains the same witness that is used in the rest of the proof. For the verifiable encryption of the witness we use Paillier encryption [18], that is secure under the DCR assumption [47].

For transforming interactive into non-interactive zero-knowledge proofs we rely on the Fiat–Shamir heuristic that ensures security in the random oracle model.

6. Conclusion and future work

We give a security model for an anonymous peer rating system $APR$ that allows accurate ratings to be incentivised, feedback to be weighted by reputation, and multiple feedback on the same subject to be detected, whilst still ensuring ratings remain anonymous. We use Linkable Ring Signatures and a modification of DAA to build a construction that is secure under these requirements. The DAA and Linkable Ring Signature primitives are not inherent in realising our $APR$ system. Different primitives could be used to build constructions that are more efficient or rely on different assumptions.

In a peer rating system, a high reputation score leads to a real payoff for users, corresponding to an increase in utility. When increasing one’s utility is the ultimate goal, game theory helps to gain new insights. A peer rating system formalised through game theory, which also follows the strategies of weighting feedback and incentivising accurate ratings, is proposed in [56] and experimentally simulated when used in collaborative intrusion detection systems in [23]. It is shown in [56] to what extent it pays off for users to rate accurately given the size of incentives and the size of the coalition(s) of dishonest users. However, anonymity of ratings is not taken into account and a fully trusted central authority receives the ratings and issues the incentives. As future work, we want to determine game theoretically whether our scheme incentivises accurate ratings.

Footnotes

Correctness of APR

We now give the full definition of correctness of an $APR$ system. We give the full games in Fig. 22. The first game ensures that given a user is honestly joined to the system, and $AllocateRep$ and $Rate$ are performed correctly, with the user private key resulting from the user’s join protocol, then the rating output will be valid. It also ensures that provided $FormRep1$ is input valid ratings all on the same subject but originating from different users, it will correctly output the average of these feedbacks weighted by reputation.

The second game ensures that if $Incent$ is performed correctly on a set of honestly generated ratings, and $CollectIncent$ is performed on one of these ratings, along with the trapdoor, and the incentives output by $Incent$ , it will output a valid incentive claim. If $FormRep2$ is input k valid incentive claims that all originate from different incentives it will output $f_{1} (k)$ .

An $APR$ system satisfies Correctness if for all functions $f_{1}$ , $f_{2}$ , for all polynomial time adversaries $A$ , the advantages $Pr [{Exp}_{A, APR}^{corr-1} (τ, f_{1}, f_{2}) = 1]$ and $Pr [{Exp}_{A, APR}^{corr-2} (τ, f_{1}, f_{2}) = 1]$ are negligible in τ.

Security requirements of linkable ring signatures

We now give the security requirements for Linkable Ring Signatures given in [3] which are Correctness, Linkability, Linkable Anonymity, Non-Frameability and Unforgeability. We give the first three explicitly as we make use of these to prove our $APR$ construction is secure.

Correctness We say that a linkable ring signature scheme $LRS = (LRKeyGen, LRSign, LRVerify, LRLink)$ is correct if it holds for all $τ \in Z_{p}^{*}$ , all $q = poly (τ)$ , all $i^{*} \in [q]$ , all messages $m, m^{'} \in {0, 1}^{*}$ that, if for all $i \in [q]$ , $(v k_{i}, s k_{i}) \leftarrow $ LRKeyGen (1^{τ})$ , for all $R, R^{'} \subseteq {v k_{1}, \dots, {vk}_{q}}$ , $Σ \leftarrow $ LRSign (s k_{i^{*}}, m, R)$ , $Σ^{'} \leftarrow $ LRSign (s k_{i^{*}}, m^{'}, R^{'})$ , then $Pr [LRVerify (R, m, Σ) = 1] = 1 - negl (τ)$ and $Pr [LRLink (Σ, Σ^{'}, m, m^{'}) = 1] = 1 - negl (τ)$ , where the probability is taken over the random coins used by $LRKeyGen$ and $LRSign$ .

Linkability This requirement ensures that signatures from the same secret key can be linked. In the game, the adversary must output k verification keys, and $k + 1$ valid signatures, each on a message and a ring. They win if all rings are subsets of the set of verification keys, and none of the signatures are linked. We give the full game in Fig. 23.

Linkable Anonymity Linkable Ring Signatures are publicly linkable, however a signature still should not be able to be traced to the signer’s verification key. The security requirement given below is a simplication of the one given in [3]. The requirement given here is clearly weaker than in [3], therefore the construction from [3] will satisfy this requirement. In the game, the adversary is given access to an $AddU$ oracle to create honest users and receive their verification keys. They return two honest users. They are then given access to an oracle, where they can submit a challenged user, a message and a ring that must contain the verification keys of both challenged users. If $b = 0$ , they are returned with a signature signed with the secret key of the user they input. If $b = 1$ they are returned with a signature signed by the other challenged user. They must guess b correctly to win. We give the full game in Fig. 24.

Non-Frameability This requirement ensures that an adversary cannot frame an honest user by forging a signature which links to this user’s signature. In the game we give the adversary the $AddU$ , $Sign$ and $Corrupt$ oracles, to create honest users, obtain their signatures and corrupt them. The adversary must output a valid signature that was not output by the $Sign$ oracle, on a ring that does not include any corrupted users. They then must output another valid signature that links to the first, on a ring that is a subset of users created by the $AddU$ oracle. We give the full game in Fig. 25.

Our game differs from that in [3] due to what we believe to be a typo. In their game the ring of the first instead of the second signature output should be a subset of all users created by the $AddU$ oracle. The non-frameability proof in [3] is based on the corrected security requirement given here, therefore the construction given satisfies this requirement. The uncorrected version does not capture an attack where an adversary forges a signature linking to another honest user, but includes their own verification key in the ring.

Proof of security of DAA* construction

We now give proofs of security that the CDL* scheme satisfies the security requirements for a $DAA*$ scheme, assuming the DDH problem is hard in $G_{1}$ , the Discrete Logarithm problem is hard in $G_{1}$ and $G_{2}$ , the bilinear LRSW assumption [43] is hard in $(G_{1}, G_{2})$ , the $SPK$ are zero knowledge, simulation sound and online extractable (for the underlined values) and the random oracle model.

The proofs of Anonymity, Traceability and Non-Frameability are similar to the simulation based proof of security of CDL [14]. We have adapted it to the game based security requirements given in Section 3.4. As the security requirements in [14] were designed to capture the all pre-existing daa security requirements it is clear that the CDL scheme satisfies the requirements given in [6]. We show that the modification to bind reputation to the scheme does not affect the security of the scheme. We also show that CDL* satisfies the new Unforgeability of Reputation requirement.

References

Abdalla,

Bellare,

Catalano,

Kiltz,

Kohno,

Lange,

Malone-Lee,

Neven,

Paillier and

Shi, Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions, in: CRYPTO 2005,

Shoup, ed., LNCS, Vol. 3621, Springer, Heidelberg, 2005, pp. 205–222. doi:10.1007/11535218_13.

Androulaki,

S.G.

Choi,

S.M.

Bellovin and

Malkin, Reputation systems for anonymous networks, in: International Symposium on Privacy Enhancing Technologies Symposium, Springer, 2008, pp. 202–218. doi:10.1007/978-3-540-70630-4_13.

Backes,

Döttling,

Hanzlik,

Kluczniak and

Schneider, Ring signatures: Logarithmic-size, no setup – from standard assumptions, in: EUROCRYPT 2019, Part III,

Ishai and

Rijmen, eds, LNCS, Vol. 11478, Springer, Heidelberg, 2019, pp. 281–311. doi:10.1007/978-3-030-17659-4_10.

Bellare,

Boldyreva,

Desai and

Pointcheval, Key-privacy in public-key encryption, in: ASIACRYPT 2001,

Boyd, ed., LNCS, Vol. 2248, Springer, Heidelberg, 2001, pp. 566–582. doi:10.1007/3-540-45682-1_33.

Bellare,

Shi and

Zhang, Foundations of group signatures: The case of dynamic groups, in: CT-RSA 2005,

Menezes, ed., LNCS, Vol. 3376, Springer, Heidelberg, 2005, pp. 136–153.

Bernhard,

Fuchsbauer,

E.M.

Ghadafi,

N.P.

Smart and

Warinschi, Anonymous attestation with user-controlled linkability, Int. J. Inf. Secur.12(3) (2013), 219–249. doi:10.1007/s10207-013-0191-z.

Bethencourt,

Shi and

Song, Signatures of reputation, in: FC 2010,

Sion, ed., LNCS, Vol. 6052, Springer, Heidelberg, 2010, pp. 400–407.

Blömer,

Bobolz,

Diemert and

Eidens, Updatable anonymous credentials and applications to incentive systems, in: ACM CCS 2019, ACM Press, 2019, pp. 1671–1685.

Blömer,

Eidens and

Juhnke, Practical, anonymous, and publicly linkable universally-composable reputation systems, in: CT-RSA 2018,

N.P.

Smart, ed., LNCS, Vol. 10808, Springer, Heidelberg, 2018, pp. 470–490.

10.

Blömer,

Juhnke and

Kolb, Anonymous and publicly linkable reputation systems, in: FC 2015,

Böhme and

Okamoto, eds, LNCS, Vol. 8975, Springer, Heidelberg, 2015, pp. 478–488.

11.

Bobolz,

Eidens,

Krenn,

Slamanig and

Striecks, Privacy-preserving incentive systems with highly efficient point-collection, in: Proceedings of the 2020 ACM Asia Conference on Computer and Communications Security, 2020.

12.

E.F.

Brickell,

Camenisch and

Chen, Direct anonymous attestation, in: ACM CCS 2004,

Atluri,

Pfitzmann and

McDaniel, eds, ACM Press, 2004, pp. 132–145.

13.

Brinckman,

Deelman,

Gupta,

Nabrzyski,

Park,

Ferreira da Silva,

I.J.

Taylor and

Vahi, Collaborative circuit designs using the CRAFT repository, Future Generation Computer Systems94 (2019), 841–853. doi:10.1016/j.future.2018.01.018.

14.

Camenisch,

Drijvers and

Lehmann, Universally composable direct anonymous attestation, in: PKC 2016, Part II,

C.M.

Cheng,

K.M.

Chung,

Persiano and

B.Y.

Yang, eds, LNCS, Vol. 9615, Springer, Heidelberg, 2016, pp. 234–264.

15.

Camenisch,

Kiayias and

Yung, On the portability of generalized Schnorr proofs, in: EUROCRYPT 2009,

Joux, ed., LNCS, Vol. 5479, Springer, Heidelberg, 2009, pp. 425–442. doi:10.1007/978-3-642-01001-9_25.

16.

Camenisch,

Kohlweiss,

Rial and

Sheedy, Blind and anonymous identity-based encryption and authorised private searches on public key encrypted data, in: PKC 2009,

Jarecki and

Tsudik, eds, LNCS, Vol. 5443, Springer, Heidelberg, 2009, pp. 196–214.

17.

Camenisch and

Lysyanskaya, Signature schemes and anonymous credentials from bilinear maps, in: CRYPTO 2004,

Franklin, ed., LNCS, Vol. 3152, Springer, Heidelberg, 2004, pp. 56–72. doi:10.1007/978-3-540-28628-8_4.

18.

Camenisch and

Shoup, Practical verifiable encryption and decryption of discrete logarithms, in: CRYPTO 2003,

Boneh, ed., LNCS, Vol. 2729, Springer, Heidelberg, 2003, pp. 126–144. doi:10.1007/978-3-540-45146-4_8.

19.

Chaum and

van Heyst, Group signatures, in: EUROCRYPT’91,

D.W.

Davies, ed., LNCS, Vol. 547, Springer, Heidelberg, 1991, pp. 257–265.

20.

Chen,

Li,

K.M.

Martin and

S.L.

Ng, A privacy-aware reputation-based announcement scheme for vanets, in: Wireless Vehicular Communications (WiVeC), 2013 IEEE 5th International Symposium on, IEEE, 2013, pp. 1–5.

21.

Chen,

Li,

K.M.

Martin and

S.L.

Ng, Private reputation retrieval in public – a privacy-aware announcement scheme for vanets, IET Information Security11(4) (2017), 204–210. doi:10.1049/iet-ifs.2014.0316.

22.

Chuang, Designing incentive mechanisms for peer-to-peer systems, in: 1st IEEE International Workshop on Grid Economics and Business Models, 2004. GECON 2004, IEEE, 2004, pp. 67–81.

23.

C.G.

Cordero,

Traverso,

Nojoumian,

S.M.

Habib,

Mühlhäuser,

J.A.

Buchmann and

Vasilomanolakis, Sphinx: A colluder-resistant trust mechanism for collaborative intrusion detection, IEEE Access6 (2018), 72427–72438. doi:10.1109/ACCESS.2018.2880297.

24.

Dellarocas, Immunizing online reputation reporting systems against unfair ratings and discriminatory behavior, in: Proceedings of the 2nd ACM Conference on Electronic Commerce, 2001.

25.

J.R.

Douceur, The sybil attack, in: Peer-to-Peer Systems,

Druschel,

Kaashoek and

Rowstron, eds, Springer Berlin Heidelberg, Berlin, Heidelberg, 2002, pp. 251–260. doi:10.1007/3-540-45748-8_24.

26.

El Kaafarani,

Katsumata and

Solomon, Anonymous reputation systems achieving full dynamicity from lattices, in: Proceedings of the 22nd International Conference on Financial Cryptography and Data Security (FC), 2018.

27.

Fiat and

Shamir, How to prove yourself: Practical solutions to identification and signature problems, in: CRYPTO’86,

A.M.

Odlyzko, ed., LNCS, Vol. 263, Springer, Heidelberg, 1987, pp. 186–194.

28.

S.D.

Galbraith,

K.G.

Paterson and

N.P.

Smart, Pairings for cryptographers, Discrete Applied Mathematics156(16) (2008), 3113–3121. doi:10.1016/j.dam.2007.12.010.

29.

Garms,

K.M.

Martin and

S.L.

Ng, Reputation schemes for pervasive social networks with anonymity, in: Proceedings of the Fifteenth International Conference on Privacy, Security and Trust (PST 2017), IEEE, 2017, pp. 1–6.

30.

Garms,

S.L.

Ng,

E.A.

Quaglia and

Traverso, Anonymity and rewards in peer rating systems, in: SCN 20, LNCS, Springer, Heidelberg, 2020, pp. 277–297.

31.

Garms and

E.A.

Quaglia, A new approach to modelling centralised reputation systems, in: AFRICACRYPT 19,

Buchmann,

Nitaj and

Rachidi, eds, LNCS, Vol. 11627, Springer, Heidelberg, 2019, pp. 429–447.

32.

Giannoulis,

Kondylakis and

Marakakis, Designing and implementing a collaborative health knowledge system, Expert Systems with Applications126 (2019), 277–294. doi:10.1016/j.eswa.2019.02.010.

33.

Gnutella. https://en.wikipedia.org/wiki/Gnutella, accessed 30 August, 2019.

34.

Goldwasser,

Micali and

R.L.

Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing17(2) (1988), 281–308. doi:10.1137/0217017.

35.

Hartung,

Hoffmann,

Nagel and

Rupp, BBA+: Improving the security and applicability of privacy-preserving point collection, in: ACM CCS 2017,

B.M.

Thuraisingham,

Evans,

Malkin and

Xu, eds, ACM Press, 2017, pp. 1925–1942.

36.

Hawley,

Howard,

Koelle and

Saxton, Collaborative security management: Developing ideas in security management for air traffic control, in: 2013 International Conference on Availability, Reliability and Security, 2013, pp. 802–806. doi:10.1109/ARES.2013.107.

37.

Hoffman,

Zage and

Nita-Rotaru, A survey of attack and defense techniques for reputation systems, ACM Computing Surveys42(1) (2009), 1:1–1:31. doi:10.1145/1592451.1592452.

38.

Hopwood,

Bowe,

Hornby and

Wilcox, Zcash protocol specification, Tech. rep., Zerocoin Electric Coin Company, 2016.

39.

Jager and

Rupp, Black-box accumulation: Collecting incentives in a privacy-preserving way, PoPETs2016(3) (2016), 62–82.

40.

Jøsang and

Golbeck, Challenges for robust trust and reputation systems, in: 5th International Workshop on Security and Trust Management (STM 2009), 2009.

41.

Libert,

K.G.

Paterson and

E.A.

Quaglia, Anonymous broadcast encryption: Adaptive security and efficient constructions in the standard model, in: PKC 2012,

Fischlin,

Buchmann and

Manulis, eds, LNCS, Vol. 7293, Springer, Heidelberg, 2012, pp. 206–224.

42.

J.K.

Liu,

V.K.

Wei and

D.S.

Wong, Linkable spontaneous anonymous group signature for ad hoc groups (extended abstract), in: ACISP 04,

Wang,

Pieprzyk and

Varadharajan, eds, LNCS, Vol. 3108, Springer, Heidelberg, 2004, pp. 325–335.

43.

Lysyanskaya,

R.L.

Rivest,

Sahai and

Wolf, Pseudonym systems, in: SAC 1999,

H.M.

Heys and

C.M.

Adams, eds, LNCS, Vol. 1758, Springer, Heidelberg, 1999, pp. 184–199.

44.

F.G.

Mármol and

G.M.

Pérez, Security threats scenarios in trust and reputation models for distributed systems, Computers & Security28(7) (2009), 545–556. doi:10.1016/j.cose.2009.05.005.

45.

Milutinovic,

Dacosta,

Put and

B.D.

Decker, uCentive: An efficient, anonymous and unlinkable incentives scheme, in: 2015 IEEE Trustcom/BigDataSE/ISPA, Vol. 1, 2015, pp. 588–595. doi:10.1109/Trustcom.2015.423.

46.

Nabuco,

Bonacin,

Fugini and

Martoglia, Web2touch 2016: Evolution and security of collaborative web knowledge, in: 2016 IEEE 25th International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE), 2016, pp. 214–216. doi:10.1109/WETICE.2016.55.

47.

Paillier, Public-key cryptosystems based on composite degree residuosity classes, in: EUROCRYPT’99,

Stern, ed., LNCS, Vol. 1592, Springer, Heidelberg, 1999, pp. 223–238.

48.

T.G.

Papaioannou and

G.D.

Stamoulis, An incentives’ mechanism promoting truthful feedback in peer-to-peer systems, in: CCGrid 2005. IEEE International Symposium on Cluster Computing and the Grid, 2005, Vol. 1, 2005, pp. 275–283. doi:10.1109/CCGRID.2005.1558565.

49.

Pavlov,

J.S.

Rosenschein and

Topol, Supporting privacy in decentralized additive reputation systems, in: International Conference on Trust Management, Springer, 2004, pp. 108–119.

50.

Petrlic,

Lutters and

Sorge, Privacy-preserving reputation management, in: Proceedings of the 29th Annual ACM Symposium on Applied Computing, SAC’14, ACM, New York, NY, USA, 2014, pp. 1712–1718. doi:10.1145/2554850.2554881.

51.

Pingel and

Steinbrecher, Multilateral secure cross-community reputation systems for Internet communities, in: International Conference on Trust, Privacy and Security in Digital Business, Springer, 2008, pp. 69–78. doi:10.1007/978-3-540-85735-8_8.

52.

R.L.

Rivest,

Shamir and

Tauman, How to leak a secret, in: ASIACRYPT 2001,

Boyd, ed., LNCS, Vol. 2248, Springer, Heidelberg, 2001, pp. 552–565. doi:10.1007/3-540-45682-1_32.

53.

Schiffner,

Clauß and

Steinbrecher, Privacy and liveliness for reputation systems, in: Public Key Infrastructures, Services and Applications,

Martinelli and

Preneel, eds, Springer, Berlin, Heidelberg, 2010, pp. 209–224. doi:10.1007/978-3-642-16441-5_14.

54.

Sillaber,

Sauerwein,

Mussmann and

Breu, Data quality challenges and future research directions in threat intelligence sharing practice, in: Proceedings of the 2016 ACM on Workshop on Information Sharing and Collaborative Security, WISCS’16, ACM, New York, NY, USA, 2016, pp. 65–70. doi:10.1145/2994539.2994546.

55.

Y.L.

Sun,

Han,

Yu and

K.J.

Ray Liu, Attacks on trust evaluation in distributed networks, in: 2006 40th Annual Conference on Information Sciences and Systems, 2006, pp. 1461–1466. doi:10.1109/CISS.2006.286695.

56.

Traverso,

Butin,

J.A.

Buchmann and

Palesandro, Coalition-resistant peer rating for long-term confidentiality, in: 2018 16th Annual Conference on Privacy, Security and Trust (PST), 2018, pp. 1–10.

57.

Zhai,

D.I.

Wolinsky,

Chen,

Syta,

Teng and

Ford, AnonRep: Towards tracking-resistant anonymous reputation, in: 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16), USENIX Association, 2016, pp. 583–596.

Anonymity and rewards in peer rating systems 1

Abstract

Keywords

1. Introduction

1.1. Our work

2 Traceability here refers to the requirement that multiple ratings cannot be given on the same subject per round.

5 The case of a corrupt Rewarder is captured in the Anonymity of Ratings under Full Corruption requirement.

2.1.2. Anonymity of ratings

2.1.3. Fair rewards

2.1.4. Traceability

2.1.5. Non-frameability

2.1.6. Unforgeability of reputation

3. Our construction

3.1. Public-key encryption schemes

3.2. Proof protocols

3.3. Linkable ring signatures

Definition 1 (Linkable ring signatures).

3.4. DAA* signatures

Definition 2 (DAA*).

5.1. CDL* construction

5.1.1. Preliminaries

Definition 3 (LRSW assumption).

5.1.2. CDL* construction

6. Conclusion and future work

Footnotes

Correctness of APR

Security requirements of linkable ring signatures

Proof of security of DAA* construction

References

²
Traceability here refers to the requirement that multiple ratings cannot be given on the same subject per round.

⁵
The case of a corrupt Rewarder is captured in the Anonymity of Ratings under Full Corruption requirement.

3.4. $DAA*$ signatures